Difference between revisions of "GSW"
| Line 1: | Line 1: | ||
Around 2013, Gentry, Sahai and Waters <ref> C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer). https://eprint.iacr.org/2013/340</ref> proposed a new way of building FHE schemes whose homomorphic multiplication algorithms are more natural than those presented in [[BFV]] or [[BGV]]. A distinguished feature of the scheme we are about to present is an asymmetric formula for the <b>growth of the noise</b> when multiplying two ciphertexts. Due to this feature, certain types of circuits have a very slow noise growth rate. Based on this asymmetry, Alperin-Sheriff and Peikert <ref> J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094</ref> found a very efficient bootstrapping technique for the [[GSW]] scheme. | Around 2013, Gentry, Sahai and Waters <ref> C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer). https://eprint.iacr.org/2013/340</ref> proposed a new way of building FHE schemes whose homomorphic multiplication algorithms are more natural than those presented in [[BFV]] or [[BGV]]. A distinguished feature of the scheme we are about to present is an asymmetric formula for the <b>growth of the noise</b> when multiplying two ciphertexts. Due to this feature, certain types of circuits have a very slow noise growth rate. Based on this asymmetry, Alperin-Sheriff and Peikert <ref> J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094</ref> found a very efficient bootstrapping technique for the [[GSW]] scheme. | ||
| + | |||
| + | More efficient FHE schemes based on ring variants of [[GSW]] have been proposed since then. These achieve very fast bootstrapping via various optimisation techniques, such as "refreshing the ciphertexts" after every single homomorphic operation. To our knowledge, among the schemes based on [[GSW]] (and not only), TFHE <ref> I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryptionover the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020). https://eprint.iacr.org/2018/421 </ref> holds the record for fastest bootstrapping. | ||
== References == | == References == | ||
Revision as of 09:06, 4 June 2020
Around 2013, Gentry, Sahai and Waters [1] proposed a new way of building FHE schemes whose homomorphic multiplication algorithms are more natural than those presented in BFV or BGV. A distinguished feature of the scheme we are about to present is an asymmetric formula for the growth of the noise when multiplying two ciphertexts. Due to this feature, certain types of circuits have a very slow noise growth rate. Based on this asymmetry, Alperin-Sheriff and Peikert [2] found a very efficient bootstrapping technique for the GSW scheme.
More efficient FHE schemes based on ring variants of GSW have been proposed since then. These achieve very fast bootstrapping via various optimisation techniques, such as "refreshing the ciphertexts" after every single homomorphic operation. To our knowledge, among the schemes based on GSW (and not only), TFHE [3] holds the record for fastest bootstrapping.
References
- ↑ C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer). https://eprint.iacr.org/2013/340
- ↑ J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094
- ↑ I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryptionover the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020). https://eprint.iacr.org/2018/421
