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}$ .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.11244Mar 20, 20212 citations

On the Round Complexity of Secure Quantum Computation

James Bartusek, Andrea Coladangelo, Dakshita Khurana +1 more

Lecture notes in computer scienceJan 1, 202122 citations

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}$ .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 ScienceFeb 1, 20226 citations

The Round Complexity of Quantum Zero-Knowledge

Orestis Chardouvelis, Giulio Malavolta

Lecture notes in computer scienceJan 1, 20212 citations

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}

\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}