A Homomorphic Encryption Illustrated Primer
Great article!<p>I feel that the article is a bit vague about the applications of homomorphic encryption, so I&#x27;ll add some examples. For instance, suppose that your mail server encrypts your mails, and only you can decrypt them. If you want to search something trough your mails, you have two choices:<p>* download all your emails, decrypt all of them, run your search, discard the rest<p>* allow the mail server to decrypt your mail, and let it run the search<p>Both options are not viable. The first one is extremely costly in bandwidth, storage and computation, the second one contradicts the premise of encrypting your data in the first place. (Fully) homomorphic encryption would allow the mail server to perform the search on encrypted data, not knowing the content of the mail, or even the query for that matter.<p>Another example, you want to get a loan from the bank. Their conditions are: not having served jail time, no critical health state, and no gambling addiction. Further more they allow you to check one of these cases if you are a veteran (go figure). All these information are sensible private data, which the bank could use to rise your interest rates. Yet, you need the loan. Using homomorphic encryption and some variants could allow the bank to only get the result: whether you are eligible to the loan or not.<p>Of course, the bank would have to agree to such a scheme in the first place and what I describe is still highly theoretical but I hope you get the idea of FHE&#x27;s potential uses.<p>------<p>I&#x27;ll also add a few precisions about the article, several homomorphic schemes exist, the one described in the article is called Ring Learning With Errors (RLWE), a derivation of the LWE problem. Mathematically it boils down to solving a problem called shortest vector problem in a lattice, it&#x27;s a bit abstract but you can Google it (basically, you have a regular grid of points, find the smallest vectors that can generate all points). It&#x27;s an NP-hard problem, but you have to pick your lattice very carefully (many instances are solvable in polynomial-time).<p>Also, if I&#x27;m not mistaken, the encryption system described in the article is a Somewhat Homomorphic Encryption (SHE), which means that you cannot use it for complicated operations. Well, the paper it&#x27;s based on is Fully Homomorphic Encryption, but the techniques to reach it are not given in the article. After a while, the errors become preponderant and you cannot decrypt anything any more. Several schemes actually solved this issue, reaching Fully Homomorphic Encryption (FHE). The first FHE scheme was described by Gendry in his PhD thesis in 2009 (damn I wish my PhD will be half as good as the quarter of his). Yet if I remember correctly many FHE schemes are still unpractical (I remember a paper in which the polynomials were several Gbytes). But the field is quite young, and research is progressing!