Paper 2020/1010

Indistinguishability Obfuscation from Circular Security

Romain Gay and Rafael Pass

Abstract

We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: - the Learning with Error (LWE) assumption (with subexponential modulus-to-noise ratio); - a circular security conjecture regarding the Gentry-Sahai-Water's (GSW) encryption scheme and a Packed version of Regev's encryption scheme. The circular security conjecture states that a notion of leakage-resilient security, that we prove is satisfied by GSW assuming LWE, is retained in the presence of an encrypted key-cycle involving GSW and Packed Regev. Our work thus places iO on qualitatively similar assumptions as (unlevelled) FHE, for which known constructions also rely on a circular security conjecture.

Note: Removed the result added in the previous version, namely, security from 1-circular security, which was flawed.