Gturcas: Created page with "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.<..."

2020-05-26T12:46:07Z

Created page with "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.<..."

New page

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.<ref name=GSW13>C. Gentry, A. Sahai, and B. Waters. [http://eprint.iacr.org/2013/340 Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based]. In ''CRYPTO 2013'' (Springer)</ref>
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.<ref>Z. Brakerski and V. Vaikuntanathan. [http://eprint.iacr.org/2013/541 Lattice-Based FHE as Secure as PKE]. In ''ITCS 2014''</ref>
Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.<ref name=AP14>J. Alperin-Sheriff and C. Peikert. [http://eprint.iacr.org/2014/094 Faster Bootstrapping with Polynomial Error]. In ''CRYPTO 2014'' (Springer)</ref>

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.

Homomorphic Encryption from LWE - Revision history

Gturcas: Created page with "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.<..."