On the composition of zero-knowledge proof systems
[For the entire collection see Zbl 0758.00017.] We prove that the original formulation of zero-knowledge as appearing in the pioneering work of \textit{S. Goldwasser}, \textit{S. Micali} and \textit{C. Rackoff} [SIAM J. Comput. 18, No. 1, 186-208 (1989; Zbl 0677.68062)] is not closed under sequential composition. This fact was conjectured by many researchers leading to the introduction of stronger formulations of zero-knowledge (e.g. black-box simulation). We also prove that the parallel composition of zero-knowledge protocols does not necessarily result in a new zero-knowledge protocol: we present two protocols, both being zero-knowledge in a strong sense yet their parallel composition is not zero-knowledge (not even in a weak sense). We present a lower bound on the round complexity of zero-knowledge proofs. We prove that only BPP languages have 3-round interactive proofs which are black-box simulation zero-knowledge. Moreover, we show that languages having constant-round Arthur-Merlin proofs that are black-box simulation zero-knowledge are in BPP. These results have significant implications to the parallelization of zero-knowledge proofs. In particular, it follows that the ``parallel versions of the original interactive proofs systems for quadratic residuosity, graph isomorphism and any language in NP, are not black-box simulation zero-knowledge, unless the corresponding languages are in BPP. This resolves an open problem arising from the early works on zero-knowledge. Other consequences are a proof of optimality for the round complexity of various known zero-knowledge protocols, and a structure theorem for the hierarchy of Arthur-Merlin zero-knowledge languages.
- Hybrid commitments and their applications to zero-knowledge proof systems
- An almost-constant round interactive zero-knowledge proof
- A uniform-complexity treatment of encryption and zero-knowledge
- On the communication complexity of zero-knowledge proofs
- Definitions and properties of zero-knowledge proof systems
- Practical proofs of knowledge without relying on theoretical proofs of membership on languages
- Mathematical problems in cryptology
- Continuous verifiable delay functions
- Random walks and concurrent zero-knowledge
- From private simultaneous messages to zero-information Arthur-Merlin protocols and back
- The knowledge tightness of parallel zero-knowledge
- On Monotone Formula Composition of Perfect Zero-Knowledge Languages
- Composition of zero-knowledge proofs with efficient provers
- Efficient Constructions of Composable Commitments and Zero-Knowledge Proofs
- Zero knowledge in the random oracle model, revisited
- Which languages have 4-round zero-knowledge proofs?
- On the concurrent composition of zero-knowledge proofs
- On the Composition of Zero-Knowledge Proof Systems
- From weak to strong zero-knowledge and applications
- Zero Knowledge and Soundness Are Symmetric
- On the Composition of Public-Coin Zero-Knowledge Protocols
- On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes
- Composable long-term security with rewinding
- Zero-knowledge systems from MPC-in-the-head and oblivious transfer
- Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
- A language-dependent cryptographic primitive
- CDLS: proving knowledge of committed discrete logarithms with soundness
- Almost-total puzzles and their applications
- Is it even possible? On the parallel composition of asynchronous MPC protocols
- On the impossibility of actively secure distributed samplers
- Non-interactive zero-knowledge proofs for composite statements
- Constant-round perfect zero-knowledge computationally convincing protocols
- Relativized perfect zero knowledge is not BPP
This page was built for publication: On the composition of zero-knowledge proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038698)
