Revision #1 Authors: Oded Goldreich, Silvio Micali.

Accepted on: 9th July 1999 00:00

Downloads: 2838

Keywords:

TR99-024 Authors: Oded Goldreich, Silvio Micali.

Publication: 25th June 1999 19:03

Downloads: 2902

Keywords:

We introduce the notion of Interleaved Zero-Knowledge (iZK),

a new security measure for cryptographic protocols which strengthens

the classical notion of zero-knowledge, in a way suitable for multiple

concurrent executions in an asynchronous environment like the internet.

We prove that iZK protocols are robust: they are ``parallelizable'',

and preserve security when run concurrently in a fully asynchronous network.

Furthermore, this holds even if the prover's random-pads

in all these concurrent invocations are identical.

Thus, iZK protocols are ideal for smart-cards and other devices which

cannot reliably toss coins on-line nor keep state between invocations.

Under general complexity asumptions (which hold

in particular if the Discrete Logarithm Problem is hard),

we construct iZK (computationally-sound) interactive

proofs for all NP languages which run in constant-rounds.

The protocols are in the public key model:

the verifier is assumed to have a public key associated with it.

This implies, concurrent constant-round zero-knowledge

computationally-sound proofs for NP in the public key model,

without resorting to any timing assumptions.

We extend iZK interactive proofs to iZK proofs of identity:

These are methods to prove identity that remain secure even

if the prover can be forced to repeatedly run the identification

protocol on the same coins. All previous ZK proofs of identity

were totally breakable in such case. In particular, this case arises

whenever the prover is realized by means of a device which can be

reset to initial conditions, such as a ``smart card''.

Here, our protocols call for the verifier of identity

(but not the prover) to have an associated public key.

Analgously, we define Interleaved Witness-Indistinguishable (iWI)

protocols which are witness instiguishable even if the prover's

random-pads in all concurrent executions are identical.

Under general complexity assumptions we construct iWI interactive

proofs for all NP languages which run in constant-rounds.

These interactive proofs do not require any public keys,

and make no assumptions about the prover computational ability.

Comment #1 Authors: Oded Goldreich, Silvio Micali

Accepted on: 9th November 1999 16:12

Downloads: 1343

Keywords:

This TR is superseeded by TR99-042.

We note that the term "Resettable Zero-Knowledge" in TR99-042

is exactly what is called in TR99-024 "Interleaved" (or "Rewindable")

Zero-Knowledge.