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.
Category / Keywords: foundations / Zero-Knowledge, Parallel Composition, Concurrent Composition, Publication Info: also posted on ECCC Date: received 27 Nov 2001 Contact author: oded at wisdom weizmann ac il Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20011127:174911 (All versions of this report) Discussion forum: Show discussion | Start new discussion