February 7, 2021
\(
\newcommand{\etal}{\textit{et al.}}
\newcommand{\afv}{A\(^\ast\)FV}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\bigO}{\mathcal{O}}
\newcommand{\bfc}{\mathbf{c}}
\newcommand{\relu}{\mathsf{ReLU}}
\def\code#1{\texttt{#1}}
\def \a {\alpha}
\def \b {\beta}
\def \d {\delta}
\def \e {\epsilon}
\def \g {\gamma}
\def \k {\kappa}
\def \lam {\lambda}
\def \s {\sigma}
\def \t {\tau}
\def \ph{\phi}
\def \v {\nu}
\def \w {\omega}
\def \ro {\varrho}
\def \vare {\varepsilon}
\def \z {\zeta}
\def \F {{\mathbb F}}
\def \Z {{\mathbb Z}}
\def \R {{\mathbb R}}
\def \deg {{\rm deg}}
\def \supp {{\rm supp}}
\def \l {\ell}
\def \Aut {{\rm Aut}}
\def \Gal {{\rm Gal}}
\def \A {{\mathcal A}}
\def \G {{\mathcal G}}
\def \H {{\mathcal H}}
\def \P {{\mathcal P}}
\def \C {{\mathcal C}}
\)
1. Scope
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/FanVercauteren [Bra12, FV12]
scheme, a RingLearning with Errors (RLWE)based cryptosystem.
2. Introduction
The FanVercauteren (FV) scheme, (also known as the BrakerskiFanVercauteren
(BFV) scheme) is considered as one of the second generation of FHE schemes
that is constructed based on the RingLearning 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:
2.1 BFV Primitives
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:
3. Plaintext and Ciphertext Spaces
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{a1}{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$.
4. Parameters
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:
5. Plaintext Encoding and Decoding
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^{n1}$. 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:
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)$.
6. Key Generation
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)$.
7. Encryption and Decryption
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.
8. Homomorphic Evaluation
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].
8.1 $\textsf{EvalAdd}$
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 worstcase 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$.
8.2 $\textsf{EvalMult}$
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.
9. Relinearization
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].
10. Security of the Scheme
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].
References
[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
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/FanVercauteren scheme (BFV) [Bra12, FV12], a
RingLearning 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
BrakerskiGentryVaikuntanathan (BGV) scheme
[BGV14] and the
CheonKimKimSong (CKKS) scheme
[CKKS17]. Note: this article is also available as a
PDF Document
for those who prefer.
1. Scope
2. Introduction
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.
2.1 BFV 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 illshaped (more on this later) $\textsf{C}'$ encrypting $\textsf{M}$, and returns a wellshaped compact $\textsf{C}$ encrypting $\textsf{M}$.
3. Plaintext and Ciphertext Spaces
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}4. Parameters
 $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$.
5. Plaintext Encoding and Decoding
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^{n1}$. 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:
 represent $m$ in binary representation $m = a_{n1}\cdots a_2 a_1 a_0$
 compose $\textsf{M} = a_{n1}x+\cdots+a_{2}x^2+a_{1}x+a_0$. Since $n$ is too large in practice, unused bits are set to $0$.
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)$.
6. Key Generation
7. Encryption and Decryption
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.
8. Homomorphic Evaluation
8.1 $\textsf{EvalAdd}$
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$.
8.2 $\textsf{EvalMult}$
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.
9. Relinearization
10. Security of the Scheme
References
[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