Concurrent zero-knowledge

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. In this article, we study the problem of maintaining zero-knowledge We introduce the notion of an (alpha, beta) timing constraint: for any two processors P-1 and P-2, if P-1 measures alpha elapsed time on its local clock and P-2 measures elapsed time on its local clock, and P-2 starts after P-1 does, then P-2 will finish after P-1 does. We show that if the adversary is constrained by an (alpha, beta) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP. We also address the more specific problem of Deniable Authentication, for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing, that is, in the standard model.