A Homomorphic Encryption Illustrated Primer
blog.n1analytics.com
blog.n1analytics.com
Homomorphic encryption is one of those things where I would have told you before learning about it that you have to decrypt information to do anything with it. That obviously you have to decrypt something to work with it. Which... maybe I'm just really simplistic, and I make brash assumptions about what is and isn't possible, but it often feels like a paradigm shift to me.
Public/private key cryptography was one another one of those moments; "wait, you mean I can have someone encrypt information without knowing how to decrypt it?" Zero-knowledge proofs are another one. Also when people started using quantum entanglement to tell if a key had been intercepted. This stuff is stupid, it shouldn't work. It feels obvious to me that it shouldn't be possible.
I dunno, it feels like a cheat code or something. Or better analogy, being given a brand new mechanic in a video game level. It's like the first time that you rotate the world in Fez.
I feel that the article is a bit vague about the applications of homomorphic encryption, so I'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:
* download all your emails, decrypt all of them, run your search, discard the rest
* allow the mail server to decrypt your mail, and let it run the search
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.
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.
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's potential uses.
------
I'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'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's an NP-hard problem, but you have to pick your lattice very carefully (many instances are solvable in polynomial-time).
Also, if I'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'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!
For example, you can use outside information to run overly specific queries: “list the male students in woman’s studies 326 that got over a C”. Tricking me into running this, and observing the number of bytes returned will give you a nice approximation of Jim’s grade if you know he’s the only male in that class. The set of queries I can safely provide varies with the side channel information the attacker has.
Also, if you have the ability to subtract and compare (I think those are the right two operators), then you can use that to decrypt the underlying data.
There is also the best picture I have ever seen on wikipedia: https://en.m.wikipedia.org/wiki/Block_cipher_mode_of_operati... Scroll down to “electronic code book” to see why basic equality computationa break encryption guarantees.
To make things worse, the attacker can keep track of what time each encrypted block is read/written, and infer communication patterns between users, and even infer which blocks contain information on which topics. (This is similar to the concerns over governments that gather “metadata”, because gathering “data” would be illegal)
Anyway, I skimmed this article, but have spent days reading negative research results in this space that are pitched as though they are somehow practical, and I suspect I’m not the only one suffering from homomorphic encryption fatigue.
About your query example, (F)HE never claimed to be secure against leaked information inherent to the query. This is more the resort of privacy, which is tackled by differential privacy researchers (and as such has nothing to do with FHE). Naturally you can put differential privacy on top of FHE but we're not there yet. The biggest problem here is that crypto is not magic: in your example, NO system can truthfully answer to the question without leaking the only male's grade, crypto or not. So maybe you'll restrict the system to run the query only when there are at least two male students. But then you're still leaking info to me if I'm the second student, and so on. Wanting crypto being able to do this kind of job is equivalent to wanting cars able to go fast anywhere anytime but that should never crash into a tree at more than 5 km/h: if you can go fast anywhere, you can go fast into a tree. Sad but true.
About the ability to subtract and compare, I don't understand what you are talking about, could you explain it?
About ECB, I mean, yeah, everyone in crypto knows ECB is insecure, this is stream cypher 101 and equivalent to "ROT13 is not secure, do not use it for crypto". But this has nothing to do with FHE.
Keeping track of time is a side-channel attack. Nothing to do with FHE in particular, it's common to all crypto. Most crypto libraries are secure against timing attacks, as it is one of the most obvious side-channel attack. FHE libraries will hopefully be too, just give them time. Also I think FHE is by nature more resilient to timing attacks as it must natively implement simultaneous computation of if/else branches, for instance.
Long story short, yeah, crypto is insanely hard to implement correctly. When your problem is well-defined (first difficulty), you must find the good tools (second difficulty), with the correct security parameters (3rd), and implement them correctly: no bugs (4th) and no side-channel attacks (5th). That's the reason why the first rule of crypto is "don't write your own crypto".
It is known that this doesn’t work if any one of these bullet points is true:
(a) the size of the results are correlated to facts contained in the answer and the attacker can get you to run queries (even if you don’t share the results)
(b) the computation on the server supports basic arithmetic
(c) the computation on the server supports equality tests
(d) it is computationally feasible for the server to perforn a computation over O(1) data by examining O(1) bytes.
Given those (and other, more subtle) constraints, the challenge is to design a practical HE service.
There aren’t any examples of people successfully building such a system so far.
(a) is a classical side-channel attack, and as I say non-homomorphic libraries already take these kinds of attacks in consideration. HE won't be an exception to that, depending on what level of privacy is needed.
I did not understand what you mean by (d), and to be honest by (b) either. If you have any papers/blogs about that I'll be glad to read them.
And yes I agree, successful FHE system is inexistent as for now. But the evidence of the bare existence of FHE is only ten years old, somewhat practical FHE is even younger. We've not even reached practical FHE yet, security issues will be tackled when they will become the blocking point. At this point of the technology you can't expect research to be immediately applicable. ZK proofs were first designed in the 80s, and as far as I know they only started to be used in practice (zk-SNARKS for instance) recently.