On the Equivalence of Obfuscation and Multilinear Maps.
Omer Paneth, Amit Sahai · 2015
Garg et al. [FOCS 2013] showed how to construct indistinguishability obfuscation (iO) from a restriction of cryptographic multilinear maps called Multilinear Jigsaw Puzzles. Since then, a num-ber of other works have shown constructions and security analyses for iO from different abstractions of multilinear maps. However, the converse question — whether some form of multilinear maps follows from iO — has remained largely open. We offer an abstraction of multilinear maps called Polynomial Jigsaw Puzzles, and show that iO for circuits implies Polynomial Jigsaw Puzzles. This implication is unconditional: no additional assumptions, such as one-way functions, are needed. Furthermore, we show that this abstraction of Polynomial Jigsaw Puzzles is sufficient to construct iO for NC1, thus showing a near-equivalence of these notions.