Difference between revisions of "GSW - Bootstrapping"

From certFHE Community KB
Jump to navigation Jump to search
 
(17 intermediate revisions by the same user not shown)
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.
  
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 ==
Line 66: Line 70:
 
<center><math>  C \leftarrow C_1 \boxdot \left( C_2 \boxdot(\dots C_k \boxdot G ) \dots) \right) </math> </center>
 
<center><math>  C \leftarrow C_1 \boxdot \left( C_2 \boxdot(\dots C_k \boxdot G ) \dots) \right) </math> </center>
 
has an error vector whose entries are mutually independent and subgaussian with parameter <math> O(||e||) </math>, where <math>e^t = (e_1^t, \dots, e_k^t) \in \mathbb Z^{knl} </math> is the concatenation of the individual error vectors.
 
has an error vector whose entries are mutually independent and subgaussian with parameter <math> O(||e||) </math>, where <math>e^t = (e_1^t, \dots, e_k^t) \in \mathbb Z^{knl} </math> is the concatenation of the individual error vectors.
 +
 +
 +
== Homomorphic encryption for Symmetric Groups ==
 +
 +
We describe HEPerm a homomorphic encryption scheme for symmetric groups. Let <math> \mathcal C </math> be the ciphertext space for the GSW scheme. The main procedures of HEPerm are as follows:
 +
 +
* HEPerm.Enc(<math>sk, \pi \in S_r </math>): let <math> P = (p_{i,j}) \in \{0,1 \}^{r \times r} </math> be the permutation matrix associated with <math> \pi \in S_r </math>. Output the following ciphertext space
 +
<center><math> C = (c_{i,j}) \in \mathcal C^{r \times r},</math>, where <math> c_{i,j} \leftarrow GSW.Enc(sk,p_{i,j}). </math>  </center>
 +
 +
This is an entry-wise encryption of <math>P</math>. Decryption is obvious. A ciphertext <math> C \in \mathcal C^{r \times r} </math> is said to be "designed" to encrypt a permutation <math>pi \in S_r</math>, if its <math>C</math>-entries are designed to encrypt the corresponding entries of <math>P_{\pi} </math>.
 +
 +
<math>J \in \mathcal C^{r \times r}</math> will denote the encryption of the identity permutation, where each entry is encrypted with zero noise.
 +
 +
* <b>Homomorphic composition:</b> <math>C^{\pi} \circ C^{\sigma} </math> will be computed in the obvious way. Namely, the entries of the output <math>C^{\pi} \circ C^{\sigma} = (c_{i,j}) \in \mathcal C^{r \times r} </math> where
 +
<center><math>c_{i,j} \leftarrow \sum\limits_{l \in [r]} (c_{i,l}^{\pi} \boxdot c_{l,j}^{\sigma}) \in \mathcal C.</math> </center>
 +
 +
Like the multiplication <math> \boxdot </math> for ciphertexts in the GSW, the composition <math> \circ </math> is right associative.
 +
 +
* <b>Homomorphic equality test </b> Eq?(<math>C^{\pi}=(c_{i,j}^{\pi}, \sigma \in S_r) </math>): Given a ciphertext encrypting some permutation <math>\pi \in S_r </math> and a permutation <math> \sigma \in S_r </math> (in the clear), output a ciphertext <math>c \in \mathcal C </math> encrypting <math>1 </math> if <math> \pi = \sigma </math> and <math>0 </math> otherwise, i.e. output
 +
<center><math>  c \leftarrow \prod\limits_{i \in [r]} c_{\sigma(i), i}^{\pi} \boxdot g</math> , </center>
 +
where <math>g \in \mathcal C </math> is the fixed zero-error encryption of <math>1</math>.
 +
 +
Remark the for the two operations above, the GSW ciphertext(s) that appear in the output are always designed to encrypt <math>\{0,1 \} </math> messages.
 +
 +
To analyse the noise resulting in these operations, let is recall that the GSW scheme is parameterized by <math>n,q </math>. Denote the space of error vectors by <math> \mathcal E = \mathbb Z^m </math>, where <math> m = n \lceil \log_2(q)  \rceil </math>. The Euclidean norm on <math>\mathcal E^r = \mathbb Z^{mr} </math> is defined in the ovious way. In the following analysis, we will often consider vectors and matrices over <math>\mathcal E </math>, i.e. in which the entries are vectors from <math>\mathcal E </math>.
 +
 +
