Cryptology ePrint Archive: Report 2010/150

Black-Box Computational Zero-Knowledge Proofs, Revisited: The Simulation-Extraction Paradigm

Mohammad Sadeq Dousti

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 ``device'' simulating the view of the verifier (or the transcript of the protocol), such that the simulation is indistinguishable from the reality. The definitions differ in many respects, including the type and power of the devices, the order of quantifiers, the type of indistinguishability, and so on.

In this paper, we will scrutinize the definition of ``black-box computational'' zero-knowledge, in which there exists one simulator \emph{for all} verifiers, the simulator has black-box access to the verifier, and the quality of simulation is such that the real and simulated views cannot be distinguished by polynomial tests (\emph{computational} indistinguishability).

Working in a theoretical model (the Random-Oracle Model), we show that the indistinguishability requirement is stated in a \emph{conceptually} inappropriate 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 model, 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}, as opposed to the previous \emph{Simulation 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 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.

Category / Keywords: Zero-Knowledge Proof, Proof of Computational Ability, Proof of Knowledge, Trapdoor One-Way Permutation, Random Oracle, Simulation Paradigm, Simulation-Extraction Paradigm

Publication Info: ---

Date: received 20 Mar 2010, last revised 5 Jun 2011

Contact author: dousti at ce sharif edu

Available format(s): PDF | BibTeX Citation

Version: 20110605:195801 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]