Difference between revisions of "BFV"

From certFHE Community KB
Jump to navigation Jump to search
Line 13: Line 13:
 
order to be able to compute additions and multiplications on, for example, integers in encrypted form,
 
order to be able to compute additions and multiplications on, for example, integers in encrypted form,
 
the encoding must be such that addition and multiplication of encoded polynomials in <math> \mathcal R_t </math>  
 
the encoding must be such that addition and multiplication of encoded polynomials in <math> \mathcal R_t </math>  
carry over correctly to the integers when the result is decoded. The library Microsoft SEAL <ref> SEAL </ref> provides a few different
+
carry over correctly to the integers when the result is decoded. The aforementioned library Microsoft SEAL provides a few different standard encoders that users can use at their convenience.
encoders for the user’s convenience
+
 
 +
The ciphertext space in this scheme consists of arrays of polynomials in <math> \mathcal R_q </math>, for some different (much larger than <math> t </math>) integer <math>q</math>. These arrays contain at least two polynomials. Their length grows with each homomorphic multiplication, unless an operation called <b> reliniarization </b> is performed. The latter is a procedure which takes a ciphertext consisting of more than <math> 2 </math> polynomials in <math> \mathcal R_q </math> back to a ciphertext with <math> 2 </math> polynomials encrypting the same message <math> m \in \mathcal R_t </math>.
 +
 
 +
== Description of the scheme ==
 +
 
 +
Let <math> \lambda </math> be the security parameter. Let <math> w </math> be a base (one can think of <math> w =2 </math> for the sake of presentation) and let <math>l+1= \lfloor \log_w q \rfloor +1 </math> denote the number of terms in the decomposition into base <math> q</math>. Polynomials in <math> \mathcal R_q </math> will also be decomposed into base <math> w </math> components coefficient-wise, resulting in <math> l+1 </math> polynomials. When <math>S</math> is a set, we denote <math>a \leftarrow S </math> we denote the fact that <math> a </math> is sampled uniformly from the set <math> S</math>.
 +
 
 +
The BFV scheme has the algorithms <math>SecretKeyGen, PublicKeyGen, EvaluationKeyGen, Encrypt, Decrypt, Add </math> and <math>Multiply </math>. We describe these below.
 +
 
 +
* <math> SecretKeyGen(\lambda) </math>: This just samples <math> s \leftarrow \mathcal  R_2 </math> and outputs the secre key <math> sk=s </math>.
 +
 
 +
* <math> PublicKeyGen(sk) </math>: Set <math> s =sk </math>, sample <math> a \leftarrow \mathcal R_q </math> uniformly and <math>e \leftarrow \chi </math> from an error distribution. Output the public key <math> pk = ([-(as+e)]_q, a) </math>.
 +
 
 +
* <math> EvaluationKeyGen(sk,w) </math>: for <math>i \in \{0,\dots, l \} </math>, sample <math>a_i \leftarrow \mathcal R_q </math> and <math> e_i \leftarrow \chi  </math>. Output
 +
<center> <math> evk = ([-(a_is+e_i)+w^is^2]_q,a_i) </math>. </center>
 +
 
 +
* <math>Encrypt(pk,m):</math> For <math> m \in \mathcal R_t </math>, let <math> p_k = (p_0,p_1)</math>. Sample <math> u \leftarrow \mathcal R_2 </math> uniformly and <math>e_1, e_2 \leftarrow \chi </math>. Compute and output
 +
<center> <math>  ct = ([ \frac{q}{t} \cdot m + p_0 u+e_1]_q, [p_qu +e_2]_q)</math> .</center>

Revision as of 09:12, 26 May 2020

Around 2012 Brakerski [1] proposed a new efficient FHE scheme whose security is based on the LWE problem. Later on, this scheme was ported to the ring-LWE setting by Fan and Vercauteren. [2] The various optimisations achieved by the last two authors made the scheme suitable for implementation. One such implementation is available in Microsoft SEAL [3] is an actively maintained library which makes homomorphic encryption available in an easy-to-use form both to experts and to non-experts.

Overview of the BFV scheme

In BFV the plaintext space consists of polynomials of degree less than with coefficients modulo , more precisely . This is a ring, where addition is just the usual addition of polynomials. Multiplication is also quite intuitive, in the sense that multiplication of two elements is just multiplication of the underlying polynomials with being converted to . In this way, the result of ring operations on is always a polynomial of degree strictly less than .

The homomorphic operations on ciphertext, that will be described later, will carry through encryption to addition and multiplication operations in the plaintext .

If we wish to encrypt an integer or a rational number, then we need to encode it first into a plaintext polynomial in and the result can be encrypted only after that. We mention that distinction should be made between encoding and encrypting data. The first one is a public operation, i.e. anybody can reverse it by decoding , whereas the latter can be reverse just by someone who knows the (secret) encryption key. In order to be able to compute additions and multiplications on, for example, integers in encrypted form, the encoding must be such that addition and multiplication of encoded polynomials in carry over correctly to the integers when the result is decoded. The aforementioned library Microsoft SEAL provides a few different standard encoders that users can use at their convenience.

The ciphertext space in this scheme consists of arrays of polynomials in , for some different (much larger than ) integer . These arrays contain at least two polynomials. Their length grows with each homomorphic multiplication, unless an operation called reliniarization is performed. The latter is a procedure which takes a ciphertext consisting of more than polynomials in back to a ciphertext with polynomials encrypting the same message .

Description of the scheme

Let be the security parameter. Let be a base (one can think of for the sake of presentation) and let denote the number of terms in the decomposition into base . Polynomials in will also be decomposed into base components coefficient-wise, resulting in polynomials. When is a set, we denote we denote the fact that is sampled uniformly from the set .

The BFV scheme has the algorithms and . We describe these below.

  • : This just samples and outputs the secre key .
  • : Set , sample uniformly and from an error distribution. Output the public key .
  • : for , sample and . Output
.
  • For , let . Sample uniformly and . Compute and output
.
  1. Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. CRYPTO 2012. http://eprint.iacr.org/2012/078.pdf
  2. J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144, Mar. 2012. https://eprint.iacr.org/2012/144.pdf
  3. Microsoft Research. Microsoft SEAL (release 3.5). 2020. https://github.com/Microsoft/SEAL