Paper 2016/281

Universal Obfuscation and Witness Encryption: Boosting Correctness and Combining Security

Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai, and Eylon Yogev


Over the last few years a new breed of cryptographic primitives has arisen: on one hand they have previously unimagined utility and on the other hand they are not based on simple to state and tried out assumptions. With the on-going study of these primitives, we are left with several different candidate constructions each based on a different, not easy to express, mathematical assumptions, where some even turn out to be insecure. A {\em combiner} for a cryptographic primitive takes several candidate constructions of the primitive and outputs one construction that is as good as any of the input constructions. Furthermore, this combiner must be efficient: the resulting construction should remain polynomial-time even when combining polynomially many candidate. Combiners are especially important for a primitive where there are several competing constructions whose security is hard to evaluate, as is the case for indistinguishability obfuscation (IO) and witness encryption (WE). One place where the need for combiners appears is in design of a {\em universal construction}, where one wishes to find ``one construction to rule them all": an explicit construction that is secure if {\em any} construction of the primitive exists. In a recent paper, Goldwasser and Kalai posed as a challenge finding universal constructions for indistinguishability obfuscation and witness encryption. In this work we resolve this issue: we construct universal schemes for IO, and for witness encryption, and also resolve the existence of combiners for these primitives along the way. For IO, our universal construction and combiners can be built based on \emph{either} assuming DDH, or assuming LWE, with security against subexponential adversaries. For witness encryption, we need only one-way functions secure against polynomial time adversaries.

Available format(s)
Publication info
Published elsewhere. Minor revision. CRYPTO 2016
Indistinguishability ObfuscationWitness EncryptionCombinersUniversal ConstructionsCorrectness Amplifiers
Contact author(s)
prabhanjan va @ gmail com
2016-08-31: revised
2016-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Aayush Jain and Moni Naor and Amit Sahai and Eylon Yogev},
      title = {Universal Obfuscation and Witness Encryption: Boosting Correctness and Combining Security},
      howpublished = {Cryptology ePrint Archive, Paper 2016/281},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.