pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

Quantum coin flipping

André Chailloux, Université de Paris-Sud

joint work with Iordanis Kerenidis

Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt(2). Closing this gap has been one of the important open questions in quantum cryptography.

In this talk, we will present a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/sqrt(2). More precisely, we will show how to use any weak coin flipping protocol with cheating probability 1/2 + ε in order to achieve a strong coin flipping protocol with cheating probability 1/sqrt(2) + O(ε). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon. In the second part of the talk, we will describe Kitaev's formalism for coin flipping and how it was used by Mochon for the construction of the optimal weak coin flipping protocol.