Explicit quantum weak coin flipping protocols with arbitrarily small bias

Staff - Faculty of Informatics

Date: 13 November 2019 / 13:30 - 14:30

USI Lugano Campus, room SI-004, Informatics building (Via G. Buffi 13)

Chrysoula Vlachou, Université Libre de Bruxelles, Belgium

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. A weak coin-flipping protocol has a bias ε if neither player can force the outcome towards their preferred value with probability more than 1/2 + ε. While it is known that classically ε = 1/2, Mochon showed in 2007 that quantumly weak coin flipping can be achieved with arbitrarily small bias, i.e. ε(k) = 1/(4k + 2) for arbitrarily large k, and he proposed an explicit protocol approaching bias 1/6. So far, the best known explicit protocol is the one by Arora et al, with ε(2) = 1/10 (corresponding to k = 2). In the current work, we present the construction of protocols approaching arbitrarily close to zero bias, i.e. ε(k) for arbitrarily large k. We connect the algebraic properties of Mochon’s assignments—at the heart of his proof of existence—with the geometric properties of the unitaries whose existence he proved. It is this connection that allows us to find these unitaries analytically. In particular, we find that the key unitary involved in the bias 1/10 protocol can be seen as an elementary example of the general solution. 

Since January 2019 Chrysoula Vlachou is a post-doc in QuIC (Center for Quantum Information and Communication), ULB (Université Libre de Bruxelles) working mainly on quantum cryptography. Before that (2014-2018), Vlachou did her PhD in Physics in IST (Instituto Superior Tecnico, Lisboa) in the Security and Quantum Information Group (SQIG-IT). Her thesis was on applications of quantum walks in quantum cryptography and finite-temperature topological phase transitions.

Host: Prof. Stefan Wolf