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.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.FOCS 2016
Keywords
Contact author(s)
rachel lin @ cs ucsb edu
History
2017-08-31: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/795

CC BY

BibTeX

@misc{cryptoeprint:2016/795,
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{https://eprint.iacr.org/2016/795}},
url = {https://eprint.iacr.org/2016/795}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.