Paper 2021/376

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

Nai-Hui Chia, Kai-Min Chung, 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}$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
zero knowledgequantum cryptography
Contact author(s)
nchia @ umd edu
kmchung @ iis sinica edu tw
qipengl @ cs princeton edu
takashi yamakawa obf @ gmail com
History
2021-06-14: revised
2021-03-22: received
See all versions
Short URL
https://ia.cr/2021/376
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/376,
      author = {Nai-Hui Chia and Kai-Min Chung and Qipeng Liu and Takashi Yamakawa},
      title = {On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2021/376},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/376}},
      url = {https://eprint.iacr.org/2021/376}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.