Paper 2017/1243

Augmented Black-Box Simulation and Zero Knowledge Argument for NP

Li Hongda, Pan Dongxue, and Ni Peifang

Abstract

The standard zero knowledge notion is formalized by requiring that for any probabilistic polynomial-time (PPT) verifier $V^*$, there is a PPT algorithm (simulator) $S_{V^*}$, such that the outputs of $S_{V^*}$ is indistinguishable from real protocol views. The simulator is not permitted to access the verifier $V^*$'s private state. So the power of $S_{V^*}$ is, in fact, inferior to that of $V^*$. In this paper, a new simulation method, called augmented black-box simulation, is presented by permitting the simulator to have access to the verifier's current private state in a special manner. The augmented black-box simulator only has the same computing power as the verifier although it is given access to the verifier's current private state. Therefore, augmented black-box simulation is a reasonable method to prove zero knowledge property, and brings results that hard to obtain with previous simulation techniques. Zero knowledge property, proved by means of augmented black-box simulation, is called augmented black-box zero-knowledge. We present a 5-round statistical augmented black-box zero-knowledge argument for Exact Cover Problem under the Decision Multilinear No-Exact-Cover Assumption. In addition, we show a 2-round computational augmented black-box zero-knowledge argument protocol for Exact Cover problem under the Decision Multilinear No-Exact-Cover Assumption and the assumption of the existence of hash functions. It is well known that 2-round zero knowledge protocols does not exist under general zero knowledge notion. Besides, following [19], we consider leakage-resilient property of augmented black-box zero knowledge, and prove that the presented statistical zero-knowledge protocol has optimal leakage-resilient property.