Paper 2018/1237

Sum-of-Squares Meets Program Obfuscation, Revisited

Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, and Amit Sahai

Abstract

We develop attacks on the security of variants of pseudo-random generators computed by quadratic polynomials. In particular we give a general condition for breaking the one-way property of mappings where every output is a quadratic polynomial (over the reals) of the input. As a corollary, we break the degree-2 candidates for security assumptions recently proposed for constructing indistinguishability obfuscation by Ananth, Jain and Sahai (ePrint 2018) and Agrawal (ePrint 2018). We present conjectures that would imply our attacks extend to a wider variety of instances, and in particular offer experimental evidence that they break assumption of Lin-Matt (ePrint 2018). Our algorithms use semidefinite programming, and in particular, results on low-rank recovery (Recht, Fazel, Parrilo 2007) and matrix completion (Gross 2009).

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
Sum-of-SquaresIndistinguishability Obfuscation
Contact author(s)
b @ boazbarak org
hopkins @ berkeley edu
aayushjainiitd @ gmail com
kothari @ cs princeton edu
sahai @ cs ucla edu
History
2019-04-01: revised
2018-12-31: received
See all versions
Short URL
https://ia.cr/2018/1237
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1237,
      author = {Boaz Barak and Samuel B.  Hopkins and Aayush Jain and Pravesh Kothari and Amit Sahai},
      title = {Sum-of-Squares Meets Program Obfuscation, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1237},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1237}},
      url = {https://eprint.iacr.org/2018/1237}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.