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

SIAM Journal on Computing

Commitments to Quantum States

Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry

Published Nov 3, 2026• 0 citations
Publisher

Abstract

Abstract. What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender’s view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions. Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian’s succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for [Formula: see text] under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to [Formula: see text]. Our security proof develops new rewinding techniques for extracting quantum information.

DOI
10.1137/23m1598556

Related papers

Commitments to Quantum States

Sam Gunn, Nathan Ju, Fermi Ma +1 more

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions.

arXiv:2210.05138•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•27 citations

Classical Commitments to Quantum States

Sam Gunn, Yael Tauman Kalai, Anand Natarajan +1 more

We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018). We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work). Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE.

arXiv:2404.14438•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•7 citations

Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks

Ivan Damgård, Serge Fehr, Louis Salvail

The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting. We propose new techniques for building quantum zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK. As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks. Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, non-oblivious verifier QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.

BRICS Report Series•May 11, 2004•10 citations

A Modular Approach to Succinct Arguments for QMA

James Bartusek, Jiahui Liu, Giulio Malavolta

Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92) established that any probabilistically checkable proof for NP can be transformed into a succinct argument system for NP using only collision-resistant hash functions. In the quantum setting, recent works have established the feasibility of (classically-verifiable) succinct arguments for QMA, capturing statements that require *quantum* proofs. However, known constructions all rely on the highly structured assumption of learning with errors (LWE), which stands in stark contrast with the unstructured assumptions that suffice for NP. In this work, we develop a new framework that broadens the cryptographic foundations of succinct arguments for QMA. We assume the existence of (i) an oblivious state preparation (OSP) protocol, which in turn can be constructed from *plain* trapdoor claw-free functions, and (ii) collapsing hash functions, the quantum analogue of collision-resistance. In particular, we obtain the first succinct, classically-verifiable argument system for QMA which does not rely on the hardness of LWE. Our construction proceeds in two steps. First, we design a *round-efficient* classically-verifiable argument system for QMA based only on the assumption of OSP. Second, we introduce a *generalized communication compression compiler*, which, assuming collapsing hash functions, transforms any $T$-round interactive protocol into one in which the communication size is bounded by $T \cdot \poly(\secp)$ for some fixed $\poly$ independent of the original size of each message. Our compiler extends a quantum rigidity-based communication compression technique of Zhang (QCrypt 25), and may be of independent interest.

quant-pharXiv:2606.10408•Lecture notes in computer science•Jun 5, 2026•2 citations

Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

Alessandro Chiesa, Fermi Ma, Nicholas Spooner +1 more

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.

arXiv:2103.08140•Annual Symposium on Foundations of Computer Science•Feb 1, 2022•40 citations

Non-Interactive Statistically-Hiding Quantum Bit Commitment from Any Quantum One-Way Function

Takeshi Koshiba, Takanori Odaira

We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.

arXiv:1102.3441•Feb 16, 2011•17 citations
Abstract. What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender’s view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions. Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian’s succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for [Formula: see text] under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to [Formula: see text]. Our security proof develops new rewinding techniques for extracting quantum information.
What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions.
We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018). We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work). Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE.
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting. We propose new techniques for building quantum zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK. As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks. Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, non-oblivious verifier QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92) established that any probabilistically checkable proof for NP can be transformed into a succinct argument system for NP using only collision-resistant hash functions. In the quantum setting, recent works have established the feasibility of (classically-verifiable) succinct arguments for QMA, capturing statements that require *quantum* proofs. However, known constructions all rely on the highly structured assumption of learning with errors (LWE), which stands in stark contrast with the unstructured assumptions that suffice for NP. In this work, we develop a new framework that broadens the cryptographic foundations of succinct arguments for QMA. We assume the existence of (i) an oblivious state preparation (OSP) protocol, which in turn can be constructed from *plain* trapdoor claw-free functions, and (ii) collapsing hash functions, the quantum analogue of collision-resistance. In particular, we obtain the first succinct, classically-verifiable argument system for QMA which does not rely on the hardness of LWE. Our construction proceeds in two steps. First, we design a *round-efficient* classically-verifiable argument system for QMA based only on the assumption of OSP. Second, we introduce a *generalized communication compression compiler*, which, assuming collapsing hash functions, transforms any TTT-round interactive protocol into one in which the communication size is bounded by $T \cdot \poly(\secp)$ for some fixed $\poly$ independent of the original size of each message. Our compiler extends a quantum rigidity-based communication compression technique of Zhang (QCrypt 25), and may be of independent interest.
We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.
We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.