Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR99-024 | 9th July 1999 00:00

Interleaved Zero-Knowledge. Revision of: TR99-024


Revision #1
Authors: Oded Goldreich, Silvio Micali.
Accepted on: 9th July 1999 00:00
Downloads: 2838



TR99-024 | 25th June 1999 00:00

Interleaved Zero-Knowledge in the Public-Key Model.


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 to TR99-024 | 9th November 1999 16:12

Resettable Zero-Knowledge Comment on: TR99-024

Comment #1
Authors: Oded Goldreich, Silvio Micali
Accepted on: 9th November 1999 16:12
Downloads: 1343


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

ISSN 1433-8092 | Imprint