Introduction to the BFV encryption scheme

In the last blog, we introduced the concept of Fully Homomorphic Encryption (FHE) and its capabilities. In this article, we will start a new blog series to dive deeper into the mathematical details of FHE and some of its popular encryption schemes. In particular, we will introduce the levelled Brakerski/Fan-Vercauteren scheme (BFV) [Bra12, FV12], a Ring-Learning with Errors (RLWE)-based cryptosystem. The readers will also learn about the fundamental operations commonly employed in FHE. In the subsequent posts, we will visit the levelled Brakerski-Gentry-Vaikuntanathan (BGV) scheme [BGV14] and the Cheon-Kim-Kim-Song (CKKS) scheme [CKKS17]. Note: this article is also available as a PDF Document for those who prefer.

This is the first article of a blog series about Fully Homomorphic Encryption (FHE) and its applications. In this article, we introduce the levelled Brakerski/Fan-Vercauteren [Bra12, FV12] scheme, a Ring-Learning with Errors (RLWE)-based cryptosystem.

The Fan-Vercauteren (FV) scheme, (also known as the Brakerski-Fan-Vercauteren (BFV) scheme) is considered as one of the second generation of FHE schemes that is constructed based on the Ring-Learning with Errors (RLWE) problem [LPR13]. BFV is instantiated over two rings: 1) the plaintext ring which includes encodings of unencrypted or intelligible messages and 2) the ciphertext ring which includes encrypted messages. Similar to any other FHE scheme, BFV allows an untrusted party to induce meaningful computation over encrypted data without access to the decryption key. This is possible due to the homomorphism property which offers a map (or function) between the plaintext and ciphertext spaces that preserves the operations in these two spaces.

This can be illustrated concretely as follows. Let $f$ be a function that maps $P → C$, where $P$ and $C$ are mathematical structures (sets for e.g.) with a defined binary operation $\diamond$, if for every $x$ and $y$ in $P$ Equation (\ref{eq:homomorphism}) holds, then f is a homomorphic map that preserves $\diamond$ between $P$ and $C$. \begin{equation}\label{eq:homomorphism} f(x \diamond y) = f(x) \diamond f(y) \end{equation}

As a simple numerical example, consider the homomorphism $f(r) = 2r$ that maps $\Z$ to $\Z$, where $\Z$ is the set of all integers. Let $x = -1$, $y = 4$ and $\diamond = +$. Let's check if Equation (\ref{eq:homomorphism}) holds for $f$. \begin{align} f(x+y) &\stackrel{?}{=}f(x)+f(y)\\ f(-1+4) &\stackrel{?}{=}f(-1)+f(4) \nonumber\\ f(3) &\stackrel{?}{=}-2+8 \nonumber\\ 6 &=6 \nonumber \end{align} To reflect the above on FHE and for the sake of clarification, one can think of $f$ as the encryption function that maps plaintext messages in $\P$ to ciphertext messages in $\C$. The left side of Equation \eqref{eq:homomorphism} corresponds to the encrypted result one would like to have after manipulating the encrypted messages on the right side (homomorphic evaluation). Note that the results of manipulating ciphertext messages in FHE are also encrypted.

There are a few worth noting points here that need to be emphasized:

• The aforementioned analogy is only illustrative, FHE includes more complex mappings and spaces as we shall see later.
• $f(r)$ preserves addition only. Applying Equation \eqref{eq:homomorphism} with $(\diamond = \times)$ does not work.
• For the encryption scheme to be really FHE (i.e., able to compute arbitrary functions on data), it must preserve at least two operations: addition and multiplication. If the scheme supports only addition, it is known as additive homomorphic scheme, whereas if it supports only multiplication, it is known as multiplicative homomorphic scheme.

Now we have a basic idea of the notion of homomorphism, we can define the basic primitives of BFV [ACC+18]. BFV includes the following primitives:

