Homomorphic Encryption / (Fully) Homomorphic Encryption

So it was tempting to headline the topic: “The decline of the Google company is close!”, But still it would be too “yellow”.

Now to the point. What is "homomorphic encryption" and where does Google?

Homomorphic encryption is called a cryptosystem that allows you to perform some mathematical operations with plaintext by performing operations with encrypted (perhaps another mathematical action or even a series of operations). For example, RSA is homomorphic for the multiplication operation (trivial from the encryption itself).
')
Surprisingly, until recently there was no cryptosystem homomorphic for multiply and sum at the same time, the so-called fully homomorphic encryption, because sums and multiplications are enough to express any mathematical function. The main problem with the previous schemes was that each operation adds some “noise” to the cryptotext ( look at the RSA formula and recall the definition of mod ), so after a certain number of steps, the accumulated noise makes decoding impossible. As I recall from the presentation, it was said that such a scheme does exist, but they are exponential in terms of "efficiency."

Craig Gentry (Craig Gentry, PhD Stanford, IBM Research) has published an example of the first such function in his PhD thesis. Without going into details (and I will not pretend that I understood all the mathematical calculations 100%), the meaning of his decision is that he uses double encryption. Those. after a certain number of steps, it “removes the top layer” (the first encryption) and “removes” the accumulated “noise”.

How it works, I will tell with common words and examples, which he himself used in his presentation. Who is interested in mathematics and a more formal explanation - to read a thesis .




The example he gave is quite simple. Imagine a jeweler working with jewels. To eliminate theft, these jewels are given to him in a transparent glove box so that he can work. In addition, unfortunately, these gloves deteriorate after a certain period of time (remember, about the accumulation of "noise"), so every time when the gloves are about to deteriorate, this initial box is inserted into the identical box. And this continues until the work is completed.

Of course, this example is not perfect, but it gives some insight into the operation of the complete homomorphic Gantry function.

Now remember where does Google? And the point is that if this algorithm is implemented, for example, in Google, then they will not be able to recognize your request and even the answer. Why should they do this is, of course, another question. A more interesting example is tax returns. Imagine that you send a declaration that is encrypted with your private key and you also receive an encrypted result from a tax specialist who has not learned a bit of information about your income.

Unfortunately, although the current implementation of a complete homomorphic system works in polynomial time, the constants there are “indecently huge”, so Google can sleep peacefully in the near future.

UPD I would like to mention an interesting fact from Craig's biography. He received a bachelor of mathematics from Duke University, then graduated from Harvard law school, and then decided that he did not have enough PhD in computer science for complete happiness! The solution to the problem described in the article, he found being on an internship at IBM Research.