Comment by blintz
3 years ago
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.