Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model
We show that interactive and noninteractive zero-knowledge are equivalent in the ‘help model’ of Ben-Or and Gutfreund (J. Cryptology, 2003). In this model, the shared reference string is generated by a probabilistic polynomial-time dealer who is given acc
- PDF / 745,383 Bytes
- 34 Pages / 430 x 660 pts Page_size
- 110 Downloads / 147 Views
niversit´e Paris-Sud, Orsay, France {andre.chailloux,jkeren}@lri.fr School of Engineering and Applied Sciences, Harvard University, Cambridge, MA {ciocan,salil}@eecs.harvard.edu
Abstract. We show that interactive and noninteractive zero-knowledge are equivalent in the ‘help model’ of Ben-Or and Gutfreund (J. Cryptology, 2003). In this model, the shared reference string is generated by a probabilistic polynomial-time dealer who is given access to the statement to be proven. Our results do not rely on any unproven complexity assumptions and hold for statistical zero knowledge, for computational zero knowledge restricted to AM, and for quantum zero knowledge when the help is a pure quantum state. Keywords: cryptography, computational complexity, noninteractive zero-knowledge proofs, commitment schemes, Arthur–Merlin games, quantum zero knowledge.
1
Introduction
Zero-knowledge proofs [4] are protocols whereby a prover can convince a verifier that some assertion is true with the property that the verifier learns nothing else from the protocol. This remarkable property is easily seen to be impossible for the classical notion of a proof system, where the proof is a single string sent from the prover to the verifier, as the proof itself constitutes ‘knowledge’ that the verifier could not have feasibly generated on its own (assuming NP ⊆ BPP). Thus zero-knowledge proofs require some augmentation to the classical model for proof systems. The original proposal of Goldwasser, Micali, and Rackoff [4] augments the classical model with both randomization and multiple rounds of interaction between
Preliminary versions of this work previously appeared on the Cryptology ePrint Archive [1,2], and in the second author’s undergraduate thesis [3]. Supported in part by ACI Securit´e Informatique SI/03 511 and ANR AlgoQP grants of the French Ministry and in part by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848. Supported by NSF Grant CNS-0430336. Some of this work was done when the S. Vadhan was visiting U.C. Berkeley, supported by a Guggenheim Fellowship and the Miller Institute for Basic Research in Science.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 501–534, 2008. c International Association for Cryptologic Research 2008
502
A. Chailloux et al.
the prover and the verifier, leading to what are called interactive zero-knowledge proofs, or simply zero-knowledge proofs. An alternative model, proposed by Blum, Feldman, and Micali [5,6], augments the classical model with a set-up in which a trusted dealer randomly generates a reference string that is shared between the prover and verifier. After this reference string is generated, the proof consists of a single message from the prover to the verifier. Thus, these are referred to as noninteractive zero-knowledge proofs. Since their introduction, there have been many constructions of both interactive and noninteractive zero-knowledge proofs, and both models have found numerous applications in
Data Loading...
