The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. Bootstrapping in the latest implementation of FHE, the HElib library of Halevi and Shoup (Crypto 2014), requires about six minutes per batch. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second. We present a detailed technical analysis of the scheme (based on the worst-case hardness of standard lattice problems) and report on the performance of our prototype implementation.

Additional Metadata
Keywords public-key cryptography / FHE, bootstrapping, Ring-LWE
MSC Cryptography (msc 94A60)
THEME Information (theme 2), Software (theme 1)
Editor F. Ottenhof , E. Oswald
Persistent URL dx.doi.org/10.1007/978-3-662-46800-5_24
Project Applications of Arithmetic Secret Sharing Schemes in Two-Party Cryptography , Cryptanalysis of Widely-used Hash Function Standards and Beyond
Conference Annual International Conference on the Theory and Applications of Cryptographic Techniques
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.023.117 - Applications of Arithmetic Secret Sharing Schemes in Two-Party Cryptography, This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.001.201 - Cryptanalysis of Widely-used Hash Function Standards and Beyond
Citation
Ducas, L, & Micciancio, D. (2015). FHEW: Bootstrapping Homomorphic Encryption in less than a second. In F Ottenhof & E Oswald (Eds.), . doi:10.1007/978-3-662-46800-5_24