Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2011.02670 · Lecture notes in computer science

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

Published Jan 1, 2021• 20 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-84242-0_12

Related papers

The Round Complexity of Black-Box Post-quantum Secure Computation

Rohit Chatterjee, Xiao Rong Liang, Omkant Pandey +1 more

arXiv:2502.13830•Lecture notes in computer science•Jan 1, 2025•3 citations

Post-quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round

Nai-Hui Chia, Kai-Min Chung, Xiao Rong Liang +1 more

arXiv:2111.08665•Lecture notes in computer science•Jan 1, 2022•11 citations

Resettable Cryptography in Constant Rounds – The Case of Zero Knowledge

Yi Deng, Dengguo Feng, Vipul Goyal +3 more

Lecture notes in computer science•Jan 1, 2011•17 citations

On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption

Divya Gupta, Amit Sahai

Lecture notes in computer science•Jan 1, 2014•16 citations

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

Nai-Hui Chia, Kai-Min Chung, Qipeng Liu +1 more

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

arXiv:2103.11244•Annual Symposium on Foundations of Computer Science•Feb 1, 2022•15 citations

The Round Complexity of Quantum Zero-Knowledge

Orestis Chardouvelis, Giulio Malavolta

Lecture notes in computer science•Jan 1, 2021•2 citations
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 unlessNP⊆BQP\text{NP} \subseteq \text{BQP}NP⊆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 unlessNP⊆BQP\text{NP} \subseteq \text{BQP}NP⊆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ϵ\epsilonϵ-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-boxϵ\epsilonϵ-zero-knowledge arguments for NP do not exist unlessNP⊆BQP\text{NP} \subseteq \text{BQP}NP⊆BQP.