Huijia Rachel Lin, University of California, Santa Barbara

Abstract

Mutlilinear maps are extremely powerful objects that imply the holy grail of general purpose indistinguishability obfuscation (IO). A fundamental goal is identifying the lowest degree of multilinearity that suffice for constructing IO, answering, in particular, whether bilinear maps are sufficient for IO, and if not what is the magic degree that makes the important difference. The state-of-the-art (Lin, EUROCRYPT'16, ePrint'16; Lin and Vaikunthanathan, FOCS'16; Ananth and Sahai, EUROCRYPT'17) is that assuming the existence of pseudo-random generators (PRG) with output locality L, L-linear maps suffice for constructing IO. However, these works do not shed light on the power of multilinear maps with degree L < 5, as no polynomial-stretch PRG with locality lower than 5 exists.

In this work, we make progress towards the fundamental goal by showing that trilinear maps are sufficient for constructing IO, assuming the existence of PRGs with block-wise locality 3 and subexponential LWE. A PRG has block-wise locality L if every output bit depends on at most L (disjoint) input blocks, each consisting of up to log λ input bits. Concretely, we give:

A construction of a general-purpose indistinguishability obfuscator from L-linear maps and a subexponentially-secure PRG with block-wise locality L and polynomial stretch.

A construction of general-purpose functional encryption from L-linear maps and any slightly super-polynomially secure PRG with block-wise locality L and polynomial stretch.

All our constructions are based on the SXDH assumption on L-linear maps and subexponential Learning With Errors (LWE) assumption.

Concurrently, we initiate the study of candidate PRGs with block-wise locality based on Goldreich's local functions, and their (in)security. In particular, we show that the security of instantiations with block-wise locality L ≥ 3 is backed by similar validation as constructions with (conventional) locality 5. We further complement this with hardness amplification techniques that weaken the pseudorandomness requirement on our candidates to qualitatively weaker requirements.

Our result implies that any advance in instantiating multilinear maps beyond the bilinear case would lead to the holy grail of IO. We leave open the question whether bilinear maps are sufficient for IO or trilinear maps are inherently needed.

Slides    Video