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

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!