Paper 2020/610

Stronger Multilinear Maps from Indistinguishability Obfuscation

Navid Alamati, Hart Montgomery, and Sikhar Patranabis

Abstract

We show how to construct new multilinear maps from subexponentially secure indistinguishability obfuscation (iO) and standard assumptions. In particular, we show how to construct multilinear maps with arbitrary predetermined degree of multilinearity where each of the following assumptions hold: SXDH, exponent-DDH (for both symmetric and asymmetric multilinear maps), and all other assumptions implied by these assumptions (including k-party-DDH and k-Lin and its variants). Our constructions almost identically achieve the full functionality of the “dream version” definition of multilinear maps as defined in the initial work of Garg et al. (Eurocrypt’13). Our work substantially extends a previous line of works including that of Albrecht et al. (TCC’16) and Farshim et al. (PKC’18), which showed how to build multilinear maps endowed with weaker assumptions (such as multilinear DDH and other related assumptions) from iO. Coupled with the exciting breakthrough work of Jain et al. (STOC’21), which shows how to build iO from well-founded assumptions, and the works of Gay et al. (STOC’21) and Brakerski et al., which show how to build iO from circular security assumptions, our work can be used to build strong multilinear maps from such assumptions. This at least partially solves another long-standing open problem about the existence of cryptographic multilinear maps for degree > 2. Moreover, a number of works have shown how to build iO from multilinear maps endowed with hardness assumptions; one example would be the work of Lin and Tessaro (Crypto’17) which shows how to construct iO from subexponentially secure SXDH-hard multilinear maps and some (subexponentially secure) plausible assumptions. Coupled with any one of these constructions, our results here can be seen as formally proving the equivalence of iO and multilinear maps/graded encodings (modulo subexponential reductions and standard assumptions, some of which must have subexponential security) for the first time. Finally, our results also establish the equivalence of many multilinear maps of different degrees and even with different assumptions (again modulo subexponential reductions and other relatively standard assumptions): if a multilinear map is powerful enough to build iO, then it can also be used to build all of the maps that we construct here.

Note: We thank the anonymous reviewers of TCC'21 for pointing out certain flaws in our core construction and proof arguments. We acknowledge these issues and are withdrawing our paper, including the main claims/results. We hope to post an update once we have managed to fix these issues.