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

Constructions and Bounds for Unconditionally Secure Commitment Schemes.

Carlo Blundo, Barbara Masucci, Douglas R. Stinson, Ruizhong Wei

Published Jan 1, 2000• 0 citations
OpenAlex

Abstract

Commitment schemes have been extensively studied since they were introduced by Blum in 1982. Rivest recently showed how to construct unconditionally secure commitment schemes, assuming the existence of a trusted initializer. In this paper, we present a formal mathematical model for such schemes, and analyze their binding and concealing properties. In particular, we show that such schemes cannot be perfectly concealing: there is necessarily a small probability that Alice can cheat Bob by committing to one value but later revealing a dierent value. We prove several bounds on Alice's cheating probability, and present constructions of schemes that achieve optimal cheating probabilities. We also show a close link between commitment schemes and the classical \\ane resolvable designs". 1 Introduction Commitment schemes were rst introduced by Blum [2] in 1982. In a commitment scheme, there is a sender, Alice, and a receiver, Bob. The scheme consists of a commit protocol and a reveal protocol...

Related papers

Possibility, impossibility, and cheat sensitivity of quantum-bit string commitment

Harry Buhrman, Matthias Christandl, Patrick M. Hayden +2 more

Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of $n$ bits at once, how far can we stretch the quantum limits? In this paper, we introduce a framework for quantum schemes where Alice commits a string of $n$ bits to Bob in such a way that she can only cheat on $a$ bits and Bob can learn at most $b$ bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: $a+b$ is at least $n$. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where $a=4\text{ }{\text{log}}_{2}\text{ }n+O(1)$ and $b=4$, which is impossible classically. We furthermore present a cheat-sensitive quantum bit string commitment protocol for which we give an explicit tradeoff between Bob's ability to gain information about the committed string, and the probability of him being detected cheating.

arXiv:quant-ph/0504078•Physical Review A•Aug 11, 2008•63 citations

Using quantum oblivious transfer to cheat sensitive quantum bit commitment

Andreas Jakoby, Maciej Liśkiewicz, Aleksander Mądry

It is well known that unconditionally secure bit commitment is impossible even in the quantum world. In this paper a weak variant of quantum bit commitment, introduced independently by Aharonov et al. [STOC, 2000] and Hardy and Kent [Phys. Rev. Lett. 92 (2004)] is investigated. In this variant, the parties require some nonzero probability of detecting a cheating, i.e. if Bob, who commits a bit b to Alice, changes his mind during the revealing phase then Alice detects the cheating with a positive probability (we call this property binding); and if Alice gains information about the committed bit before the revealing phase then Bob discovers this with positive probability (sealing). In our paper we give quantum bit commitment scheme that is simultaneously binding and sealing and we show that if a cheating gives epsilon advantage to a malicious Alice then Bob can detect the cheating with a probability Omega(epsilon^2). If Bob cheats then Alice's probability of detecting the cheating is greater than some fixed constant lambda>0. This improves the probabilities of cheating detections shown by Hardy and Kent and the scheme by Aharonov et al. who presented a protocol that is either binding or sealing, but not simultaneously both. To construct a cheat sensitive quantum bit commitment scheme we use a protocol for a weak quantum one-out-of-two oblivious transfer.

arXiv:quant-ph/0605150•May 17, 2006•1 citation

Insecurity of a relativistic quantum commitment scheme

Guang Ping He

We propose a cheating strategy to a relativistic quantum commitment scheme (Nadeem, 2014) which was claimed to be unconditionally secure. It is shown that the sender Alice can cheat successfully with probability 100%, thus disproving the security claim.

arXiv:1411.0013•Results in Physics•May 27, 2023•0 citations

Security of Quantum Bit String Commitment Depends on the Information Measure

Harry Buhrman, Matthias Christandl, Patrick M. Hayden +2 more

Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? In this Letter, we introduce a framework of quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a + b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a = 4log2(n) + O(1) and b = 4, which is impossible classically. Our findings significantly extend known no-go results for quantum bit commitment.

arXiv:quant-ph/0609237•Physical Review Letters•Dec 19, 2006•36 citations

Unconditionally Secure Qubit Commitment Scheme Using Quantum Maskers

Seok Hyung Lie, Hyukjoon Kwon, Myung-Gun Kim +1 more

A commitment scheme allows one to commit to hidden information while keeping its value recoverable when needed. Despite considerable efforts, an unconditionally and perfectly secure bit commitment has been proven impossible both classically and quantum-mechanically. The situation is similar when committing to qubits instead of classical bits as implied in the no-masking theorem [K. Modi et al., Phys. Rev. Lett. {\bf 120}, 230501 (2018)]. In this Letter, we find that circumvention of the no-masking theorem is possible with the aid of classical randomness. Based on this, we construct an unconditionally secure quit-commitment scheme that utilises any kind of universal quantum maskers with optimal randomness consumption, which is distributed by a trusted initializer. This shows that randomness, which is normally considered only to obscure the information, can benefit a quantum secure communication scheme. This result can be generalised to an arbitrary dimensional system.

