Paper 2016/795

Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings

Huijia Lin and Vinod Vaikuntanathan


All constructions of general purpose indistinguishability obfuscation (IO) rely on either meta-assumptions that encapsulate an exponential family of assumptions (e.g., Pass, Seth and Telang, CRYPTO 2014 and Lin, EUROCRYPT 2016), or polynomial families of assumptions on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry, Lewko, Sahai and Waters, FOCS 2014). We present a new construction of IO, with a security reduction based on two assumptions: (a) a DDH-like assumption — called the joint-SXDH assumption — on constant degree graded en- codings, and (b) the existence of polynomial-stretch pseudorandom generators (PRG) in NC0. Our assumption on graded encodings is simple, has constant size, and does not require handling composite-order rings. This narrows the gap between the mathematical objects that exist (bilinear maps, from elliptic curve groups) and ones that suffice to construct general purpose indistinguishability obfuscation.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.FOCS 2016
ObfuscationConstant-Degree Graded Encoding SchemesSXDH
Contact author(s)
rachel lin @ cs ucsb edu
2017-08-31: last of 2 revisions
2016-08-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Huijia Lin and Vinod Vaikuntanathan},
      title = {Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings},
      howpublished = {Cryptology ePrint Archive, Paper 2016/795},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.