==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
\frac{1}{2\sqrt{2}} #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
\frac{1}{\sqrt{2}}-\frac{1}{2} #Kitaev. It is not known
whether this figure represents an achievable bias. The best known
bias to date is \frac{1}{4}. 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
\frac{1}{\sqrt{2}}-\frac{1}{2} have been achieved (see for example
#Mochon2 for the best bias to date). Moreover, Ambainis has
shown that a protocol with bias \epsilon>0 must have a number of
rounds that grows as \Omega(\log\log\frac{1}{\epsilon})
#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 N_1,\ldots,N_r.
If both parties are honest, a coin tossing protocol guarantees that
they are returned the same outcome, b\in\{0,1\} where outcome b
occurs with probability \frac{1}{2}+\zeta_b(N_1,\ldots,N_r), or
“abort” which occurs with probability \zeta_2(N_1,\ldots,N_r),
where for each j\in\{0,1,2\}, \zeta_j(N_1,\ldots,N_r)\rightarrow 0
as the N_i\rightarrow\infty. The '' bias'' of the protocol towards
party P\in\{A,B\} is denoted
\epsilon_P=\max\left(\epsilon_P^0,\epsilon_P^1\right), where P can
deviate from the protocol in such a way as to convince the other
(honest) party that the outcome is b with probability at most
\frac{1}{2}+\epsilon_{P}^{b}+\delta_P^b(N_1,\ldots,N_r), where the
\delta_P^b(N_1,\ldots,N_r)\rightarrow 0 as the
N_i\rightarrow\infty. We make no requirements of the protocol in
the case where both parties cheat.
The '' bias'' of the protocol is defined to be
\max(\epsilon_A,\epsilon_B). A protocol is said to be {\it
balanced} if \epsilon_A^{b}=\epsilon_B^{b}, for b=0 and b=1.
We define the following types of coin tossing:
''' Ideal Coin Tossing:''' A coin tossing protocol is ideal if it
has \epsilon_A=\epsilon_B=0, 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 N_1,\ldots,N_r, the quantities
\zeta_j(N_1,\ldots,N_r) and \delta_P^b(N_1,\ldots,N_r) are
strictly zero, and otherwise is said to be '' secure''.
''' Strong Coin Tossing:''' A strong coin tossing protocol is
parameterized by a bias, \gamma. The protocol has the property that
\epsilon_P^b\leq\gamma for all P\in\{A,B\} and b\in\{0,1\}, with
equality for some P, b.
''' Weak Coin Tossing:''' A weak coin tossing protocol is also
parameterized by a bias, \gamma. It has the property that
\epsilon_A^0\leq\gamma and \epsilon_B^1\leq\gamma, 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.
# Alice creates 2 copies of the state \left | \psi \right>=\frac{1}{\sqrt{2}}(\left | 00 \right>+\left | 11 \right>) and sends the second qubit of each to Bob.
# Bob randomly selects one of the states to be used for the coin toss. He informs Alice of his choice.
# Alice and Bob measure their halves of the chosen state in the \{\left | 0 \right>,\left | 1 \right>\} basis to generate the result of the coin toss.
# 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 \left | \psi \right>. 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
\begin{array}{ccc}
\left | \phi_{b,x} \right>=\left\{\begin{array}{c}
\frac{1}{\sqrt{2}}(\left | 0 \right>+\left | 1 \right>) \,\,\,\,\,\, b=0,\, x=0\\
\frac{1}{\sqrt{2}}(\left | 0 \right>-\left | 1 \right>) \,\,\,\,\,\, b=0,\, x=1\\
\frac{1}{\sqrt{2}}(\left | 0 \right>+\left | 2 \right>) \,\,\,\,\,\, b=1,\, x=0\\
\frac{1}{\sqrt{2}}(\left | 0 \right>-\left | 2 \right>) \,\,\,\,\,\, b=1,\, x=1
\end{array}\right.
\end{array}
The protocol then proceeds as follows:
# Alice picks two random bits b\in\{0,1\} and x\in\{0,1\}, using a uniform distribution. She creates the qutrit state \left | \phi_{b,x} \right> and sends it to Bob.
# Bob picks a random bit, b'\in\{0,1\} from a uniform distribution, and sends b' to Alice.
# Alice sends b and x to Bob, who then checks that the state he received in step 1 matches (by measuring it with respect to a basis consisting of \left | \phi_{b,x} \right> and two states orthogonal to it). If the outcome of the measurement is not the one corresponding to \left | \phi_{b,x} \right>, Bob aborts.
# Otherwise, the result of the coin flip is b\oplus b'.
This protocol has Alice (imperfectly) commit a bit, b, 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 b' 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 A_1 and A_2, and likewise for Bob. The distance between A_1 and B_1 (likewise A_2 and B_2) is much smaller than that between A_1 and A_2.
# At time t_0, A_1 sends a bit, b\in\{0,1\}, to B_1 choosing b from a uniform distribution.
# B_2 simultaneously sends his guess of b, b' to A_2.
# B_1 checks that his received message arrived before time t_0+\frac{D}{c}, and likewise, so does A_2. If this is not the case, they abort.
# The disconnected agents of Alice communicate with one another, as do those of Bob. Alice and Bob can then compute the coin toss outcome, b\oplus b'.
==References==
# M. Blum, in ''CRYPTO'' (1981), pp. 11--15.
# C. Döscher and M. Keyl, ''An introduction to quantum coin tossing'', e-print quant-ph/0206088 (2002).
# 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.
# R. W. Spekkens and T. Rudolph, Quantum Information and Computation '''2''', 66 (2001{\natexlab{a}}).
# A. Kitaev, (unpublished), proof recreated in #Ambainis&.
# A. Ambainis, Journal of Computer and System Sciences '''68''', 398 (2004), ISSN 0022-0000.
# R. W. Spekkens and T. Rudolph, Physical Review A '''65''', 012310 (2001{\natexlab{b}}).
# C. Mochon, Physical Review A '''72''', 022341 (2005).
# A. Kent, Physical Review Letters '''83''', 5382 (1999).
# R. Colbeck, quant-ph/0609034
# 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.
Category:Quantum Communication

## Last modified:

Monday, October 26, 2015 - 17:56