IQIM Postdoctoral and Graduate Student Seminar
Abstract: In this talk, I will discuss weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating party can try to bias the output bit towards a preferred value. For weak coin flipping the parties have known opposite preferred values. By a weak coin flipping protocol with bias ϵ we mean that neither player can force the outcome towards their preferred value with probability more than 1/2+ϵ. While it is known that classically, ϵ=1/2 (the worst possible), Mochon showed in 2007 that quantumly, weak coin flipping can be performed with arbitrarily small bias (near perfect). His non-constructive proof used the so-called point game formalism—a series of equivalent reductions which were introduced by Kitaev to study coin-flipping. He constructed point games with bias ϵ_M(k)=1/(4k+2) to prove the existence. The best known explicit protocol, however, had bias approaching ϵ_M(1)=1/6 (also due to Mochon, 2005).
In our work, we try to make the non-constructive part of the proof constructive, to wit, we make three main contributions towards the conversion of point-games into explicit protocols. First, we propose a framework—TIPG-to-Explicit-protocol Framework (TEF)—which simplifies the task of constructing explicit protocols. We use this framework to construct a protocol with bias ϵ_M(2)=1/10. We then give the exact formulae for the unitaries corresponding to the point-games due to Mochon, allowing us to describe (almost) perfect coin flipping protocols analytically, i.e. with bias ϵ_M(k) for arbitrarily large k. Finally, we introduce an algorithm we call the Elliptic Monotone Align (EMA) algorithm. This algorithm, together with TEF, lets us convert any point-game into an explicit protocol numerically. We conclude by giving another analytic construction of unitaries for Mochon's games using the ellipsoid picture introduced for the EMA algorithm.
To attend the talk, please register in advance. Enter your name and email and you'll receive the zoom link by email https://caltech.zoom.us/meeting/register/tZUkce-qqD4iHtf0-WWMuJDp-CfCx0xyM03w