Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto; for example, in the case of zero-knowledge interactive proofs or arguments, the interactions remain proofs but may fail to remain zero-knowledge. This paper addresses the problem of achieving concurrent zero-knowledge.
We introduce timing in order to obtain zero-knowledge in concurrent executions. We assume that the adversary is constrained in its control over processors' clocks by what we call (alpha,beta)-constraint for some alpha< beta: for any two processors P_1 and P_2, if P_1 measures alpha elapsed time on its local clock and P_2 measures beta elapsed time on its local clock, and P_2 starts after P_1 does, then P_2 will finish after P_1 does. We obtain four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP. (Without the timing assumption we are limited by an impossibility result of Kilian et al., FOCS 98). We also address the more specific problem of Deniable Authentication, for which we propose efficient solutions allowing concurrent executions.
Postscript , gzipped Postscript .