2001/07/03 by Joe Kilian, Kilian, Joe, Erez Petrank +3
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #D.4.6 #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #cs.CR
paper · pdf · doi:10.48550/arxiv.cs/0107004
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
arxiv created 2001/07/03 · openalex publication_date 2001/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(log2 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 Ω(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 O(log2 k) rounds.