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:2103.11244

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

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

Published Mar 20, 2021• 2 citations
arXivHTMLPDF

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

DOI
10.48550/arxiv.2103.11244

Related papers

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}$.

Annual Symposium on Foundations of Computer Science•Feb 1, 2022•6 citations

Post-quantum Zero Knowledge in Constant Rounds

Nir Bitansky, Omri Shmueli

We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

arXiv:1912.04769•Dec 10, 2019•0 citations

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

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

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $ε$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $ε$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $ε$-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $ε$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

arXiv:2011.02670•Nov 5, 2020•1 citation

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

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

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $\epsilon$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $\epsilon$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $\epsilon$-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $\epsilon$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

•Jan 1, 2020•0 citations

Post-Quantum Zero-Knowledge with Space-Bounded Simulation

Prabhanjan Ananth, Alex B. Grilo

The traditional definition of quantum zero-knowledge stipulates that the knowledge gained by any quantum polynomial-time verifier in an interactive protocol can be simulated by a quantum polynomial-time algorithm. One drawback of this definition is that it allows the simulator to consume significantly more computational resources than the verifier. We argue that this drawback renders the existing notion of quantum zero-knowledge not viable for certain settings, especially when dealing with near-term quantum devices. In this work, we initiate a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. We introduce the notion of $(s,f)$ space-bounded quantum zero-knowledge. In this new notion, we require that an $s$-qubit malicious verifier can be simulated by a quantum polynomial-time algorithm that uses at most $f(s)$-qubits, for some function $f(\cdot)$, and no restriction on the amount of the classical memory consumed by either the verifier or the simulator. We explore this notion and establish both positive and negative results: - For verifiers with logarithmic quantum space $s$ and (arbitrary) polynomial classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be achieved based on the existence of post-quantum one-way functions. Moreover, our protocol runs in constant rounds. - For verifiers with super-logarithmic quantum space $s$, assuming the existence of post-quantum secure one-way functions, we show that $(s,f)$-space-bounded QZK protocols, with fully black-box simulation (classical analogue of black-box simulation) can only be achieved for languages in BQP.

arXiv:2210.06093•Oct 12, 2022•2 citations

Post-quantum zero knowledge in constant rounds

Nir Bitansky, Omri Shmueli

We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA.

ACM Symposium on Theory of Computing (STOC)•Jun 6, 2020•45 citations
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for NP\mathbf{NP}NP. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for NP\mathbf{NP}NP unless NP⊆BQP\mathbf{NP}\subseteq \mathbf{BQP}NP⊆BQP. As constant-round black-box zero-knowledge arguments for NP\mathbf{NP}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⊆BQP\mathbf{NP}\subseteq \mathbf{BQP}NP⊆BQP, constant-round post-quantum zero-knowledge protocols for NP\mathbf{NP}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\mathbf{NP}NP do not exist unless NP⊆BQP\mathbf{NP}\subseteq \mathbf{BQP}NP⊆BQP.
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.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called εεε-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box εεε-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of εεε-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box εεε-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ϵ\epsilonϵ-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ϵ\epsilonϵ-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ϵ\epsilonϵ-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ϵ\epsilonϵ-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
The traditional definition of quantum zero-knowledge stipulates that the knowledge gained by any quantum polynomial-time verifier in an interactive protocol can be simulated by a quantum polynomial-time algorithm. One drawback of this definition is that it allows the simulator to consume significantly more computational resources than the verifier. We argue that this drawback renders the existing notion of quantum zero-knowledge not viable for certain settings, especially when dealing with near-term quantum devices. In this work, we initiate a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. We introduce the notion of (s,f)(s,f)(s,f) space-bounded quantum zero-knowledge. In this new notion, we require that an sss-qubit malicious verifier can be simulated by a quantum polynomial-time algorithm that uses at most f(s)f(s)f(s)-qubits, for some function f(⋅)f(\cdot)f(⋅), and no restriction on the amount of the classical memory consumed by either the verifier or the simulator. We explore this notion and establish both positive and negative results: - For verifiers with logarithmic quantum space sss and (arbitrary) polynomial classical space, we show that (s,f)(s,f)(s,f)-space-bounded QZK, for f(s)=2sf(s)=2sf(s)=2s, can be achieved based on the existence of post-quantum one-way functions. Moreover, our protocol runs in constant rounds. - For verifiers with super-logarithmic quantum space sss, assuming the existence of post-quantum secure one-way functions, we show that (s,f)(s,f)(s,f)-space-bounded QZK protocols, with fully black-box simulation (classical analogue of black-box simulation) can only be achieved for languages in BQP.