Practical Bootstrapping for Fully Homomorphic Encryption

Fully homomorphic encryption (FHE) enables arbitrary computation on encrypted data. Since Gentry's seminal construction in 2009, several FHE schemes have been constructed, almost all of which adhere to the following template: first, one constructs a "somewhat homomorphic" encryption (SHE) scheme, which supports homomorphic computations of some bounded depth. (The depth bound arises because ciphertexts have some internal "noise" that grows under homomorphic operations, yet must remain sufficiently small to ensure correct decryption.) Then, one converts the SHE into an FHE using a "refreshing" procedure that reduces the noise in a given ciphertext. This refreshing process is also known as "bootstrapping," because it uses the SHE to homomorphically evaluate *its own decryption function*.

Because bootstrapping involves a lot of homomorphic computation, and must be run very frequently, it is the main bottleneck (by far) in all known FHE constructions. In this talk I will describe some mathematical and algorithmic techniques that dramatically speed up bootstrapping, both asymptotically and in practice. One of the main ideas is a "ring-hopping" procedure that gradually converts a ciphertext from one cyclotomic ring to an entirely different one, which has the side-effect of evaluating an FFT-like transform on the encrypted message (without increasing the noise much). Using this technique, one can practically refresh a linear number of encrypted bits in only quasi-linear time. Time permitting, I will also mention a completely different method of bootstrapping which incurs very small *polynomial* error growth, which yields FHE with relatively small keys and ciphertexts.
Chris Peikert is an Associate Professor in the School of Computer
Science at Georgia Tech. His research interests include cryptography,
computational complexity, and algorithms, especially in relation to
lattices, error-correcting codes, and number theory. He is the
recipient of a Sloan Fellowship, an NSF CAREER Award, a Google Faculty
Award, and multiple Best Paper and teaching awards.