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: ia.cr/2016/1096 Discussion forum: Show discussion | Start new discussion