Welcome to the resource topic for 2021/376
Title:
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Authors: Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, 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}.
ePrint: https://eprint.iacr.org/2021/376
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .