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

From certFHE Community KB
Jump to navigation Jump to search
Line 15: Line 15:
  
 
<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>
 +
 +
 +
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
 +
 +
<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>
 +
 +
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.
 +
 +
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.
 +
 +
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>.
  
 
== The Bootstrappable Scheme BTS ==  
 
== The Bootstrappable Scheme BTS ==  

Revision as of 14:47, 31 March 2020

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.

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


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 .

The Bootstrappable Scheme BTS

Bootstrapping BTS into a Fully Homomorphic encryption scheme

Efficiency of the Scheme