International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Sum-of-Squares Meets Program Obfuscation, Revisited

Authors:
Boaz Barak
Samuel B. Hopkins
Aayush Jain
Pravesh Kothari
Amit Sahai
Download:
DOI: 10.1007/978-3-030-17653-2_8
Search ePrint
Search Google
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).
BibTeX
@article{eurocrypt-2019-29336,
  title={Sum-of-Squares Meets Program Obfuscation, Revisited},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11476},
  pages={226-250},
  doi={10.1007/978-3-030-17653-2_8},
  author={Boaz Barak and Samuel B. Hopkins and Aayush Jain and Pravesh Kothari and Amit Sahai},
  year=2019
}