Paper 2020/1024

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

Zvika Brakerski and Nico Döttling and 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 is a variant on a beautiful recent work by Gay and Pass [ePrint 2020] who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Doettling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security of natural homomorphic encryption schemes --- specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work, we replace the DCR-based encryption with an LWE-based one and thus obtain a result solely from the circular security of LWE-based encryption schemes. Our circular security assumption is the same as in the prior work and refers to leakage on encryption randomness in the presence of key-cycles.