Webpage for a paper by Ran Canetti, Oded Goldreich,
Shafi Goldwasser and Silvio Micali
Versions available on-line
and related work (below).
original version, 1999.
(This version contains some errors corrected in the next versions.)
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.)
``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:
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.)
- (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).
Related work available on-line
- O. Goldreich, S. Goldwasser and S. Micali,
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,
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).
either Oded Goldreich's homepage.
or general list of papers.