Paper 2016/1096

Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs

Huijia Lin


Two recent works [Lin, EUROCRYPT 2016, Lin and Vaikuntanathan, FOCS 2016] showed how to construct Indistinguishability Obfuscation (IO) from constant degree multilinear maps. However, the concrete degrees of multilinear maps used in their constructions exceed 30. 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Indistinguishability Obfuscation5-linear MapsLocal PRG
Contact author(s)
rachel lin @ cs ucsb edu
2017-06-24: last of 4 revisions
2016-11-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Huijia Lin},
      title = {Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1096},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.