Weak coin flipping (WCF) is a fundamental cryptographic primitive for two-party secure computation, where two distrustful parties need to remotely establish a shared random bit whilst having opposite preferred outcomes. It is the strongest known primitive with arbitrarily close to perfect security in the quantum case, while classically its security is completely compromised (unless one makes further assumptions, such as computational hardness).

The existence of almost perfectly secure quantum WCF protocols was established in the seminal work of C. Mochon in 2007, however, his proof was partially non-constructive, thus, setting back the proposal of explicit protocols. More recently, Arora, Roland and Weis designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC’19, p.205-216].

In this talk, we present new techniques which yield a fully analytical construction of WCF protocols with different levels of security including nearly perfect security, thus achieving a solution that has been missing for more than a decade. In particular, we study the quantum WCF problem from both an algebraic and a geometric perspective and propose two different solutions, respectively. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon’s proof.