Quantum Weak Coin Flipping
This addresses a fundamental cryptographic problem for secure communication, offering incremental improvements in explicit protocol construction.
The paper tackles the problem of weak coin flipping, a cryptographic primitive where two distrustful parties establish a shared random bit, by proposing a framework to construct explicit quantum protocols that achieve biases below the previous best of 1/6, with examples approaching 1/10 and numerically achieving arbitrarily small biases.
We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias $ε$ if neither player can force the outcome towards their preferred value with probability more than $\frac{1}{2}+ε$. While it is known that all classical protocols have $ε=\frac{1}{2}$, Mochon showed in 2007 [arXiv:0711.4114] that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the best known explicit protocol has bias $1/6$ (also due to Mochon, 2005 [Phys. Rev. A 72, 022341]). We propose a framework to construct new explicit protocols achieving biases below $1/6$. In particular, we construct explicit unitaries for protocols with bias approaching $1/10$. To go below, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to numerically construct protocols with arbitrarily small biases.