International Conference on Advanced Information Networking and Applications (AINA)

Game-Theoretic Security of Commitment Protocols under a Realistic Cost Model

Tsuyoshi Komatsubara, Yoshifumi Manabe

Published Mar 1, 2016• 1 citation

Abstract

This paper considers game-theoretic security of bit commitment protocols under a realistic cost model. Higo et. al (IWSEC 2013) proved equivalence of game-theoretic security and cryptographic security of bit commitment protocols under an ideal cost model. Their model assumes that there is no cost for communication and computation. Under a realistic model that cost for communication and computation is non-negligible, this paper shows that conventional bit commitment protocols are not game-theoretically secure, and abort detection property is necessary for bit commitment protocols to achieve game-theoretic security.

DOI: 10.1109/aina.2016.47

Related papers

The quantum bit commitment: a complete classification of protocols

Giacomo Mauro D’Ariano

This paper addresses the controversy between Mayers, Lo and Chau on one side, and Yuen on the opposite side, on whether there exist or not unconditionally secure protocols. For such purpose, a complete classification of all possible bit commitment protocols is given, including all possible cheating attacks. For the simplest class of protocols (non-aborting and with complete and perfect verification), it is shown how naturally a game-theoretical situation arises. For these protocols, bounds for the cheating probabilities are derived, which turn out to be different from those given in the impossibility proof. The whole classification and analysis has been carried out using a "finite open system" approach. The discrepancy with the impossibility proof is explained on the basis of the implicit adoption of a "closed system approach"--equivalent to modeling the commitment as performed by two fixed machines interacting unitarily in a overall "closed system". However, it is shown that the closed system approach for the classification of commitment protocols unavoidably leads to infinite dimensions, which then invalidate the continuity argument at the basis of the impossibility proof.

arXiv:quant-ph/0209150Sep 26, 20021 citation

Quantum bit commitment and unconditional security

Horace P. Yuen

It is generally believed that unconditionally secure quantum bit commitment is impossible, due to widespread acceptance of an impossibility proof that utilizes quantum entaglement cheating. In this paper, we delineate how the impossibiliy proof formulation misses various types of quantum bit commitment protocols based on two-way quantum communications. We point out some of the gaps in the impossibility proof reasoning, and present corresponding counterexamples. Four different types of bit commitment protocols are constructed with several new protocol techniques. A specific Type 4 protocol is described and proved unconditionally secure. Security analysis of a Type 1 protocol and a Type 2 protocol are also sketched. The security of Type 3 protocols is as yet open. A development of quantum statistical decision theory and quantum games is needed to provie a complete security analysis of many such protocols.

arXiv:quant-ph/0207089Jul 16, 20024 citations

The quantum bit commitment: a finite open system approach for a complete classification of protocols

Giacomo Mauro D’Ariano

Mayers, Lo and Chau argued that all quantum bit commitment protocols are insecure, because there is no way to prevent an Einstein-Podolsky-Rosen (EPR) cheating attack. However, Yuen presented some protocols which challenged the previous impossibility argument. Up to now, it is still debated whether there exist or not unconditionally secure protocols. In this paper the above controversy is addressed. For such purpose, a complete classification of all possible bit commitment protocols is given, including all possible cheating attacks. Focusing on the simplest class of protocols (non-aborting and with complete and perfect verification), it is shown how naturally a game-theoretical situation arises. For these protocols, bounds for the cheating probabilities are derived, involving the two quantum operations encoding the bit values and their respective alternate Kraus decompositions. Such bounds are different from those given in the impossibility proof. The whole classification and analysis has been carried out using a "finite open system" approach. The discrepancy with the impossibility proof is explained on the basis of the implicit adoption of a "closed system approach"--equivalent to modeling the commitment as performed by two fixed machines interacting unitarily in a overall "closed system"--according to which it is possible to assume as "openly known" both the initial state and the probability distributions for all secret parameters, which can be then "purified". This approach is also motivated by existence of unitary extensions for any open system. However, it is shown that the closed system approach for the classification of commitment protocols unavoidably leads to infinite dimensions, which then invalidate the continuity argument at the basis of the impossibility proof.

arXiv:quant-ph/0209149Sep 26, 20021 citation

Bit Commitment Based on Information Theoretic Security

Hong Yan

A trusted protocol for committing a classical bit could be used for protocols implementing a wide range of other cryptographic tasks. This paper discusses a safe bit commitment scheme over noisy Channels, which imports one-way hash function and interaction. It introduces the commitment capacity and analyses the security performance of the scheme studied from an information-theoretic perspective.

Computers & SecurityJan 1, 20090 citations

A feasible and practically secure quantum bit commitment protocol

Li Li, Runhua Shi

As a fundamental cryptographic primitive, bit commitment has lots of important and practical applications in modern cryptography. All previously proposed non-relativistic quantum bit commitment protocols cannot evade the Lo–Chau and Mayers attacks. Furthermore, relativistic quantum bit commitment protocols require rigorous spacetime constraints. In this paper, we present a simple, feasible but practically secure quantum bit commitment protocol without any spacetime constraint. The security of the proposed protocol is based on non-relativistic quantum mechanics, but it can resist all known attacks, including the Lo–Chau and Mayers attacks in practice.

Modern Physics Letters ANov 10, 20213 citations

Practical Quantum Bit Commitment Protocol Based on Quantum Oblivious Transfer

Yaqi Song, Li Yang

Oblivious transfer (OT) and bit commitment (BC) are two-party cryptographic protocols which play crucial roles in the construction of various cryptographic protocols. We propose three practical quantum cryptographic protocols in this paper. We first construct a practical quantum random oblivious transfer (R-OT) protocol based on the fact that non-orthogonal states cannot be reliably distinguished. Then, we construct a fault-tolerant one-out-of-two oblivious transfer ( O T 1 2 ) protocol based on the quantum R-OT protocol. Afterwards, we propose a quantum bit commitment (QBC) protocol which executes the fault-tolerant O T 1 2 several times. Mayers, Lo and Chau (MLC) no-go theorem proves that QBC protocol cannot be unconditionally secure. However, we find that computing the unitary transformation of no-go theorem attack needs so many resources that it is not realistically implementable. We give a definition of physical security for QBC protocols and prove that the practical QBC we proposed is physically secure and can be implemented in the real world.

Applied SciencesOct 19, 20188 citations