GSW - Revision history

Gturcas at 10:10, 30 December 2020

2020-12-30T10:10:44Z

Gturcas at 10:10, 30 December 2020

2020-12-30T10:10:01Z

Gturcas: /* Homomorphic operations */

2020-06-09T15:57:47Z

Homomorphic operations

Gturcas: /* Homomorphic operations */

2020-06-09T15:56:23Z

Homomorphic operations

Gturcas at 08:53, 9 June 2020

2020-06-09T08:53:34Z

Gturcas: /* The basic algorithms of the encryption scheme */

2020-06-09T08:45:52Z

The basic algorithms of the encryption scheme

Gturcas: /* The basic algorithms of the encryption scheme */

2020-06-09T08:37:45Z

The basic algorithms of the encryption scheme

Gturcas: /* Flattening ciphertexts and keeping the noise small */

2020-06-09T08:30:36Z

Flattening ciphertexts and keeping the noise small

Gturcas: /* Flattening ciphertexts and keeping the noise small */

2020-06-09T07:55:04Z

Flattening ciphertexts and keeping the noise small

Gturcas at 12:34, 5 June 2020

2020-06-05T12:34:25Z

@@ Line 1: / Line 1: @@
 Around 2013, Gentry, Sahai and Waters <ref name = "GSW"> 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. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] problem (see Section 1.3.4) of GSW <ref name = "GSW"/>, basic the security of their scheme only on the [[LWE]] problem.
+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. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] problem (see Section 1.3.4) of GSW <ref name = "GSW"/>, basic the security of their scheme only on the LWE problem.
 == Overview of the GSW scheme ==

@@ Line 1: / Line 1: @@
 Around 2013, Gentry, Sahai and Waters <ref name = "GSW"> 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. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the [[LWE]] problem (see Section 1.3.4) of GSW <ref name = "GSW"/>, basic the security of their scheme only on the [[LWE]] problem.
+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. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] problem (see Section 1.3.4) of GSW <ref name = "GSW"/>, basic the security of their scheme only on the [[LWE]] problem.
 == Overview of the GSW scheme ==
@@ Line 8: / Line 8: @@
 Conceptually-Simpler, Asymptotically-Faster, Attribute-Based" <ref name = "GSW" /> 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.
