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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zero-knowledge proofs (arguments)black-box simulationconstant- roundExact-Cover problemleakage-resilient.
Contact author(s)
pandongxue @ iie ac cn
History
2018-05-04: last of 3 revisions
2017-12-23: received
See all versions
Short URL
https://ia.cr/2017/1243
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1243,
      author = {Li Hongda and Pan Dongxue and Ni Peifang},
      title = {Augmented Black-Box Simulation and Zero Knowledge Argument for NP},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1243},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1243}},
      url = {https://eprint.iacr.org/2017/1243}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.