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 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.

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

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

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

Available format(s): PDF | BibTeX Citation

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

Version: 20201208:212255 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]