Cryptology ePrint Archive: Report 2018/1237

Sum-of-Squares Meets Program Obfuscation, Revisited

Boaz Barak and Samuel B. Hopkins and Aayush Jain and 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).

Category / Keywords: Sum-of-Squares, Indistinguishability Obfuscation

Date: received 24 Dec 2018, last revised 1 Apr 2019

Contact author: b at boazbarak org,hopkins@berkeley edu,aayushjainiitd@gmail com,kothari@cs princeton edu,sahai@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20190401:081038 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]