### Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices

Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta

##### Abstract

We construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [ePrint 2020], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Döttling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes --- specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a relaxed assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle.

Note: Update on the writeup and new results on XiO.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
obfuscationLWE
Contact author(s)
giulio malavolta @ hotmail it
History
2022-03-28: last of 5 revisions
See all versions
Short URL
https://ia.cr/2020/1024

CC BY

BibTeX

@misc{cryptoeprint:2020/1024,
author = {Zvika Brakerski and Nico Döttling and Sanjam Garg and Giulio Malavolta},
title = {Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices},
howpublished = {Cryptology ePrint Archive, Paper 2020/1024},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1024}},
url = {https://eprint.iacr.org/2020/1024}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.