+The description of this scheme is strikingly simple. In GSW, homomorphic encryption based on [https://en.wikipedia.org/wiki/Learning_with_errors LWE] is achieved while the homomorphic addition and multiplications correspond to matrix addition and multiplication, respectively.
 Let <math> q </math> be a natural number, representing some modulus and <math> N </math> a dimension parameter. A ciphertext is a matrix <math>  C </math> of dimension <math> N \times N </math> with "small" entries from <math> \mathbb Z_q </math>. A secret key <math> \vec{v} </math> is a <math> N</math>-dimensional vector over <math>\mathbb Z_q </math> with one big coefficient <math> v_i</math>. We can intuitively think of "small" as meaning much smaller (in order of magnitude) than <math> q</math> and "big" meaning the same order of magnitude as <math>q </math>. In fact, we will make use of the case when the entries of <math>C </math> belong to <math>\{0,1 \} </math>. We also restrict the message <math> \mu </math> to be a "small" integer.

@@ Line 112: / Line 112: @@
 * Mult(<math>C_1, C_2 </math>): To multiply ciphertexts <math>C_1, C_2 \in \mathbb Z_q^{N \times N} </math>, output <math>Flatten(C_1\cdot C_2) </math>.
-* MultConst(C, <math>\alpha</math>): To multiply a ciphertext <math>C \in \mathbb Z_q^{N \times N} </math> by a known constant <math> \alpha \in \mathbb Z_q</math>, given in the clear, we set <math>M_{\alpha} \leftarrow \alpha \cdot I_N </math> and output <math>M_{\alpha} \cdot C </math>.
+* MultConst(C, <math>\alpha</math>): To multiply a ciphertext <math>C \in \mathbb Z_q^{N \times N} </math> by a known constant <math> \alpha \in \mathbb Z_q</math>, given in the clear, we set <math>M_{\alpha} \leftarrow \alpha \cdot I_N </math> and output <math>Flatten(M_{\alpha} \cdot C) </math>.
 One could compute multiplication by <math>\alpha </math> by repeating additions. However, by repeating additions, the error of the resulting ciphertext will be linear in <math> \alpha </math>. On the other hand, if one uses MultConst(), the error term depends only on the dimension <math>N</math> and not on <math>\alpha </math>. This turns out to be extremely convenient for when <math>\alpha </math> is very large (possible applications of this includes homomorphic fast Fourier transforms).

@@ Line 112: / Line 112: @@
 * Mult(<math>C_1, C_2 </math>): To multiply ciphertexts <math>C_1, C_2 \in \mathbb Z_q^{N \times N} </math>, output <math>Flatten(C_1\cdot C_2) </math>.
-* MultConst(C, \alpha): To multiply a ciphertext <math>C \in \mathbb Z_q^{N \times N} </math> by a known constant <math> \alpha \in \mathbb Z_q</math>, given in the clear, we set <math>M_{\alpha} \leftarrow \alpha \cdot I_N </math> and output <math>M_{\alpha} \cdot C </math>.
+* MultConst(C, <math>\alpha</math>): To multiply a ciphertext <math>C \in \mathbb Z_q^{N \times N} </math> by a known constant <math> \alpha \in \mathbb Z_q</math>, given in the clear, we set <math>M_{\alpha} \leftarrow \alpha \cdot I_N </math> and output <math>M_{\alpha} \cdot C </math>.
 One could compute multiplication by <math>\alpha </math> by repeating additions. However, by repeating additions, the error of the resulting ciphertext will be linear in <math> \alpha </math>. On the other hand, if one uses MultConst(), the error term depends only on the dimension <math>N</math> and not on <math>\alpha </math>. This turns out to be extremely convenient for when <math>\alpha </math> is very large (possible applications of this includes homomorphic fast Fourier transforms).

@@ Line 1: / Line 1: @@
 Around 2013, Gentry, Sahai and Waters <ref name = "GSW"> 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. 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]]. The authors also provide a reduction from the approximate eigenvector problem to the [[LWE]] problem (see Section 1.3.4) of GSW <ref name = "GSW"/>.
+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. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the [[LWE]] problem (see Section 1.3.4) of GSW <ref name = "GSW"/>, basic the security of their scheme only on the [[LWE]] problem.
 == Overview of the GSW scheme ==

@@ Line 88: / Line 88: @@
 * SecretKeyGen(<math>params</math>): Sample <math>\vec{t} \leftarrow \mathbb Z_{q}^n </math> uniformly. Output <math> sk = \vec{s} \leftarrow (1, -t_1, \dots, -t_n) \in \mathbb \Z_q^{n+1}</math>. Let <math>\vec{v} = Powersof2(\vec{s}) </math>.
-* PublicKeyGen(<math>params</math>): Generate a matrix <math> B = \mathbb Z_q^{m \times n} </math> and a vector with small entries (noise) <math>\vec{e} \leftarrow \chi^m </math>. Set <math>\vec{b} = B \cdot \vec{t} + \vec{e}</math> and <math>A </math> to be the <math>(n+1) </math> column matrix which is obtained by the placing <math> \vec b </math> on the first column, fllowed by the <math> n</math> columns of <math> B </math>. Set the public key <math> pk = </math>. We observe that <math>A \cdot \vec{s} = \vec{e}.</math>
+* PublicKeyGen(<math>params</math>): Generate a matrix <math> B = \mathbb Z_q^{m \times n} </math> and a vector with small entries (noise) <math>\vec{e} \leftarrow \chi^m </math>. Set <math>\vec{b} = B \cdot \vec{t} + \vec{e}</math> and <math>A </math> to be the <math>(n+1) </math> column matrix which is obtained by the placing <math> \vec b </math> on the first column, fllowed by the <math> n</math> columns of <math> B </math>. Set the public key <math> pk = A </math>. We observe that <math>A \cdot \vec{s} = \vec{e}.</math>
 * Enc(<math>params,pk,\mu </math>): To encrypt a message <math>\mu \in \mathbb Z_q </math>, sample a uniform matrix <math>R \in \{0,1 \}^{N \times m} </math> and output the ciphertext

