LWE with polynomial ratio ⇒ Leveled FHE (BV14)

Fully-black-box reduction · standard model · BV14 · security loss: additive: at most twice the sum of one LWE advantage per key of the chain, from the hybrid along it, the last step being IND-CPA under the first key, plus a statistical leftover-hash term in that last step

Statement

If LWE is hard with polynomial modulus-to-noise ratio, there is a leveled FHE scheme for circuits of any depth fixed at key generation. Its security therefore rests on worst-case lattice problems with the approximation factors of plain lattice-based PKE, $\tilde{O}(n^{1.5+\epsilon })$ for GapSVP under quantum reductions and $\tilde{O}(n^{2+\epsilon })$ under classical ones, for any constant $\epsilon >0$ — BV14.

Sketch

Fresh ciphertexts are encrypted under the first key of a chain, every piece of the evaluation key (dimension-modulus reduction and bootstrapping material) encrypts a secret of the chain under a strictly later key, and nothing encrypts the last key. A hybrid from the end of the chain replaces each piece by an encryption of $0$, each step reducing to LWE because the secret key it is encrypted under by then appears nowhere else; IND-CPA under the first key then hides the challenge message — BV14.

Notes

• The polynomial ratio comes from bootstrapping: decryption is evaluated as a width-5 permutation branching program (Barrington’s theorem), whose sequential multiplications grow noise additively, combined with successive dimension-modulus reduction; the chain of independent keys, one per level, removes the need for circular security — BV14.
• With circular security of the scheme itself, the same bootstrapping gives compact FHE — BV14.
• Without bootstrapping, the BGV12 scheme uses a ratio exponential in the depth: BGV12 — BGV12.