Cryptology ePrint Archive: Report 2013/754

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

Omkant Pandey and 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!

Category / Keywords: foundations / Obfuscation, Concurrent Zero Knowledge, Non-black-box Simulation

Date: received 14 Nov 2013

Contact author: omkant at uiuc edu

Available format(s): PDF | BibTeX Citation

Version: 20131117:022017 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]