Sum-of-Squares Meets Program Obfuscation, Revisited

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

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-Squares Indistinguishability 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: 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},
      url = {https://eprint.iacr.org/2018/1237}
}