Cryptology ePrint Archive: Report 2016/1096

Indistinguishability Obfuscation from DDH on 5-linear Maps and Locality-5 PRGs

Huijia Lin

Abstract: We present a new construction of Indistinguishability Obfuscation (IO) from the following:

1. asymmetric $L$-linear maps [Boneh and Silverberg, Eprint 2002, Rothblum, TCC 2013] with subexponential Decisional Diffie-Hellman (DDH) assumption,

2. locality-$L$ polynomial-stretch pseudorandom generators (PRG) with subexponential security, and

3. the subexponential hardness of Learning With Errors (LWE).

When plugging in a candidate PRG with locality-5 (eg, [Goldreich, ECCC 2010, O'Donnell and Witmer, CCC 2014]), we obtain a construction of IO from subexponential DDH on 5-linear maps and LWE. Previous IO constructions rely on multilinear maps or graded encodings with higher degrees (at least larger than 30), more complex functionalities (eg, graded encodings with complex label structures), and stronger assumptions (eg, the joint-SXDH assumption).

Category / Keywords: Indistinguishability Obfuscation, 5-linear Maps, Local PRG

Date: received 21 Nov 2016, last revised 23 Nov 2016

Contact author: rachel lin at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Version: 20161123:174919 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]