Cryptology ePrint Archive: Report 2017/250

Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs

Huijia Lin and Stefano Tessaro

Abstract: We consider the question of finding the lowest degree $L$ for which $L$-linear maps suffice to obtain IO. The current state of the art (Lin, EUROCRYPT'16, CRYPTO '17; Lin and Vaikunthanathan, FOCS'16; Ananth and Sahai, EUROCRYPT '17) is that $L$-linear maps (under suitable security assumptions) suffice for IO, assuming the existence of pseudo-random generators (PRGs) with output locality $L$. However, these works cannot answer the question of whether $L < 5$ suffices, as no polynomial-stretch PRG with locality lower than $5$ exists.

In this work, we present a new approach that relies on the existence of PRGs with block-wise locality $L$, i.e., every output bit depends on at most $L$ (disjoint) input blocks, each consisting of up to $\log \lambda$ input bits. We show that the existence of PRGs with block-wise locality is plausible for any $L \geq 3$, and also provide:

* 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, and follow by instantiating our new generic bootstrapping theorems with Lin's recently proposed FE scheme (CRYPTO '17). Inherited from Lin's work, our security proof requires algebraic multilinear maps (Boneh and Silverberg, Contemporary Mathematics), whereas security when using noisy multilinear maps is based on a family of more complex assumptions that hold in the generic model. Our candidate PRGs with block-wise locality are based on Goldreich's local functions, and we show that the security of instantiations with block-wise locality $L \ge 3$ is backed by similar validation as constructions with (conventional) locality $5$. We further complement this with hardness amplification techniques that further weaken the pseudorandomness requirements.

Category / Keywords: Indistinguishability Obfuscation, triinear Maps, Block-wise Local PRG

Date: received 16 Mar 2017, last revised 23 Jun 2017

Contact author: rachel lin at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Version: 20170624:044439 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]