On Concurrent and Resettable Zero-Knowledge Proofs for NP
| dc.creator | Kilian, Joe | |
| dc.creator | Petrank, Erez | |
| dc.creator | Richardson, Ransom | |
| dc.date | 2001-07-03 | |
| dc.date.accessioned | 2026-07-07T03:17:18Z | |
| dc.date.available | 2026-07-07T03:17:18Z | |
| dc.description | 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Ω(\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^{θ(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. | |
| dc.description | This paper is a join of two works. The preliminary versions of these works appeared in the Proceeedings of Advances in Cryptology - EUROCRYPT '99}, May 1999, Lecture Notes in Computer Science Vol. 1592 Springer 1999, pp. 415-431, and in the Proceedings of the thirty third annual ACM Symposium on Theory of Computing, ACM Press, 2001 | |
| dc.identifier | https://arxiv.org/abs/cs/0107004 | |
| dc.identifier | http://arxiv.org/abs/cs/0107004 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30677 | |
| dc.subject | Cryptography and Security | |
| dc.subject | D.4.6 | |
| dc.title | On Concurrent and Resettable Zero-Knowledge Proofs for NP | |
| dc.type | text |