International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Boaz Barak

Publications

Year
Venue
Title
2019
EUROCRYPT
Sum-of-Squares Meets Program Obfuscation, Revisited
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).
2018
EUROCRYPT
2017
JOFC
2014
EUROCRYPT
2014
TCC
2011
CRYPTO
2011
JOFC
2010
EUROCRYPT
2009
CRYPTO
2008
EUROCRYPT
2005
CRYPTO
2004
TCC
2003
CHES
2003
CRYPTO
2001
CRYPTO

Program Committees

TCC 2013
TCC 2011
Crypto 2008
TCC 2008
Crypto 2006
Crypto 2005
TCC 2005