Title: Towards Practical Fully Homomorphic Encryption

Jacob Alperin-Sheriff

School of Computer Science

College of Computing

Georgia Institute of Technology

Date: Tuesday, July 14, 2015

Time: 2:00pm

Location: Klaus 1212

Committee:

----------

Dr. Chris Peikert, School of Computer Science, Georgia Tech (Advisor) Dr. Alexandra Boldyreva, School of Computer Science, Georgia Tech Dr. Richard Lipton, School of Computer Science, Georgia Tech Dr. Zvika Brakerski, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science Dr. Matt Baker, Department of Mathematics, Georgia Tech

Abstract:

Fully homomorphic encryption (FHE) allows for computation of arbitrary func- tions on encrypted data by a third party, while keeping the contents of the encrypted data secure. This area of research has exploded in recent years following Gentry’s seminal work. However, the early realizations of FHE, while very interesting from a theoretical and proof-of-concept perspective, are unfortunately far too inefficient to provide any use in practice.

The bootstrapping step is the main bottleneck in current FHE schemes. This step refreshes the noise level present in the ciphertexts by homomorphically evaluating the scheme’s decryption function over encryptions of the secret key. Bootstrapping is necessary in all known FHE schemes in order to allow an unlimited amount of computation, as without bootstrapping, the noise in the ciphertexts eventually grows to a point where decryption is no longer guaranteed to be correct.

In this work, we present two new bootstrapping algorithms for FHE schemes. The first works on packed ciphertexts, which encrypt many bits at a time, while the second works on unpacked ciphertexts, which encrypt a single bit at a time. Our algorithms lie at the heart of the fastest currently existing implementations of fully homomorphic encryption for packed ciphertexts and for single-bit encryptions, respectively, running hundreds of times as fast for practical parameters as the previous best implementations.