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

Post-quantum Zero Knowledge in Constant Rounds

Nir Bitansky, Omri Shmueli

Published Dec 10, 2019• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1912.04769

Related papers

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•48 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 $\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•1 citation

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

Post-Quantum Multi-Party Computation

Agarwal, Amit, James Bartusek, Vipul Goyal +2 more

We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.

arXiv:2005.12904•May 23, 2020•5 citations

Post-Quantum Multi-Party Computation in Constant Rounds.

Amit Agarwal, James Bartusek, Vipul Goyal +2 more

We obtain the first constant-round post-quantum multi-party computation protocol for general classical functionalities in the plain model, with security against malicious corruptions. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption. Along the way, we also construct the following protocols that may be of independent interest. (1) Constant-round zero-knowledge against parallel quantum verifiers from quantum polynomial assumptions. Here, we develop a novel parallel no-cloning non-black-box simulation technique. This uses as a starting point the recently introduced no-cloning technique of Bitansky and Shmueli (STOC 2020) and Ananth and La Placa (ePrint 2019), which in turns builds on the classical non-black-box technique of Bitansky, Khurana and Paneth (STOC 2019). Our approach relies on a new technical tool, spooky encryption for relations computable by quantum circuits, that we also construct. (2) Constant-round post-quantum non-malleable commitments from mildly super-polynomial quantum hardness of LWE. This is the first construction of post-quantum non-malleable commitments in the plain model, and is obtained by transforming the construction of Khurana and Sahai (FOCS 2017) to obtain post-quantum security. We achieve quantum security by building a new straight-line non-black-box simulator against parallel verifiers that does not clone the adversary's state. This technique may also be relevant to the classical setting.

•May 23, 2020•2 citations

A New Approach to Post-Quantum Non-Malleability

Xiao Liang, Omkant Pandey, Takashi Yamakawa

We provide the first constant-round construction of post-quantum non-malleable commitments under the minimal assumption that post-quantum one-way functions exist. We achieve the standard notion of non-malleability with respect to commitments. Prior constructions required $\Omega\left(\log ^{*} \lambda\right)$ rounds under the same assumption. We achieve our results through a new technique for constant-round non-malleable commitments which is easier to use in the post-quantum setting. The technique also yields an almost elementary proof of security for constant-round non-malleable commitments in the classical setting, which may be of independent interest. When combined with existing work, our results yield the first constant-round quantum-secure multiparty computation for both classical and quantum functionalities in the plain model, under the polynomial hardness of quantum fully-homomorphic encryption and quantum learning with errors.

arXiv:2207.05861•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•7 citations
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.
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.
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.
We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.
We obtain the first constant-round post-quantum multi-party computation protocol for general classical functionalities in the plain model, with security against malicious corruptions. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption. Along the way, we also construct the following protocols that may be of independent interest. (1) Constant-round zero-knowledge against parallel quantum verifiers from quantum polynomial assumptions. Here, we develop a novel parallel no-cloning non-black-box simulation technique. This uses as a starting point the recently introduced no-cloning technique of Bitansky and Shmueli (STOC 2020) and Ananth and La Placa (ePrint 2019), which in turns builds on the classical non-black-box technique of Bitansky, Khurana and Paneth (STOC 2019). Our approach relies on a new technical tool, spooky encryption for relations computable by quantum circuits, that we also construct. (2) Constant-round post-quantum non-malleable commitments from mildly super-polynomial quantum hardness of LWE. This is the first construction of post-quantum non-malleable commitments in the plain model, and is obtained by transforming the construction of Khurana and Sahai (FOCS 2017) to obtain post-quantum security. We achieve quantum security by building a new straight-line non-black-box simulator against parallel verifiers that does not clone the adversary's state. This technique may also be relevant to the classical setting.
We provide the first constant-round construction of post-quantum non-malleable commitments under the minimal assumption that post-quantum one-way functions exist. We achieve the standard notion of non-malleability with respect to commitments. Prior constructions required Ω(log⁡∗λ)\Omega\left(\log ^{*} \lambda\right)Ω(log∗λ) rounds under the same assumption. We achieve our results through a new technique for constant-round non-malleable commitments which is easier to use in the post-quantum setting. The technique also yields an almost elementary proof of security for constant-round non-malleable commitments in the classical setting, which may be of independent interest. When combined with existing work, our results yield the first constant-round quantum-secure multiparty computation for both classical and quantum functionalities in the plain model, under the polynomial hardness of quantum fully-homomorphic encryption and quantum learning with errors.