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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- obfuscationcircular securityhomomorphic encryption
- Contact author(s)
-
romain rgay @ gmail com
rnp3 @ cornell edu - History
- 2020-12-08: last of 7 revisions
- 2020-08-22: received
- See all versions
- Short URL
- https://ia.cr/2020/1010
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1010,
author = {Romain Gay and Rafael Pass},
title = {Indistinguishability Obfuscation from Circular Security},
howpublished = {Cryptology ePrint Archive, Paper 2020/1010},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1010}},
url = {https://eprint.iacr.org/2020/1010}
}