• $\textsf{ParamGen}(\lambda) \to \textsf{Params}$:
  Parameter generator $(\textsf{ParamGen})$ takes as input the security parameter $\lambda$, which is a number used to define the security level of BFV, and returns a set of encryption parameters used in BFV. Possible values of $\lambda$ with increasing security level are $80, 128$ and $256$, with $80$ being deprecated according to the FHE standardization consortium [ACC+18]. One can view $\lambda$ as the computational cost of successful attacks on the scheme. In order for these attacks to succeed with probability $1$, they would require $2^{\lambda}$ basic computational operations.
• $\textsf{KeyGen}(\textsf{Params}) \to {\textsf{SK}, \textsf{PK}, \textsf{EK}}$:
  Key generation $(\textsf{KeyGen})$ takes as input the encryption parameters and returns a set of keys: 1) the secret key $(\textsf{SK})$ which is mainly used for decryption (and also be used in symmetric encryption, i.e., $\textsf{SK}$ is used in encryption and decryption), 2) the public key $(\textsf{PK})$ which is used for encryption and 3) the evaluation key $(\textsf{EK})$ which is used to evaluate homomorphic operations on ciphertexts as we shall see later. While $\textsf{SK}$ should be kept private by the user (sensitive data owner), $\textsf{PK}$ and $\textsf{EK}$ can be shared publicly without affecting the security of the scheme.
• $\textsf{Encrypt}(\textsf{PK}, \textsf{M}) \to \textsf{C}$:
  Encrypt takes as input $\textsf{PK}$ and a plaintext message $\textsf{M}$ in the plaintext space $\P$, and returns a valid ciphertext $\textsf{C}$ from the ciphertext space $\C$.
• $\textsf{Decrypt}(\textsf{SK}, \textsf{C}) \to \textsf{M}$:
  Decrypt takes as input $\textsf{SK}$ and a valid ciphertext $\textsf{C}$ in $\C$, which encrypts message $\textsf{M}$ in $\P$, and returns $\textsf{M}$.
• $\textsf{EvalAdd}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{C}^{(2)}) \to \textsf{C}^{(3)}$:
  $\textsf{EvalAdd}$ takes as input the encryption parameters $\textsf{Params}$, $\textsf{EK}$, two valid ciphertexts $\textsf{C}^{(1)}$ encrypting $\textsf{M}^{(1)}$ and $\textsf{C}^{(2)}$ encrypting $\textsf{M}^{(2)}$, and returns a valid ciphertext $\textsf{C}^{(3)}$ encrypting $(\textsf{M}^{(1)}+\textsf{M}^{(2)})$.
• $\textsf{EvalAddConst}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{M}^{(2)}) \to \textsf{C}^{(3)}$:
  $\textsf{EvalAddConst}$ is similar to $\textsf{EvalAdd}$ but with either of the operands is a plaintext. For the input $\textsf{C}^{(1)}$ encrypting $\textsf{M}^{(1)}$, it outputs a ciphertext $\textsf{C}^{(3)}$ encrypting $(\textsf{M}^{(1)}+\textsf{M}^{(2)})$.
• $\textsf{EvalMult}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{C}^{(2)}) \to \textsf{C}^{(3)}$:
  $\textsf{EvalMult}$ takes as input the encryption parameters $\textsf{Params}$, $\textsf{EK}$, two valid ciphertexts $\textsf{C}^{(1)}$ encrypting $\textsf{M}^{(1)}$ and $\textsf{C}^{(2)}$ encrypting $\textsf{M}^{(2)}$, and returns a valid ciphertext $\textsf{C}^{(3)}$ encrypting $(\textsf{M}^{(1)} \times \textsf{M}^{(2)})$.
