CryptoDB
Concurrent Zero-Knowledge
| Authors: | |
|---|---|
| Download: | |
| Abstract: | One of the toughest challenges in designing cryptographic protocols is to design them so that they will remain secure even when composed. For example, 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 work we: (1) Suggest time as a mechanism to design concurrent cryptographic protocols and in particular maintaining zero-knowledge under concurrent execution. (2) Introduce the notion of of Deniable Authentication and connect it to the problem of concurrent zero-knowledge. We do not assume global synchronization, however we assume 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 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 show that for an adversary controlling all the processors clocks (as well as their communication channels) but which is constrained by an (alpha,beta) constraint 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, i.e., in the standard model. |
BibTeX
@misc{eprint-1999-11343,
title={Concurrent Zero-Knowledge},
booktitle={IACR Eprint archive},
keywords={Zero-Knowledge, Concurrent Zero-Knowledge, Concurrency, Deniable Authentication, Non-Malleability.},
url={http://eprint.iacr.org/1999/023},
note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. naor@wisdom.weizmann.ac.il 10500 received November 22nd, 1999. This is the full version of the STOC 1998 paper.},
author={Cynthia Dwork and Moni Naor and Amit Sahai},
year=1999
}