Progress in FHE by Craig Gentry
Craig Gentry, who recently invented the first fully-homomorphic encryption scheme, has invented another way to do FHE. This is described in "Fully Homomorphic Encryption without Bootstrapping." Here's the abstract from this paper:
We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance, bases security on weaker assumptions, and does not require Gentry's bootstrapping procedure.
Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or ring-LWE (RLWE) problems that have 2λ security against known attacks. For RLWE, we have:
- A leveled FHE scheme without bootstrapping that can evaluate L-level arithmetic circuits with (Õ·L3) per-gate computation – i.e., computation quasi-linear in the security parameter. Security is based on RLWE for an approximation factor exponential in L.
- A leveled FHE scheme that uses bootstrapping as an optimization, where the per-gate computation, which includes the bootstrapping procedure, is Õ(λ2) (independent of L). Security is based on the hardness of RLWE for quasi-polynomial factors (as opposed to the sub-exponential factors needed in previous schemes).
We obtain similar results for LWE, but with worse performance. For circuits of large width – e.g., where a constant fraction of levels have width at least λ – we can reduce the per-gate computation of the bootstrapped version to Õ(λ), independent of L, by batching the bootstrapping operation.
Previous FHE schemes all required Ω(λ3.5) computation per gate. We eliminate bootstrapping and improve performance using the same technique – namely, a much more effective approach for managing the noise level of lattice-based ciphertexts as homomorphic operations are performed. This new noise management approach uses tools recently introduced by Brakerski and Vaikuntanathan.
The bootstrapping that previous ways to do FHE required also made them fairly slow – too slow to be practical. But Gentry remarks in a footnote in this paper that:
We are aware of the seeming irony of trumpeting "FHE without bootstrapping" and then proposing bootstrapping "as an optimization". First, FHE without bootstrapping is exciting theoretically, independent of performance. Second, in terms of performance, whether bootstrapping as an optimization actually improves performance depends on the number of levels in the circuit one is evaluating; for circuits of depth sub-polynomial in the security parameter, this "optimization" will not improve performance asymptotically.
So I'm left with the impression that this is probably just a theoretical breakthrough instead of a practical one. But with the steady progress being made in FHE, it may not be long until it's actually practical. But it looks like we're still not quite there yet.