Bgv-Notes

Prior to this BGV scheme, all schemes relied on the SWHE + bootstrapping approach. However implementations of this kind result in an overhead that is polynomial in the security parameter $p(\lambda)$.
Why? The complexity of homomorphically evaluating decryption is at least the decryption time multiplied by the bit length of the individual ciphertexts used to encrypt each bit of the secret key.
Prior schemes base security on lattices problems with sub-exponential approximation factors.

Based on lattice problem with quasi-polynomial approximation factors.
Leveled FHE scheme with better per-gate computation, optionally using bootstrapping as an optimizaion.
Instead of bootstrapping, they use modulus switching iteratively, to keep noise level constant.
- The key idea is that while this does reduce the modulus $q$, they carefully choose a ladder of moduli to gradually reduce the modulus so that it doesn't impact the overall computation.
- Better asymptotic performance than bootstrapping.

LWE: Given $n, q, \chi$ dependent on security param $\lambda$, the LWE problem is to distinguish between two distributions:

$(\textbf{a}_i, b_i) \xleftarrow{\$} \mathbb{Z}_q^{n+1}$
$(\textbf{a}_i, b_i)$ where $\textbf{s} \xleftarrow{\$} \mathbb{Z}_q^n,\quad \textbf{a} \xleftarrow{\$} \mathbb{Z}_q^n,\quad e_i \leftarrow \chi, \quad\text{and}\quad b_i = \langle \textbf{a}, \textbf{s} \rangle + e_i.$

For certain $q$ and Guassian error distributions $\chi$, LWE is true as long as certain worst-case lattice problems are hard to solve using quantum.

RLWE: Quite similar, but $R = \mathbb{Z}[x]/(x^d + 1)$ and $R_q = R/qR$. Distinguish between

$(a_i, b_i) \xleftarrow{\$} R_q^2$
$(a_i, b_i)$ where $s \xleftarrow{\$} R_q,\quad a_i \xleftarrow{\$} R_q,\quad e_i \leftarrow \chi, \quad\text{and}\quad b_i = a_i \cdot s + e_i.$

The shortest vector problem (SVP) over ideal lattices can be reduced to RLWE.

Basic lattice scheme based on RLWE (looks like what we've seen before, public key is a matrix multiplied by secret key with small error, which drops away during decryption)
Key switching technique that can take $s_1, c_1, s_2$ and produce $c_2$ which decrypts to the same plaintext as $c_1$ (with small additive noise factor).
Modulus switching technique that can transform $(q, m, c_1) \to (p, m, c_2)$ such that $c_2$ has less noise, still decrypts to $m$ but under a smaller modulus $p$.
In detail:
- Setup: Given securtiy param $\lambda,$ levels $L$, set up a ladder of moduli from $0$ to $L$.
- KeyGen: the secret is an array of secret keys for each level. similarly the public key is an array of public key matrices along with the key switching info.
- Encode: as usual
- Decode: as usual but ciphertext indicates which level's secret key to use
- Add/Multiply: first ensure both ciphertexts have the same level index; if not use "Refresh" operation on one of them until they match. Then do add/multiply as usual, followed by an extra "Refresh" operation afterwards (not strictly necessary for addition).
- Refresh: Use the auxiliary key switching info (in the public key) to facilitate a modulus switch and key switch from current level $j$ to $j-1$.