Bootstrappable SHE ⇒ Leveled FHE

Free reduction · standard model · Gen09 · security loss: factor $O(\ell d)$ for depth $d$ and $\ell$-bit secret keys, from the hybrid over the bitwise encryptions of the secret keys along the chain

Statement

A bootstrappable somewhat homomorphic encryption scheme — one that homomorphically evaluates its own decryption circuit augmented by one gate — yields leveled fully homomorphic encryption for circuits of any a-priori bounded depth, via a chain of independent key pairs, one per level, with each secret key encrypted under the next public key in the chain — Gen09.

Sketch

Given ciphertexts $c_1,c_2$ under ${\mathsf{pk}}_i$, homomorphically evaluate the augmented decryption circuit $\mathsf{sk}\mapsto \neg \left(\mathsf{Dec}(\mathsf{sk},c_1)\wedge \mathsf{Dec}(\mathsf{sk},c_2)\right)$ on the encryption of ${\mathsf{sk}}_i$ under ${\mathsf{pk}}_{i+1}$: the result encrypts the NAND of the two plaintexts under ${\mathsf{pk}}_{i+1}$, with noise set by the depth of that circuit, not by the computation so far. Each level of NAND gates moves one key pair along the chain, so the chain’s length bounds the depth.

Notes

• Unbounded-depth FHE by bootstrapping additionally needs circular security of the scheme itself: a single key pair publishes an encryption of its own secret key — Circular-secure bootstrappable SHE ⇒ Compact FHE, Gen09.