[link]
Summary by quaxton 6 years ago
Brakerski and Vaikuntanathan introduce a fully homomorphic encryption scheme (FHE) based solely on the decisional learning with errors (LWE) security assumptions. Moving away from the relatively obscure mathematics of ideal lattices. They introduce relinearization and modulus switching techniques for dimensionality reduction and for removing the “squashing” step of Craig Gentry’s FHE scheme. BV11 and other similar schemes are commonly referred to as “Second generation FHE” schemes.
Reliearnization lowers the dimensions of the produced ciphertext, and allows the construction of a somewhat homomorphic encryption scheme that is capable of evaluating $O(\log n)$ depth (ie, multiplicative depth, circuit). With every homomorphic multiplication, the ciphertext error is squared. To slow down the growth of the error, BV11 shows that you can choose a new secret key used in re-linearization to have small modulus $p$. Thus taking the ciphertext dimensions from $(n,\log q)$ down to $(k, \log p)$, where it is small enough to achieve a bootstrappable scheme, thus making it FHE.
$$\\
$$
Below is an example of re-linearization for multiplicative homomorphism from the paper. Mostly for my own notes, but may help give additional intuition for others. What confused me was the "publishing" of the linear and quadratic terms in $s$. What they mean is that an evaluation key is published, containing the 'encryptions' of the linear and quadratic variables. For example, if $n=2$, this would be the set of encryptions for secret key $s$ : Enc ${\{s_1, s_2, s_1s_2, s_1^2, s_2^2\}}$.
Given a ciphertext $(\mathbf{a},b)$ and $(\mathbf{a}',b')$, we can describe homomorphic multiplication with the decryption function $f$:
$$\begin{align}
f_{(\mathbf{a},b)}(x) \cdot f_{(\mathbf{a'},b')}(x) &= (b - {\sum_{i}^n} a[i] \cdot x[i]) \cdot (b' - {\sum_{i}^n} a'[i] \cdot x[i])\\
&= h_0 + \sum_{i}^n h_i \cdot x[i] + \sum_{i,j}^n h_{i,j} \cdot x[i]x[j] \\
\end{align}
$$
where $h_i$ and $h_{i,j}$ are coefficients of the 2-degree polynomial in $\mathbf{x}$.
$$\begin{align} h_0 &= bb' \\
h_i &= -(b\mathbf{a}'[i] + b'\mathbf{a}[i]) \\
h_{i,j} &= \mathbf{a}[i]\mathbf{a}'[j]
\end{align}$$
With the secret key $s \in \mathbb{Z}_q^n$, we evaluate $f$ on $s$ to get the plaintext.
Because the decryption function needs to know all of the coefficients of the quadratic polynomial to be able to decrypt correctly, the size of the ciphertext jumps from $n+1$ to an order of $\approx n^2$.
What BV11 shows is a relinearization technique that reduces the size of the ciphertext back down to $n+1$.
To do this, we create an evaluation key $evk$ that is made up of the encryption of the quadratic terms of $x$. The ciphertexts will be the set $\{(\mathbf{a}_i,b), (\mathbf{a}_{i,j},b)\}$
Note: $\mathbf{a}$ is a random vector $\in \mathbb{Z}_q^n$
where
$$\begin{align}
b_{i,j} &\approx \langle \mathbf{a}_{i,j},t\rangle + s[i] \cdot s[j] \\
b_{i} &\approx \langle \mathbf{a}_{i},t\rangle + s[i]
\end{align}
$$
Now we can rewrite the symbolic multiplication of the decryption function as:
$$\begin{align}
f_{(\mathbf{a}_{mult},b_{mult})}(t) &= h_0 + \sum_{i}^n h_i (b_i - \langle \mathbf{a}_i,\mathbf{t} \rangle) + \sum_{i,j}^n h_{i,j} (b_{i,j} - \langle \mathbf{a}_{i,j}, \mathbf{t} \rangle) \\
\end{align}
$$
This is a linear function in $\mathbf{t}$! The number of coefficients of this linear equation are at most $n+1$.
$$\begin{align}
\mathbf{a}_{mult} &= \sum_{i}^n h_i \mathbf{a}_i + \sum_{i,j}^n h_{i,j} \mathbf{a}_{i,j}\\
\mathbf{b}_{mult} &= h_0 + \sum_{i}^n h_i \mathbf{b}_i + \sum_{i,j}^n h_{i,j} \mathbf{b}_{i,j}
\end{align}
$$
## See Also
[lecture](https://www.youtube.com/watch?v=MB3mSaG6Bro) from MathNet Korea (potato res).
