Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP

Omkant Pandey, Manoj Prabhakaran, Amit Sahai

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We show the following result: Assuming the existence of public-coin differing-input obfuscation (pc-diO) for the class of all polynomial time Turing machines, then there exists a four message, fully concurrent zero-knowledge proof system for all languages in NP with negligible soundness error. This result is constructive: given pc-diO,our reduction yields an explicit protocol along with an explicit simulator that is "straight line" and runs in strict polynomial time. The obfuscation security property is used only to prove soundness.Public-coin differing-inputs obfuscation is a notion of obfuscation closely related to indistinguishability obfuscation. Most importantly for our result, pc-diO does not suffer from any known impossibility results: recent negative results on standard differing-inputs obfuscation do not apply to pc-diO. Furthermore, candidate constructions for pc-diO for the class of all polynomial-time Turing Machines are known.Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. We view the development of this new non-black-box simulation technique as the main contribution of our work. In addition to assuming pc-diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Proceedings
EditorsYevgeniy Dodis, Jesper Buus Nielsen
Number of pages30
ISBN (Electronic)9783662464960
StatePublished - 2015
Event12th Theory of Cryptography Conference, TCC 2015 - Warsaw, Poland
Duration: Mar 23 2015Mar 25 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th Theory of Cryptography Conference, TCC 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP'. Together they form a unique fingerprint.

Cite this