Quantum coin flipping
Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, e.g. Quantum Byzantine agreement. Unlike other types of quantum cryptography (in particular, quantum key distribution), quantum coin flipping is a protocol used between two users who do not trust each other. Consequently, both users (or players) want to win the coin toss and will attempt to cheat in various ways. It is known that if the communication between the players is over a classical channel, i.e. a channel over which quantum information cannot be communicated, then one player can (in principle) always cheat regardless of which protocol is used. We say in principle because it might be that cheating requires an unfeasible amount of computational resource. Under standard computational assumptions, coin flipping can be achieved with classical communication. The most basic figure of merit for a coin-flipping protocol is given by its bias, a number between and . The bias of a protocol captures the success probability of an all-powerful cheating player who uses the best conceivable strategy. A protocol with bias means that no player can cheat. A protocol with bias means that at least one player can always succeed at cheating. Obviously, the smaller the bias better the protocol. When the communication is over a quantum channel, it has been shown that even the best conceivable protocol can not have a bias less than . Consider the case where each player knows the preferred bit of the other. A coin flipping problem which makes this additional assumption constitutes the weaker variant thereof called weak coin flipping (WCF). In the case of classical channels this extra assumption yields no improvement. On the other hand, it has been proven that WCF protocols with arbitrarily small biases do exist. However, the best known explicit WCF protocol has bias . Although quantum coin flipping offers clear advantages over its classical counterpart in theory, accomplishing it in practice has proven difficult. (Wikipedia).
