Difference between revisions of "GSW"

From certFHE Community KB
Jump to navigation Jump to search
Line 33: Line 33:
  
 
Remark that <math>C_2 \cdot C_1 </math> is also an encryption of <math>\mu_1 \mu_2</math>, even though matrix multiplication is not commutative. The essence of the previously anticipated asymmetry is captured by the fact that the noises of <math>C_1 \cdot C_2 </math> and <math>C_2 \cdot C_1</math> are very different.
 
Remark that <math>C_2 \cdot C_1 </math> is also an encryption of <math>\mu_1 \mu_2</math>, even though matrix multiplication is not commutative. The essence of the previously anticipated asymmetry is captured by the fact that the noises of <math>C_1 \cdot C_2 </math> and <math>C_2 \cdot C_1</math> are very different.
 +
 +
== Flattening ciphertexts and keeping the noise small ==
  
 
== References ==
 
== References ==

Revision as of 14:58, 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. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". Their security is based on the so-called approximate eigenvector problem.

Overview of the GSW scheme

We follow the exposition in the paper "Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based" [1] by Gentry, Sahai and Waters.

The description of this scheme is strikingly simple. In GSW, homomorphic encryption based on LWE is achieved while the homomorphic addition and multiplications correspond to matrix addition and multiplication, respectively.

Let be a natural number, representing some modulus and a dimension parameter. A ciphertext is a matrix of dimension with "small" entries from . A secret key is a -dimensional vector over with one big coefficient . We can intuitively think of "small" as meaning much smaller (in order of magnitude) than and "big" meaning the same order of magnitude as . In fact, we will make use of the case when the entries of belong to . We also restrict the message to be a "small" integer.

encrypts under if , where is a small error vector.

To decrypt, one first exacts the -th row of . Compute . Now, as is large and small, we have

.

Basically, is almost an eigenvector for corresponding to the eigenvalue . This is commonly referred to being an approximate eigenvector.


Observe that if and encrypt and respectively under the same key vector , then

,

where represents the error vector of , for . As long as the sum is small, the sum matrix is an encryption of .

Looking at the equality

,

we observe that is an encryption of the product , which can be decrypted correctly if the -th component of the vector is smaller than .

Remark that is also an encryption of , even though matrix multiplication is not commutative. The essence of the previously anticipated asymmetry is captured by the fact that the noises of and are very different.

Flattening ciphertexts and keeping the noise small

References

  1. 1.0 1.1 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
  2. J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094
  3. 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