Paper 2017/250

Indistinguishability Obfuscation from Bilinear Maps and Block-Wise Local PRGs

Huijia Lin and Stefano Tessaro

Abstract

Recent works (Lin, EUROCRYPT'16, ePrint'16; Lin and Vaikunthanathan, FOCS'16; Ananth and Sahai, EUROCRYPT'17) establish a tight connection between constructions of indistinguishability obfuscation from $L$-linear maps and pseudo-random generators (PRGs) with output locality $L$. This approach appears however not to be suitable to obtain instantiations from bilinear maps, as no polynomial-stretch PRG with locality lower than 5 exists. This paper presents new candidate constructions of indistinguishability obfuscation from (i) $L$-linear maps for any $L \ge 2$, and (ii) PRGs with block-wise locality $L$. 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 \lambda$ input bits. In particular, 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. In the special case of $L = 2$, our constructions can be alternatively based on bilinear maps with the Matrix Diffie-Hellman assumption and the 3-party Decision Diffie Hellman assumption, without assuming LWE. Concurrently, we initiate the study of candidate PRGs with block-wise locality $L\ge 2$ based on Goldreich's local functions, and their security. In particular, lower bounds on the locality of PRGs do not apply to block-wise locality for any $L \ge 2$, and the security of instantiations with block-wise locality $L \ge 3$ is backed by similar validation as constructions with (conventional) locality $5$. We complement this with hardness amplification techniques that weaken the pseudorandomness requirement on our candidates to qualitatively weaker requirements.