Simple proof of the impossibility of bit-commitment in generalised probabilistic theories using cone programming

Abstract

Bit-commitment is a fundamental cryptographic task, in which Alice commits a bit to Bob such that she cannot later change the value of the bit, while, simultaneously, the bit is hidden from Bob. It is known that ideal bit-commitment is impossible within quantum theory. In this work, we show that it is also impossible in generalised probabilistic theories (under a small set of assumptions) by presenting a quantitative trade-off between Alice's and Bob's cheating probabilities. Our proof relies crucially on a formulation of cheating strategies as cone programs, a natural generalisation of semidefinite programs. In fact, using the generality of this technique, we prove that this result holds for the more general task of integer-commitment.

Version 2. Improved presentation. References added. Accepted version

References in corpus (5)

• Higher-order interference and single-system postulates characterizing quantum theory
• Entanglement is necessary for emergent classicality in all physical theories
• Ruling out higher-order interference from purity principles
• Conditions on the existence of maximally incompatible two-outcome measurements in General Probabilistic Theory
• Structure of Optimal State Discrimination in Generalized Probabilistic Theories

Cited by in corpus (15)

• General probabilistic theories: An introduction
• A no-go theorem on the nature of the gravitational field beyond quantum theory
• Reconstructing quantum theory from diagrammatic postulates
• Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
• How to make unforgeable money in generalised probabilistic theories
• Universal structure of objective states in all fundamental causal theories
• On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
• Correlations constrained by composite measurements
• Compositional resource theories of coherence
• A no-go theorem for theories that decohere to quantum mechanics
• Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
• Complete extension: the non-signaling analog of quantum purification
• An optical implementation of quantum bit commitment using infinite-dimensional systems
• Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming
• Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions