Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0607211

On parallel composition of zero-knowledge proofs with black-box quantum simulators

Rahul Jain, Alexandra Kolla, Gatis Midrijānis, Ben W. Reichardt

Published Jul 28, 2006• 1 citation
arXivHTMLPDF

Abstract

Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator S, then L in BQP. Our result also applies to any language having a three-round quantum interactive proof (QIP), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when L notin BQP would imply an impossibly-good quantum search algorithm.

DOI
10.48550/arxiv.quant-ph/0607211

Related papers

On parallel composition of zero-knowledge proofs with black-box quantum

Rahul Jain, Alexandra Kolla, Gatis Midrijānis +1 more

Let $L$ be a language decided by a constant-round quantum Arthur-Merlin ($\QAM$) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator $\cS$, then $L \in \BQP$. Our result also applies to any language having a three-round quantum interactive proof ($\QIP$), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when $L \notin \BQP$ would imply an impossibly-good quantum search algorithm.

Quantum Information and Computation•May 1, 2009•4 citations

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds.

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $\epsilon$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $\epsilon$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $\epsilon$-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $\epsilon$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

•Jan 1, 2020•0 citations

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $ε$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $ε$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $ε$-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $ε$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

arXiv:2011.02670•Nov 5, 2020•1 citation

On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round

Nai-Hui Chia, Kai-Min Chung, Qipeng Liu +1 more

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for NP. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for NP unless$\text{NP} \subseteq \text{BQP}$. As constant-round black-box zero-knowledge arguments for NP exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless$\text{NP} \subseteq \text{BQP}$, constant-round post-quantum zero-knowledge protocols for NP exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to$\epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box$\epsilon$-zero-knowledge arguments for NP do not exist unless$\text{NP} \subseteq \text{BQP}$.

Annual Symposium on Foundations of Computer Science•Feb 1, 2022•6 citations

On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds

Nai-Hui Chia, Kai-Min Chung, Qipeng Liu +1 more

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $ε$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $ε$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.

arXiv:2103.11244•Mar 20, 2021•2 citations

Quantum Arthur–Merlin games

Chris Marriott, John Watrous

This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that $$ {\text{QMA}} \subseteq {\text{PP}}. $$ Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.

Computational Complexity•Jun 1, 2005•240 citations
Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator S, then L in BQP. Our result also applies to any language having a three-round quantum interactive proof (QIP), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when L notin BQP would imply an impossibly-good quantum search algorithm.
Let LLL be a language decided by a constant-round quantum Arthur-Merlin ($\QAM$) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator $\cS$, then $L \in \BQP$. Our result also applies to any language having a three-round quantum interactive proof ($\QIP$), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when $L \notin \BQP$ would imply an impossibly-good quantum search algorithm.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ϵ\epsilonϵ-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ϵ\epsilonϵ-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ϵ\epsilonϵ-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ϵ\epsilonϵ-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called εεε-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box εεε-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of εεε-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box εεε-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for NP. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for NP unlessNP⊆BQP\text{NP} \subseteq \text{BQP}NP⊆BQP. As constant-round black-box zero-knowledge arguments for NP exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unlessNP⊆BQP\text{NP} \subseteq \text{BQP}NP⊆BQP, constant-round post-quantum zero-knowledge protocols for NP exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge toϵ\epsilonϵ-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-boxϵ\epsilonϵ-zero-knowledge arguments for NP do not exist unlessNP⊆BQP\text{NP} \subseteq \text{BQP}NP⊆BQP.
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for NP\mathbf{NP}NP. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for NP\mathbf{NP}NP unless NP⊆BQP\mathbf{NP}\subseteq \mathbf{BQP}NP⊆BQP. As constant-round black-box zero-knowledge arguments for NP\mathbf{NP}NP exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless NP⊆BQP\mathbf{NP}\subseteq \mathbf{BQP}NP⊆BQP, constant-round post-quantum zero-knowledge protocols for NP\mathbf{NP}NP exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to εεε-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box εεε-zero-knowledge arguments for NP\mathbf{NP}NP do not exist unless NP⊆BQP\mathbf{NP}\subseteq \mathbf{BQP}NP⊆BQP.
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA⊆PP. {\text{QMA}} \subseteq {\text{PP}}. QMA⊆PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.