BFV

Around 2012 Brakerski 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. The various optimisations achieved by the last two authors made the scheme suitable for implementation. One such implementation is available in Microsoft SEAL 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 Failed to parse (MathML with SVG or PNG fallback (recommended 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 } with coefficients modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t} , more precisely ${\mathcal {R}}_{t}=\mathbb {Z} _{t}[x]/(x^{n}+1)$. 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 $x^{n}$ being converted to $-1$. In this way, the result of ring operations on ${\mathcal {R}}_{t}$ is always a polynomial of degree strictly less than $n$.

The homomorphic operations on ciphertext, that will be described later, will carry through encryption to addition and multiplication operations in the plaintext ${\mathcal {R}}_{t}$.

If we wish to encrypt an integer or a rational number, then we need to encode it first into a plaintext polynomial in ${\mathcal {R}}_{t}$ 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 ${\mathcal {R}}_{t}$ 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 ${\mathcal {R}}_{q}$, for some different (much larger than $t$) integer $q$. 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 $2$ polynomials in ${\mathcal {R}}_{q}$ back to a ciphertext with $2$ polynomials encrypting the same message $m\in {\mathcal {R}}_{t}$.

Description of the scheme

Let $\lambda$ be the security parameter. 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 w } be a base (one can think 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 w =2 } for the sake of presentation) 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+1= \lfloor \log_w q \rfloor +1 } denote the number of terms in the decomposition into base Failed to parse (MathML with SVG or PNG fallback (recommended 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} . Polynomials 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 \mathcal R_q } will also be decomposed into base Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w } components coefficient-wise, resulting 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 l+1 } polynomials. 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 S} is a set, we denote Failed to parse (MathML with SVG or PNG fallback (recommended 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 \leftarrow S } we denote the fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a } is sampled uniformly from 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 S} .

The BFV scheme has the algorithms Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle SecretKeyGen, PublicKeyGen, EvaluationKeyGen, Encrypt, Decrypt, Add } 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 Multiply } . We describe these below.

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle SecretKeyGen(\lambda) } : This just samples Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \leftarrow \mathcal R_2 } and outputs the secre key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle sk=s } .

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle PublicKeyGen(sk) } : 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 s =sk } , 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 a \leftarrow \mathcal R_q } uniformly and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e \leftarrow \chi } from an error distribution. Output 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 = ([-(as+e)]_q, 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 EvaluationKeyGen(sk,w) } : 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 \{0,\dots, l \} } , 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 a_i \leftarrow \mathcal R_q } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_i \leftarrow \chi } . 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 evk = ([-(a_is+e_i)+w^is^2]_q,a_i) } .

The autors note that one can think of the evaluation key essentially as a masking of the secret key raised to the power 2 (or, more generally, to some higher power). Unfortunately, it is not possible to argue the uniformity of the evaluation key based on the decision-RLWE assumption. Instead, one can think of it as an encryption of (some power of) the secret key under the secret key itself, and to argue security one needs to make the extra assumption that the encryption scheme is secure even when the adversary has access to all of the evaluation keys which may exist. This point is also explained in the SEAL manual .

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Encrypt(pk,m):} 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 m \in \mathcal R_t } , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_k = (p_0,p_1)} . 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 u \leftarrow \mathcal R_2 } uniformly and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_1, e_2 \leftarrow \chi } . Compute 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 ct = ([ \frac{q}{t} \cdot m + p_0 u+e_1]_q, [p_qu +e_2]_q)} .

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Decrypt(sk,ct) } : 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 s=sk, c_0 = ct[0] } 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_1 = ct[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 \left[ \left\lfloor \frac{t}{q} \cdot [c_0+c_1s]_q \right\rfloor \right]_t } .

The homomorphic operations on ciphertext are as follows

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Add(ct_0, ct_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 (ct_0[0]+ct_1[0], ct_0[1]+ct_1[1]).}

