Amit Sahai: Obfuscation without multilinear maps

Abstract:

 

Suppose we sample a set of m>>n constant-degree polynomials over n real variables, and evaluate them on a random vector. How hard is it to solve the resulting set of equations over the reals? Such questions have a long history of scientific inquiry; indeed, solving polynomial equations over the reals has been studied by mathematicians, scientists, and engineers for hundreds of years. 

 

In this talk, we show that simple-to-state hardness assumptions closely related to this question, when combined with LWE and bilinear maps, can be used to construct indistinguishability obfuscation for general circuits. In particular, we do not require any assumptions related to multilinear maps.

 

Critical to our work are techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage. In particular, as a byproduct of our work, we obtain a new security amplification theorem for functional encryption.

 

Talk based primarily on joint work with Prabhanjan Ananth and Aayush Jain, and joint work with Aayush Jain.