[Resource Topic] 2017/1243: Augmented Black-Box Simulation and Zero Knowledge Argument for NP

Welcome to the resource topic for 2017/1243

Augmented Black-Box Simulation and Zero Knowledge Argument for NP

Authors: Li Hongda, Pan Dongxue, Ni Peifang


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.

ePrint: https://eprint.iacr.org/2017/1243

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .