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.
Category / Keywords: Zero-Knowledge, Concurrent Zero-Knowledge, Concurrency, Deniable Authentication, Non-Malleability. Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Date: received November 22nd, 1999. This is the full version of the STOC 1998 paper. Contact author: naor at wisdom weizmann ac il Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Discussion forum: Show discussion | Start new discussion