The BGV scheme

The BGV scheme aims to achieve fully homomorphic encryption without bootstrapping. The key technical tool used in doing so is modulus switching. This is used recursively in order to keep the noise level constant by switching to a smaller modulus, thus eliminating the need for bootstrapping.

The scheme is over a ring $R$, usually the ring of integers modulo an odd integer $q$ in the LWE instantiation, or a polynomial ring over the integers modulo an irreducible $f(x)$ and an odd integer $q$ in the RLWE one. In the GHS variant, $f(x)$ is always chosen to be a cyclotomic polynomial $\Phi_{m}$ for some $m$ coprime with $q$.

A ciphertext c in $R^{n}$ is said to encrypt a message $m$ if it satisfies

$m = [[<c,s>]_{q}]_{2}$,

where s is the secret key. In the RLWE version, this becomes $m=[[<c,s>\mod f(x)]_{q}]_{2}$. $[.]_{q}$ denotes modular reduction in the interval $(-q/2, q/2]$.

$[<c,s>]_{q}$ is called the noise associated with c under s, and c decrypts as long as the noise remains below $q/2$. For two ciphertexts of noise at most $B$, addition results in noise with magnitude at most $2B$, whereas multiplication roughly squares the noise.

Modulus-switching allows for the noise level to be kept constant, while the modulus size decreases with each modulus switch, as does the homomorphic capacity of the scheme. It allows us to go from a ciphertext c with respect to a modulus $q$ to a ciphertext c' with respect to a modulus $p$ by simply scaling by $p/q$ and rounding appropriately. Most importantly, while preserving correctness,

$[<c,s>]_{q}=[<c',s>]_{p} \mod 2$.

This reduces the magnitude of the noise without having to resort to bootstrapping and without needing to know the secret key s. Note however that it only decreases the absolute magnitude of the noise. The noise to modulus ratio remains unchanged. To see why the absolute magnitude is important, suppose your modulus $q$ is such that $q \approx x^{k}$, and you multiply two modulus-$q$ ciphertexts with magnitude $\approx x$. After four multiplications only, the noise magnitude reaches $x^{16}$. Another multiplication brings the noise level to $x^{32}$. In this case, the noise ceiling is reached in only $\log k$ multiplications.

To allow for more multiplications, we take a ladder of gradually decreasing moduli $q_{0} > q_{1} > ... > q_{L}$ such that $q_{i} \approx q/ x^{i} $ for $i < k$ and $q$ as above. After each multiplication, switch down to the next modulus; multiplying two $\mod q_{0}$ ciphertexts of noise $x$ gives a ciphertext of noise $x^{2}$. Then switching down to $q_{1}=q_{0}/x$ reduces the noise back down to $x$. This approach allows for $k$ levels of homomorphic operations, as opposed to $\log k$.

Of course, once the last level $q_{L}$ is reached, modulus switching cannot be performed anymore. Bootstrapping is then used as an optimisation to allow for an indefinite number of homomorphic operations.

Another interesting optimisation proposed is batching. The idea is to pack multiple plaintexts into one ciphertexts, so that homomorphic operations can be evaluated on multiple inputs efficiently. This relies on the Chinese Remainder theorem; use the ring $R = \mathbb{Z}[x]/(f)$ for some irreducible polynomial $f \in \mathbb{Z}[x]$, and take plaintexts to be elements of $R_{p}=R/(p)$. If we pick the parameters carefully, it will turn out that $f(x)$ factors $\mod p$, which by the Chinese Remainder theorem gives the isomorphism $R_{p} \cong R_{\mathfrak{p}_{1}} \times ... R_{\mathfrak{p}_{l}}$. Each $\mathfrak{p}_{i}$ is an ideal in the ring $R$, corresponding to a factor of $f(x) \mod p$. Then, performing one operation in $R_{p}$ means performing many operations in parallel on $R_{\mathfrak{p}_{1}} \times ... R_{\mathfrak{p}_{l}}$.