On the Complexity of Fair Coin Flipping

Iftach Haitner, Nikolaos Makriyannis, Eran Omri

Dana Dachman-Soled, Yehuda Lindell, Mohammad Mahmoody +1 more

Gene S. Kopp, John D. Wiltshire-Gordon

Ou Ruan, Zhou Jing, Guohua Cui +1 more

Coin-flipping protocols allow mutually distrustful parties to generate a random bit with uniform distribution. Minimizing bias and keeping fairness are two key requirements in designing such protocols. However, the best previously known fair coin-flipping protocol only guarantees with bias O (1/ r ). In the paper, we introduce a new approach for fair coin-flipping protocol construction by using Garay et al ’s “resource fairness” technique and propose a resource-fair two-party coin-flipping protocol according to the standard real/ideal simulation paradigm. Compared with the other coin-flipping protocols, our protocol enjoys an important advantage that its bias is 0.

Roy van Houte

Quantum coin flipping is a cryptographic primitive in which two or more parties that do not trust each other want establish a fair coin flip. These parties are not physically near each other and use quantum communication channels to interact. A quality of protocols is measured by the best possible cheating strategy, which is the solution of a complex semidefinite optimization problem. In this master thesis we show new explicit bounds in multiparty quantum coin flipping, we investigate how to explicitly formulate these problem in a standard form, we show that a fair coin flip results in the lowest possible bias and we determine more measures of the quality of a protocol. Furthermore, this master thesis presents a rigorous and detailed mathematical description of semidefinite optimization, quantum information theory and quantum coin flipping. This thesis also includes an article written together with J. Mulderij, T. Attema, I. Chiscop and F. Phillipson on distributed quantum computing. In this article, we pose new questions and formulate integer linear programs that solve to find optimal assignment of qubits to computers for a given network of quantum computers and quantum algorithm.

Tal Moran, Moni Naor, Gil Segev