© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:quant-ph/0605150

Using quantum oblivious transfer to cheat sensitive quantum bit commitment

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

Published May 17, 2006• 1 citation

Abstract

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.

DOI: 10.48550/arxiv.quant-ph/0605150

Related papers

Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

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

We define $(varepsilon,delta)$-secure quantum computations between two parties that can play dishonestly to maximise advantage $delta$, however keeping small the probability $varepsilon$ that the computation fails in evaluating correct value. We present a simple quantum protocol for computing one-out-of-two oblivious transfer that is $(O(sqrt{varepsilon}),varepsilon)$-secure. Using the protocol as a black box we construct a scheme for cheat sensitive quantum bit commitment which guarantee that a mistrustful party has a nonzero probability of detecting a cheating.

Electronic colloquium on computational complexity•Jan 1, 2006•0 citations

Quantum bit commitment with cheat sensitive binding and approximate sealing

Yan-Bing Li, Sheng-Wei Xu, Wei Huang +1 more

This paper proposes a cheat-sensitive quantum bit commitment scheme based on single photons, in which Alice commits a bit to Bob. Here, Bob's probability of success at cheating as obtains the committed bit before the opening phase becomes close to (just like performing a guess) as the number of single photons used is increased. And if Alice alters her committed bit after the commitment phase, her cheating will be detected with a probability that becomes close to 1 as the number of single photons used is increased. The scheme is easy to realize with present day technology.

arXiv:1407.6939•Journal of Physics A Mathematical and Theoretical•Mar 12, 2015•6 citations

Lower bounds for quantum oblivious transfer

André Chailloux, Iordanis Kerenidis, Jamie Sikora

Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest player's cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than $1/2$. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a bit commitment protocol and conclude by using lower bounds on quantum bit commitment. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most $3/4$. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.

Quantum Information and Computation•Jan 1, 2013•34 citations

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

Quantum Bit Escrow

Dorit Aharonov, Amnon Ta‐Shma, Umesh V. Vazirani +1 more

Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new primitive - {\em quantum bit escrow}. In this primitive Alice commits to a bit $b$ to Bob. The commitment is {\em binding} in the sense that if Alice is asked to reveal the bit, Alice can not bias her commitment without having a good probability of being detected cheating. The commitment is {\em sealing} in the sense that if Bob learns information about the encoded bit, then if later on he is asked to prove he was playing honestly, he is detected cheating with a good probability. Rigorously proving the correctness of quantum cryptographic protocols has proved to be a difficult task. We develop techniques to prove quantitative statements about the binding and sealing properties of the quantum bit escrow protocol. A related primitive we construct is a quantum biased coin flipping protocol where no player can control the game, i.e., even an all-powerful cheating player must lose with some constant probability, which stands in sharp contrast to the classical world where such protocols are impossible.

arXiv:quant-ph/0004017•Apr 4, 2000•0 citations

Cheat Sensitive Quantum Bit Commitment

Lucién Hardy, Adrian Kent

We define cheat sensitive cryptographic protocols between mistrustful parties as protocols which guarantee that, if either cheats, the other has some nonzero probability of detecting the cheating. We describe an unconditionally secure cheat sensitive nonrelativistic bit commitment protocol which uses quantum information to implement a task which is classically impossible; we also describe a simple relativistic protocol.

arXiv:quant-ph/9911043•Physical Review Letters•Apr 16, 2004•98 citations

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.

We define

(varepsilon,delta)

-secure quantum computations between two parties that can play dishonestly to maximise advantage

delta

, however keeping small the probability

varepsilon

that the computation fails in evaluating correct value. We present a simple quantum protocol for computing one-out-of-two oblivious transfer that is

(O(sqrt{varepsilon}),varepsilon)

-secure. Using the protocol as a black box we construct a scheme for cheat sensitive quantum bit commitment which guarantee that a mistrustful party has a nonzero probability of detecting a cheating.

This paper proposes a cheat-sensitive quantum bit commitment scheme based on single photons, in which Alice commits a bit to Bob. Here, Bob's probability of success at cheating as obtains the committed bit before the opening phase becomes close to (just like performing a guess) as the number of single photons used is increased. And if Alice alters her committed bit after the commitment phase, her cheating will be detected with a probability that becomes close to 1 as the number of single photons used is increased. The scheme is easy to realize with present day technology.

Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest player's cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than

1/2

. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a bit commitment protocol and conclude by using lower bounds on quantum bit commitment. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most

3/4

. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.

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.

Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new primitive - {\em quantum bit escrow}. In this primitive Alice commits to a bit

b

to Bob. The commitment is {\em binding} in the sense that if Alice is asked to reveal the bit, Alice can not bias her commitment without having a good probability of being detected cheating. The commitment is {\em sealing} in the sense that if Bob learns information about the encoded bit, then if later on he is asked to prove he was playing honestly, he is detected cheating with a good probability. Rigorously proving the correctness of quantum cryptographic protocols has proved to be a difficult task. We develop techniques to prove quantitative statements about the binding and sealing properties of the quantum bit escrow protocol. A related primitive we construct is a quantum biased coin flipping protocol where no player can control the game, i.e., even an all-powerful cheating player must lose with some constant probability, which stands in sharp contrast to the classical world where such protocols are impossible.