Computer Science – Cryptography and Security
Scientific paper
2001-07-03
Computer Science
Cryptography and Security
This paper is a join of two works. The preliminary versions of these works appeared in the Proceeedings of Advances in Cryptol
Scientific paper
A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment. Designing concurrent zero-knowledge proofs is a fundamental issue in the study of zero-knowledge since known zero-knowledge protocols cannot be run in a realistic modern computing environment. In this paper we present a concurrent zero-knowledge proof systems for all languages in NP. Currently, the proof system we present is the only known proof system that retains the zero-knowledge property when copies of the proof are allowed to run in an asynchronous environment. Our proof system has $\tilde{O}(\log^2 k)$ rounds (for a security parameter $k$), which is almost optimal, as it is shown by Canetti Kilian Petrank and Rosen that black-box concurrent zero-knowledge requires $\tilde{\Omega}(\log k)$ rounds. Canetti, Goldreich, Goldwasser and Micali introduced the notion of {\em resettable} zero-knowledge, and modified an earlier version of our proof system to obtain the first resettable zero-knowledge proof system. This protocol requires $k^{\theta(1)}$ rounds. We note that their technique also applies to our current proof system, yielding a resettable zero-knowledge proof for NP with $\tilde{O}(\log^2 k)$ rounds.
Kilian Joe
Petrank Erez
Richardson Ransom
No associations
LandOfFree
On Concurrent and Resettable Zero-Knowledge Proofs for NP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Concurrent and Resettable Zero-Knowledge Proofs for NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Concurrent and Resettable Zero-Knowledge Proofs for NP will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-566907