Cryptology ePrint Archive: Report 2016/795

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

Huijia Lin and Vinod Vaikuntanathan

Abstract: 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.

Category / Keywords: foundations / Obfuscation, Constant-Degree Graded Encoding Schemes, SXDH

Original Publication (with major differences): FOCS 2016

Date: received 19 Aug 2016, last revised 31 Aug 2017

Contact author: rachel lin at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Version: 20170831:131738 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]