Abstract
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 an (α, β)-constraint for some α<β: for any two processors P1 and P2, if P1 measures α elapsed time on its local clock and P2 measures β elapsed time on its local clock, and P2 starts after P1 does, then P2 will finish after P1 does. We obtain four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in N P. We also address the more specific problem of Deniable Authentication, for which we propose efficient solutions.