GSW - Bootstrapping - Revision history

Gturcas: /* Bootstrapping */

2020-12-30T10:18:34Z

Bootstrapping

Gturcas: /* Bootstrapping */

2020-12-30T10:17:36Z

Bootstrapping

Gturcas: /* Bootstrapping */

2020-12-30T10:16:53Z

Bootstrapping

Gturcas at 10:15, 30 December 2020

2020-12-30T10:15:58Z

Gturcas at 10:12, 30 December 2020

2020-12-30T10:12:51Z

Gturcas at 13:30, 16 June 2020

2020-06-16T13:30:10Z

Gturcas: /* Bootstrapping */

2020-06-16T13:19:30Z

Bootstrapping

Gturcas: /* Bootstrapping */

2020-06-16T13:17:43Z

Bootstrapping

Gturcas: /* Bootstrapping */

2020-06-16T12:41:56Z

Bootstrapping

Gturcas at 12:35, 16 June 2020

2020-06-16T12:35:10Z

@@ Line 126: / Line 126: @@
 Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.
-We refer to the paper of Alperin-Sheriff and Peikert <ref tag= "ASP"></ref>  for a detailed analysis of the security and correctness.
+We refer to the paper of Alperin-Sheriff and Peikert [2] for a detailed analysis of the security and correctness.
 == References ==

@@ Line 126: / Line 126: @@
 Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.
-We refer to the paper of Alperin-Sheriff and Peikert <ref name = "ASP">  for a detailed analysis of the security and correctness.
+We refer to the paper of Alperin-Sheriff and Peikert <ref tag= "ASP"></ref>  for a detailed analysis of the security and correctness.
 == References ==

@@ Line 126: / Line 126: @@
 Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.
-We refer to the paper of Alperin-Sheriff and Peikert <ref name = "ASP"> </ref> for a detailed analysis of the security and correctness.
+We refer to the paper of Alperin-Sheriff and Peikert <ref name = "ASP">  for a detailed analysis of the security and correctness.
 == References ==

@@ Line 126: / Line 126: @@
 Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.
-==Correctness and error analysis ==
+We refer to the paper of Alperin-Sheriff and Peikert <ref name = "ASP"> </ref> for a detailed analysis of the security and correctness.
 == References ==

← Older revision		Revision as of 10:12, 30 December 2020
Line 1:		Line 1:
−	Gentry's [[bootstrapping]] theorem allows for converting a “somewhat homomorphic” encryption scheme (which supports only a bounded number of homomorphic operations) into a fully	+	Gentry's bootstrapping theorem <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref> allows for converting a “somewhat homomorphic” encryption scheme (which supports only a bounded number of homomorphic operations) into a fully
	homomorphic encryption one (which has no such bound). The bounded nature of all known somewhat homomorphic schemes cannot be avoided due to “error” terms in their ciphertexts, which are necessary for security. The error grows as a result of performing homomorphic operations, and if it grows too large, the ciphertext will no longer decrypt correctly.		homomorphic encryption one (which has no such bound). The bounded nature of all known somewhat homomorphic schemes cannot be avoided due to “error” terms in their ciphertexts, which are necessary for security. The error grows as a result of performing homomorphic operations, and if it grows too large, the ciphertext will no longer decrypt correctly.

← Older revision		Revision as of 13:30, 16 June 2020
Line 6:		Line 6:

	Here we present an efficient bootstrapping method for a variant of the [[GSW]] scheme, as presented in the paper of Alperin-Sheriff and Peikert <ref name = "ASP"> J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094</ref>.		Here we present an efficient bootstrapping method for a variant of the [[GSW]] scheme, as presented in the paper of Alperin-Sheriff and Peikert <ref name = "ASP"> J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094</ref>.
		+
		+	Recall that in [[GSW]], a ciphertext is a square binary matrix <math>C</math>, a secret key is a "structured" mod <math> q </math> vector <math> s </math>, and <math>s </math> is an "approximate mod <math> q</math> eigenvector" of <math>C</math>, in the sense that <math>s^t C \approx \mu \cdot s^t </math>, where <math> \mu \in \mathbb Z </math> is the message.
		+
		+	In this new variant, a ciphertext is a rectangular mod <math>q </math> matrix <math>C</math>, a secret key is some (unstructured, short) integer vector <math>s \in \mathbb Z^n </math> and <math>s^t C \approx \mu \cdot s^t G</math> (mod <math> q </math>), i.e. <math>s </math> amd <math>G^ts </math> are corresponding left- and right- "approximate singular vectors" of <math> C</math>.

	== A "simpler" variant of the GSW cryptosystem ==		== A "simpler" variant of the GSW cryptosystem ==

← Older revision		Revision as of 13:19, 16 June 2020
Line 121:		Line 121:

	Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.		Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.
		+
		+	==Correctness and error analysis ==
		+
		+	TODO!

	== References ==		== References ==

