Difference between revisions of "Efficient FHE from (Standard) LWE"

From certFHE Community KB
Jump to navigation Jump to search
 
(27 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
As anounced in the title, Brakerski and Vaikuntanathan (TODO: cite) introduced a fully homomorphic encryption scheme which is based only on the [[LWE]] assumption. They show that the security of the scheme can be reduced to the worst-case hardness of [[short vector problems]] on arbitrary latices.
+
As anounced in the title, Brakerski and Vaikuntanathan <ref> Z. Brakerski, F. Vaikuntanathan, Efficient Fully Homomorphic Encryption from (Standard) LWE, SIAM J. Comput., 43(2), 831–871.</ref>
 +
introduced a fully homomorphic encryption scheme which is based only on the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] assumption. The authors show that the security of the scheme can be reduced to the worst-case hardness of [https://en.wikipedia.org/wiki/Lattice_problem short vector problem] on arbitrary latices.
  
They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in [[FHE over the integers]] and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the sparse subset-sum problem.
+
They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in [[FHE over the Integers]] and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the [https://eprint.iacr.org/2011/567.pdf sparse subset-sum problem].
  
 
This scheme has particularly short ciphertexts and for this reasons the authors managed to use it for constructing an efficient single-server private information retrieval (PIR) protocol.
 
This scheme has particularly short ciphertexts and for this reasons the authors managed to use it for constructing an efficient single-server private information retrieval (PIR) protocol.
Line 12: Line 13:
 
We are not going to elaborate on the appropriate choice of the size for the parameters, but we invite the curious reader to look at the paper. However, for brevity, we mention that the dimension <math>  n</math> is polynomial in the security parameter <math>  \lambda </math>, <math>  m \geq n \log(q) + 2 \lambda </math> is a polynomial in <math>  n </math>, the modulus is an odd number <math>  q \in [ 2^{n^{\epsilon}}, 2 \cdot 2^{n^{\epsilon}}) </math> is sub-exponential in <math> n </math>, i.e. <math>  \epsilon </math> is a positive constant which is strictly smaller than <math> 1 </math>.  The noise distribution <math> \chi </math> produces small samples, of magnitude at most <math> n </math> in <math>  \mathbb Z_{\mathfrak q} </math>. The depth bound <math> L </math> is approximately of the size <math> \epsilon \cdot \log(n) </math>.
 
We are not going to elaborate on the appropriate choice of the size for the parameters, but we invite the curious reader to look at the paper. However, for brevity, we mention that the dimension <math>  n</math> is polynomial in the security parameter <math>  \lambda </math>, <math>  m \geq n \log(q) + 2 \lambda </math> is a polynomial in <math>  n </math>, the modulus is an odd number <math>  q \in [ 2^{n^{\epsilon}}, 2 \cdot 2^{n^{\epsilon}}) </math> is sub-exponential in <math> n </math>, i.e. <math>  \epsilon </math> is a positive constant which is strictly smaller than <math> 1 </math>.  The noise distribution <math> \chi </math> produces small samples, of magnitude at most <math> n </math> in <math>  \mathbb Z_{\mathfrak q} </math>. The depth bound <math> L </math> is approximately of the size <math> \epsilon \cdot \log(n) </math>.
  
SH.Keygen: sample <math> L+1</math> vectors <math> s_0, \dots, s_{L}</math> uniformly from <math> \mathbb Z_{q}^n</math> and compute, for all <math> l \in [L]</math>, <math>0 \leq I \leq j \leq n </math> and <math> \tau \in \{0, \dots, \lfloor \log{q} \rfloor \}</math>, the value
+
<b>SH.Keygen</b>: sample <math> L+1</math> vectors <math> s_0, \dots, s_{L}</math> uniformly from <math> \mathbb Z_{q}^n</math> and compute, for all <math> l \in [L]</math>, <math>0 \leq I \leq j \leq n </math> and <math> \tau \in \{0, \dots, \lfloor \log{q} \rfloor \}</math>, the value
  
<math> \psi_{l,i,j, \tau} := \left( a_{l,i,j,\tau}, b_{l,i,j,\tau} := \langle a_{l,i,j,\tau}, s_l \rangle  + 2 \cdot e_{l,I,j,\tau} + 2^{\tau} \cdot s_{l-1} \cdot s_{l-1}[j] \right)  \in \mathbb Z_q^n \times \mathbb Z_{q}</math>
+
<math> \psi_{l,i,j, \tau} := \left( a_{l,i,j,\tau}, b_{l,i,j,\tau} := \langle a_{l,i,j,\tau}, s_l \rangle  + 2 \cdot e_{l,i,j,\tau} + 2^{\tau} \cdot s_{l-1} \cdot s_{l-1}[j] \right)  \in \mathbb Z_q^n \times \mathbb Z_{q}</math>
  
== The Bootstrappable Scheme BTS ==
+
where <math> a_{l,i,j,\tau} </math> and <math> e_{l,i,j,\tau}</math> are chosen uniformly at from <math> \mathbb Z_{q}^n </math> and from the distribution <math> \chi </math>, respectively.
  
== Bootstrapping BTS into a Fully Homomorphic encryption scheme ==
+
Let <math>\Psi := \{ \psi_{l,i,j, \tau} \}_{l,i,j,\tau} </math> be the set of all these values. Notice that these seem like encryptions of <math> 2^{\tau} \cdot s_{l-1}[i] \cdot s_{l-1}[j]  </math> (mod <math>q </math>), except these “ciphertexts” can’t be decrypted since the underlying message <math> 2^{\tau} \cdot s_{l-1}[i] \cdot s_{l-1}[j]  </math> is not a single bit value.
  
'''Efficiency of the Scheme'''
+
The key generation might seem rather strange now, but publishing these “encryptions” of the quadratic terms in the secret keys <math>s_l </math> is very important and we will explain this when we describe homomorphic multiplication.
 +
 
 +
The key-generation algorithm proceeds to choose a uniformly random matrix <math>A </math> from <math> \mathbb Z_{q}^{m \times n} </math> and an <math> m</math>-dimensional vector <math> e </math> from the distribution <math> \chi^m </math>. Set <math> b := A s_0 + 2 e</math>.
 +
 
 +
The algorithm <b> outputs </b> the secret key <math> sk = s_L </math>, the evaluation key <math> evk := \Psi</math> and the public key <math> pk := (A,b) </math>.
 +
 
 +
<b> Encryption</b>(<math> \mu</math>): We recall that the public key is <math>pk = (A,b) </math>. To encrypt a message <math> \mu \in GF(2) </math>, we sample a random vector <math> r \in \{0,1 \}^m </math> and set:
 +
 
 +
<math> v:= A^{T} \cdot r </math> and <math> w := b^{T} \cdot r + \mu </math>.
 +
 
 +
The <b>output</b> ciphertext contains the pair <math>(v,w) \in \mathbb Z_q^{n} \times \mathbb Z_{q} </math>, together with a "level tag" which is used during homomorphic evaluation and indicates the multiplicative depth of the ciphertexts. Fresh ciphertexts, i.e. ciphertexts that are obtained straight from the encryption of messages and that did not suffer any homomorphic evaluation, will have this tag level zero. The encryption algorithm <b>outputs</b> <math> c:= ((v,w),0) </math>.
 +
 
 +
<b>Homomorphic evaluation</b>: We now present the algorithm <math>SH.Eval_{evk}(f,c_1, \dots, c_t) </math>, where <math> f: \{0,1 \}^{t} \to \{0,1 \} </math>. We require that <math>f </math> is represented by a binary arithmetic circuit with '<math>+</math>' gates of arbitrary fan-in and '<math>\times </math>' gates with fan-in equal to <math> 2</math>. Furthermore, it is required that every circuit is layered, namely that it is composed of layers containing having either all '<math> +</math>' gates or all '<math> \times </math>' gates. Every binary circuit can be represented in this way. It is also required that the multiplicative depth of the circuit <math>f </math> is exactly <math>L</math>.
 +
 
 +
The algorithm homomorphically evaluates the circuit <math>f </math> gate by gate. We present how to perform homomorphic addition for arbitrarily many ciphertexts and homomorphic multiplication for two ciphertexts. Combining the two, any circuit <math>f </math> can be evaluated.
 +
 
 +
Homomorphic evaluation will generate ciphertexts of the form <math> c = ((v,w),l) </math>, where the tag <math> l </math> indicates the multiplicative level at which the ciphertext has been generated. Here the fact that <math> f</math> is layered plays an important role, as it makes sure that all inputs to a gate have the same tag. Throughout the evaluation, it is important that the output of each gate evaluation <math> c = ((v,w),l) </math> is such that
 +
 
 +
<math> w - \langle v, s_l \rangle = \mu + 2 \cdot e </math>,
 +
 
 +
where <math> \mu</math> is the output of the gate in plaintext, i.e. the correct output, and <math>e </math> is a noise term that depends on the ciphertexts that went into the gate. We always have <math> l \leq L</math> due to the bound on the multiplicative depth and the <b>output</b> of the homomorphic evaluation of the entire circuit must have <math> l = L </math>.
 +
 
 +
<b> Addition gates: </b> Let <math>c_, \dots, c_t </math>, where <math>c_i = ((v_i,w_i),l) </math> be ciphertexts. The homomorphic evaluation of their sum is performed by <b>outputting</b>
 +
 
 +
<math>c_{add} = ((v_{add}, w_{add}), l) = \left( \left( \sum_{i} v_i, \sum_{i} w_i\right) , l \right) </math>
 +
 
 +
One can see that
 +
 
 +
<math>w_{add} - \langle v_{add}, s_l \rangle = \sum_i \left( w_i - \langle v_i,s_l\rangle \right) \sum_{i} \mu_i + 2 \sum_i e_i.</math>
 +
 
 +
Here <math>\mu_i </math> is the plaintext corresponding to <math> c_i</math>, so the homomorphic evaluation outputs a ciphertexts that corresponds to the sum of the inputs with a noise term that is equal to the sum of the noises of <math>c_i </math>'s.
 +
 
 +
<b> Multiplication of two ciphertexts </b>. Let <math>c = ((v,w),l),c' = ((v',w'),l') </math> be two ciphertexts of level <math> l</math>. The <b>output</b> of the multiplication will be a ciphertext of the form <math>c_{mult} = ((v_{mult}, w_{mult}), l+1) </math>, since the level of multiplication is increased by <math> 1</math>.
 +
 
 +
Let us first consider the <math>n </math>-variable symbolic polynomial in the vector <math> x</math>:
 +
 
 +
<math>\phi(x) = \phi_{(v,w),(v',w')}(x) := (w- \langle v,x \rangle) \cdot (w' - \langle v',x \rangle) </math>.
 +
 
 +
Notice that when evaluated at the secret key vector <math> x=s_l </math>, the above expression should give the plaintext <math> \mu \cdot \mu' </math> (underlying message of the product of the ciphertexts) plus some additional noise term.
 +
 
 +
If we symbolically open the parenthesis of the (quadratic in <math>x </math>) polynomial above, we get something of the form
 +
 
 +
<math>\phi(x) = \sum_{0 \leq i \leq j \leq n} h_{i,j} \cdot x[i] \cdot x[j] </math>,
 +
 
 +
where <math> h_{i_j} \in \mathbb Z_q</math> are known coefficients. For managing the growth of the noise term, it is essential to express <math>\phi </math> as a polynomial with small coefficients. This can be achieved by considering the binary representations <math> h_{i,j} = \sum_{\tau =0}^{\lfloor \log q \rfloor} h_{i,j,\tau} \cdot 2^{\tau} </math>, where <math> h_{i,j,\tau} \in \{0,1 \}</math>.
 +
 
 +
Then we have <math> \phi(x) = \sum h_{i,j,\tau} \cdot \left( 2^{\tau} \cdot x[i] \cdot  x[j] \right) </math>, where the sum is over <math> 0 \leq i \leq j \leq n </math> and <math> 0 \leq \tau \leq \lfloor \log q \rfloor </math>.
 +
 
 +
Now recall that the evaluation key <math> evk = \Psi </math> produced by <math>SH.Keygen </math> contains elements of the form <math> \psi_{l,i,j,\tau} =(a_{l,i,j,\tau}, b_{l,i,j,\tau}) </math> such that <math>2^{\tau} s_l[i] s_l[j] \approx b_{l+1,i,j,\tau} - \langle a_{l+1,i,j,\tau}, s_{l+1} \rangle </math>. The <b> homomorphic multiplication </b> algorithm will thus set
 +
 
 +
<math> v_{mult} := \sum h_{i,j,\tau} \cdot a_{l+1,i,j,\tau} </math> and <math> w_{mult} = \sum h_{i,j,\tau} \cdot b_{l+1,i,j,\tau} </math> and the final <b> output </b> will be <math> c_{mult} := ((v_{mult}, w_{mult}),l+1) </math>.
 +
 
 +
By computing <math> w_{mult} - \langle v_{mult}, s_{l+1} \rangle </math> one will see that indeed this will be equal to the plaintext output <math> \mu \mu' </math> plus some noise term that depends on the input ciphertexts <math>c, c' </math> and also on the evaluation key <math> \Psi</math>.
 +
 
 +
The advantages of using this re-liniarisation technique for multiplications are detailed in Section 1.1 of [https://eprint.iacr.org/2011/344.pdf [1]].
 +
 
 +
<b> Decryption </b>: In this scheme, we only want to decrypt ciphertexts of the form <math>c = ((v,w),L) </math>, which are the ones that are <math>SH.Eval(\dots)</math> outputs. The algorithm <math>SH.Dec_{s_L}(c)</math> computes and <b> outputs </b>:
 +
 
 +
(<math> (w - \langle v, s_L \rangle)</math> mod <math> q</math>) mod 2.
 +
 
 +
== The Bootstrappable Scheme BTS ==
 +
 
 +
Although the scheme <math> SH </math> presented in the previous section is not bootstrappable, the authors introduce a new "dimension-modulus reduction" technique which allows them to transform <math> SH </math> into a scheme which has much shorter ciphertexts and lower decryption complexity.
 +
 
 +
The new scheme inherits the parameters <math> (n,m,q, \chi, L) </math> from <math> SH </math> and has additional parameters <math> (k,p, \hat{\chi}) </math>, to which the authors refer as "small parameters".
 +
 
 +
The parameters <math>n,q \in \mathbb N </math> are the "long" dimension and the "long" modulus. while <math>k,p </math> are the "short" dimension and modulus, respectively. <math>\chi, \hat{\chi} </math> are the long and short noise distributions taken over <math>\mathbb Z_{q} </math> and <math> \mathbb Z_p </math>. The parameter <math> m</math> is used just for key generation and the parameter <math>L </math> is an upper bound on the multiplicative depth of the evaluated function.
 +
 
 +
For details concerning this new scheme <math>\mathrm{BTS}</math> as well as the proof that this is boostrappable, hence can (at least in theory) evaluate any circuit, we refer to the article listed below.
 +
 
 +
== References ==

Latest revision as of 13:15, 4 January 2021

As anounced in the title, Brakerski and Vaikuntanathan [1] introduced a fully homomorphic encryption scheme which is based only on the LWE assumption. The authors show that the security of the scheme can be reduced to the worst-case hardness of short vector problem on arbitrary latices.

They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in FHE over the Integers and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the sparse subset-sum problem.

This scheme has particularly short ciphertexts and for this reasons the authors managed to use it for constructing an efficient single-server private information retrieval (PIR) protocol.

A Somewhat Homomorphic encryption Scheme SH

Let us start by presenting a somewhat homomorphic encryption scheme. Denote by the security parameter. The scheme is parameterized by a dimension , a positive integer , an odd modulus (which does not have to be prime) and a noise distribution over . An additional parameter of the scheme is an upper bound on the maximal multiplicative depth that the scheme can homomorphically evaluate.

We are not going to elaborate on the appropriate choice of the size for the parameters, but we invite the curious reader to look at the paper. However, for brevity, we mention that the dimension is polynomial in the security parameter , is a polynomial in , the modulus is an odd number is sub-exponential in , i.e. is a positive constant which is strictly smaller than . The noise distribution produces small samples, of magnitude at most in . The depth bound is approximately of the size .

SH.Keygen: sample vectors uniformly from and compute, for all , and , the value

where and are chosen uniformly at from and from the distribution , respectively.

Let be the set of all these values. Notice that these seem like encryptions of (mod ), except these “ciphertexts” can’t be decrypted since the underlying message is not a single bit value.

The key generation might seem rather strange now, but publishing these “encryptions” of the quadratic terms in the secret keys is very important and we will explain this when we describe homomorphic multiplication.

The key-generation algorithm proceeds to choose a uniformly random matrix from and an -dimensional vector from the distribution . Set .

The algorithm outputs the secret key , the evaluation key and the public key .

Encryption(): We recall that the public key is . To encrypt a message , we sample a random vector and set:

and .

The output ciphertext contains the pair , together with a "level tag" which is used during homomorphic evaluation and indicates the multiplicative depth of the ciphertexts. Fresh ciphertexts, i.e. ciphertexts that are obtained straight from the encryption of messages and that did not suffer any homomorphic evaluation, will have this tag level zero. The encryption algorithm outputs .

Homomorphic evaluation: We now present the algorithm , where . We require that is represented by a binary arithmetic circuit with '' gates of arbitrary fan-in and '' gates with fan-in equal to . Furthermore, it is required that every circuit is layered, namely that it is composed of layers containing having either all '' gates or all '' gates. Every binary circuit can be represented in this way. It is also required that the multiplicative depth of the circuit is exactly .

The algorithm homomorphically evaluates the circuit gate by gate. We present how to perform homomorphic addition for arbitrarily many ciphertexts and homomorphic multiplication for two ciphertexts. Combining the two, any circuit can be evaluated.

Homomorphic evaluation will generate ciphertexts of the form , where the tag indicates the multiplicative level at which the ciphertext has been generated. Here the fact that is layered plays an important role, as it makes sure that all inputs to a gate have the same tag. Throughout the evaluation, it is important that the output of each gate evaluation is such that

,

where is the output of the gate in plaintext, i.e. the correct output, and is a noise term that depends on the ciphertexts that went into the gate. We always have due to the bound on the multiplicative depth and the output of the homomorphic evaluation of the entire circuit must have .

Addition gates: Let , where be ciphertexts. The homomorphic evaluation of their sum is performed by outputting

One can see that

Here is the plaintext corresponding to , so the homomorphic evaluation outputs a ciphertexts that corresponds to the sum of the inputs with a noise term that is equal to the sum of the noises of 's.

Multiplication of two ciphertexts . Let be two ciphertexts of level . The output of the multiplication will be a ciphertext of the form , since the level of multiplication is increased by .

Let us first consider the -variable symbolic polynomial in the vector :

.

Notice that when evaluated at the secret key vector , the above expression should give the plaintext (underlying message of the product of the ciphertexts) plus some additional noise term.

If we symbolically open the parenthesis of the (quadratic in ) polynomial above, we get something of the form

,

where are known coefficients. For managing the growth of the noise term, it is essential to express as a polynomial with small coefficients. This can be achieved by considering the binary representations , where .

Then we have , where the sum is over and .

Now recall that the evaluation key produced by contains elements of the form such that . The homomorphic multiplication algorithm will thus set

and and the final output will be .

By computing one will see that indeed this will be equal to the plaintext output plus some noise term that depends on the input ciphertexts and also on the evaluation key .

The advantages of using this re-liniarisation technique for multiplications are detailed in Section 1.1 of [1].

Decryption : In this scheme, we only want to decrypt ciphertexts of the form , which are the ones that are outputs. The algorithm computes and outputs :

( mod ) mod 2.

The Bootstrappable Scheme BTS

Although the scheme presented in the previous section is not bootstrappable, the authors introduce a new "dimension-modulus reduction" technique which allows them to transform into a scheme which has much shorter ciphertexts and lower decryption complexity.

The new scheme inherits the parameters from and has additional parameters , to which the authors refer as "small parameters".

The parameters are the "long" dimension and the "long" modulus. while are the "short" dimension and modulus, respectively. are the long and short noise distributions taken over and . The parameter is used just for key generation and the parameter is an upper bound on the multiplicative depth of the evaluated function.

For details concerning this new scheme as well as the proof that this is boostrappable, hence can (at least in theory) evaluate any circuit, we refer to the article listed below.

References

  1. Z. Brakerski, F. Vaikuntanathan, Efficient Fully Homomorphic Encryption from (Standard) LWE, SIAM J. Comput., 43(2), 831–871.