Bit commitments are very fundamental protocols in modern cryptography. In this paper, we introduce a model to study bit commitment schemes with a probability of failure (we call them, weak bit commitments). We characterize when it is possible to reduce bit commitments to weak bit commitments. We introduce a new concept in cryptographic reductions called the rate. We prove that our reductions are optimal regarding the rate. Additionally, we show that, when written in the appropriate way, several reductions among cryptographic primitives are equivalent to well known problems in Shannon theory.
Bit commitments are very fundamental protocols in modern cryptography. In this paper, we introduce a model to study bit commitment schemes with a probability of failure (we call them, weak bit commitments). We characterize when it is possible to reduce bit commitments to weak bit commitments. We introduce a new concept in cryptographic reductions called the rate. We prove that our reductions are optimal regarding the rate. Additionally, we show that, when written in the appropriate way, several reductions among cryptographic primitives are equivalent to well known problems in Shannon theory.
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.
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[Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2} [Kit03] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question. In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then 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 + eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. 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.
We present and compare definitions of the notion of "statistically hiding" protocols, and we propose a novel statistically hiding commitment scheme. Informally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the secret learns almost nothing about it. One definition is based on the L1-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. For completeness, we also show that statistical counterparts of definitions of computational secrecy are essentially equivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statistically hiding commitment scheme allowing commitment to many bits. The commitment and reveal protocols of this scheme are constant round, and the size of a commitment is independent of the number of bits committed to. This also holds for the total communication complexity, except of course for the bits needed to send the secret when it is revealed. The proof of the hiding property exploits the equivalence of the two definitions. Index terms -- Cryptology, Shannon theory, unconditional security, statistically hiding, multi-bit commitment, similarity of ensembles of distributions, zero-knowledge, protocols.
Bit commitment is a fundamental cryptographic primitive and a cornerstone for numerous two-party cryptographic protocols, including zero-knowledge proofs. However, it has been proven that unconditionally secure bit commitment, both classical and quantum, is impossible. In this work, we demonstrate that imposing a restriction on the committing party to perform only separable operations enables secure quantum bit-commitment schemes. Specifically, we prove that in any perfectly hiding bit-commitment protocol, an honestly committing party limited to separable operations will be detected with high probability if they attempt to alter their commitment. To illustrate our findings, we present an example protocol.
Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than 1/2 [A. Kitaev, Presentation at the 6th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/2. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+ε in order to achieve a strong coin flipping protocol with cheating probability 1/2+O(ε). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately γ≈0.739, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to γ. 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 γ+O(ε). To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.
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.