← Older revision		Revision as of 13:17, 16 June 2020
Line 106:		Line 106:

	Let <math>q</math> be of the form <math>q = \prod_{i \in [t]} r_i </math>, where <math> r_i</math> are small powers of distinct primes. One can choose <math>q = \tilde{O}(\lambda) </math> to be large enough by letting it be the product of all maximal prime-powers <math>r_i </math> that are bounded by <math>O(\log(\lambda)) </math>, of which there are <math>t = O(\log(\lambda)/log(\log(\lambda))) </math>. Let <math> \phi</math> be the group embedding of <math>\mathbb Z_{q} </math> into <math>S= S_{r_1} \times S_{r_t} </math>, and let <math>\phi_i </math> denote the <math>i</math>-th component of this embedding, i.e. the one from <math>\mathbb Z_{q} </math> into <math>S_{r_i} </math>.		Let <math>q</math> be of the form <math>q = \prod_{i \in [t]} r_i </math>, where <math> r_i</math> are small powers of distinct primes. One can choose <math>q = \tilde{O}(\lambda) </math> to be large enough by letting it be the product of all maximal prime-powers <math>r_i </math> that are bounded by <math>O(\log(\lambda)) </math>, of which there are <math>t = O(\log(\lambda)/log(\log(\lambda))) </math>. Let <math> \phi</math> be the group embedding of <math>\mathbb Z_{q} </math> into <math>S= S_{r_1} \times S_{r_t} </math>, and let <math>\phi_i </math> denote the <math>i</math>-th component of this embedding, i.e. the one from <math>\mathbb Z_{q} </math> into <math>S_{r_i} </math>.
		+
		+	* BootGen(<math>s \in \mathbb Z_{q}^d, sk </math>): Given secret key <math>s \in \mathbb Z_{q}^d </math> for the scheme GSW and a secret key <math> sk </math> for HEPerm, embed each coordinate <math>s_j \in \mathbb Z_{q} </math> of <math>s</math> as <math>\phi(s_j)\in S</math> and encrypt the components under HEPerm. That is, generate and output the bootstrapping key
		+	<center><math>bk = \{C_{i,j} \leftarrow HEPerm.Enc(sk,\phi_i(s_j)): i \in [t], j \in [d] \} </math>.</center>
		+
		+	Recalling that we are working with embeddings of <math>\mathbb Z_{r_i} </math>, each <math> C_{i,j} \in \mathcal C^{r_i}</math> can be represented as a tuple of <math>r_i </math> GSW ciphertexts encrypting an indicator vector. Since <math>t, r_i = O(\log \lambda) </math> and <math>d= \tilde{O}(\lambda) </math>, the bootstrapping key has <math>\tilde O(\lambda) </math> ciphertexts.
		+
		+	* Bootstrap(<math>bk, c \in \{0,1 \}^{d} </math>): given a binary ciphertext <math>c \in \{0,1 \}^d </math>, do the following:
		+
		+	First, homomorphically compute an encryption of
		+	<math> v = \langle s,c \rangle = \sum_{j: c_j =1} s_j \in \mathbb Z_q </math>
		+	using the encryptions of the <math>s_j \in \mathbb Z_{q} </math> as embedded into the permutation group <math>S</math>. Additions above are replaced using a chain of compositions.
		+
		+	Then, one has to round. Homomorphically map <math>v \in \mathbb Z_q </math> to <math> \{0,1 \} </math>, in the following way. For each <math>x \in \mathbb Z_{q} </math> such that <math> f(x) =1 </math>, homomorphically tests whether <math>v = x </math> by evaluating the homomorphic product of the resulting ciphertexts from all the equality tests <math> v = x </math> mod <math> r_i</math>. Then homomorphically sum the results of all the <math>v= x </math> tests.
		+
		+	Bootstrapping performs <math>\tilde O(\lambda) </math> homomorphic multiplications and additions on GSW ciphertexts.

	== References ==		== References ==

@@ Line 103: / Line 103: @@
 ==Bootstrapping ==
-We have to instantiate the GSW and HEPerm with parameters <math>n, Q, \chi </math>. Importantly, the ciphertext modulus <math> Q </math> is not the modulus <math> q</math> of the scheme to be bootstrapped, but rather some modulus <math> Q >> q </math>.
+We have to instantiate the GSW and HEPerm with parameters <math>n, Q, \chi </math>. Importantly, the ciphertext modulus <math> Q </math> is not the modulus <math> q</math> of the scheme to be bootstrapped, but rather some modulus <math> Q >> q </math>. Let <math> \mathcal C</math> be the ciphertext of the GSW scheme.
 == References ==

@@ Line 100: / Line 100: @@
 <center><math>C \leftarrow C_1 \circ(C_2 \circ(\dots (C_k \circ J)\dots)) </math></center>
 has an error matrix whose <math>\mathbb Z </math>-entries are mutually independent, and those in its <math>i</math>-th row are subgaussian with parameter <math> O(||e_i||) </math>, where <math>e_i^t \in \mathcal E^{kr} </math> is the <math> i</math>-th row of the concatenated matrices <math>[E_1| \dots | E_k] </math>.
 == References ==