Homomorphic Encryption from LWE
In 2013, Gentry, Sahai and Brent Waters (GSW) proposed a new technique for building FHE schemes that avoids an expensive "relinearization" step in homomorphic multiplication.[1] Zvika Brakerski and Vinod Vaikuntanathan observed that for certain types of circuits, the GSW cryptosystem features an even slower growth rate of noise, and hence better efficiency and stronger security.[2] Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.[3]
These techniques were further improved to develop efficient ring variants of the GSW cryptosystem: FHEW (2014). The FHEW scheme was the first to show that by refreshing the ciphertexts after every single operation, it is possible to reduce the bootstrapping time to a fraction of a second. FHEW introduced a new method to compute Boolean gates on encrypted data that greatly simplifies bootstrapping, and implemented a variant of the bootstrapping procedure. The efficiency of FHEW was further improved by the TFHE scheme, which implements a ring variant of the bootstrapping procedure using a method similar to the one in FHEW.
- ↑ C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer)
- ↑ Z. Brakerski and V. Vaikuntanathan. Lattice-Based FHE as Secure as PKE. In ITCS 2014
- ↑ J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer)
