Paper 2020/610

Stronger Multilinear Maps from Indistinguishability Obfuscation

Navid Alamati and Hart Montgomery and Sikhar Patranabis

Abstract

We show how to construct new multilinear maps from subexponentially secure indistinguishability obfuscation (iO) and (relatively) 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, joint-SXDH, exponent-DDH and all other assumptions implied by them (including k-party-DDH, 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. A number of recent 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 other relatively standard assumptions) for the first time.

Note: Fixed minor typographical errors