## Cryptology ePrint Archive: Report 1999/022

**Resettable Zero-Knowledge **

*Ran Canetti, Oded Goldreich, Shafi Goldwasser and Silvio Micali*

**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 adeversary
can interact with the prover many times, each time resetting the
prover to its initial state and forcing him to use the same random
tape.

Under general complexity asumptions, which hold for example if the
Discrete Logarithm Problem is hard, we construct (1) rZK proof-systems
for NP: (2) constant-round resettable witness-indistinguishable
proof-systems for NP; and (3) constant-round rZK arguments for NP in
the 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 a ZK protocols
can be securely implemented, including devices which cannot reliably
toss coins on line, nor keep state betweeen invocations. (For
instance, because ordinary smart cards with secure hardware are
resattable, 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.)

**Category / Keywords: **Zero-Knowledge, Concurrent Zero-Knowledge, Public-Key Cryptography, Witness-Indistinguishable Proofs, Smart Cards, Identification Schemes, Commitment Schemes, Discrete Logarithm Problem.

**Publication Info: **Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

**Date: **received October 25th, 1999. Supercedes Theory of Cryptography Library Record 99-15. Revised, June 22nd, 2000.

**Contact author: **oded at wisdom weizmann ac il

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]