TY  - JOUR
T1  - Concurrent zero-knowledge.
JF  - Journal of the ACM
A1  - Dwork, Cynthia
LA  - English
UL  - https://tuklas.up.edu.ph/Record/UP-99796217608727323
AB  - 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 (α, β) 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 finish 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 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.
KW  - Data.
KW  - Data encryption.
KW  - Public key cryptosystems.
KW  - Theory of computation.
KW  - Computation by abstract devices.
KW  - Modes of computation.
KW  - Parallelism and concurrency.
KW  - Analysis of algorithms and problem complexity.
KW  - Algorithms.
KW  - Security.
KW  - Theory.
ER  -