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 - 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 -