Chrysoula Vlachou

Abstract 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 quantumly while classically, its security is completely compromised (unless one makes further assumptions, such as computational hardness). A WCF protocol is said to have bias \epsilon if neither party can force their preferred outcome with probability greater than 1/2 + \epsilon. Classical WCF protocols are shown to have bias 1/2, i.e., a cheating party can always force their preferred outcome. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias \epsilon(k)=1/(4k + 2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC'19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon's proof. As an example, we illustrate the construction of a WCF protocol with bias 1/14.

Weak coin flipping (WCF) is a fundamental cryptographic primitive, where two distrustful parties need to remotely establish a shared random bit, whilst having opposite preferred outcomes. A WCF protocol is said to have bias ε if neither party can force their preferred outcome with probability greater than 1/2+ε. Classical WCF protocols are shown to have bias 1/2, i.e., a cheating party can always force their preferred outcome. A lower bias can only be achieved by employing extra assumptions, such as computational hardness. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias ε(k) = 1/(4k + 2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC’19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon’s proof. The construction of an explicit WCF protocol approaching bias 1/14 is illustrated as an example.

High-dimensional entanglement promises to increase the information capacity of photons and isnow routinely generated exploiting spatio-temporal degrees of freedom of single photons. A curiousfeature of these systems is the possibility to certify entanglement despite strong noise in the data.We show that it is also possible to exploit this noisy entanglement by introducing a protocol thatuses mutliple subspaces of the high-dimensional system simultaneously. Our protocol can be used toincrease key rates in realistic conditions. To that end, we conduct two simulations of our protocol fornoise models that apply to the two most commonly used sources of high-dimensional entanglement:time-bins and spatial modes.