LWE with sub-exponential ratio ⇒ Leveled FHE (BGV12)

Fully-black-box reduction · standard model · BGV12 · security loss: additive: one LWE advantage per level, $L+1$ in all, from the hybrid along the chain of keys, plus a leftover-hash term for the challenge ciphertext

Statement

For every depth bound $L$ fixed at key generation, the BGV scheme is a leveled FHE scheme for all polynomial-size circuits of depth $L$, IND-CPA-secure if decision LWE is hard with modulus-to-noise ratio exponential in $L$ (the largest modulus $q_L$ has $(L+1)\mu$ bits, $\mu =\Theta (\log \lambda +\log L)$), a ratio $2^{n^{\epsilon }}$ once the dimension $n$ is a large enough polynomial in $L$ and $\lambda$. It uses neither bootstrapping nor a circular-security assumption — BGV12.

Sketch

Ciphertexts are LWE encryptions under a ladder of moduli $q_L>\cdots >q_0$. After each multiplication, key switching returns the ciphertext from the tensored secret to a fresh secret, and modulus switching rescales it from $q_j$ to $q_{j-1}$, dividing the noise by the same factor; the noise returns to a fixed bound $B$ at each level while the modulus shrinks one rung, so depth $L$ is reached without bootstrapping.

Notes

• The approximate-eigenvector method gives leveled FHE from LWE with no evaluation key and no relinearization: homomorphic addition and multiplication are matrix addition and multiplication — GSW13.
• Leveled FHE from LWE was first obtained by relinearization and dimension–modulus reduction, bootstrapping along a chain of independent keys — BV11.
• Leveled FHE can rest on the same lattice approximation factors as plain lattice-based PKE, $\tilde{O}(n^{1.5+\epsilon })$ for GapSVP under quantum reductions, up to the $\epsilon$, by bootstrapping at polynomial ratio: LWE with polynomial ratio ⇒ Leveled FHE — BV14.
• Over Ring LWE the scheme evaluates depth-$L$ circuits with $\tilde{O}(\lambda \cdot L^3)$ computation per gate, without bootstrapping — BGV12.