In this work, we reduce the degree of multilinear maps needed to 5, by giving a new construction of IO from asymmetric $L$-linear maps and a pseudo-random generator (PRG) with output locality $L$ and polynomial stretch. When plugging in a candidate PRG with locality-$5$ (\eg, [Goldreich, ECCC 2010, Mossel, Shpilka, and Trevisan, FOCS 2013, O'Donnald and Wither, CCC 2014]), we obtain a construction of IO from 5-linear maps.
Our construction improves the state-of-the-art at two other fronts: First, it relies on ``classical'' multilinear maps, instead of their powerful generalization of graded encodings. Second, it comes with a security reduction to i) the SXDH assumption on algebraic multilinear maps [Boneh and Silverberg, Contemporary Mathematics, Rothblum, TCC 2013], ii) the security of PRG, and iii) sub-exponential LWE, all with sub-exponential hardness. The SXDH assumption is weaker and/or simpler than assumptions on multilinear maps underlying previous IO constructions. When noisy multilinear maps [Garg, Gentry, and Halivi, EUROCRYPT 2013] are used instead, security is based on a family of more complex assumptions that hold in the generic model.
Category / Keywords: Indistinguishability Obfuscation, 5-linear Maps, Local PRG Date: received 21 Nov 2016, last revised 23 Jun 2017 Contact author: rachel lin at cs ucsb edu Available format(s): PDF | BibTeX Citation Version: 20170624:045647 (All versions of this report) Short URL: ia.cr/2016/1096 Discussion forum: Show discussion | Start new discussion