Ran Canetti, Oded Goldreich, S. Goldwasser, Silvio Micali
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape. Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct (non-constant round) Resettable Zero-Knowledge proof-systems for NP constant-round Resettable Witness-Indistinguishable proof-systems for NP constant-round Resettable Zero-Knowledge arguments for NP in the public key model: where veriers have fixed, public keys associated with them. In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications. Firstly, we show that rZK protocols are closed under parallel and
A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he “knows” the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. In this paper, we investigate the concept of a zero-knowledge proof of knowledge in the noninteractive model of [5, 61. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zeroknowledge proofs of knowledge is a delicate task. The main results of the paper are the following e We present formal definitions for the concept of non-interactive zero-knowledge proofs