<b>Claim.</b> (Lemma 4.1 in the first reference) The error matrix in <math>  C^{\pi} \circ C^{\sigma}</math> is <math>E + P^{\pi} \cdot E^{\sigma} </math>, where <math>P^{\pi} </math> is the matrix encoding <math> \pi</math> (in the clear), <math>E^{\sigma} \in \mathcal E^{r \times r}</math> is the error of <math> C^{\sigma} </math> and the <math>\mathbb Z </math>-entries of the matrix <math>E</math> are mutually independent, and those in its <math>i </math>-th row are subgaussian with parameter <math>O(||e_i^\pi||) </math>, where <math>e_{i}^{\pi} </math> is the <math>i</math>-th row of <math>E^{\pi} </math>.
 +
 +
Similarly to a multiplication chain of GSW ciphertexts, one can perform a (right-associative) chain of compositions while incurring only small error growth. For conveniece of analysis, we always include the fixed zero-error ciphertext <math> J \in \mathcal C^{r \times r} </math> as the rightmost ciphertext in the chain.
 +
 +
<b>Claim.</b> (Corollary 4.2 in the first reference) Suppose that <math> C_i</math>  are designed to encrypt permutation matrices <math>P_i \in \{0,1 \}^{r \times r} </math> and have error matrices <math>E_i \in \mathcal E^{r \times r} </math>. Then for any fixed values of these variables,
 +
 +
<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>.
 +
 +
==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>. Let <math> \mathcal C</math> be the ciphertext of the GSW scheme.
 +
 +
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.
 +
 +
We refer to the paper of Alperin-Sheriff and Peikert [2] for a detailed analysis of the security and correctness.
  
 
== References ==
 
== References ==

Latest revision as of 12:18, 30 December 2020

Gentry's bootstrapping theorem [1] 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.

Bootstrapping the error of a ciphertext so that it can support more homomorphic operations, by homomorphically evaluating the decryption function on the ciphertext. The result is a ciphertext that still encrypts the original encrypted message. If the error coming from the homomorphic evaluation is smaller than the error in the original ciphertext, we say that the ciphertext is “refreshed”. To date, bootstrapping is the only known way of obtaining an unbounded FHE scheme, i.e., one that can homomorphically evaluate any efficient function using keys and ciphertexts of a fixed size.

Here we present an efficient bootstrapping method for a variant of the GSW scheme, as presented in the paper of Alperin-Sheriff and Peikert [2].

Recall that in GSW, a ciphertext is a square binary matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} , a secret key is a "structured" mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s } , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s } is an "approximate mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} eigenvector" of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} , in the sense that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s^t C \approx \mu \cdot s^t } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu \in \mathbb Z } is the message.

In this new variant, a ciphertext is a rectangular mod matrix , a secret key is some (unstructured, short) integer vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \in \mathbb Z^n } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s^t C \approx \mu \cdot s^t G} (mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } ), i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s } amd Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G^ts } are corresponding left- and right- "approximate singular vectors" of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} .

A "simpler" variant of the GSW cryptosystem

The authors present a variant of the GSW scheme which permits a tighter analysis of its error growth under homomorphic operations.

Given a modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } , let us denote by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l = \lceil \log_2(q) \rceil } and define the "gadget" (we will think of it as column) vector

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak g = (1,2,4, \dots, 2^{l-1}) \in \mathbb Z_q^l. }

Remark that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{l-2} \in [q/4,q/2) \pmod{q}} , according to our choice of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l} .

A randomized decomposition function. There is a randomized, efficiently computable function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak g^{-1}: \mathbb Z_q \to \mathbb Z^l } such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x \leftarrow \mathfrak g^{-1}(a) } is "subgaussian" with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(1)} , and always satisfies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \langle g,x \rangle =a } . [3]

In particular Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x } is randomized and has low entries with very large probability.

