Strong coin tossing

Introduction

Alice and Bob, having recently divorced, want to decide who keeps the car #Blum. Both now live separate lives on opposite sides of the country, and to meet in person would be inconvenient and traumatic. A coin tossing protocol seeks to provide a sequence of information exchanges that allow the decision to be fairly made. Whether or not this is possible depends on the physical properties of the systems used for information exchange. Protocols which cannot satisfy the full requirements demanded of coin tossing are given a figure of merit depending on the maximum cheating probability they allow.

Coin tossing comes in two flavours, weak and strong. A weak coin tossing protocol suffices if the parties know which outcome the other prefers. This is the case in the divorcees example above, where both Alice and Bob would like to keep the car. Suppose outcome 0 means Alice keeps the car, and 1 means Bob does. A protocol need not protect against Alice biasing towards 1, nor Bob towards 0, and hence a weak coin toss protocol can be used. In contrast, a strong coin tossing protocol is needed when it is not known which outcome the other party prefers.

Coin tossing was introduced by Blum #Blum in 1981. There, computational assumptions were used to give security.

In a classical setting where unconditional security (i.e., security based only in a belief in the laws of physics) is sought, no protocol can offer any protection against a cheat #DoscherKeyl.

That quantum coin tossing protocols offer some advantage over classical ones was realized by Aharonov et al.\ #Aharonov&2, who introduced a protocol achieving a bias of #Aharonov&2#Spekkens&Rudolph2. For strong coin tossing, it has been shown by Kitaev that in any protocol, at least one party can achieve a bias greater than #Kitaev. It is not known whether this figure represents an achievable bias. The best known bias to date is . Two conceptually different methods have been introduced to achieve this. One is based on bit commitment, the other on sharing entanglement.

For weak coin tossing, Kitaev's bound is known not to apply and lower biases than have been achieved (see for example #Mochon2 for the best bias to date). Moreover, Ambainis has shown that a protocol with bias must have a number of rounds that grows as #Ambainis.

If one extends the scenario to allow for relativistic protocols, in which the impossibility of superluminal signalling is exploited for security, ideal coin tossing can be implemented with perfect security #Kent_CTBC.

Definitions

In a coin tossing protocol, two separated and mistrustful parties, Alice and Bob, wish to generate a shared random bit. We consider a model in which they do not initially share any resources, but have access to trusted laboratories containing trusted error-free apparatus for creating and manipulating quantum states. In general, a protocol for this task may be defined to include one or more security parameters, which we denote .

If both parties are honest, a coin tossing protocol guarantees that they are returned the same outcome, where outcome occurs with probability , or “abort” which occurs with probability , where for each , as the . The bias of the protocol towards party is denoted , where can deviate from the protocol in such a way as to convince the other (honest) party that the outcome is with probability at most , where the as the . We make no requirements of the protocol in the case where both parties cheat.

The bias of the protocol is defined to be . A protocol is said to be {\it balanced} if , for and .

We define the following types of coin tossing:

Ideal Coin Tossing: A coin tossing protocol is ideal if it has , that is, no matter what one party does to try to bias the outcome, their probability of successfully doing so is strictly zero. It is then said to be perfectly secure if for some finite values of , the quantities and are strictly zero, and otherwise is said to be secure.

Strong Coin Tossing: A strong coin tossing protocol is parameterized by a bias, . The protocol has the property that for all and , with equality for some , .

Weak Coin Tossing: A weak coin tossing protocol is also parameterized by a bias, . It has the property that and , with equality in one of the two inequalities.

An Entanglement Based Protocol

This protocol is found in #Colbeck, where a full security proof is given.

1. Alice creates copies of the state and sends the second qubit of each to Bob.
2. Bob randomly selects one of the states to be used for the coin toss. He informs Alice of his choice.
3. Alice and Bob measure their halves of the chosen state in the basis to generate the result of the coin toss.
4. Alice sends her half of the other state to Bob who tests whether it is the state it should be by measuring the projection onto . If his test fails, Bob aborts.

A Bit-Commitment Based Protocol

This protocol is found in #Ambainis, and a security proof given.

Define the states

The protocol then proceeds as follows:

1. Alice picks two random bits and , using a uniform distribution. She creates the qutrit state and sends it to Bob.
2. Bob picks a random bit, from a uniform distribution, and sends to Alice.
3. Alice sends and to Bob, who then checks that the state he received in step 1 matches (by measuring it with respect to a basis consisting of and two states orthogonal to it). If the outcome of the measurement is not the one corresponding to , Bob aborts.
4. Otherwise, the result of the coin flip is .

This protocol has Alice (imperfectly) commit a bit, , to Bob by encoding it using one of two non-orthogonal pairs of states. Bob then makes a guess of the committed bit by sending to Alice. The outcome is decided by whether Bob's guess was correct or not. Many of the schemes considered in the literature are of this type. The security of such a protocol is only as strong as the bit commitment on which it is based. Bounds on the possible biases achievable in bit commitment schemes are well known #Spekkens&Rudolph.

A Perfectly Secure Relativistic Scheme

The setup here involves Alice having two separated agents and , and likewise for Bob. The distance between and (likewise and ) is much smaller than that between and .

1. At time , sends a bit, , to choosing from a uniform distribution.
2. simultaneously sends his guess of , to .
3. checks that his received message arrived before time , and likewise, so does . If this is not the case, they abort.
4. The disconnected agents of Alice communicate with one another, as do those of Bob. Alice and Bob can then compute the coin toss outcome, .

References

1. M. Blum, in CRYPTO (1981), pp. 11--15.
2. C. Döscher and M. Keyl, An introduction to quantum coin tossing, e-print quant-ph/0206088 (2002).
3. D. Aharonov, A. Ta-Shma, U. V. Vazirani, and A. C. Yao, in Proceedings of the 32nd annual ACM symposium on Theory of computing (STOC-00) (ACM Press, New York, NY, USA, 2000), pp. 705--714.
4. R. W. Spekkens and T. Rudolph, Quantum Information and Computation 2, 66 (2001{\natexlab{a}}).
5. A. Kitaev, (unpublished), proof recreated in #Ambainis&.
6. A. Ambainis, Journal of Computer and System Sciences 68, 398 (2004), ISSN 0022-0000.
7. R. W. Spekkens and T. Rudolph, Physical Review A 65, 012310 (2001{\natexlab{b}}).
8. C. Mochon, Physical Review A 72, 022341 (2005).
9. A. Kent, Physical Review Letters 83, 5382 (1999).
10. R. Colbeck, quant-ph/0609034
11. A. Ambainis, H. Buhrman, Y. Dodis, and H. Röhrig, in Proceedings of the 19th IEEE Annual Conference on Complexity (IEEE Computer Society, 2004), pp. 250--259, ISBN 0-7695-2120-7.