• $\textsf{EvalMultConst}(\textsf{Params}, \textsf{EK}, \textsf{C}^{(1)}, \textsf{M}^{(2)}) \to \textsf{C}^{(3)}$:
  $\textsf{EvalMultConst}$ is similar to $\textsf{EvalMult}$ but with either of the operands is a plaintext. For the input $\textsf{C}^{(1)}$ encrypting $\textsf{M}^{(1)}$, it outputs ciphertext $\textsf{C}^{(3)}$ encrypting $(\textsf{M}^{(1)} \times \textsf{M}^{(2)})$.
• $\textsf{Relinearize}(\textsf{Params}, \textsf{EK}, \textsf{C}') \to \textsf{C}$:
  $\textsf{Relinearize}$ takes as input the encryption parameters $\textsf{Params}$, $\textsf{EK}$ and an ill-shaped (more on this later) $\textsf{C}'$ encrypting $\textsf{M}$, and returns a well-shaped compact $\textsf{C}$ encrypting $\textsf{M}$.

Later on in this note, we provide a more concrete description of these primitives alongside correctness analyses.

The plaintext and ciphertext spaces in BFV are defined over two distinct polynomial rings denoted by $\P = R_t = \Z_t[x]/(x^n+1)$ and $\C = R_q \times R_q$, where $R_q = \Z_q[x]/(x^n+1)$, $n \in \Z$ is the ring dimension and $t \in \Z$ and $q \in \Z$ are the plaintext and ciphertext coefficients, respectively. The notation $\Z_a[x]/(x^n+1)$ can be viewed as the set of polynomials with integer coefficients modulo both $a$ and $(x^n+1)$, i.e., with coefficients in $\{\left \lceil{-\frac{a}{2}}\right \rceil, \ldots , \left \lfloor{\frac{a-1}{2}}\right \rfloor\}$ and of degree less than $n$. For efficiency purposes, $n$ is usually set as a power of 2 integer. Note that in practice, $q$ is usually much greater than $t$, hence, the cardinality of $\C$ is much larger than that of $\P$, which also means a plaintext message $\textsf{M}$ in $\P$ can be mapped to multiple valid ciphertexts in $\C$. The order (or number of distinct elements) in $R_t$ and $R_q$ is $t^n$ and $q^n$, respectively. Table 1 shows examples of valid plaintext messages for the parameters $n = 4$ and $t = 5$.

Table 1: Examples of valid plaintext messages for $(n,t) = (4, 5)$

\begin{array} {rr}\hline \textsf{M}^{(0)} & 1 + 2x + 1x^2 -1x^3\\ \hline \textsf{M}^{(1)} & -1 - 2x -1 x^2 +2x^3\\ \hline \textsf{M}^{(2)} & 1 + 1x + 1x^2 +1x^3\\ \hline \end{array}

We describe here the main parameters used in BFV. Besides the plaintext and ciphertext space parameters $(t,q,n)$ introduced in Section 3, BFV uses a number of random distributions defined as follows:

• $R_2$: is the key distribution used to sample polynomials with integer coefficients in $\{-1,0,1\}$.
• $\mathcal{X}$: is the error distribution defined as a discrete Gaussian distribution with parameters $\mu$ and $\sigma$ over $R$ bounded by some integer $\beta$. According to the current version of the homomorphic encryption standard [ACC+18], $(\mu, \sigma, \beta)$ are set as $(0, \frac{8}{\sqrt{2\pi}}\approx 3.2, \lfloor 6\cdot \sigma \rceil = 19)$.
• $R_q$: is a uniform random distribution over $R_q$.

We note that the choice of the parameters $(t, q, n)$ is application-specific and is also driven by the desired security level. For a set of contemporary accepted parameters, we refer the reader to Tables 1 and 2 in the homomorphic encryption standard [ACC+18]. As a rule of thumb, one should opt for minimizing these parameters so long as the application of interest can still be implemented in FHE.

Recall that the plaintext space is the polynomial ring $R_t$. This means that messages need to be converted to polynomials in $R_t$. This conversion is referred to by encoding. The literature includes plenty of encoding schemes proposed for FHE. We review here two simple schemes for integer datatypes.

Let $m$ denote an integer message we would like to encrypt in FHE. The first encoding scheme (let's call it the naive encoding scheme) composes the plaintext element (polynomial) as: $\textsf{M} = m + 0x +0x^2 + \cdots + 0x^{n-1}$. I.e., we set $\textsf{M}$ as a constant polynomial with $m$ being the constant term. While this encoding scheme is simple in principle, it is extremely inefficient especially with large messages $m$. The reason is that while performing homomorphic operations on ciphertexts, the magnitude of plaintext coefficients grow larger. To ensure that the results of homomorphic evaluation matches the expected results of the computation of interest, we need to ensure that the plaintext coefficients do not wrap around $t$. Thus we need to ensure that $t$ is sufficiently larger than the inputs, any intermediate result and outputs of the computation to be implemented in FHE. The naive encoding scheme exhibits a fast growth of coefficients. We remark that this encoding scheme suffers from a more serious limitation, that is, wasting $n - 1$ coefficients in the plaintext polynomial. Other more efficient encoding schemes make use of a subset or even all of the coefficients, known as packed or batched encoding schemes.

Decoding for this scheme works by simply reading the constant term of the plaintext polynomial that results from decryption.

The other encoding scheme we would like to introduce, which is known as the integer encoding scheme, works as follows:

1. represent $m$ in binary representation $m = a_{n-1}\cdots a_2 a_1 a_0$
2. compose $\textsf{M} = a_{n-1}x+\cdots+a_{2}x^2+a_{1}x+a_0$. Since $n$ is too large in practice, unused bits are set to $0$.

Due to the smaller magnitude of plaintext coefficients, the coefficient growth during homomorphic evaluation is typically slower. Note that homomorphic evaluation with this encoding may cause the degree of the plaintext polynomial to grow. To ensure that the results of homomorphic evaluation matches the expected results of the computation of interest, we need to ensure that the degree of the plaintext coefficient does not wrap around $n$ and the coefficients do not wrap around $t$.

Note that for the integer encoding scheme, one can choose any integer decomposition base other than $2$ such as ternary, quaternary or $k$-ary base decomposition. Decoding for the integer encoding scheme works by evaluating the plaintext polynomial at $k$, i.e., computing $\textsf{M}(k)$.

The secret key $\textsf{SK}$ is generated as a random ternary polynomial from $R_2$, a polynomial of degree $n$ with coefficients in $\{-1,0,+1\}$. The public key $\textsf{PK}$ is a pair of polynomials $(\textsf{PK}_1, \textsf{PK}_2)$ calculated as follows: \begin{align} \textsf{PK}_1 &= [-1(a\cdot \textsf{SK}+e)]_q\\ \textsf{PK}_2 &= a \nonumber \end{align} where $a$ is a random polynomial in $R_q$, and $e$ is a random error polynomial sampled from $\mathcal{X}$. The notation $[\cdot]_q$ means that polynomial arithmetic should be done modulo $q$. Note that as $\textsf{PK}_2$ is in $\R_q$, polynomial arithmetic should also be performed modulo the ring polynomial modulus $(x^n+1)$.

To encrypt a plaintext message $\textsf{M}$ in $\P$, one first generates three small random polynomials $u$ from $R_2$ and $e_1$ and $e_2$ from $\mathcal{X}$ and returns the ciphertext $\textsf{C} = (\textsf{C}_1,\textsf{C}_2)$ in $\C$ as follows: \begin{align}\label{eq:encrypt} \textsf{C}_1 &= [\textsf{PK}_1\cdot u + e_1 + \Delta \textsf{M}]_q\\ \textsf{C}_2 &= [\textsf{PK}_2\cdot u + e_2]_q \nonumber \end{align} The parameter $\Delta$ is defined as the quotient of dividing $q$ by $t$, i.e., $\Delta = \lfloor \frac{q}{t} \rfloor$. It is used to scale the message. Decryption is performed by evaluating the ciphertext on the secret key as follows and inverting the scaling factor applied in encryption: \begin{equation} \label{eq:decryption} \textsf{M} = \bigg[ \bigg\lfloor \dfrac{t[\textsf{C}_1+\textsf{C}_2\cdot \textsf{SK}]_q}{q} \bigg\rceil \bigg]_t \end{equation} In order to check why decryption works and under which conditions, let's expand Equation \eqref{eq:decryption} as follows: \begin{align} \label{eq:dec:proof} \textsf{C}_1+\textsf{C}_2\cdot\textsf{SK} &= \textsf{PK}_1\cdot u + e_1 + \Delta \textsf{M} + (\textsf{PK}_2\cdot u + e_2)\cdot \textsf{SK}\\ &= -(a\cdot \textsf{SK}+e)\cdot u+e_1+\Delta \textsf{M} + a\cdot u \cdot \textsf{SK} + e_2\cdot \textsf{SK} \nonumber\\ &= \cancel{-a\cdot u \cdot \textsf{SK}} - e\cdot u+e_1+\Delta \textsf{M} + \cancel{a\cdot u \cdot \textsf{SK}} + e_2\cdot \textsf{SK} \nonumber\\ &= \Delta \textsf{M} - e\cdot u + e_1 + e_2\cdot\textsf{SK} \nonumber\\ &= \Delta \textsf{M} + v \nonumber \end{align} It should be noted that infinity norm of $v$, which is the largest absolute coefficient in the polynomial $v$ denoted by $\left\| v \right\|$, is very small since $e, e_1, e_2$ and $\textsf{SK}$ are all small polynomials. More concretely, given that these small polynomials are bounded by the parameter $\beta$, it is straightforward to show that $\left\| v \right\| \leq n \beta^2 + \beta + n \beta^2 = 2n \beta^2 + \beta$.

To carry on with the proof, we need to expand Equation \eqref{eq:dec:proof} modulo $q$ and complete evaluating the decryption function. This can be done as follows: \begin{align}\label{eq:dec:modq} \textsf{C}_1+\textsf{C}_2\cdot\textsf{SK} &= \Delta \textsf{M} + v + q\cdot r \end{align} where $r$ is some polynomial. Scaling Equation \eqref{eq:dec:modq} by $\frac{t}{q}$ results in $\textsf{M} +\frac{t}{q}\cdot v+t\cdot r$. The rounding function in decryption removes $\frac{t}{q}\cdot v$ and the final modulo $t$ operation removes $t\cdot r$ and recovers $\textsf{M}$. In short, for decryption to recover $\textsf{M}$ correctly, we need to ensure that $\frac{t}{q}\cdot \left\| v \right\| < \frac{1}{2}$, otherwise the noise will overflow and destroy the message.

In this section, we explain how homomorphic evaluation procedures work. Much of this section is based on the correctness analysis that can be found in the proposal of BFV [FV12].
Let's take $\textsf{EvalAdd}$ as a reference to understand how homomorphic addition works. This procedure is quite simple, we just add the corresponding polynomials in each ciphertext as shown in Equation \eqref{eq:homo:add}. \begin{equation}\label{eq:homo:add} \textsf{EvalAdd}(\textsf{C}^{(1)}, \textsf{C}^{(2)}) = ([\textsf{C}^{(1)}_1 + \textsf{C}^{(2)}_1]_q, [\textsf{C}^{(1)}_2 + \textsf{C}^{(2)}_2]_q) = ( \textsf{C}^{(3)}_1, \textsf{C}^{(3)}_2) = \textsf{C}^{(3)} \end{equation} In order to see why this works, let's break Equation \eqref{eq:homo:add} as follows: Assume that $\textsf{C}^{(1)}$ and $\textsf{C}^{(2)}$ are fresh encryptions of $\textsf{M}^{(1)}$ and $\textsf{M}^{(2)}$. Algebraically, they can be expressed as follows (See Equation \eqref{eq:encrypt}): \begin{align} \label{eq:homo:add_det1} \textsf{C}^{(1)} &= ([\textsf{PK}_1\cdot u^{(1)} + e_1^{(1)} + \Delta \textsf{M}^{(1)}]_q, [\textsf{PK}_2 \cdot u^{(1)} + e_2^{(1)}]_q)\\ \textsf{C}^{(2)} &= ([\textsf{PK}_1\cdot u^{(2)} + e_1^{(2)} + \Delta \textsf{M}^{(2)}]_q, [\textsf{PK}_2 \cdot u^{(2)} + e_2^{(2)}]_q) \nonumber \end{align} By substituting the $\textsf{C}^{(1)}$ and $\textsf{C}^{(2)}$ in Equation \eqref{eq:homo:add} we get the following: \begin{align} \textsf{C}^{(3)} ={}& ( \textsf{C}^{(3)}_1, \textsf{C}^{(3)}_2)\\ ={}& ( [\textsf{PK}_1\cdot(u^{(1)}+u^{(2)})+(e_1^{(1)}+e_1^{(2)})+ \Delta(\textsf{M}^{(1)}+\textsf{M}^{(2)})]_q, \nonumber \\ {}&~[\textsf{PK}_2\cdot(u^{(1)}+u^{(2)})+(e_2^{(1)}+e_2^{(2)})]_q ) \nonumber \\ ={}& ( [\textsf{PK}_1\cdot u^{(3)}+e_1^{(3)}+ \Delta(\textsf{M}^{(1)}+\textsf{M}^{(2)})]_q, [\textsf{PK}_2 \cdot u^{(3)}+e_2^{(3)}]_q )\label{eq:homo:add_det2} \end{align} It is straightforward to notice that Equation \eqref{eq:homo:add_det2} has the form of a valid ciphertext encrypting $\textsf{M}^{(3)} = \textsf{M}^{(1)} + \textsf{M}^{(2)}$. Note that the error term in $\textsf{C}^{(3)}$ is approximately, following a worst-case scenario analysis, the sum of noise terms in the input ciphertexts, i.e., the noise grows additively.

One can follow the procedure used above to derive the expression for $\textsf{EvalAddPlain}$, the plaintext message can be transformed to a ciphertext form by encryption with no error terms, i.e., $e_1=e_2=0$.
Homomorphic multiplication is more complex compared to homomorphic addition. We present here the basic procedure and refer the reader to external resources for further details. It is useful to write the ciphertext as an evaluation at $\textsf{SK}$ similar to what we did in the derivation of decryption: \begin{align} \textsf{C}^{(1)}(\textsf{SK}) &= \Delta \textsf{M}^{(1)}+v_1+q \cdot r_1\\ \textsf{C}^{(2)}(\textsf{SK}) &= \Delta \textsf{M}^{(2)}+v_2+q \cdot r_2 \nonumber \end{align} Multiplying the ciphertexts would give us: \begin{equation}\label{eq:homo:mul} \begin{split} (\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK}) = &\Delta^2 \textsf{M}^{(1)}\cdot \textsf{M}^{(2)} + \Delta(\textsf{M}^{(1)}\cdot v_2+\textsf{M}^{(2)}\cdot v_1)+\\ &q(v_1\cdot r_2 + v_2\cdot r_1) + q\cdot \Delta(\textsf{M}^{(1)}\cdot r_2 + \textsf{M}^{(2)} \cdot r_1)+\\ &v_1 \cdot v_2 + q^2 \cdot r_1 \cdot r_2 \end{split} \end{equation} The product ciphertext looks close to an encryption of what we want $\Delta \cdot[\textsf{M}^{(1)} \cdot \textsf{M}^{(2)}]_t$. We notice that scaling by $\frac{1}{\Delta}$ gives us exactly what we want in the first term plus some noise. However, the last term ($q^2 \cdot r_1 \cdot r_2$) would generate large noise since $q^2$ does not divide $\Delta$. Instead, we would scale by the factor $\frac{t}{q}$. Now, we can write $\textsf{M}^{(1)}\cdot \textsf{M}^{(2)} = [\textsf{M}^{(1)}\cdot \textsf{M}^{(2)}]_t + t\cdot r_M$. We can also write $v_1\cdot v_2 = [v_1 \cdot v_2]_{\Delta} + \Delta \cdot r_v$. Scaling by $\frac{t}{q}$ and substituting these expressions in Equation \eqref{eq:homo:mul}, we obtain the following: \begin{equation}\label{eq:homo:mul:2} \begin{split} \frac{t}{q}(\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK}) = &\Delta [\textsf{M}^{(1)}\cdot \textsf{M}^{(2)}]_t+(\textsf{M}^{(1)}\cdot v_2+\textsf{M}^{(2)}\cdot v_1)+\\ &t(v_1\cdot r_2 + v_2\cdot r_1) + r_v + (q-[q]_t)\cdot(r_M+\textsf{M}^{(1)}\cdot r_2+\textsf{M}^{(2)}\cdot r_1)+\\ &q\cdot t\cdot r_1 \cdot r_2 +\frac{t}{q}[v_1\cdot v_2]_\Delta -\\ &\frac{[q]_t}{q} ( \Delta \textsf{M}^{(1)} \cdot \textsf{M}^{(2)} + \textsf{M}^{(1)} \cdot v_2 + \textsf{M}^{(2)} \cdot v_1 + r_v ) \end{split} \end{equation} The final step in the derivation is reducing Equation \eqref{eq:homo:mul:2} modulo $q$, which gives us: \begin{equation} \begin{split} \frac{t}{q}(\textsf{C}^{(1)} \cdot \textsf{C}^{(2)})(\textsf{SK}) = &\Delta [\textsf{M}^{(1)}\cdot \textsf{M}^{(2)}]_t+(\textsf{M}^{(1)}\cdot v_2+\textsf{M}^{(2)}\cdot v_1)+\\ &t(v_1\cdot r_2 + v_2\cdot r_1) + r_v -\\ &[q]_t (r_M+\textsf{M}^{(1)}\cdot r_2+\textsf{M}^{(2)}\cdot r_1) + r_e \end{split} \end{equation} , where $r_e$ is the rounding error generated from the last two terms in Equation \eqref{eq:homo:mul:2}.

