Coin Flipping

From Quantum Protocol Zoo
Jump to: navigation, search

Functionality description[edit]

Coin flipping is a cryptographic primitive which allows two mistrustful parties, Alice and Bob, to remotely generate a random bit, such that none of the two parties can bias the outcome beyond a specified probability.

In order to explicit the protocol properties, let us first define and upper-bound Alice and Bob's probabilities of forcing their opponent to declare outcome as:

Alice forces Bob to declare

Bob forces Alice to declare


Properties[edit]

  • A coin flipping scheme is fair when it outputs bit with probability and bit with probability , where is the honest probability that the protocol aborts.
  • A coin flipping scheme is secure with bias when none of the parties can force any outcome with probability higher than , where .
  • A coin flipping scheme is balanced when .


Protocols[edit]

Strong coin flipping (SCF)

In SCF, two parties remotely wish to agree on a random bit such that none of the parties can bias any outcome with a probability higher than , where is the protocol bias. SCF is fundamental in multiparty computation, online gaming and more general randomized consensus protocols involving leader election.


Using quantum mechanics, information-theoretically secure SCF is possible, but with a fundamental lower bound on the achievable bias:


Weak coin flipping (WCF)

In WCF, two parties wish to agree on a random bit in the same manner as SCF, but given that they both have known, preferred, opposite outcomes. In other words, the outcome of the flip will designate a winner and a loser. In the classical world, WCF arises from SCF with two unconstrained biases (Alice and Bob can always choose to lose with probability ):

Alice forces Bob to declare

Alice forces Bob to declare

Bob forces Alice to declare

Bob forces Alice to declare


With quantum mechanics, on the other hand, WCF is crucial to the construction of optimal quantum SCF and quantum bit commitment schemes. Crucially and unlike quantum SCF, quantum WCF may reach biases arbitrarily close to zero:

References[edit]

contributed by Mathieu Bozzio