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!