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