Welcome to the resource topic for 2001/104
Concurrent Zero-Knowledge With Timing, Revisited
Authors: Oded GoldreichAbstract:
Following Dwork, Naor, and Sahai (30th STOC, 1998),
we consider concurrent execution of protocols in a
semi-synchronized network. Specifically, we assume that each party
holds a local clock such that a constant bound on the relative rates
of these clocks is a-priori known, and consider protocols that
employ time-driven operations
(i.e., time-out in-coming messages and delay out-going messages).
We show that the constant-round zero-knowledge proof for NP
of Goldreich and Kahan (Jour. of Crypto., 1996)
preserves its security when polynomially-many independent copies
are executed concurrently under the above timing model.
We stress that
our main result establishes zero-knowledge of interactive proofs,
whereas the results of Dwork et al. are
either for zero-knowledge arguments
or for a weak notion of zero-knowledge (called \epsilon-knowledge) proofs.
Our analysis identifies two extreme schedulings
of concurrent executions under the above timing model:
the first is the case of parallel execution of polynomially-many copies,
and the second is of concurrent execution of polynomially-many
copies such the number of copies that are simultaneously active
at any time is bounded by a constant (i.e., bounded simultaneity).
Dealing with each of these extreme cases is of independent interest,
and the general result (regarding concurrent executions under
the timing model) is obtained by combining the two treatments.
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .