# Concurrent Zero-Knowledge

or

The Timing Model for Designing Concurrent Protocols

### Cynthia Dwork, Moni Naor and Amit Sahai

### 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 (*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
.

#####
Related On-Line Papers:

Back to On-Line Publications

Back Home