For vectors and matrices over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z_q } , define the randomized function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G^{-1} : \mathbb Z_q^{n \times m} \to \mathbb Z^{nl \times m}} by applying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak g } independently to each entry. Notice that for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \in \mathbb Z_{q}^{n \times m}} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X \leftarrow G^{-1}(A) } , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X} has small entries (is "subgaussian") and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G \cdot X = A } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G = \mathfrak g^t \otimes I_n = \mathrm{diag}(\mathfrak g^t, \dots ,\mathfrak g^t) \in \mathbb Z_q^{n \times nl},}

is the block matrix with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} copies of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak g^t} as diagonal blocks, and zeros elsewhere.

This version of the GSW scheme has as parameters a dimension Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n } , a modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l = \lceil \log_2(q) \rceil } , as defined above. For bootstrapping, we only work with ciphertexts encrypting messages in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{0,1 \} \subseteq \mathbb Z } . The ciphertext space is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal C = \mathbb Z_q^{n \times nl} } . For simplicity, we present just a symmetric-key scheme, which can be converted to a public key setting, similar to the one described in GSW.

A substantial difference between the original GSW scheme and this variant is the following: the homomorphic multiplication procedure in the current variant uses the randomized Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G^{-1}(\cdot)} operation presented above. This gives important advantages, such as very simple error analysis (using the subgaussianity property) and the ability to completely re-randomize the error in a ciphertext.

The algorithms of the scheme are as follows

  • GSW.Gen(): choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \overline{s} \leftarrow \chi^{n-1}} and output the secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s = (\overline s, 1) \in \mathbb Z^n} .
  • GSW.Enc(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (\overline s, 1), \mu \in \mathbb Z } ): choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \overline{C} \leftarrow Z_{q}^{(n-1) \times nl} } uniformly and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e \leftarrow \chi^{nl}} , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b^t = e^t - \overline{s}^t \overline{C}} mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} , and output the ciphertext
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C = \left( \begin{array}{c} \overline{C} \\ b^t \end{array} \right) + \mu G \in \mathcal C,}

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G = \mathrm{diag}(\mathfrak g^t, \dots ,\mathfrak g^t) \in \mathbb Z_q^{n \times nl} } .

  • GSW.Dec(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s, C \in \mathcal C } ): let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c} be the penultimate column of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} . Output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu = \lfloor \langle s,c \rangle \rceil_2 } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lfloor \cdot \rfloor_2 : \mathbb Z_{q} \to \{0,1 \} } indicates whether its argument is closer modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0} or to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{l-2} } , the penultimate entry of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathfrak g } .
  • GSW.Add(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_1, C_2 } ): Output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_1 + C_2 } .
  • GSW.Multiply(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_1, C_2 } ): Output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_1 \cdot G^{-1}(C_2) } . This operation is a ramdomized one, as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G^{-1}} is randomized. The multiplication is also right-associative.

The authors remark that a fresh ciphertext is just Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu G} plus a matrix which contains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle nl} independent LWE samples under the secret Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \overline{s} } which are pseudorandom if one assumes the hardness of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle LWE_{n-1},q, \chi } .

Correctness and homomorphic operations

A ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} is said to be designed to encrypt a message Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu \in \mathbb Z } (under a secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s } ) if it is a fresh encryption of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu} , or if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C } is the sum (or the product) of two ciphertexts that are designed to encrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu_1, \mu_2 \in \mathbb Z} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu = \mu_1 +\mu_2} .

The error vector of a ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C } designed to encrypt a message Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu } under the key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^t = s^t C - \mu \cdot s^t G } (mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} ).

Notice that the matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu G } is designed to encrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu} and has error Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0} .

Claim. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C } is designed to encrypt some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu \in \{0,1 \} \subset \mathbb Z} and has error vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^t } whose penultimate coordinate has magnitude less than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q/8} , then GSW.Dec(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s,C } ) correctly outputs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu} .

This follows from the fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s=(\overline s,1)} and the penultimate column of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (0,\dots, 0, 2^{l-2})} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{l-2} \in [q/4,q/2) } mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} .

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_1, C_2 } be ciphertexts designed to encrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu_1, \mu_2 \in \mathbb Z } and have error vectors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_1^t, e_2^t } . Then, their homomorphic sum has error vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_1^t + e_2^t} . Moreover, if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_1 \boxdot C_2 } is the homomorphic product of these ciphertexts, then for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X \leftarrow G^{-1}(C_2) } (subgaussian), we have the following

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s^t(C_1 \boxdot C_2)= s^t C_1 \cdot X = (e_1^t + \mu_1 \cdot s^t G)X} ,

