Indistinguishability obfuscation from circular security
Romain Gay, Rafael Pass
Abstract
We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: (a) the Learning with Errors (LWE) assumption (with subexponential modulus-to-noise ratio); (b) a circular security conjecture regarding the Gentry-Sahai-Waters' (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.
Topics & Concepts
EncryptionLearning with errorsObfuscationConjectureMathematicsCryptographyGadgetTheoretical computer scienceComputer scienceDiscrete mathematicsComputer securityCombinatoricsAlgorithmCryptography and Data SecurityComplexity and Algorithms in GraphsPrivacy-Preserving Technologies in Data