Paper 2024/856

Indistinguishability Obfuscation from Bilinear Maps and LPN Variants

Seyoon Ragavan, Massachusetts Institute of Technology
Neekon Vafa, Massachusetts Institute of Technology
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Abstract

We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$. As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2024
Keywords
Indistinguishability ObfuscationSparse LPNHomomorphic Encryption
Contact author(s)
sragavan @ mit edu
nvafa @ mit edu
vinodv @ mit edu
History
2024-09-26: revised
2024-05-31: received
See all versions
Short URL
https://ia.cr/2024/856
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/856,
      author = {Seyoon Ragavan and Neekon Vafa and Vinod Vaikuntanathan},
      title = {Indistinguishability Obfuscation from Bilinear Maps and {LPN} Variants},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/856},
      year = {2024},
      url = {https://eprint.iacr.org/2024/856}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.