which as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G \cdot X = C_2} is further equal to

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s^t(C_1 \boxdot C_2) = e_1^t X + \mu_1(e_2^t + \mu_2 \cdot s^t G) = (e_1^t X + \mu_1 e_2^t) + \mu_1 \mu_2 \cdot s^t G.}

It is important to remember that the error upon multiplication is quasi-additive and asymmetric with respect to the errors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_1^t, e_2^t } . The first error is multiplied by a subgaussian matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X} , the second error vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_2^t } is only multiplied by the message , which the authors make sure they always keep in .

Homomorphic product of multiple ciphertexts. Suppose that are designed to encrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu_i \in \{0, 1 \} } and have error vectors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_i^{t} } . Then for any fixed values of these variables, the matrix

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C \leftarrow C_1 \boxdot \left( C_2 \boxdot(\dots C_k \boxdot G ) \dots) \right) }

has an error vector whose entries are mutually independent and subgaussian with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(||e||) } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^t = (e_1^t, \dots, e_k^t) \in \mathbb Z^{knl} } is the concatenation of the individual error vectors.


Homomorphic encryption for Symmetric Groups

We describe HEPerm a homomorphic encryption scheme for symmetric groups. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal C } be the ciphertext space for the GSW scheme. The main procedures of HEPerm are as follows:

  • HEPerm.Enc(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle sk, \pi \in S_r } ): let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P = (p_{i,j}) \in \{0,1 \}^{r \times r} } be the permutation matrix associated with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \pi \in S_r } . Output the following ciphertext space
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C = (c_{i,j}) \in \mathcal C^{r \times r},} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_{i,j} \leftarrow GSW.Enc(sk,p_{i,j}). }

This is an entry-wise encryption of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P} . Decryption is obvious. A ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C \in \mathcal C^{r \times r} } is said to be "designed" to encrypt a permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle pi \in S_r} , if its Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C} -entries are designed to encrypt the corresponding entries of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_{\pi} } .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle J \in \mathcal C^{r \times r}} will denote the encryption of the identity permutation, where each entry is encrypted with zero noise.

  • Homomorphic composition: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C^{\pi} \circ C^{\sigma} } will be computed in the obvious way. Namely, the entries of the output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C^{\pi} \circ C^{\sigma} = (c_{i,j}) \in \mathcal C^{r \times r} } where
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_{i,j} \leftarrow \sum\limits_{l \in [r]} (c_{i,l}^{\pi} \boxdot c_{l,j}^{\sigma}) \in \mathcal C.}

Like the multiplication Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \boxdot } for ciphertexts in the GSW, the composition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \circ } is right associative.

  • Homomorphic equality test Eq?(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C^{\pi}=(c_{i,j}^{\pi}, \sigma \in S_r) } ): Given a ciphertext encrypting some permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \pi \in S_r } and a permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma \in S_r } (in the clear), output a ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c \in \mathcal C } encrypting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1 } if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \pi = \sigma } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0 } otherwise, i.e. output
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c \leftarrow \prod\limits_{i \in [r]} c_{\sigma(i), i}^{\pi} \boxdot g} ,

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g \in \mathcal C } is the fixed zero-error encryption of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1} .

Remark the for the two operations above, the GSW ciphertext(s) that appear in the output are always designed to encrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{0,1 \} } messages.

To analyse the noise resulting in these operations, let is recall that the GSW scheme is parameterized by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n,q } . Denote the space of error vectors by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal E = \mathbb Z^m } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = n \lceil \log_2(q) \rceil } . The Euclidean norm on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal E^r = \mathbb Z^{mr} } is defined in the ovious way. In the following analysis, we will often consider vectors and matrices over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal E } , i.e. in which the entries are vectors from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal E } .

