Homomorphic encryption

What it is?

Completely homomorphic encryption (Fully Homomorphic Encryption) for a very long time was the most striking discovery in the young and rapidly developing field of Computer Science - cryptography. In short, this type of encryption allows you to make arbitrary calculations on the encrypted data without decrypting it. For example, Google can search for a request without knowing what kind of request it is, you can filter spam without reading letters, count votes, without opening envelopes with votes, do DNA tests, without reading DNA and much, much more.

That is, the person / machine / server performing the computations performs mechanical operations with ciphers, executing its own algorithm (database search, analysis for spam, etc.), but at the same time has no idea about the information encrypted inside. Only a user who has encrypted his data can decipher the result of the calculation.

Great, right? And this is not from the realm of fantasy - this is something that can already be “theoretically” brought to life.


')
It is not always from theory to practice, however, it is at hand and sometimes it takes decades. Operations in modern schemes of homomorphic encryption are much slower than usual and according to Moore's law will become comparable with the speed of calculations today in 40 years. But every year the schemes become easier and faster, so that, who knows, the new milestone in development may be just around the corner IT technology.

History of creation

The history of the creation of the first scheme is rather unusual: Dan Boneh, a professor at Stanford University, made it a rule for all newly arrived graduate students to offer the “Automatic PhD problem”. As a rule, this is a very difficult (but not a grave) cryptography task, over which scientists have been fighting for at least a dozen years now. In 2006, Dan offered to invent a scheme for Fully Homomorphic Encryption to his new student, Craig Gentry. Two years later, Craig decided it. Dan kept his promise and Craig became one of the first students who so quickly received a Ph.D. Having a long-time passion for mathematics, Craig first received a law degree and worked as a lawyer for a while, until, at a rather conscious age, he decided to return to mathematics again and entered Stanford postgraduate school.

Simple idea

The schemes for fully homomorphic encryption were at first available for understanding only to specialists in number theory, but over the past 5 years they have become so simplified that their basic idea can be explained to the student.

So, imagine that you want to encrypt the number x (maybe this is just another bit of your data, maybe a small natural number). Choose an arbitrary vector v (it will be your secret key). It is possible to find a matrix A such that Av ~ = xv, i.e. the product of A by v will give approximately a vector v multiplied by the number x (for those who remember a little algebra, v will be an “exemplary” eigenvector, and x an “approximate” eigenvalue of the matrix A). If you want to encrypt a new number y, then again you can find the matrix B, such that Bv ~ = yv. Thus, you can, having only one secret key v, encrypt as many numbers as you need, where the cipher of each number is the matrix. To decipher the number, we multiply the matrix by the secret vector v.

It can be proved by assuming the complexity of an archaic task of finding a short vector in a lattice, which is also difficult, having matrices A and B, with a significant probability (distinct from random guessing) to tell which numbers x and y they encrypt (without knowing, of course, the secret vector v).

Thus, this is indeed a cipher scheme, but it is also homomorphic! That is, by operating with matrices A and B, namely, multiplying and adding them, we will multiply and add the numbers that they encrypt. Indeed, let's see what decoding works A and B will give:

(AB) v = A (Bv) ~ = A xv = x (Av) ~ = (xy) v, it gives the product of x and y!

A decryption of the sum of A and B will give

(A + B) v = Av + ​​Bv ~ = xv + yv ~ = (x + y) v, the sum of x and y!

Of course, more precise analysis is required here to make sure that approximate equality is preserved. Also, finding an encryption matrix is ​​not quite a trivial task, but it’s quite realistic to figure it out if you briefly dive into some good articles, like this one:
[GSW'13] "Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based" ( pdf )

A window to a new world

Craig opened the door to a kind of new world. Today we have a huge number of variations of homomorphic encryption and the most interesting is that one of the variations can give the best possible, theoretically the most resistant way to obfuscate programs, and this will open up even more possibilities for fantasy! But more about that another time. If you are interested in the current task, for which Dan gives the PhD automatically, write in the comments;)