Oct 10

Seminar: Jérémie Roland “Quantum Weak Coin Flipping” (Oct 22, 2019)

Oct 22, 2019 – 13.00 – room P.2NO8.08

Speaker: Jérémie Roland (ULB)

Title: “Quantum Weak Coin Flipping”
Short abstract: “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 1/2+ϵ. It is known that any classical coin flipping protocol has bias ϵ=1/2, so that practically coin flipping can only be achieved under
computational assumptions. As for quantum protocols, Mochon showed in 2007 [arXiv:0711.4114] that weak coin flipping can be achieved under information-theoretic security with arbitrarily small bias (near
perfectly), but the previously best-known explicit protocol had bias 1/6 (also due to Mochon, 2005 [Phys. Rev. A 72, 022341]). We propose a framework to construct new explicit protocols achieving biases beyond 1/6. In particular, we construct explicit unitaries (quantum operations) for protocols with bias up to 1/10. To go beyond, we introduce an algorithm which, together with the framework, allows us to numerically construct protocols with arbitrarily small biases. This therefore provides a solution
for the problem of quantum weak coin flipping in the absence of noise.”