International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Zero-Knowledge Proofs, Revisited: The Simulation-Extraction Paradigm

Authors:
Mohammad Sadeq Dousti
Rasool Jalili
Download:
URL: http://eprint.iacr.org/2010/150
Search ePrint
Search Google
Abstract: The concept of zero-knowledge proofs has been around for about 25 years. It has been redefined over and over to suit the special security requirements of protocols and systems. Common among all definitions is the requirement of the existence of some efficient machine simulating the view of the verifier (or the transcript of the protocol), such that the simulation is indistinguishable from the reality. In this paper, we will scrutinize the philosophy behind such definition, and show that the indistinguishability requirement is stated in a \emph{conceptually} wrong way: Present definitions allow the knowledge of the \emph{verifier} and \emph{distinguisher} to be independent; while, the two entities are essentially coupled. Therefore, our main take on the problem will be \emph{conceptual} and \emph{semantic}, rather than \emph{literal}. We formalize the concept by introducing a ``knowledge extractor'' into the definition, which tries to extract the extra knowledge hard-coded into the distinguisher (if any), and then helps the simulator to construct the view of the verifier. The new paradigm is termed \emph{Simulation-Extraction Paradigm}. We also provide an important application of the new formalization: Using the simulation-extraction paradigm, we construct one-round (i.e. two-move) zero-knowledge protocols of proving ``the computational ability to invert some trapdoor permutation'' in the Random-Oracle Model. It is shown that the protocol cannot be proven zero-knowledge in the classical \emph{simulation paradigm}. The proof of the zero-knowledge property in the new paradigm is interesting in that it does not require knowing the internal structure of the trapdoor permutation, or a polynomial-time reduction from it to another (e.g. an $\mathcal{NP}$-complete) problem.
BibTeX
@misc{eprint-2010-23051,
  title={Zero-Knowledge Proofs, Revisited: The Simulation-Extraction Paradigm},
  booktitle={IACR Eprint archive},
  keywords={Zero-Knowledge Proof, Proof of Computational Ability, Proof of Knowledge, Trapdoor One-Way Permutation, Random Oracle, Simulation Paradigm, Simulation-Extraction Paradigm},
  url={http://eprint.iacr.org/2010/150},
  note={Extended abstract submitted to FSTTCS 2010 dousti@ce.sharif.edu 14850 received 20 Mar 2010, last revised 29 Aug 2010},
  author={Mohammad Sadeq Dousti and Rasool Jalili},
  year=2010
}