Revision #1 Authors: Ran Canetti, Oded Goldreich, Silvio Micali.

Accepted on: 7th June 2000 00:00

Downloads: 1733

Keywords:

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.

Under general complexity assumptions, which hold

for example if the Discrete Logarithm Problem is hard, we construct:

rZK proof-systems for NP with non-constant number of rounds,

five-round Resettable Witness-Indistinguishable proof-systems for NP,

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

TR99-042 Authors: Ran Canetti, Oded Goldreich, Silvio Micali.

Publication: 27th October 1999 18:05

Downloads: 1667

Keywords:

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