**Augmented Black-Box Simulation and Zero Knowledge Argument for NP**

*Li Hongda and 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.

**Category / Keywords: **cryptographic protocols / zero-knowledge proofs (arguments), black-box simulation, constant- round, Exact-Cover problem, leakage-resilient.

**Date: **received 22 Dec 2017, last revised 4 May 2018

**Contact author: **pandongxue at iie ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20180504:080601 (All versions of this report)

**Short URL: **ia.cr/2017/1243

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]