Difference between revisions of "GSW"
| (27 intermediate revisions by the same user not shown) | |||
| 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. | 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". | + | 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 == | == Overview of the GSW scheme == | ||
| Line 8: | Line 8: | ||
Conceptually-Simpler, Asymptotically-Faster, Attribute-Based" <ref name = "GSW" /> by Gentry, Sahai and Waters. | 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 [ | + | 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. | 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 35: | Line 35: | ||
== Flattening ciphertexts and keeping the noise small == | == Flattening ciphertexts and keeping the noise small == | ||
| + | |||
| + | We can decrypt homomorphically evaluated ciphertext <math>C</math> as long as the <math>i</math>-th component of the error vector <math>\vec{e}</math> is small enough. As we saw in the overview section, the noise might grow quickly with each multiplication. To mitigate this and to perform homomorphically evaluations of deep circuits (in the sense of multiplication depth), observing that the noise growth depends of the size of the coefficients of the ciphertexts, the size of the messages and the fresh error size (in an asymmetric way), we can try to restrict the message space and the entries of the ciphertexts to <math> \{0,1 \} </math>. We also impose a bound <math>B</math> for the entries of the fresh fresh error vectors <math>\vec{e}</math>. | ||
| + | |||
| + | Such ciphertexts will be further called <math>B</math>-strongly bounded, terminology that is used throughout the paper GSW <ref name = "GSW" />. | ||
| + | |||
| + | The homomorphic operations performed on ciphertexts should correspond to operations "in the clear" that keep the message within the set <math>\{0,1 \}</math>. To achieve this, we will use only <b>NAND</b> gates to evaluate any circuit. | ||
| + | |||
| + | 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 [[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. | ||
| + | |||
| + | <center> <math>BitDecomp(\vec a) = (a_{1,0}, \dots, a_{1,l-1}, \dots, a_{k,0},\dots, a_{k,l-1}),</math> where <math>a_{i,j}</math> is the <math>j</math>-th bit in the binary decomposition of <math>a_i </math>, so a <math>N</math>-dimensional vector. </center> | ||
| + | |||
| + | For any <math>N</math>-dimensional vector <math>\vec{a'}= (a_{1,0}, \dots, a_{1,l-1}, \dots, a_{k,0},\dots, a_{k,l-1}) </math>, define | ||
| + | |||
| + | <center><math>BitDecomp^{-1}(\vec{a'}) = \left( \sum 2^j \cdot a_{1,j}, \dots, \sum 2^j \cdot a_{k,j} \right) </math>, now a <math>k</math> dimensional vector, </center> | ||
| + | and | ||
| + | |||
| + | <center><math>Flatten(\vec{a'}) = BitDecomp(BitDecomp^{-1}(\vec{a})) \in \mathbb Z_q^{N} </math>. </center> | ||
| + | |||
| + | The authors also introduce | ||
| + | |||
| + | <center><math>Powersof2(\vec{b}) = (b_1, 2b_1, \dots, 2^{l-1}b_1, \dots, b_k, 2b_k, \dots, 2^{l-1}b_k) </math>, an <math>N</math>-dimensional vector. </center> | ||
| + | |||
| + | Some obvious properties of these definitions are | ||
| + | |||
| + | *<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 | ||
| + | <math> \langle \vec{a'}, Powersof2(\vec{b}) \rangle = \langle BitDecomp^{-1}(\vec{a'}),\vec{b} \rangle = \langle Flatten(\vec{a'}), Powersof2(\vec{b}) \rangle.</math> | ||
| + | |||
| + | The latter is showing us an interesting feature of <math> Flatten </math>, i.e. it makes the coefficients of a vector "small", without changing its inner product with <math>Powersof2(\vec{b})</math> | ||
| + | |||
| + | We will have to "flatten" ciphertexts, which are matrices. When <math>Flatten </math> is applied to a <math>N \times N </math> matrix <math>C</math> , this will be done by applying <math> Flatten</math> to each row of <math>C</math>. Recall that a step in the decryption process is multiplying the ciphertext matrix <math>C</math> with a secret key vector <math>\vec v</math>. We will always use <math> \vec{v} = Powersof2(\vec{s}) </math>, a vector of this special form in order for flattening to preserve the product between <math> C</math> and <math>\vec{v} </math> required for decryption. | ||
| + | |||
| + | Now, for any <math>N \times N</math> ciphertext matrix <math>C</math>, we have | ||
| + | |||
| + | <center><math>Flatten(C) \cdot \vec{v} = C \cdot \vec{v}</math> </center> | ||
| + | |||
| + | After computing a ciphertext <math>C_3 \leftarrow I_N - C_1 \cdot C_2 </math> for the NAND gate, we will immediately flatten it, namely we will set | ||
| + | |||
| + | <center><math> C^{NAND} \leftarrow Flatten(C_3) </math>.</center> | ||
| + | |||
| + | == The basic algorithms of the encryption scheme == | ||
| + | |||
| + | 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= 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>. | ||
| + | |||
| + | * 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 | ||
| + | |||
| + | <center><math> C \leftarrow Flatten(\mu \cdot I_N + BitDecomp(R \cdot A)) \in \mathbb Z_{q}^{N \times N} </math> </center> | ||
| + | |||
| + | <b>Disclaimer</b>: The decryption algorithm we describe below decrypts correctly only messages in <math> \{ 0,1 \} </math>. This can be easily generalised to recover any <math>\mu \in \mathbb Z_q</math>, bit by bit, starting with the least significant one. The interested reader should consult for example the paper of Micciano and Peikert. <ref>D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, | ||
| + | smaller. In EUROCRYPT, pages 700–718, 2012. https://eprint.iacr.org/2011/501 </ref> | ||
| + | |||
| + | * Dec(<math> params, sk, C</math>): Observe that the first <math> l</math> coefficients of <math> \vec{v} </math> are <math> 1, 2, \dots, 2^{l-1}</math>. Let us choose, among these coefficients, the unique <math>v_i = 2^i \in (q/4,q/2] </math>. Let <math>C_i </math> be the <math> i</math>-th row of <math>C </math>. We output | ||
| + | <center><math> \mu' = \left\lfloor \frac{\langle C_i, \vec v \rangle}{v_i} \right\rceil</math> .</center> | ||
| + | |||
| + | We remark that <math>Dec </math> is only applied to one row of the ciphertext, however extra rows will play a role in the homomorphic operations. If <math>C </math> is properly generated (fresh), then by the properties of <math>BitDecomp </math> described above, we have | ||
| + | |||
| + | <center><math> C \cdot \vec{v} = \mu \cdot v + R\cdot A \cdot \vec{s} = \mu \cdot v + R \cdot \vec{e} </math> </center> | ||
| + | |||
| + | The <math>i</math>-th coefficient of the above expression is <math>x_i = \mu \cdot v_i + \langle R, \vec e \rangle </math>. In the encryption scheme, we set <math> \chi </math> to ensure that the error <math>\vec{e} </math> is <math>B</math>-bounded with very high probability. | ||
| + | |||
| + | == Homomorphic operations == | ||
| + | |||
| + | * Add(<math>C_1, C_2 </math>): To add ciphertexts <math>C_1, C_2 \in \mathbb Z_q^{N \times N} </math>, output <math>Flatten(C_1+C_2)</math>. | ||
| + | |||
| + | * 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>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). | ||
| + | |||
| + | * NAND(<math> </math>): To NAND ciphertexts <math>C_1, C_2 \in \mathbb Z_q^{N \times N} </math> that are known to encrypt messages <math>\mu_1, \mu_2 \in \{0,1 \} </math>, output <math>Flatten(I_N - C_1 \cdot C_2) </math>. | ||
| + | |||
| + | The NAND homomorphic operation increases the error by a factor of at most <math>N+1 </math>. | ||
| + | |||
| + | By iteratively applying the homomorphic operations above, different types of (boundeddepth) circuits may be homomorphically computed while maintaining correctness of decryption. | ||
| + | The simplest ones to analyse are Boolean circuits computed over encryptions of | ||
| + | <math> \{0, 1\}</math> values. Here the circuit can be converted to use only NAND gates, and the final ciphertext’s error | ||
| + | will be bounded by <math> (N + 1)^L \cdot B</math>, where L is the NAND-depth of the circuit, and <math> B </math> is the original | ||
| + | bound on the error of a fresh encryption of <math> \{0, 1\}</math>. | ||
== References == | == References == | ||
Latest revision as of 12:10, 30 December 2020
Around 2013, Gentry, Sahai and Waters [1] proposed a new way of building FHE schemes whose homomorphic multiplication algorithms are more natural than those presented in BFV or BGV. A distinguished feature of the scheme we are about to present is an asymmetric formula for the growth of the noise when multiplying two ciphertexts. Due to this feature, certain types of circuits have a very slow noise growth rate. Based on this asymmetry, Alperin-Sheriff and Peikert [2] found a very efficient bootstrapping technique for the GSW scheme.
More efficient FHE schemes based on ring variants of GSW have been proposed since then. These achieve very fast bootstrapping via various optimisation techniques, such as "refreshing the ciphertexts" after every single homomorphic operation. To our knowledge, among the schemes based on GSW (and not only), TFHE [3] holds the record for fastest bootstrapping. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the LWE problem (see Section 1.3.4) of GSW [1], basic the security of their scheme only on the LWE problem.
Contents
Overview of the GSW scheme
We follow the exposition in the paper "Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based" [1] by Gentry, Sahai and Waters.
The description of this scheme is strikingly simple. In GSW, homomorphic encryption based on LWE is achieved while the homomorphic addition and multiplications correspond to matrix addition and multiplication, respectively.
Let be a natural number, representing some modulus and 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 dimension parameter. A ciphertext is a 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 } of 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 \times N } with "small" entries 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 } . 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 \vec{v} } is a 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} -dimensional vector 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 } with one big coefficient 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_i} . We can intuitively think of "small" as meaning much smaller (in order of magnitude) 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} and "big" meaning the same order of magnitude 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 q } . In fact, we will make use of the case when the 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 C } belong 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 \} } . We also restrict the 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 } to be a "small" integer.
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 } encrypts 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 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 \vec{v}} 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 \cdot \vec{v} = \mu \cdot \vec{v} + \vec{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 \vec{e} } is a small error vector.
To decrypt, one first exacts 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 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} 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} . Compute 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 \langle C_i, \vec{v} \rangle = \mu \cdot v_i + e_i } . Now, 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 v_i} is large 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_i } small, we have
Basically, 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 \vec{v} } is almost an eigenvector 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 C } corresponding to the eigenvalue 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 is commonly referred to being an approximate eigenvector.
Observe that 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 }
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 C_2 }
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 }
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_2 }
respectively under the same key 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 v }
, then
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 \vec{e_i} } represents the error vector 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_i} , 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 i \in \{ 1,2\} } . As long as the sum 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 \vec{e_1} + \vec{e_2} } is small, the sum 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_1 +C_2 } is 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 \mu_1 +\mu_2} .
Looking at the equality
,
we observe 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_1 \cdot C_2 } is an encryption of the product 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 } , which can be decrypted correctly if 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 the 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 \mu_2 \cdot \vec{e_1} + C_1 \cdot \vec{e_2} } is smaller 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 v_i} .
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 C_2 \cdot C_1 } is also 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 \mu_1 \mu_2} , even though matrix multiplication is not commutative. The essence of the previously anticipated asymmetry is captured by the fact that the noises 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_1 \cdot C_2 } 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 C_2 \cdot C_1} are very different.
Flattening ciphertexts and keeping the noise small
We can decrypt homomorphically evaluated 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} as long as 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 the 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 \vec{e}} is small enough. As we saw in the overview section, the noise might grow quickly with each multiplication. To mitigate this and to perform homomorphically evaluations of deep circuits (in the sense of multiplication depth), observing that the noise growth depends of the size of the coefficients of the ciphertexts, the size of the messages and the fresh error size (in an asymmetric way), we can try to restrict the message space and the entries of the ciphertexts 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 \} } . We also impose a bound 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} for the entries of the fresh fresh 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 \vec{e}} .
Such ciphertexts will be further called 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} -strongly bounded, terminology that is used throughout the paper GSW [1].
The homomorphic operations performed on ciphertexts should correspond to operations "in the clear" that keep the message within the set 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 \}} . To achieve this, we will use only NAND gates to evaluate any circuit.
Notice that 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, C_2} are two 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} -strongly bounded ciphertexts, 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_3 \leftarrow I_N - C_1 C_2 } obtained by evaluating a NAND gate has underlying message 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 \} } , but the coefficients 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_3} 's error vector have magnitude at most 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+1)B} . If one could ensure that the coefficients 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_3} have magnitude at most 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} , 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 flattening, 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 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 = k \cdot l} , 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 l = \lfloor \log_2{q}+1 \rfloor } 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 k} is a positive integer. We will consider 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 \vec{a}, \vec{b} \in \mathbb Z_q^k } , two 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 k} -dimensional vector spaces.
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 N} -dimensional 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 \vec{a'}= (a_{1,0}, \dots, a_{1,l-1}, \dots, a_{k,0},\dots, a_{k,l-1}) } , define
and
The authors also introduce
Some obvious properties of these definitions 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 \langle BitDecomp(\vec{a}), Powersof2(\vec{b}) \rangle = \langle a,b \rangle } ;
- 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 N} -dimensional 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 \vec{a'} } , we have 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 \langle \vec{a'}, Powersof2(\vec{b}) \rangle = \langle BitDecomp^{-1}(\vec{a'}),\vec{b} \rangle = \langle Flatten(\vec{a'}), Powersof2(\vec{b}) \rangle.}
The latter is showing us an interesting feature 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 Flatten } , i.e. it makes the coefficients of a vector "small", without changing its inner product 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 Powersof2(\vec{b})}
We will have to "flatten" ciphertexts, which are matrices. When 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 Flatten } is applied to a 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 \times N } 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} , this will be done 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 Flatten} to each 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 C} . Recall that a step in the decryption process is multiplying the ciphertext 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} with a secret key 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 \vec v} . We will always use 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 \vec{v} = Powersof2(\vec{s}) } , a vector of this special form in order for flattening to preserve the product between 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} 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 \vec{v} } required for decryption.
Now, 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 N \times N} ciphertext 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} , we have
After computing 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_3 \leftarrow I_N - C_1 \cdot C_2 } for the NAND gate, we will immediately flatten it, namely we will set
The basic algorithms of the encryption 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 \lambda } be the security parameter 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} a natural number representing the multiplicative level of homomorphic operations this scheme can achieve. If we know the maximal level 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 } that we want to evaluate, we can choose parameters such that the scheme can handle circuits of depth 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} . 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(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^{\lambda}, 1^L } ): We choose a modulus , depending 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 \lambda, L } , a lattice dimension 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 n=n(\lambda, L)} and an error distribution 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 \chi = \chi(\lambda, L) } such that the scheme achieves at least 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^{\lambda}} security against known attacks. We also choose a 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 m= m(\lambda, L) = O(n \log_{q}) } . We set the paramaters of the scheme 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 params = (n , q, \chi,m) } 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 l = \lfloor \log_{2}q \rfloor +1 } 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 N = (n+1)\cdot l} .
- SecretKeyGen(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 params} ): Sample 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 \vec{t} \leftarrow \mathbb Z_{q}^n } uniformly. 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 sk = \vec{s} \leftarrow (1, -t_1, \dots, -t_n) \in \mathbb \Z_q^{n+1}} . 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 \vec{v} = Powersof2(\vec{s}) } .
- PublicKeyGen(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 params} ): Generate a 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 B = \mathbb Z_q^{m \times n} } and a vector with small entries (noise) 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 \vec{e} \leftarrow \chi^m } . Set 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 \vec{b} = B \cdot \vec{t} + \vec{e}} 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 A } to be 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 (n+1) } column matrix which is obtained by the placing 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 \vec b } on the first column, fllowed by 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 n} columns 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 B } . Set the public 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 pk = A } . We observe 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 A \cdot \vec{s} = \vec{e}.}
- 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 params,pk,\mu } ): 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_q } , sample a uniform 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 R \in \{0,1 \}^{N \times m} } and output the ciphertext
Disclaimer: The decryption algorithm we describe below decrypts correctly only 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 \} } . This can be easily generalised to recover 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 \mu \in \mathbb Z_q} , bit by bit, starting with the least significant one. The interested reader should consult for example the paper of Micciano and Peikert. [4]
- 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 params, sk, C} ): Observe that the first 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} coefficients 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 \vec{v} } 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 1, 2, \dots, 2^{l-1}} . Let us choose, among these coefficients, the unique 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_i = 2^i \in (q/4,q/2] } . 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_i } be 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 C } . We output
We 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 Dec } is only applied to one row of the ciphertext, however extra rows will play a role in the homomorphic operations. 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 properly generated (fresh), then by the properties 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 BitDecomp } described above, we have
The -th coefficient of the above expression is . In the encryption scheme, we set to ensure that the error is -bounded with very high probability.
Homomorphic operations
- Add(): To add ciphertexts , 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 Flatten(C_1+C_2)} .
- Mult(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 } ): To multiply ciphertexts 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 \in \mathbb Z_q^{N \times N} } , 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 Flatten(C_1\cdot C_2) } .
- MultConst(C, 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 \alpha} ): To multiply 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 \mathbb Z_q^{N \times N} } by a known constant 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 \alpha \in \mathbb Z_q} , given in the clear, we set 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_{\alpha} \leftarrow \alpha \cdot I_N } and 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 Flatten(M_{\alpha} \cdot C) } .
One could compute multiplication 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 \alpha } by repeating additions. However, by repeating additions, the error of the resulting ciphertext will be linear 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 \alpha } . On the other hand, if one uses MultConst(), the error term depends only on the 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} and not 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 \alpha } . This turns out to be extremely convenient for when 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 \alpha } is very large (possible applications of this includes homomorphic fast Fourier transforms).
- NAND(): To NAND ciphertexts 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 \in \mathbb Z_q^{N \times N} } that are known to encrypt messages 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 \{0,1 \} } , 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 Flatten(I_N - C_1 \cdot C_2) } .
The NAND homomorphic operation increases the error by a factor of at most 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+1 } .
By iteratively applying the homomorphic operations above, different types of (boundeddepth) circuits may be homomorphically computed while maintaining correctness of decryption. The simplest ones to analyse are Boolean circuits computed over encryptions 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 \{0, 1\}} values. Here the circuit can be converted to use only NAND gates, and the final ciphertext’s error will be 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 (N + 1)^L \cdot B} , where L is the NAND-depth of the circuit, 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 B } is the original bound on the error of 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 \{0, 1\}} .
References
- ↑ 1.0 1.1 1.2 1.3 C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer). https://eprint.iacr.org/2013/340
- ↑ J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094
- ↑ I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryptionover the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020). https://eprint.iacr.org/2018/421
- ↑ D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, pages 700–718, 2012. https://eprint.iacr.org/2011/501
