right]] Coin tossing is the task of generating a random bit by two mistrusting parties.
To illustrate the difficulty behind this, consider the following scenario. Assume that Alice and Bob, freshly divorced, want to decide on the phone who of them gets their common car. They agree to let the decision depend on the outcome of a coin toss. Obviously, each of them wants to be sure that the coin toss is fair. How to do that over a telephone line?
A coin tossing protocol between two parties is a sequence of instructions between two parties involving local computations as well as communication over a channel which eventually results in an output bit. A coin tossing protocol is said to be secure if the output bit is virtually uniformly distributed even if one of the parties does not follow the protocol.
In a purely classical setting, unconditionally secure coin tossing protocols do not exist. However, it is possible to construct coin tossing protocols which are secure under the assumption that the parties are computationally bounded.
A generic example of a coin tossing protocol is based on bit commitment. Alice first chooses a random bit r1 and then uses the bit commitment scheme to commit to this bit. Bob then chooses another random bit r2 and sends the bit to Alice. Then, Alice opens her commitment. The final bit is then computed as the sum modulo two of the bits r1 and r2.
It is easy to see that this bit coin tossing protocol is secure if the underlying bit commitment scheme is secure. In fact, if at least one of the parties correctly generates a random bit then the final bit will be completely random (independently of the strategy of the other party).
If one allows Alice and Bob to communicate over a quantum channel, then information-theoretic coin tossing is partially possible. More precisely, there are protocols such that each party has the guarantee that the other can not influence the final bit with probability larger than a certain threshold.