Comment by jerf
3 years ago
This is the first thing out of homomorphic encryption I personally have seen that seems to be in the ballpark of useful for some practical use, which is impressive. Have I missed out on any other such things of interest?
(And this is not a criticism; this is a compliment. You start so far behind the eight-ball with homomorphic encryption with regard to the resources it consumes I wasn't convinced it was ever going to be even remotely useful for much of anything. Precisely because I was so skeptical, I am that impressed to see something work this well. It's not the fastest Wikipedia mirror, but... honestly... I've been on slower websites! Websites with far less excuse.)
There has recently been a lot of great work on making homomorphic encryption more practical for particular applications. We definitely stand on the shoulders of all that work!
One reason homomorphic encryption has a reputation as absurdly slow is that people typically talk about “fully” homomorphic encryption, which essentially means that you can compute an arbitrarily large function on the encrypted data. This involves a very expensive process called bootstrapping, which incurs a roughly ~15 ms cost per binary operation evaluated. As you can imagine, that adds up.
This work uses “leveled” homomorphic encryption, where we only perform a function of ‘bounded’ size (that is, the homomorphic dot product). So, we do not have to perform bootstrapping, and thus avoid some of the more extreme costs.
The other reason this work is practical is that we ‘tailored’ our construction to the particular problem of private information retrieval. When people try to apply homomorphic encryption generically to their problem, they typically end up with disappointingly slow and expensive results. Cool work on better ‘FHE compilers’ so in progress, so hopefully that will also help!
> can compute an arbitrarily large function on the encrypted data
What is the meaning of the word "large" here? How are we defining the size of a function?
Either the amount of Boolean logic operations or the amount of integer additions and multiplications, as these are the operations FHE schemes support.
It's generally multiplicative depth; that is, the number of ciphertext-ciphertext multiplications that feed into each other. The primary way we define and evaluate functions in FHE is as Boolean (or sometimes arithmetic) circuits, so "depth" is in that context.
You missed the widely panned Apple iCloud child sexual abuse imagery detection feature. The private set intersection is basically doing homomorphic encryption. In raising some very valid policy critiques, people forget that it's actually a nifty piece of engineering. (This is not an endorsement of that feature.) https://www.apple.com/child-safety/pdf/Apple_PSI_System_Secu...
I'm also closely working together with a team at $WORK who's using a protocol very similar to Apple's but not doing CSAM detection. We are seeing some severe pushback on this technology. I wouldn't be surprised if there are multiple homomorohic encryption based products at Big Tech that have yet to see the light of day.
I think it is very counterintuitive---even to professional programmers---that you can compute things without letting the computer know them. I literally had to go through the entire paper to understand that this can actually work as long as human in the loop doesn't screw up (see my summary [1], which was revised multiple times at that time).
[1] https://news.ycombinator.com/item?id=28223141
Apple's Differential Privacy uses homomorphic encryption for parts of its functioning.
Citation?