Indistinguishability Obfuscation from Well-Founded Assumptions

URL: https://dl.acm.org/doi/10.1145/3406325.3451093 Authors: Aayush Jain, Huijia Lin, Amit Sahai

Abstract

In this work, we show how to construct indistinguishability obfuscation (iO) from the sub-exponential security of four well-studied hardness assumptions: the Learning With Errors (LWE) assumption, the Learning Parity with Noise (LPN) assumption, an assumption about the existence of a Boolean Pseudorandom Generator (PRG) in ${\mathsf{NC}}^1$, and the decision Diffie-Hellman (DDH) assumption over specific groups. This gives the first construction of iO from assumptions that do not involve multilinear maps or other newly-introduced objects.

BibTeX

Copy

@Inproceedings{STOC:JaiLinSah21,
  author = {Aayush Jain and Huijia Lin and Amit Sahai},
  title = {Indistinguishability obfuscation from well-founded assumptions},
  pages = {60--73},
  editor = {Samir Khuller and Virginia Vassilevska Williams},
  booktitle = {53rd Annual {ACM} Symposium on Theory of Computing},
  address = {Virtual Event, Italy},
  month = {jun~21--25},
  publisher = {{ACM} Press},
  year = {2021},
  doi = {10.1145/3406325.3451093},
}