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