The noise growth for multiplication grows by a linear factor that is approximately $2\cdot t \cdot n^2 \cdot \left\| SK \right\|$, i.e., $\left\| v_{p} \right\| = \left\| v_i \right\| \cdot 2\cdot t \cdot n^2 \cdot \left\| SK \right\|$, where $v_p$ is the noise in the product ciphertext, and $v_i$ is the noise in the input ciphertexts.

In short, to evaluate $\textsf{EvalMult}$, we compute the tensor product of the input ciphertexts and scale by $\frac{t}{q}$ as follows: \begin{equation} \begin{split} \textsf{EvalMult}(\textsf{C}^{(1)}, \textsf{C}^{(2)}) = \bigg(& \bigg[ \bigg\lfloor \dfrac{t(\textsf{C}^{(1)}_1\cdot\textsf{C}^{(2)}_1)}{q} \bigg\rceil \bigg]_q, \bigg[ \bigg\lfloor \dfrac{t(\textsf{C}^{(1)}_1 \cdot \textsf{C}^{(2)}_2 + \textsf{C}^{(1)}_2 \cdot \textsf{C}^{(2)}_1 )}{q} \bigg\rceil \bigg]_q, \\& \bigg[ \bigg\lfloor \dfrac{t(\textsf{C}^{(1)}_2 \cdot \textsf{C}^{(2)}_2)}{q} \bigg\rceil \bigg]_q \bigg) \end{split} \end{equation} It can be noticed that $\textsf{EvalMult}$ increases the number of terms in the resulting ciphertext from 2 to 3 ring elements. Moreover, in order to decrypt the resulting ciphertext, a slightly different decryption procedure has to be used. Fortunately, these complications can be resolved via $\textsf{Relinearization}$ which will be described in the subsequent section.

