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.Category / Keywords: foundations / Indistinguishability Obfuscation, Bilinear Maps, Block-wise Local PRGs Date: received 16 Mar 2017 Contact author: rachel lin at cs ucsb edu Available format(s): PDF | BibTeX Citation Version: 20170320:142653 (All versions of this report) Short URL: ia.cr/2017/250 Discussion forum: Show discussion | Start new discussion