Sub-exponential iO + Rerandomizable encryption ⇒ Compact FHE (CLTV)

Free reduction · standard model · CLTV15 · security loss: sub-exponential in the iO security and slightly super-polynomial in the encryption’s security

Statement

If sub-exponentially secure iO and a re-randomizable PKE scheme secure against slightly super-polynomial adversaries exist, then compact fully homomorphic encryption exists, with no circular-security assumption — CLTV15.

Notes

• The evaluation key is a probabilistic-iO obfuscation of the randomized circuit that decrypts two ciphertexts, applies a gate and re-encrypts; CLTV15 build the probabilistic iO they need from sub-exponentially secure iO and one-way functions — CLTV15.
• Lattice-based unbounded-depth FHE goes through bootstrapping, whose security rests on circular security of the scheme itself (Circular-secure bootstrappable SHE ⇒ Compact FHE, LWE with sub-exponential ratio ⇒ Bootstrappable SHE (BV11)) — Gen09, BV11.