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 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 log2 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.
We found a cheating strategy for the quantum cheat-sensitive bit commitment protocol proposed in Phys. Rev. A 84, 022308 (2011). It enables the receiver of the commitment to cheat with a probability not less than
1/2, no matter what values are chosen for the security parameters in the protocol. More interestingly, the probability for successful cheating will rise as the number
n of the particles used in the protocol increases and will be arbitrarily close to
100 in the limit $n\ensuremath{\rightarrow}\ensuremath{\infty}$.
Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/√2 (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important open question. In this paper, we provide the optimal bound for quantum bit commitment. First, we show a lower bound of approximately 0.739, improving Kitaev's lower bound. For this, we present some generic cheating strategies for Alice and Bob and conclude by proving a new relation between the trace distance and fidelity of two quantum states. Second, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + ε in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(ε). We then use the optimal quantum weak coin flipping protocol described by Mochon. Last, in order to stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.
This paper proposes a quantum protocol for a cheat-sensitive commitment of a classical bit. Alice, the receiver of the bit, can examine dishonest Bob, who changes or postpones his choice. Bob, the sender of the bit, can examine dishonest Alice, who violates concealment. For each round-trip case, Alice sends one of two spin states |
S\ifmmode\pm\else\textpm\fi{}⟩ by choosing basis
S at random from two conjugate bases
X and
Y. Bob chooses basis
C \ensuremath{\in} {
X,
Y} to perform a measurement and returns a resultant state |
C\ifmmode\pm\else\textpm\fi{}⟩. Alice then performs a measurement with the other basis
R (\ensuremath{\ne}
S) and obtains an outcome |
R\ifmmode\pm\else\textpm\fi{}⟩. In the opening phase, she can discover dishonest Bob, who unveils a wrong basis with a faked spin state, or Bob can discover dishonest Alice, who infers basis
C but destroys |
C\ifmmode\pm\else\textpm\fi{}⟩ by setting
R to be identical to
S in the commitment phase. If a classical bit is coded in a block of
m \ifmmode\times\else\texttimes\fi{}
n qubit particles, impartial examinations and probabilistic security criteria can be achieved.
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.