Sum-of-squares meets program obfuscation, revisited

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

doi:10.1007/978-3-030-17653-2_8

Sum-of-squares meets program obfuscation, revisited

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

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

Original language	English (US)
Title of host publication	Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Yuval Ishai, Vincent Rijmen
Publisher	Springer Verlag
Pages	226-250
Number of pages	25
ISBN (Print)	9783030176525
DOIs	https://doi.org/10.1007/978-3-030-17653-2_8
State	Published - 2019
Externally published	Yes
Event	38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany Duration: May 19 2019 → May 23 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11476 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Country/Territory	Germany
City	Darmstadt
Period	5/19/19 → 5/23/19

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-17653-2_8

Cite this

Barak, B., Hopkins, S. B., Jain, A., Kothari, P., & Sahai, A. (2019). Sum-of-squares meets program obfuscation, revisited. In Y. Ishai, & V. Rijmen (Eds.), Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 226-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11476 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-17653-2_8

Barak, Boaz ; Hopkins, Samuel B. ; Jain, Aayush et al. / Sum-of-squares meets program obfuscation, revisited. Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Yuval Ishai ; Vincent Rijmen. Springer Verlag, 2019. pp. 226-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{45a39fdbe23c4d52a15ca9f0b9143222,

title = "Sum-of-squares meets program obfuscation, revisited",

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).",

author = "Boaz Barak and Hopkins, {Samuel B.} and Aayush Jain and Pravesh Kothari and Amit Sahai",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2019.; 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 ; Conference date: 19-05-2019 Through 23-05-2019",

year = "2019",

doi = "10.1007/978-3-030-17653-2_8",

language = "English (US)",

isbn = "9783030176525",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "226--250",

editor = "Yuval Ishai and Vincent Rijmen",

booktitle = "Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Germany",

}

Barak, B, Hopkins, SB, Jain, A, Kothari, P & Sahai, A 2019, Sum-of-squares meets program obfuscation, revisited. in Y Ishai & V Rijmen (eds), Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11476 LNCS, Springer Verlag, pp. 226-250, 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019, Darmstadt, Germany, 5/19/19. https://doi.org/10.1007/978-3-030-17653-2_8

Sum-of-squares meets program obfuscation, revisited. / Barak, Boaz; Hopkins, Samuel B.; Jain, Aayush et al.
Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Yuval Ishai; Vincent Rijmen. Springer Verlag, 2019. p. 226-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11476 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Barak B, Hopkins SB, Jain A, Kothari P, Sahai A. Sum-of-squares meets program obfuscation, revisited. In Ishai Y, Rijmen V, editors, Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer Verlag. 2019. p. 226-250. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17653-2_8

Sum-of-squares meets program obfuscation, revisited

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this