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.
 
 All known examples of zero-knowledge proofs and arguments
 are trivially breakable in this setting. Moreover, by definition,
 all zero-knowledge proofs of knowledge are breakable in this setting.
 Thus, a valid question is whether rZK protocols for non-trivial
 languages exist at all. We answer this question in the affirmative:
 Under general complexity assumptions, which hold for example if the
 Discrete Logarithm Problem is hard, we construct rZK and rWI 
 (resettable Witness Indistinguishable) proof-systems for NP in 
 various models.

 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, 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 so as to foil security. Secondly, rZK protocols
 enlarge the range of physical ways in which provers of ZK protocols
 can be securely implemented, including devices (such as smart cards)
 which have no on-line randomness, nor the ability to keep state between
 invocations.
 
 Joint work with Oded Goldreich, Shafi Goldwasser and Silvio Micali.