Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / multilinear maps, indistinguishability obfuscation

Date: received 23 May 2020, last revised 5 Jun 2020

Contact author: sikharpatranabis at gmail com

Available format(s): PDF | BibTeX Citation

Note: Fixed minor typographical errors

Version: 20200605:143403 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]