Concurrent zero-knowledge
Cynthia Dwork, Moni Naor, Amit Sahai · 1998
Concurrent executions of a zero-knowledge protocol by a ainSle 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-ltnowlcd~e, 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 conntrained in its control over processors' clocks by what we call an (cr,j+constroint for some o < p: for any two processors Pr and Pa, if A measures (Y elapsed time on its local clock nnd Pz measures /3 elapsed time on its local clock, and Pz atarts ajtcr PI does, then P2 will finish after PI does.We obtain four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP.We also address the more apccific problem of Deniable Authentication, for which we propose efilcicnt solutions.