Practical Bootstrapping with Polylogarithmic Overhead''
Chris Peikert
Georgia Tech
Monday, April 29, 2013, 2:00 pm
EBU3B, Room 4140
Abstract:
Gentry's "bootstrapping" technique constructs a fully homomorphic encryption (FHE) scheme from a ``somewhat homomorphic'' one that is powerful enough to evaluate its own decryption circuit. To date, it remains the only known way of obtaining (unbounded) FHE. Bootstrapping is computationally very expensive, and a great deal of effort has been spent on improving its efficiency. The current state of the art, due to Gentry, Halevi, and Smart (PKC 2012), is able to bootstrap with multiplicative overhead only *poly-logarithmic* in the security parameter, relative to performing decryption ``in the clear.'' While this performance is very good *asymptotically*, the practical impact is less clear: the procedure composes multiple layers of expensive and complicated operations, to the point where it appears very difficult to implement, and its concrete runtime for real-world parameters appears much worse than that of simpler methods having larger asymptotic overhead (e.g., quasilinear).
In this talk I will describe simple, practical methods for bootstrapping with (small) poly-logarithmic overhead, i.e., in quasi-linear time. Our methods are easy to implement, and we believe that they will be substantially more efficient in practice than prior realizations of bootstrapping. We give two complementary algorithms:
The first applies to ``unpacked'' ciphertexts (encrypting single bits) and is extremely simple. It improves upon previous methods for unpacked ciphertexts, which achieve only *amortized* quasi-linear time when bootstrapping a linear number of ciphertexts.
Our main algorithm bootstraps ``packed'' ciphertexts (encrypting a linear number of bits), also in quasi-linear time. Its main component is a substantial enhancement of the ``ring-switching'' procedure of Gentry et al. (SCN 2012), which allows us to switch between two rings where neither is a subring of the other. Using this procedure, we give a very natural method for homomorphically evaluating a wide class of linear transformations on plaintexts, including the transformations needed to implement the full decryption function on packed ciphertexts.
This is joint work with Jacob Alperin-Sheriff.