@@ Line 84: / Line 84: @@
 Let <math> \lambda </math> be the security parameter and <math>L</math> a natural number representing the multiplicative level of homomorphic operations this scheme can achieve. If we know the maximal level <math> L </math>  that we want to evaluate, we can choose parameters such that the scheme can handle circuits of depth <math>L</math>.  Thus, the scheme described here is a priori a Somewhat Homomorphic Encryption scheme and can be made fully homomorphic after applying Gentry's bootstrapping theorem.
-* Setup(<math>1^{\lambda}, 1^L </math>): We choose a modulus <math> q=q(\lambda, L)</math>, depending of <math>\lambda, L </math>, a lattice dimension parameter <math>n=n(\lambda, L)</math> and an error distribution <math>\chi = \chi(\lambda, L) </math> such that the scheme achieves at least <math>2^{\lambda}</math> security against known attacks. We also choose a parameter <math> m= (\lambda, L) = O(n \log_{q}) </math>. We set the paramaters of the scheme <math>params = (n , q, \chi,m) </math> and let <math> l = \lfloor \log_{2}q  \rfloor +1 </math> and <math>N = (n+1)\cdot l</math>.
+* Setup(<math>1^{\lambda}, 1^L </math>): We choose a modulus <math> q=q(\lambda, L)</math>, depending of <math>\lambda, L </math>, a lattice dimension parameter <math>n=n(\lambda, L)</math> and an error distribution <math>\chi = \chi(\lambda, L) </math> such that the scheme achieves at least <math>2^{\lambda}</math> security against known attacks. We also choose a parameter <math> m= m(\lambda, L) = O(n \log_{q}) </math>. We set the paramaters of the scheme <math>params = (n , q, \chi,m) </math> and let <math> l = \lfloor \log_{2}q  \rfloor +1 </math> and <math>N = (n+1)\cdot l</math>.
 * SecretKeyGen(<math>params</math>): Sample <math>\vec{t} \leftarrow \mathbb Z_{q}^n </math> uniformly. Output <math> sk = \vec{s} \leftarrow (1, -t_1, \dots, -t_n) \in \mathbb \Z_q^{n+1}</math>. Let <math>\vec{v} = Powersof2(\vec{s}) </math>.

@@ Line 63: / Line 63: @@
 Some obvious properties of these definitions are
-*<math> \langle BitDecomp(\vec{a}), Powersof2(\vec{b}) \rangle = \langle a,b \rangle \rangle </math>;
+*<math> \langle BitDecomp(\vec{a}), Powersof2(\vec{b}) \rangle = \langle a,b \rangle </math>;
 * For any <math>N</math>-dimensional <math>\vec{a'} </math>, we have that

@@ Line 44: / Line 44: @@
 Notice that if <math>C_1, C_2</math> are two <math>B</math>-strongly bounded ciphertexts, the ciphertext <math>C_3 \leftarrow I_N - C_1 C_2 </math> obtained by evaluating a NAND gate has underlying message in <math> \{0,1 \} </math>, but the coefficients of <math> C_3</math>'s error vector have magnitude at most <math>(N+1)B</math>. If one could ensure that the coefficients of <math>C_3</math> have magnitude at most <math> 1</math>, then the noise after evaluating a NAND gate will remain quite small, allowing us to evaluate deeper circuits.
-The authors introduce an operation on ciphertexts called <b> flattening</b>, inspired by ideas in second generation FHE schemes such as [[BFV]] and [[BGV]]. Flattening is basically an operation that modify vectors without affecting their dot product.
+The authors introduce an operation on ciphertexts called <b> flattening</b>, inspired by ideas in second generation FHE schemes such as [[BGV]]. Flattening is basically an operation that modify vectors without affecting their dot product.
 Let <math> N = k \cdot l</math> , where <math> l = \lfloor \log_2{q}+1 \rfloor </math>  and <math> k</math> is a positive integer. We will consider <math>\vec{a}, \vec{b} \in \mathbb Z_q^k </math>, two <math>k</math>-dimensional vector spaces.