•Mar 29, 2019•9 citations

On minimal assumptions to obtain a universally composable quantum bit commitment

Mariano Lemus, Preeti Yadav, Paulo Mateus +2 more

It is well known, due to the no-go theorems, that perfectly secure bit commitment is impossible. For that reason, there exist many proposals for bit commitment protocols that are secure under certain assumptions (such as the existence of a trusted party, computational hardness, or noisy memories). In this paper, we investigate the minimal assumptions required to obtain a secure bit commitment protocol. We show that it is possible to construct a bit commitment scheme with two parties Alice and Bob as long as there is a third party that is willing to broadcast either entangled qubits for the parties or to produce classical strings that are xor-correlated. We also show that the bit commitment scheme proposed is universally composable.

International Conference on Transparent Optical Networks•Jul 1, 2019•3 citations
Commitment schemes have been extensively studied since they were introduced by Blum in 1982. Rivest recently showed how to construct unconditionally secure commitment schemes, assuming the existence of a trusted initializer. In this paper, we present a formal mathematical model for such schemes, and analyze their binding and concealing properties. In particular, we show that such schemes cannot be perfectly concealing: there is necessarily a small probability that Alice can cheat Bob by committing to one value but later revealing a dierent value. We prove several bounds on Alice's cheating probability, and present constructions of schemes that achieve optimal cheating probabilities. We also show a close link between commitment schemes and the classical \ane resolvable designs". 1 Introduction Commitment schemes were rst introduced by Blum [2] in 1982. In a commitment scheme, there is a sender, Alice, and a receiver, Bob. The scheme consists of a commit protocol and a reveal protocol...
Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of nnn bits at once, how far can we stretch the quantum limits? In this paper, we introduce a framework for quantum schemes where Alice commits a string of nnn bits to Bob in such a way that she can only cheat on aaa bits and Bob can learn at most bbb bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a+ba+ba+b is at least nnn. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a=4 log2 n+O(1)a=4\text{ }{\text{log}}_{2}\text{ }n+O(1)a=4 log2​ n+O(1) and b=4b=4b=4, which is impossible classically. We furthermore present a cheat-sensitive quantum bit string commitment protocol for which we give an explicit tradeoff between Bob's ability to gain information about the committed string, and the probability of him being detected cheating.
It is well known that unconditionally secure bit commitment is impossible even in the quantum world. In this paper a weak variant of quantum bit commitment, introduced independently by Aharonov et al. [STOC, 2000] and Hardy and Kent [Phys. Rev. Lett. 92 (2004)] is investigated. In this variant, the parties require some nonzero probability of detecting a cheating, i.e. if Bob, who commits a bit b to Alice, changes his mind during the revealing phase then Alice detects the cheating with a positive probability (we call this property binding); and if Alice gains information about the committed bit before the revealing phase then Bob discovers this with positive probability (sealing). In our paper we give quantum bit commitment scheme that is simultaneously binding and sealing and we show that if a cheating gives epsilon advantage to a malicious Alice then Bob can detect the cheating with a probability Omega(epsilon^2). If Bob cheats then Alice's probability of detecting the cheating is greater than some fixed constant lambda>0. This improves the probabilities of cheating detections shown by Hardy and Kent and the scheme by Aharonov et al. who presented a protocol that is either binding or sealing, but not simultaneously both. To construct a cheat sensitive quantum bit commitment scheme we use a protocol for a weak quantum one-out-of-two oblivious transfer.
Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? In this Letter, we introduce a framework of quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a + b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a = 4log2(n) + O(1) and b = 4, which is impossible classically. Our findings significantly extend known no-go results for quantum bit commitment.
A commitment scheme allows one to commit to hidden information while keeping its value recoverable when needed. Despite considerable efforts, an unconditionally and perfectly secure bit commitment has been proven impossible both classically and quantum-mechanically. The situation is similar when committing to qubits instead of classical bits as implied in the no-masking theorem [K. Modi et al., Phys. Rev. Lett. {\bf 120}, 230501 (2018)]. In this Letter, we find that circumvention of the no-masking theorem is possible with the aid of classical randomness. Based on this, we construct an unconditionally secure quit-commitment scheme that utilises any kind of universal quantum maskers with optimal randomness consumption, which is distributed by a trusted initializer. This shows that randomness, which is normally considered only to obscure the information, can benefit a quantum secure communication scheme. This result can be generalised to an arbitrary dimensional system.
It is well known, due to the no-go theorems, that perfectly secure bit commitment is impossible. For that reason, there exist many proposals for bit commitment protocols that are secure under certain assumptions (such as the existence of a trusted party, computational hardness, or noisy memories). In this paper, we investigate the minimal assumptions required to obtain a secure bit commitment protocol. We show that it is possible to construct a bit commitment scheme with two parties Alice and Bob as long as there is a third party that is willing to broadcast either entangled qubits for the parties or to produce classical strings that are xor-correlated. We also show that the bit commitment scheme proposed is universally composable.