



01365nas a2200145   4500008004100000245008500041210006900126260001400195520089800209100001801107700001901125700001601144700002201160856003701182       2021                        eng d00aOn the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds0 aImpossibility of PostQuantum BlackBox ZeroKnowledge in Constant   c3/20/20213 a<p>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 NP&sube;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 NP&sube;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 ϵ-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box ϵ-zero-knowledge arguments for NP do not exist unless NP&sube;BQP.</p>1 aChia, Nai-Hui1 aChung, Kai-Min1 aLiu, Qipeng1 aYamakawa, Takashi  uhttps://arxiv.org/abs/2103.11244