Indistinguishability Obfuscation from Simpler Graded Encodings Schemes

Graded encoding schemes [Garg et al. EUROCRYPT 2013] play a central role in constructing general purpose indistinguishability obfuscation (IO). Up until recently, all known IO schemes rely on either meta-assumptions that encapsulates an exponential family of assumptions (e.g., Pass et al. Crypto 2014), or polynomial families of assumptions on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry et al. FOCS 2014).

 

In this talk, we present two recent works on simplifying graded encodings needed for constructing IO [Lin EUROCRYPT 2016 and Lin-Vankuntanathan FOCS 2016]. In sum,  IO can be constructed from only constant-degree graded encodings, with a security reduction to a DDH-like assumption — called the joint-SXDH assumption — on the graded encodings, and the sub-exponential security of a polynomial-stretch 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 IO.