© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1102.3441

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

Takeshi Koshiba, Takanori Odaira

Published Feb 16, 2011• 6 citations

Abstract

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.

DOI: 10.48550/arxiv.1102.3441

Related papers

Statistically-hiding commitment from any one-way function

Iftach Haitner, Omer Reingold

We give a construction of statistically-hiding commitment schemes (ones where the hiding propertyholds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS '06), and universal one-way hash functions introduced and constructedby Naor and Yung (STOC '89) and Rompel (STOC '90).

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•84 citations

Randomness Certification from Statistically Hiding Commitments

Ilya Merkulov, Rotem Arnon

Randomness certification aims to guarantee that the output of an untrusted quantum device contains genuine randomness that remains unpredictable even given quantum side information held by an adversary. For a classical verifier interacting with a single quantum device, such a guarantee cannot rely on the physical separation underlying standard Bell tests and must instead follow from computational restrictions on the prover. Building on the framework of Computational Bell Inequalities, we distinguish classical and quantum virtual-input hiding, showing that the former suffices for proofs of quantumness, whereas the latter enables randomness certification against quantum side information. Our main technical contribution is to establish quantum virtual-input hiding for a commitment-based protocol derived from the proof of quantumness from one-way-functions by Morimae and Yamakawa. We show that statistical hiding together with ordinary computational binding against quantum polynomial-time senders suffices, without requiring stronger quantum binding notions such as sum-binding or collapse-binding. This yields a randomness-certification protocol from post-quantum statistically hiding bit commitments. In particular, existing constructions of such commitments from post-quantum one-way permutations imply that post-quantum one-way permutations suffice for randomness certification. We further instantiate our construction using quantum-secure trapdoor claw-free functions, obtaining an efficient classical verifier, and in the quantum random oracle model, obtaining randomness certification without additional computational assumptions but with an inefficient verifier. These instantiations separate the cryptographic properties sufficient for randomness certification from the additional structure required for efficient verification within our commitment-based framework.

quant-pharXiv:2610.25518•Oct 20, 2026•0 citations

Revisiting the security of quantum bit commitment schemes

Medhioub, Khaireddine

Bit commitment is one of the cornerstones of both classical and quantum cryptography. In the classical world, security analysis is straightforward because both hiding and binding each admit a single natural interpretation. In the quantum world, however, security notions can be defined in different ways that are not necessarily equivalent. Over three decades, several works have introduced numerous binding notions whose precise statements and mu- tual implications remain scattered across the literature. This thesis clarifies that ambiguity. We study quantum binding notions within the framework of canonical purified quantum bit commitment (QBC) schemes, a class that captures both the theoretical generality and the practical mechanisms of recent constructions. In the statistical setting, we examine six binding notions: strong-binding, honest-binding, sum-binding, collapse-binding, extractor- binding, and arbitrary-binding. We prove that all these definitions except strong-binding are equivalent for the class of canonical purified schemes. In the computational setting, we establish that honest-binding, sum-binding, and collapse-binding are equivalent for the same class of schemes. Moreover, we introduce a quantitative framework based on the work of Ref. [26] to quantify the tradeoff between hiding and binding properties, and we use it to provide a geometric proof of the impossibility theorem of Mayers [21] and Lo & Chau [20], for canonical purified schemes. We next revisit the quantum notion of hiding, which is far less ambiguous than binding. Finally, we survey some technical tools that can be used to construct secure QBC schemes.

•Aug 1, 2025•0 citations

Concurrent Non-malleable Statistically Hiding Commitment

Rui Li, Qiuliang Xu, Hao Wang

Commitment schemes are fundamental building blocks in cryptography, and have wide applications in constructing various protocols. Non-malleable commitment considers concurrent executions of a commitment scheme against a man-in-the-middle adversary. In this paper, we investigate non-malleability of statistically hiding commitment schemes, and present the first concurrent non-malleable statistically hiding commitment scheme. Our protocol admits black-box simulation, and relies on the robust (stand-alone) non-malleable commitment and specially designed witness indistinguishable proofs to achieve concurrent non-malleability. Based on the one-way function assumption, the commit phase of our protocol needs polynomial rounds, and the decommit phase needs super-logarithmic rounds.

International Conference on Computational Intelligence and Security (CIS)•Dec 1, 2011•0 citations

Statistically-Secure Bit Commitment and Coin Flipping Protocols Based on Quantum Hardware Assumptions

Roo Dunnill, Mina Doosti

Bit commitment is impossible to achieve with unconditional security, even in quantum cryptogra- phy. We show that statistically secure bit commitment, satisfying both hiding and binding, can be constructed from hybrid locked physical unclonable functions (HLPUFs), a hardware primitive that combines classical hardware tokens and quantum communication. Our protocol uses these hardware assumptions in a novel and non-trivial way to achieve the first mistrustful two-party cryptographic protocol based on hybrid hardware modules. We prove statistical hiding and binding under natu- ral assumptions on the HLPUF and using a carefully designed challenge generation algorithm as a subroutine of our bit-commitment protocol. The construction also yields the first hardware-based coin-flipping protocol. Our results suggest a new paradigm for secure two-party cryptography in quantum networks, combining rigorous security guarantees with a concrete route toward practical implementation.

quant-pharXiv:2608.11187•Aug 12, 2026•0 citations

A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction

Tomoyuki Yamakami

We propose an efficient quantum protocol performing quantum bit commitment, which is a simple cryptographic primitive involved with two parties, called a committer and a verifier. Our protocol is non-interactive, uses no supplemental shared information, and achieves computational concealing and statistical binding under a natural complexity-theoretical assumption. An earlier protocol in the literature relies on the existence of an efficient quantum one-way function. Our protocol, on the contrary, exploits a seemingly weaker assumption on computational difficulty of distinguishing two specific ensembles of reduced quantum states. This assumption is guaranteed by, for example, computational hardness of solving the graph automorphism problem efficiently on a quantum computer.

arXiv:1309.0436•Sep 2, 2013•0 citations

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.

Randomness certification aims to guarantee that the output of an untrusted quantum device contains genuine randomness that remains unpredictable even given quantum side information held by an adversary. For a classical verifier interacting with a single quantum device, such a guarantee cannot rely on the physical separation underlying standard Bell tests and must instead follow from computational restrictions on the prover. Building on the framework of Computational Bell Inequalities, we distinguish classical and quantum virtual-input hiding, showing that the former suffices for proofs of quantumness, whereas the latter enables randomness certification against quantum side information. Our main technical contribution is to establish quantum virtual-input hiding for a commitment-based protocol derived from the proof of quantumness from one-way-functions by Morimae and Yamakawa. We show that statistical hiding together with ordinary computational binding against quantum polynomial-time senders suffices, without requiring stronger quantum binding notions such as sum-binding or collapse-binding. This yields a randomness-certification protocol from post-quantum statistically hiding bit commitments. In particular, existing constructions of such commitments from post-quantum one-way permutations imply that post-quantum one-way permutations suffice for randomness certification. We further instantiate our construction using quantum-secure trapdoor claw-free functions, obtaining an efficient classical verifier, and in the quantum random oracle model, obtaining randomness certification without additional computational assumptions but with an inefficient verifier. These instantiations separate the cryptographic properties sufficient for randomness certification from the additional structure required for efficient verification within our commitment-based framework.

Bit commitment is one of the cornerstones of both classical and quantum cryptography. In the classical world, security analysis is straightforward because both hiding and binding each admit a single natural interpretation. In the quantum world, however, security notions can be defined in different ways that are not necessarily equivalent. Over three decades, several works have introduced numerous binding notions whose precise statements and mu- tual implications remain scattered across the literature. This thesis clarifies that ambiguity. We study quantum binding notions within the framework of canonical purified quantum bit commitment (QBC) schemes, a class that captures both the theoretical generality and the practical mechanisms of recent constructions. In the statistical setting, we examine six binding notions: strong-binding, honest-binding, sum-binding, collapse-binding, extractor- binding, and arbitrary-binding. We prove that all these definitions except strong-binding are equivalent for the class of canonical purified schemes. In the computational setting, we establish that honest-binding, sum-binding, and collapse-binding are equivalent for the same class of schemes. Moreover, we introduce a quantitative framework based on the work of Ref. [26] to quantify the tradeoff between hiding and binding properties, and we use it to provide a geometric proof of the impossibility theorem of Mayers [21] and Lo & Chau [20], for canonical purified schemes. We next revisit the quantum notion of hiding, which is far less ambiguous than binding. Finally, we survey some technical tools that can be used to construct secure QBC schemes.

Commitment schemes are fundamental building blocks in cryptography, and have wide applications in constructing various protocols. Non-malleable commitment considers concurrent executions of a commitment scheme against a man-in-the-middle adversary. In this paper, we investigate non-malleability of statistically hiding commitment schemes, and present the first concurrent non-malleable statistically hiding commitment scheme. Our protocol admits black-box simulation, and relies on the robust (stand-alone) non-malleable commitment and specially designed witness indistinguishable proofs to achieve concurrent non-malleability. Based on the one-way function assumption, the commit phase of our protocol needs polynomial rounds, and the decommit phase needs super-logarithmic rounds.

Bit commitment is impossible to achieve with unconditional security, even in quantum cryptogra- phy. We show that statistically secure bit commitment, satisfying both hiding and binding, can be constructed from hybrid locked physical unclonable functions (HLPUFs), a hardware primitive that combines classical hardware tokens and quantum communication. Our protocol uses these hardware assumptions in a novel and non-trivial way to achieve the first mistrustful two-party cryptographic protocol based on hybrid hardware modules. We prove statistical hiding and binding under natu- ral assumptions on the HLPUF and using a carefully designed challenge generation algorithm as a subroutine of our bit-commitment protocol. The construction also yields the first hardware-based coin-flipping protocol. Our results suggest a new paradigm for secure two-party cryptography in quantum networks, combining rigorous security guarantees with a concrete route toward practical implementation.

We propose an efficient quantum protocol performing quantum bit commitment, which is a simple cryptographic primitive involved with two parties, called a committer and a verifier. Our protocol is non-interactive, uses no supplemental shared information, and achieves computational concealing and statistical binding under a natural complexity-theoretical assumption. An earlier protocol in the literature relies on the existence of an efficient quantum one-way function. Our protocol, on the contrary, exploits a seemingly weaker assumption on computational difficulty of distinguishing two specific ensembles of reduced quantum states. This assumption is guaranteed by, for example, computational hardness of solving the graph automorphism problem efficiently on a quantum computer.