The main purpose of this procedure is to reduce the size of product ciphertexts, those resulting from $\textsf{EvalMult}$, back to 2 ring elements. This problem can be formulated concretely as follows: Let $\textsf{C}^{*} = \{\textsf{C}^{*}_1, \textsf{C}^{*}_2, \textsf{C}^{*}_3\}$. Our goal is to find $\hat{\textsf{C}}^{*} = \{\hat{\textsf{C}}^{*}_1, \hat{\textsf{C}}^{*}_2\}$ such that: \begin{equation} [\textsf{C}^{*}_1 + \textsf{C}^{*}_2\cdot \textsf{SK} + \textsf{C}^{*}_3 \cdot \textsf{SK}^2]_q \approx [\hat{\textsf{C}}^{*}_1 + \hat{\textsf{C}}^{*}_2 \cdot \textsf{SK} + r]_q \end{equation} Access to $\textsf{SK}^2$ is provided by means of the evaluation key $\textsf{EK} = (-(a\cdot \textsf{SK} + e) + \textsf{SK}^2, a)$. Note that this is a masked version of $\textsf{SK}^2$ since $\textsf{EK}_1 + \textsf{EK}_2 \cdot \textsf{SK} = \textsf{SK}^2 - e$. Now we can compute $\hat{\textsf{C}^{*}}$ as follows: \begin{align}\label{eq:relin} \hat{\textsf{C}}^{*}_1 &= [\textsf{C}^*_1 + \textsf{EK}_1\cdot \textsf{C}^*_3]_q\\ \hat{\textsf{C}}^{*}_2 &= [\textsf{C}^*_2 + \textsf{EK}_2\cdot \textsf{C}^*_3]_q \nonumber \end{align} If we write the decryption formula for Equation \eqref{eq:relin} we obtain: \begin{align} \hat{\textsf{C}}^{*}_1 + \hat{\textsf{C}}^{*}_2 \cdot \textsf{SK} &= \textsf{C}^*_1 + \textsf{EK}_1\cdot \textsf{C}^*_3 + \textsf{SK}\cdot (\textsf{C}^*_2 + \textsf{EK}_2\cdot \textsf{C}^*_3)\\ &= \textsf{C}^*_1 + \textsf{C}^*_2 \cdot \textsf{SK} + \textsf{C}^*_3\cdot(\textsf{EK}_1 + \textsf{EK2} \cdot \textsf{SK} )\nonumber\\ &= \textsf{C}^*_1 + \textsf{C}^*_2 \cdot \textsf{SK} + \textsf{C}^*_3 \cdot \textsf{SK}^2 + \textsf{C}^*_3 \cdot e \nonumber \end{align} It should be noted that the term $\textsf{C}^*_3 \cdot e$ can be quite large as $\textsf{C}^*_3$ has coefficients in $\Z_q$. Nevertheless, there is a technique to reduce this error using base decomposition. For further details, we refer the reader to [FV12].

Analyzing the security of the BFV scheme is quite complex and beyond the scope of this article. Choosing optimal BFV parameters that maximize performance and respect security and functionality constraints is an art that is practiced by expert cryptographers. That said, for a brief security analysis and a set of recommended parameters for BFV (and other FHE schemes), we refer the reader to the homomorphic encryption standard [ACC+18].

[ACC+18] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, November 2018.

[Bra12] Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Annual Cryptology Conference, pages 868–886. Springer, 2012.

[BGV14] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014.

[CKKS17] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 409–437. Springer, 2017.

[FV12] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. 2012. https://eprint.iacr.org/2012/144.

[LPR13] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60(6):1–35, 2013