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

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).

Available format(s)
Publication info
Indistinguishability ObfuscationSparse LPNHomomorphic Encryption
Contact author(s)
sragavan @ mit edu
nvafa @ mit edu
vinodv @ mit edu
2024-05-31: approved
2024-05-31: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.