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

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
Zero-KnowledgeConcurrent Zero-KnowledgePublic-Key CryptographyWitness-Indistinguishable ProofsSmart CardsIdentification SchemesCommitment SchemesDiscrete Logarithm Problem.
Contact author(s)
oded @ wisdom weizmann ac il
History
2000-06-22: revised
1999-10-25: received
Short URL
https://ia.cr/1999/022
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1999/022,
      author = {Ran Canetti and Oded Goldreich and Shafi Goldwasser and Silvio Micali},
      title = {Resettable Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 1999/022},
      year = {1999},
      note = {\url{https://eprint.iacr.org/1999/022}},
      url = {https://eprint.iacr.org/1999/022}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.