Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. FOCS 2016
- Keywords
- ObfuscationConstant-Degree Graded Encoding SchemesSXDH
- Contact author(s)
- rachel lin @ cs ucsb edu
- History
- 2017-08-31: last of 2 revisions
- 2016-08-20: received
- See all versions
- Short URL
- https://ia.cr/2016/795
- License
-
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},
url = {https://eprint.iacr.org/2016/795}
}