As one can see addition is done in the most natural way, component-wise. Multiplication is a little bit more tricky.

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Multiply(ct_0, ct_1):} 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 c_0 = \left[ \left\lfloor \frac{t}{q} ct_0[0] ct_1[0] \right\rceil \right]_q } , $c_{1}=\left[\left\lfloor {\frac {t}{q}}(ct_{0}[0]ct_{1}[1]+ct_{0}[1]ct_{1}[0])\right\rceil \right]_{q}$ ,

and $c_{2}=\left[\left\lfloor {\frac {t}{q}}(ct_{0}[1]ct_{1}[1])\right\rceil \right]_{q}$.

This first step is quite easy. One can think of $ct_{i}$ as a polynomial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ct_i(x)= ct_i[0] + x \cdot ct_i[1] } with coefficients in ${\mathcal {R}}_{q}$. What we did so far corresponds to computing the product of the polynomials Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ct_1(x) } 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 ct_2(x) } , resulting in a (quadratic 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 x} ) polynomial Failed to parse (MathML with SVG or PNG fallback (recommended 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_0+c_1x+c_2x^2 } . This corresponds to a length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3} array Failed to parse (MathML with SVG or PNG fallback (recommended 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_0,c_1,c_2) } . To keep the size of the ciphertext small, we now apply a reliniarization step. The latter consists in computing

Failed to parse (MathML with SVG or PNG fallback (recommended 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_0' = c_0+ \sum_{i=0}^l evk[i][0] c_2^{(i)} } , Failed to parse (MathML with SVG or PNG fallback (recommended 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_1 + \sum_{i=0}^l evk[i][1] c_2^{(i)} } ,

and return as output the ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (c_0', c_1')} .

We remark that the last step is the only place where one has to use the evaluation key, therefore having to rely on the extra circular security assumption. In practice, if one does not need to perform bootstrapping for obtaining a fully homomorphic encryption scheme, the reliniarization step can be avoided. For example, in the SEAL library, the function Evaluator::multiply(ct_0, ct_1) performs only the first step in the multiplication and outputs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (c_0,c_1, c_2) } , a ciphertext of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3} . Homomorphic operations are defined naturally on ciphertexts of arbitrary size and the decryption algorithm works well without reliniarization. The only problem with this approach is that the ciphertexts will grow with the number of homomorphic multiplications we perform, so one has to know a priori an upper bound on this number in order to choose parameters correctly. The problem of choosing parameters is also a delicate one. Increasing Failed to parse (MathML with SVG or PNG fallback (recommended 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} while keeping Failed to parse (MathML with SVG or PNG fallback (recommended 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 } constant, one obtains more room for homomorphic multiplications (good), but the security of the scheme decreases (bad). This problem can be mitigated by increasing Failed to parse (MathML with SVG or PNG fallback (recommended 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 } as well.

Making the scheme fully homomorphic

What is described above is a somewhat homomorphic encryption scheme. As all existing schemes that are based on LWE or ring-LWE, a small “noise” component is added to the message during encryption (the vectors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_1,e_2 } sampled from the 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 } above). Computing homomorphically on ciphertexts will cause these noise to grow up to the point when it becomes so large (in practice, this happens when a certain norm of the vectors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e_1,e_2} is larger 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 1/2 \cdot \lfloor q/t \rceil } ) that decryption fails. The bootstrapping approach by Gentry can then be used to lower the noise in a ciphertext to a fixed level determined by the complexity of the decryption circuit. Gentry’s idea of bootstrapping is really simple, namely run the decryption of the somewhat homomorphic scheme above in the encrypted domain, i.e. homomorphically. The result of this operation is an encryption of the same message, but with noise of a fixed size. If the decryption circuit can be evaluated in depth D, then the noise after bootstrapping equals the noise one would obtain by evaluating a depth D circuit, which is clearly independent of the starting noise present in the ciphertext. Therefore, if 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 D + 1 } , we can still handle one multiplication after bootstrapping and thus obtain a fully homomorphic scheme. The BFV scheme is designed such that it handles its own decryption circuit, therefore it can be turned into a fully homomorphic scheme via bootstrapping.

Unfortunately this is slow, and requires the encryption parameters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (n,q) } to be large enough to support bootstrapping (not currently implemented in SEAL for the BFV scheme).