Concurrent Zero-Knowledge

Concurrent executions of a zero-knowledge protocol by a single prover (with one or more veriers) may leak information and may not be zero-knowledge in toto. In this paper, we study the problem of maintaining zero-knowledge We introduce the notion of an (; ) timing constraint: 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 nish after P1 does. We show that if the adversary is constrained by an (; ) 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 specic problem of Deniable Authentication, for which we propose several particularly ecient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing..