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. More precisely, 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 encryption of the secret key. Our work thus places iO on qualitatively similar assumptions as (unlevelled) FHE, for which known constructions also rely on a circular security conjecture.

Note: result improvement: security based only one 1-circular SRL security of GSW.