Quantum coin flipping

André Chailloux — arXiv:0904.1511

André talks about the divorce of Alice and Bob: they're divorcing and they need to flip a coin to know who's gonna keep the car.

There are two versions:

State of the art:

The proof is a classical reduction to any optimal weak coin flipping protocol. The main trick is to create an unbiaised but unbalanced weak coin flipping.

« Bob does not touch Alice's private parts when he performs his operations » André is the only one that did not get his own joke!

I already seen this talk many times, but now comes the brand-new-QIP2010 part: the Kitaev's lower bound and the Mochon's paper condensed in 30 minutes.

You write the primal SDP, the dual, the right quantity, and it just “magically” appears. That does not really convince Dorit. (but SDP are black magic!)

The idea in Mochon's paper is to find in one block a protocol for weak coin flipping and dual feasible points that prove an upper bound on the optimal cheating probability. How do we find good ones? By making little drawings called Point Games. By making more and more complicated point games, one can achieve an ε biais point game.

I'm wondering more and more if one cannot use Learning technics in order to find useful point games. (ie, we can actually make real-life quantum protocols from them)(or maybe we can also just give a point game board to a monkey and wait long enough)

André's girlfriend just connect on skype! Everybody saw it. And now she's saying something in polish… (I offer some chocolate to anyone who tells me what she said…)

(As a Ph.D. student, I wonder what do we get from our adviser. André uses the same font that his adviser on his slides — courier new — and that is not a good idea)


Highly entangled states with almost no secrecy

Matthias Christandl, Norbert Schuch, and Andreas Winter — arXiv:0910.4151

There are way too many "entanglement cost", "entanglement of formation", "bound entanglement", "squashed entanglement" for me. Unable to liveblog this talk.


Improved extractors against bounded quantum storage

Anindya De and Thomas Vidick — arXiv:0911.4680

Using a public source (long almost-random classical string) and a seed (a short one) shared between Alice & Bob, how much randomness can they extract? In this model, the adversary has a bounded memory (he cannot store all the public source). The goal is to be protected against quantum adversaries.

Their extractor is based on Trevisan's extractor and not on 2 universal hashing.

Thomas is underlining the role that the conditional min-entropy plays. My problem: this quantity is ill-defined for continuous variables!

(There will be a workshop on Cryptography from storage imperfection in march in Caltech)


Improving the security of quantum protocols via open-and-commit

Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner — arXiv:0902.3918

They are able to transform a large class of cryptographic protocols into more secure protocols (weaker assumptions on the power of the cheater) by performing so commit phase in the middle. The number of round is linear in the number of rounds of the initial protocols. In particular for protocols in the bounded storage model, protocols are also secure against cheater that have only a small quantum computer.

Unconditional security from noisy quantum storage

Robert Koenig, Stephanie Wehner, and Juerg Wullschleger — arXiv:0906.1030  also arXiv:0911.2302

Yet another talk in which the Graal is two-party secure computation. The noisy storage model
* The adversary is computationally powerful
* Unlimited classical storage
* Actions are instantaneous
* Noisy storage

If the information sent to the memory (quantum channel) at a rate above the classical capacity of the channel, they are able to derive bound on the security of the protocols (bit commitment and oblivious transfer). They are even better than the one derived in the quantum bounded storage model! The protocols are composed by a weak string erasure (the quantum part) and classical post-processing.

Open question: by using the quantum capacity of channel, can we get a bound for other channels? (against individual attacks, at least)
Open question: what are the real limits on security?

(I always loved Stephanie's talks. They are accessible, she speaks quite slowly, her slides are helpful…)


Unitary plus causality implies localisability

Pablo Arrighi, Vincent Nesme, and Reinhard Werner

There is a trap: this talk is about quantum cellular automata! So there are actually people who study quantum cellular automata…

I. do. not. understand. (but I think, the words quantum cellular automata activated a switch in my head, and I suddenly remembered when I was little and my lecturer was trying to teach me cellular automata.)

(I was wondering why Vincent wrote localisability and not localizability. It's not because he is a snob. He speaks with a light British accent)