- 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).)

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.

- 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).

- 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.