Resettable Zero-Knowledge

Webpage for a paper by Ran Canetti, Oded Goldreich, Shafi Goldwasser and Silvio Micali

Versions available on-line

The original version, 1999. (This version contains some errors corrected in the next versions.)
The version that I prefer, 2000. (This version focuses on the construction of rZK (and rWI) protocol via a transformation of known protocols from the concurrent model to the resettable model.)
An ``official'' revision, 2000. (This version focusses on providing a self-contained proof for the main result (i.e., rZK for NP).)

Abstract

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) rZK proof-systems for NP.
constant-round resettable witness-indistinguishable (rWI) proof systems for NP.
constant-round rZK arguments for NP in a (weak) public-key model where verifiers 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 concurrent execution, and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent. Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state between invocations. (For instance, because ordinary smart cards with secure hardware are resettable, they could not be used to implement securely the provers of classical ZK protocols, but can now be used to implement securely the provers of rZK protocols.)

Errata

The original version contains two main inaccuracies: First, the argument provided for the rWI scheme contains a gap. Second, the description of the simulator of the RK-protocol (which follows the description of [RK]) is not correct. Both errors are corrected in the revised versions.
The proof of the validity of the main transformation (of admissible protocols to resettable ones) contains a small gap. One should note that the ``determining'' condition (i.e., 3rd condition) in the definition of admissibility (which is stated in the standard single-invocation setting) holds also in the resettable setting. Towards this end, one has to rely on the convention by which the paper considers only presecribed prover strategies that can be implemented in probabilistic polynomial-time (with suitable auxiliary inputs). [Pointed out by Yehuda Lindell]
In the definition of rZK (and rWI) one has to require that the sequence of common input contains distinct strings. The analysis of the transformation of admissible protocols secure in the hybrid model to resettably-secure protocols assumes that the common inputs are distinct. It seems that this requirement is essential for the non-triviality of rZK, and that no protocol can achieve the stronger definition (in which some of the $x_i$'s may be equal whereas the corresponding auxiliary $y_i$'s may be either equal or not).

Related work available on-line

O. Goldreich, S. Goldwasser and S. Micali, Interleaved Zero-Knowledge in the Public-Key Model, 1999.
This is a preliminary version of the current work, which presents a constant-round rWI for NP and a constant-round rZK for NP in the public-key model. The existence of rZK for NP in the vanilla model is left as an open problem, which is resolved in the current work.
B. Barak, O. Goldreich, S. Goldwasser and Y. Lindell, Resettably-Sound Zero-Knowledge and its Applications, 2001.
This is a follow-up work in which the notion of resettability is applied to the verifier (rather than to the prover), and the concern is preservation of soundness (rather than of zero-knowledge).

Back to either Oded Goldreich's homepage. or general list of papers.