Paper 2016/795 Original: eprint.iacr.org/2016/795 ↗
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 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
- Preprint.
- History
- 2017-08-31: last updated
- 2016-08-20: published
- Short URL
- https://ia.cr/2016/795
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}