Title: Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings
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 sSXDH assumption - on constant degree graded encodings, 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.
Publication Year: 2016
Publication Date: 2016-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 104
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot