Paper 2013/754

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

Omkant Pandey, Manoj Prabhakaran, and Amit Sahai

Abstract

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!

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
ObfuscationConcurrent Zero KnowledgeNon-black-box Simulation
Contact author(s)
omkant @ uiuc edu
History
2013-11-17: received
Short URL
https://ia.cr/2013/754
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/754,
      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{https://eprint.iacr.org/2013/754}},
      url = {https://eprint.iacr.org/2013/754}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.