FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second

By Léo Ducas, Daniele Micciancio. International Conference on the Theory and Application of Cryptographic Techniques, 2015

935 citations recorded by the source corpus.

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. 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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/b023ac9848659893c2ed17c5b6ad5e1a9448c590

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Wei Dai
2. Hao Chen
3. Miran Kim
4. Yongsoo Song
5. Kim Laine
6. Berk Sunar
7. Andrey Kim
8. Jung Hee Cheon

In Computer Vision and Pattern Recognition

1. Wei Dai
2. Berk Sunar
3. David M. Brooks
4. Miran Kim
5. Yongsoo Song
6. Gu-Yeon Wei
7. Jung Hee Cheon
8. Andrey Kim

Citations in the corpus

• A Survey on Homomorphic Encryption Schemes (2017, methodology): “HElib is designed using low-level programming, which deals with C++ Yes [Ducas and Micciancio 2015] FFTW TFHE [Chillotti et al. 2017] CGGI16 [Chillotti et al. 2016] C++ Yes [Chillotti et al. 2016] FFTW SEAL [Laine et al. 2017] FV12 [Fan and Vercauteren 2012b] C++ Yes [Chen et al. 2017] No external…”
• Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping (2017, methodology): “As already noticed in [17], this assumption matches experimental results.”
• Bootstrapping for Approximate Homomorphic Encryption (2018, background): “Meanwhile, Ducas and Micciancio [24] proposed the FHEW scheme that bootstraps a single-bit encryption in less than a second based on the framework of [2].”
• Cheetah: Optimizing and Accelerating Homomorphic Encryption for Private Inference (2020, background): “…distribution with variance σ 2 , and if X i ’s are IBDG with variance σ 2 i , then As the noise grows multiplicatively in HE Mult and additively in HE Add and HE Rotate , we can compute the variance of the output noise after each layer under the independence assumption, which was validated in [19].”
• TFHE: Fast Fully Homomorphic Encryption Over the Torus (2019, methodology): “The fastest one in the lineage of [29,33] must be performed after each gate in a circuit and is therefore denoted as gate bootstrapping.”
• Polynomial multipliers for fully homomorphic encryption on FPGA (2015, methodology): “In Section V, we compare and discuss the proposed solutions and we compare to software runtimes.”
• Security and Privacy Issues in Deep Learning (2018, background): “…various attempts on fully homomorphic encryption (FHE), which allows any computable function to be performed on the encrypted data, have been proposed [Van Dijk et al. 2010; Yagisawa 2015; Brakerski and Vaikuntanathan 2014; Bos et al. 2013; Hesamifard et al. 2017; Ducas and Micciancio 2015].”
• TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service (2018, background): “Ducas and Micciancio (2015) devised a scheme that that could bootstrap a single Boolean gate in under one second with reduced memory.”
• Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference (2019, methodology): “It looks similar to the ring variant of GSW [21, 28] but our scheme supports some operations between ciphertexts under different keys.”
• Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds (2016, methodology): “The last corollaries describe exactly the internal products already presented in [16], [3], [13] and [11] with adapted notations.”
• cuHE: A Homomorphic Encryption Accelerator Library (2015, methodology): “More recently, Ducas and Micciancio [15] presented an efficient implementation of the bootstrapping algorithm.”
• Homomorphic Encryption (2017, methodology): “Also, building on techniques from [20, 3], Ducas and Micciancio implemented bootstrapping for a (non packed) GSW-like scheme in less than a second [30].”
• Homomorphic Encryption for Arithmetic of Approximate Numbers (2017, background): “HE schemes with matrix ciphertexts [21,26] support homomorphic operations over the integers”