TY - GEN
T1 - Sum-of-squares meets program obfuscation, revisited
AU - Barak, Boaz
AU - Hopkins, Samuel B.
AU - Jain, Aayush
AU - Kothari, Pravesh
AU - Sahai, Amit
N1 - Funding Information:
Acknowledgements. Boaz Barak was supported by NSF awards CCF 1565264 and CNS 1618026 and a Simons Investigator Fellowship. Samuel B. Hopkins was supported by a Miller Postdoctoral Fellowship and NSF award CCF 1408673. Pravesh Kothari was supported in part by Ma fellowship from the Schmidt Foundation and Avi Wigder-son’s NSF award CCF-1412958. Amit Sahai and Aayush Jain were supported in part from a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. Aayush Jain was also supported by Google PhD Fellowship 2018, in the area of Privacy and Security. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, the U.S. Government or Google.
Funding Information:
Boaz Barak was supported by NSF awards CCF1565264 and CNS1618026 and a Simons Investigator Fellowship. Samuel B. Hopkins was supported by a Miller Postdoctoral Fellowship and NSF award CCF 1408673. Pravesh Kothari was supported in part by Ma fellowship from the Schmidt Foundation and Avi Wigder-son’s NSF award CCF-1412958. Amit Sahai and Aayush Jain were supported in part from a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. Aayush Jain was also supported by Google PhD Fellowship 2018, in the area of Privacy and Security. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, the U.S. Government or Google.
Publisher Copyright:
© International Association for Cryptologic Research 2019.
PY - 2019
Y1 - 2019
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=85065922321&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85065922321&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-17653-2_8
DO - 10.1007/978-3-030-17653-2_8
M3 - Conference contribution
AN - SCOPUS:85065922321
SN - 9783030176525
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 226
EP - 250
BT - Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Ishai, Yuval
A2 - Rijmen, Vincent
PB - Springer Verlag
T2 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Y2 - 19 May 2019 through 23 May 2019
ER -