In the distrustful quantum cryptography model the parties have conflicting interests and do not trust one another. Nevertheless, they trust the quantum devices in their labs. The aim of the device-independent approach to cryptography is to do away with the latter assumption, and, consequently, significantly increase security. It is an open question whether the scope of this approach also extends to protocols in the distrustful cryptography model, thereby rendering them “fully” distrustful. In this Letter, we show that for bit commitment—one of the most basic primitives within the model—the answer is positive. We present a device-independent (imperfect) bit-commitment protocol, where Alice’s and Bob’s cheating probabilities are $\simeq 0.854$ and $\frac{3}{4}$, which we then use to construct a device-independent coin flipping protocol with bias $\lesssim 0.336$.

• Received 26 January 2011

DOI:https://doi.org/10.1103/PhysRevLett.106.220501