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

*Nai-Hui Chia and Kai-Min Chung and Qipeng Liu and Takashi Yamakawa*

**Abstract: **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 $\epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $\epsilon$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.

**Category / Keywords: **foundations / zero knowledge, quantum cryptography

**Date: **received 20 Mar 2021, last revised 14 Jun 2021

**Contact author: **nchia at umd edu, kmchung at iis sinica edu tw, qipengl at cs princeton edu, takashi yamakawa obf at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20210614:132008 (All versions of this report)

**Short URL: **ia.cr/2021/376

[ Cryptology ePrint archive ]