Paper 2021/376
On the Impossibility of PostQuantum BlackBox ZeroKnowledge in Constant Rounds
NaiHui Chia, KaiMin Chung, Qipeng Liu, and Takashi Yamakawa
Abstract
We investigate the existence of constantround postquantum blackbox zeroknowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constantround postquantum blackbox zeroknowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constantround blackbox zeroknowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between postquantum and classical zeroknowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constantround postquantum zeroknowledge protocols for $\mathbf{NP}$ exist if and only if we use nonblackbox techniques or relax certain security requirements such as relaxing standard zeroknowledge to $\epsilon$zeroknowledge. Additionally, we also prove that threeround and publiccoin constantround postquantum blackbox $\epsilon$zeroknowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.
Metadata
 Available format(s)
 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
 20210614: revised
 20210322: received
 See all versions
 Short URL
 https://ia.cr/2021/376
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/376, author = {NaiHui Chia and KaiMin Chung and Qipeng Liu and Takashi Yamakawa}, title = {On the Impossibility of PostQuantum BlackBox ZeroKnowledge 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} }