Paper 2013/754

Obfuscation-based Non-black-box Simulation and Four Message Concurrent Zero Knowledge for NP

Omkant Pandey, Manoj Prabhakaran, and Amit Sahai


As recent studies show, the notions of *program obfuscation* and *zero knowledge* are intimately connected. In this work, we explore this connection further, and prove the following general result. If there exists *differing input obfuscation* (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 diO, our reduction yields an explicit protocol along with an *explicit* simulator that is ``straight line'' and runs in strict polynomial time. Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. In addition to assuming diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions. The round complexity of our protocol also sheds new light on the *exact* round complexity of concurrent zero-knowledge. It shows, for the first time, that in the realm of non-black-box simulation, concurrent zero-knowledge may not necessarily require more rounds than *stand alone* zero-knowledge!

Available format(s)
Publication info
Preprint. Minor revision.
ObfuscationConcurrent Zero KnowledgeNon-black-box Simulation
Contact author(s)
omkant @ uiuc edu
2013-11-17: received
Short URL
Creative Commons Attribution


      author = {Omkant Pandey and Manoj Prabhakaran and Amit Sahai},
      title = {Obfuscation-based Non-black-box Simulation and Four Message Concurrent Zero Knowledge for NP},
      howpublished = {Cryptology ePrint Archive, Paper 2013/754},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.