Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / obfuscation, circular security, homomorphic encryption

Date: received 21 Aug 2020, last revised 8 Sep 2020

Contact author: romain rgay at gmail com, rnp3@cornell edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200908:195609 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]