Circular-secure bootstrappable SHE ⇒ Compact FHE

Free reduction · standard model · Gen09 · security loss: none: the FHE public key is the SHE public key with encryptions of its own secret-key bits, so the FHE IND-CPA game is the circular-security game

Statement

Any bootstrappable somewhat homomorphic encryption (SHE) scheme — one able to compactly evaluate its own decryption circuit augmented by a NAND gate — that is circular secure, IND-CPA-secure given encryptions of its own secret-key bits, yields compact FHE for circuits of arbitrary depth; without circular security, a chain of independent key pairs gives only leveled FHE — Gen09.

Sketch

The public key includes an encryption of the secret key under its own public key. A NAND gate on ciphertexts $c_1,c_2$ is evaluated by homomorphically evaluating $\mathsf{sk}\mapsto \neg \left(\mathsf{Dec}(\mathsf{sk},c_1)\wedge \mathsf{Dec}(\mathsf{sk},c_2)\right)$ on that encryption, so every output ciphertext carries the bounded noise of one augmented decryption and circuits of any depth can be evaluated gate by gate. Encrypting each ${\mathsf{sk}}_i$ under a fresh ${\mathsf{pk}}_{i+1}$ instead, one key pair per level, gives leveled FHE without circular security.