Claim. (Lemma 4.1 in the first reference) The error matrix in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C^{\pi} \circ C^{\sigma}} is , where is the matrix encoding (in the clear), is the error of and the -entries of the matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E} are mutually independent, and those in its Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i } -th row are subgaussian with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(||e_i^\pi||) } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_{i}^{\pi} } is the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} -th row of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E^{\pi} } .

Similarly to a multiplication chain of GSW ciphertexts, one can perform a (right-associative) chain of compositions while incurring only small error growth. For conveniece of analysis, we always include the fixed zero-error ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle J \in \mathcal C^{r \times r} } as the rightmost ciphertext in the chain.

Claim. (Corollary 4.2 in the first reference) Suppose that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_i} are designed to encrypt permutation matrices Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_i \in \{0,1 \}^{r \times r} } and have error matrices Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_i \in \mathcal E^{r \times r} } . Then for any fixed values of these variables,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C \leftarrow C_1 \circ(C_2 \circ(\dots (C_k \circ J)\dots)) }

has an error matrix whose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z } -entries are mutually independent, and those in its Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} -th row are subgaussian with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(||e_i||) } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_i^t \in \mathcal E^{kr} } is the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} -th row of the concatenated matrices Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [E_1| \dots | E_k] } .

Bootstrapping

We have to instantiate the GSW and HEPerm with parameters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n, Q, \chi } . Importantly, the ciphertext modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q } is not the modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} of the scheme to be bootstrapped, but rather some modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q >> q } . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal C} be the ciphertext of the GSW scheme.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} be of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q = \prod_{i \in [t]} r_i } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r_i} are small powers of distinct primes. One can choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q = \tilde{O}(\lambda) } to be large enough by letting it be the product of all maximal prime-powers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r_i } that are bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(\log(\lambda)) } , of which there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t = O(\log(\lambda)/log(\log(\lambda))) } . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \phi} be the group embedding of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z_{q} } into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S= S_{r_1} \times S_{r_t} } , and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \phi_i } denote the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} -th component of this embedding, i.e. the one from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z_{q} } into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_{r_i} } .

  • BootGen(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \in \mathbb Z_{q}^d, sk } ): Given secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \in \mathbb Z_{q}^d } for the scheme GSW and a secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle sk } for HEPerm, embed each coordinate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_j \in \mathbb Z_{q} } of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \phi(s_j)\in S} and encrypt the components under HEPerm. That is, generate and output the bootstrapping key
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle bk = \{C_{i,j} \leftarrow HEPerm.Enc(sk,\phi_i(s_j)): i \in [t], j \in [d] \} } .

Recalling that we are working with embeddings of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z_{r_i} } , each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{i,j} \in \mathcal C^{r_i}} can be represented as a tuple of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r_i } GSW ciphertexts encrypting an indicator vector. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t, r_i = O(\log \lambda) } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d= \tilde{O}(\lambda) } , the bootstrapping key has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde O(\lambda) } ciphertexts.

  • Bootstrap(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle bk, c \in \{0,1 \}^{d} } ): given a binary ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c \in \{0,1 \}^d } , do the following:

First, homomorphically compute an encryption of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v = \langle s,c \rangle = \sum_{j: c_j =1} s_j \in \mathbb Z_q } using the encryptions of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_j \in \mathbb Z_{q} } as embedded into the permutation group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S} . Additions above are replaced using a chain of compositions.

Then, one has to round. Homomorphically map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v \in \mathbb Z_q } to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{0,1 \} } , in the following way. For each such that , homomorphically tests whether Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v = x } by evaluating the homomorphic product of the resulting ciphertexts from all the equality tests Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v = x } mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r_i} . Then homomorphically sum the results of all the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v= x } tests.

Bootstrapping performs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde O(\lambda) } homomorphic multiplications and additions on GSW ciphertexts.

We refer to the paper of Alperin-Sheriff and Peikert [2] for a detailed analysis of the security and correctness.

References

  1. ↑ C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.
  2. ↑ J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094
  3. ↑ D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, pages 700–718. 2012 https://www.iacr.org/archive/eurocrypt2012/72370695/72370695.pdf
Retrieved from "https://certfhewiki.certsign.ro/wiki/index.php?title=GSW_-_Bootstrapping&oldid=256"