Paper 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).