Paper 2022/1101

Solutions to quantum weak coin flipping

Abstract

Weak coin flipping is an important cryptographic primitive, as it is the strongest known secure two-party computation primitive, that classically becomes secure only when certain assumptions are made (e.g. computational hardness), while quantumly there exist protocols that achieve arbitrarily close to perfect security. This breakthrough result was established by C. Mochon in 2007 [arXiv:0711.4114], however, his proof of existence was partially non-constructive, thus, setting back the proposal of explicit protocols. In this work, we report three different solutions to the quantum weak coin flipping problem. In particular, we propose different methods that result---either analytically or numerically---in the operators needed to construct weak coin flipping protocols with different levels of security, including nearly perfect security. In order to develop these methods, we study the quantum weak coin flipping problem from both an algebraic and a geometric perspective. We also analytically construct illustrative examples of weak coin flipping protocols achieving different levels of security.

Note: Parts of the original work presented in this paper have been presented in the STOC19 (https://dl.acm.org/doi/10.1145/3313276.3316306) and SODA21 (https://epubs.siam.org/doi/10.1137/1.9781611976465.58) conferences.