User:Tylerni7/Cryptographic coin flipping

In cryptography a coin toss is a cryptographic primitive which allows two physically separated parties, Alice and Bob, who do not trust each other to establish a shared random bit. This idea is a cryptographic analogue of a coin flip, in which Alice and Bob will both observe the outcome (heads or tails, or equivalently a bit 0 or 1) of a coin. However, when Alice and Bob are physically separated, this becomes a difficult prospect. The concept of a non-local coin toss was first posed in 1981 by Manuel Blum.

A simple scenario where this primitive may be useful is the following. Imagine Alice and Bob, who do not trust each other, want to play a game of chess over the phone. In order to determine who gets to make the first move, they wish to toss a coin. Clearly if one party flips a coin and reports the result, it is possible for them to lie. The goal of a cryptographic coin tossing protocol, however, is to make it possible for the parties to agree on an outcome that neither can influence heavily.

Formalism

A coin toss is a cryptographic communications protocol. The protocol dictates what information Alice and Bob can generate and when they should share it with each other. The players do not have a source of shared randomness, but can perform any local operations they wish (though they may have bounded computational power). A cheating player may choose to not follow the protocol, but must still communicate messages which conform to the protocol. For example, if a step requires five random bits to be sent from Bob to Alice, he may instead send non-random bits, but he still must send five.

As a cryptographic protocol, there are a number of questions that are natural to ask about coin tossing, such as:

• With what types of players can such a protocol deliver a truly random bit?
• Can the requirements of the coin toss be relaxed to make it easier for Alice and Bob to carry out?
• How certain can one be that their opponent did not cheat?
• If one's opponent does cheat, how can that be detected and proven?

To attempt to answer these questions, the problem of coin tossing is formalised thusly:

Denote the probability of Alice determining the result of the coin toss is the bit $x$ and Bob determining the result is the bit $y$ to be $P_{x,y}$ If neither Alice nor Bob cheat, the outcome of the coin tossing protocol should have the following probabilities

$P_{0,0}=P_{1,1}={\frac {1}{2}},\quad P_{0,1}=P_{1,0}=0~.$

In other words, Alice and Bob should always agree on the outcome bit, which should have an equal chance of being 0 or 1.

Of course, it is possible that Alice or Bob does not follow the protocol when playing the game in order to try to adjust the outcome in their favor. In this case we want to know the bias, or how strongly one party can skew the probability distribution of the coin toss if the protocol is not followed.

It is useful to note the maximum probability of a certain outcome when Alice or Bob is cheating. Letting ${\widetilde {A}},{\widetilde {B}}$ represent any possible strategy for Alice and Bob, respectively, the maximum probabilities that can be obtained by cheating are

$P_{x,*}=\max _{\widetilde {B}}\;\operatorname {Pr} [{\text{Alice outputs }}x],\quad P_{*,y}=\max _{\widetilde {A}}\;\operatorname {Pr} [{\text{Bob outputs }}y]$

We say that the bias is at most $\varepsilon$ if

$P_{x,*},P_{*,y}\leq {\frac {1}{2}}+\varepsilon$

In this sense, the fairness of a particular protocol can be measured by how small its bias is.

Additionally, one may also consider the case in which one party detects the other party cheating. In this case, the coin flipping game can be modified to allow for some chance of an abort signal, in which case no bit is derived and the protocol is abandoned.

Classical coin flipping

In a classical setting (one in which Alice and Bob do not share quantum information), the security of coin tossing relies on the presumed computational difficulty of solving certain problems. When the two parties have bounded computational resources, one-way functions can be used to implement bit commitment.

Bit commitment is a related cryptographic primitive in which Alice chooses a bit and and can later prove to Bob her choice of bit, if challenged to do so. A scheme of this sort allows for coin tossing: Alice can commit to the outcome of a coin toss, the outcome of which she does not reveal to Bob. Bob guesses whether Alice's coin was heads or tails, and communicates his guess to Alice. Alice can then use the bit commitment scheme to reveal to Bob the outcome she obtained. Bob wins the game if his guess was correct, and Alice wins otherwise.

Although the protocols seem related, bit commitment is strictly more powerful than coin tossing. That is, while the bit commitment primitive can be used to implement coin tossing, a coin tossing primitive cannot be used to implement bit commitment.

Classical coin flipping is not possible if players are allowed unlimited computational power. That is, if Alice or Bob have access to arbitrary computational resources, at least one party can cheat to obtain a bias of $\varepsilon ={\frac {1}{2}}$, making the game always come out in their favor. This impossibility result holds both for strong and weak coin flipping (discussed below).

Quantum coin flipping

A portion of a quantum coin flipping game, with Hilbert spaces ${\mathcal {V}},{\mathcal {P}},{\mathcal {M}}$ assigned to Alice, Bob, and the message space between them, respectively.

In the case where the coin tossing protocol allows Alice and Bob to exchange and compute with quantum information, protocols exist which are unconditionally robust. That is, their security relies on validity of quantum mechanics as the true laws of physics, and therefore the security guarantees on the protocol hold so long as Alice and Bob obey the rules imposed by quantum theory.

A quantum coin flipping protocol is an example of a quantum game between Alice and Bob. Informally, in such protocols, the two parties hold some number of qubits; the qubits with each party are initialized to a fixed pure state. The initial joint state is therefore unentangled across Alice and Bob. The two parties then play in turns. Suppose it is Alice's turn to play. Alice applies a unitary transformation on her qubits and then sends one or more qubits to Bob. Sending qubits does not change the overall superposition, but rather changes the ownership of the qubits. This allows Bob to apply his next unitary transformation on the newly received qubits. After a pre-determined number of rounds of play, each player makes a measurement of their qubits and announces the outcome as the result of the protocol.

Formally, the players Alice and Bob, hold some number of qubits. The Hilbert spaces corresponding to Alice's private quits, the message quits, and Bob's private quits are denoted as ${\mathcal {V}},{\mathcal {M}},{\mathcal {P}}$, respectively. When the protocol starts, all the qubits are initialized to state$|0\rangle$. The communication consists of $t\geq 1$ alternations of message exchange ("rounds"), in which the two players "play". The protocol specifies which player plays first. In the $i$th round, $i\geq 1$, suppose it is Alice's turn to play. Alice applies a unitary operator $A_{i}$ to the qubits in ${\mathcal {V}}\otimes {\mathcal {M}}$. Then, Alice sends the qubits in ${\mathcal {M}}$ to Bob. Consequently, Bob's state space after receiving the $i$th message is ${\mathcal {M}}\otimes {\mathcal {P}}$. In the next, $(i+1)$th round, Bob may thus apply unitary operation $B_{i+1}$ to the message qubits previously in Alice's control.

At the end of the $t$ rounds of play, Alice and Bob observe the qubits in their possession according to some measurement with outcomes $0,1$ or "abort". The outcomes of these measurements represent their outputs. We emphasize that there are no measurements until all rounds of communication are completed. A protocol with intermediate measurements may be transformed into this form by appealing to standard techniques.

When both parties follow the protocol, they do not abort. In other words, only get outcomes $0$ or $1$. Further, each party outputs the same bit and each bit occurs with probability $1/2$.

As in the classical protocol, cheating players need not send or prepare quantum states as dictated by the protocol, but must send messages which conform to the protocol in terms of number of qubits sent. In particular, a cheating player may maintain an arbitrary number of qubits for their private use, may apply arbitrary unitary transformations to the qubits in their control, and an arbitrary measurement at the end of the protocol. These possibilities together capture all possible cheating strategies allowed by quantum mechanics.

Semidefinite programming formulation

Kitaev showed that the maximum cheating probability for a player in a quantum coin tossing game can be formulated as a semidefinite program (SDP). We present the SDP corresponding to Bob cheating in order to maximize outcome $0$. The other cases are similar.

For concreteness, assume that Alice plays first, and that the number of rounds $t$ is even. Denote the state (reduced density matrix) of the qubits corresponding to the space ${\mathcal {V}}\otimes {\mathcal {M}}$ at the beginning of round $i,i\geq 1$, by $\rho _{i-1}$. Initially, $\rho _{0}=|{\bar {0}}\rangle \langle {\bar {0}}|$. Now consider an odd round $i\geq 1$. After Alice applies the unitary $A_{i}$ in round $i$, the state becomes $\rho _{i}=A_{i}\rho _{i-1}A_{i}^{\dagger }$. Alice then sends the qubits corresponding to ${\mathcal {M}}$ to Bob. The state of Alice's qubits, corresponding to space ${\mathcal {V}}$, can be written as $\operatorname {Tr} _{\mathcal {M}}(\rho _{i})$. In round $i+1$, when Bob operates on the message qubits and his private quits, the reduced density matrix of Alice's qubits does not change. Therefore $\operatorname {Tr} _{\mathcal {M}}(\rho _{i})=\operatorname {Tr} _{\mathcal {M}}(\rho _{i+1})$. Bob seeks to maximize the probability of outcome$0$ at the end of the game, i.e., $\operatorname {Tr} (E_{0}\rho _{t})$. Thus, the maximum cheating probability is at most the optimum of the following SDP: ${\begin{array}{rcl}{\displaystyle \max _{(\rho _{i})}}&\operatorname {Tr} (E_{0}\rho _{t})\\{\text{subject to}}&\rho _{0}=|{\bar {0}}\rangle \langle {\bar {0}}|\\&\operatorname {Tr} _{\mathcal {M}}(\rho _{i+1})=\operatorname {Tr} _{\mathcal {M}}(A_{i}\rho _{i-1}A_{i}^{\dagger })&\quad {\text{for odd }}i\in \{0,\ldots ,t\}\\&\rho _{i}\succeq 0&\forall i\in \{0,1,\dotsc ,t\}~.\end{array}}$

In fact, every feasible solution of the SDP corresponds to a possible cheating strategy for Bob. Consider such a feasible solution and a purification $|psi_{i-1}\rangle \in {\mathcal {V}}\otimes {\mathcal {M}}\otimes {\mathcal {P}}$, with $\dim({\mathcal {P}})\geq \dim({\mathcal {V}}\otimes {\mathcal {M}})$ of the state $\rho _{i-1}$ for each odd $i$. Then $(A_{i}\otimes I)|\psi _{i-1}\rangle$ is a purification of $\rho _{i}$. Since $\operatorname {Tr} _{\mathcal {M}}(\rho _{i+1})=\operatorname {Tr} _{\mathcal {M}}(A_{i}\rho _{i-1}A_{i}^{\dagger })$, the unitary equivalence of purifications then guarantees that there is a unitary operator $B'_{i+1}$ on ${\mathcal {P}}$ such that $(I\otimes B'_{i+1})(A_{i}\otimes I)|\psi _{i-1}\rangle =|\psi _{i+1}\rangle$. Thus, we get a cheating strategy for Bob that achieves probability equal to the objective function value of the SDP, and that the SDP characterizes the optimum cheating probability for Bob.

The dual of the above SDP is :

${\begin{array}{rcl}{\displaystyle \min _{Z^{A}(i)}}&\operatorname {Tr} (Z^{A}(0)|{\bar {0}}\rangle \langle {\bar {0}}|)\\{\text{subject to}}&Z^{A}(t)\otimes I\succeq E_{1}\\&Z^{A}(0)\succeq A_{1}^{\dagger }(Z^{A}(1)\otimes I)A_{i}\\&Z^{A}(i-1)\otimes \mathbb {I} \succeq A_{i}^{\dagger }(Z^{A}(i+1)\otimes \mathbb {I} )A_{i}\\&Z^{A}(i){\text{ is Hermitian }}&\forall i\in \{0,1,\dotsc ,t\}~.\end{array}}$

The dual variables $Z^{A}$ may be interpreted as sub-goals for Bob: at each step $i$ he wishes to maximize $\operatorname {Tr} (Z^{A}(i)\operatorname {Tr} _{{\mathcal {M}}\otimes {\mathcal {P}}}(\rho _{i}))$.

Weak coin flipping

A weak coin flipping protocol is one in which Alice and Bob each have a prefered (and opposite) outcome. The protocol restricts Alice and Bob from biasing the outcome of a coin too far in their favor. However, it makes no restrictions on how much they may bias it towards their opponents prefered outcome. This is a natural way to represent a coin flipping protocol: Alice and Bob each pick a side of the coin, and whoever guessed the outcome correctly wins.

Without loss of generality, Bob can prefer the outcome 1, and Alice the outcome 0, and so the weak coin flipping protocol has the restriction that

$P_{*,1}\leq {\frac {1}{2}}+\varepsilon ,\quad P_{0,*}\leq {\frac {1}{2}}+\varepsilon$

Unconditional weak coin flipping protocols exist only for quantum players. With quantum information and a multi-round protocol, it is also possible for a quantum weak coin flipping protocol to achieve an arbitrarily small bias.

Quantum weak coin flipping example

A simple example of a weak coin flipping protocol is given by Mochon:

Alice and Bob work in the space $\mathbb {C} ^{3}$ spanned by the vectors $|A\rangle ,|B\rangle ,|U\rangle$ (representing a win for Alice, Bob, or undecided), and share a message space $\mathbb {C} ^{2}$. A unitary operation will also be used, which is defined as

$\operatorname {Rot} (|\alpha \rangle ,|\beta \rangle ,\epsilon )={\begin{pmatrix}|\alpha \rangle &|\beta \rangle \end{pmatrix}}{\begin{pmatrix}{\sqrt {1-\epsilon }}&-{\sqrt {\epsilon }}\\{\sqrt {\epsilon }}&{\sqrt {1\epsilon }}\end{pmatrix}}{\begin{pmatrix}\langle \alpha |\\\langle \beta |\end{pmatrix}}+{\begin{pmatrix}I-|\alpha \rangle \langle \alpha |-|\beta \rangle \langle \beta |\end{pmatrix}}$

The winner of the coin toss will be whomever first outputs $|1\rangle$ in the shared message space. With honest play, the game can be specified by the probability that the $i$^th message sent is $|1\rangle$, which can be denoted by $\{p_{i}\}$.

At round $i$, the probability of a win going to Alice, Bob, or being undecided is:

${\begin{aligned}P_{A}(i)&={\begin{cases}P_{A}(i-1)&{\text{ for i even}}\\P_{A}(i-t)+p_{i}P_{U}(i-1)&{\text{ for i odd}}\end{cases}}\\P_{B}(i)&={\begin{cases}P_{B}(i-t)+p_{i}P_{U}(i-1)&{\text{ for i even}}\\P_{B}(i-1)&{\text{ for i odd}}\end{cases}}\\P_{U}(i)&=(1-p_{i})P_{U}(i-1)\end{aligned}}$

The game proceeds as follows:

1. Alice prepares $|U\rangle \otimes |0\rangle$ and Bob prepares $|u\rangle$
2. For $i=1,\ldots ,n$, (let X represent Alice and her state $|A\rangle$ and Y represent the corresponding quantities for Bob if $i$ is even, otherwise switch X and Y)
   1. X applies the operation $\operatorname {Rot} (|U\rangle \otimes |0\rangle ,|X\rangle \otimes |1\rangle ,p_{i})$
   2. X sends the message qubit to Y
   3. Y applies $\operatorname {Rot} (|U\rangle \otimes |1\rangle ,|X\rangle \otimes |0\rangle ,{\frac {p_{i}P_{U}(i-1)}{P_{X}(i)}})$
   4. Y measures the message qubit. If the output is 1, Y terminates the game and declares foulplay.
3. Alice and Bob will each measure their qutrit. If the outcome is $U$, they output themselves as the winner, otherwise they report the measurement outcome as the winner.

For a set of values of $\{p_{i}\}$ such that $p_{i}\in (0,1)$ and $P_{A}(n)=P_{B}(n)={\frac {1}{2}}$, this protocol achieves a bias of ${\frac {1}{6}}$.

Strong coin flipping

A strong coin flipping protocol is one in which biases away from randomness in either direction are limited. That is, Alice (or Bob) is not able to force either heads or tails to show up more than a certain amount. This is in contrast to weak coin flipping (in which each player has a prefered coin face), and is somewhat less of a natural way to represent the problem. Nevertheless, a strong coin flipping protocol meets all the criteria of a weak coin flipping protocol, but with some additional guarantees.

The restriction in the strong coin flipping case can be written as

$P_{*,1}\leq {\frac {1}{2}}+\varepsilon ,\quad P_{1,*}\leq {\frac {1}{2}}+\varepsilon$

Note that now both Alice and Bob are trying to maximize the probability the other player returns 1 (though this can equivalently be 0 for both players).

In the quantum setting, unconditional strong coin flipping protocols exist, but they suffer from a large bias of $\varepsilon ={\frac {1}{2}}-{\frac {1}{\sqrt {2}}}$. It has been shown that this is the smallest bias possible for strong quantum coin flipping. Additionally, it has been shown that a weak coin flipping protocol can be used to construct strong coin flipping protocols with biases arbitrarily close to the optimum.

Proof of quantum strong coin flipping lower bound

Using the SDP formulation of a quantum coin flipping game given above, the lower bound on $\varepsilon$ is fairly simple. Taking $Z^{B}$ to be Alice's equivalent value for Bob's $Z^{A}$, and $\{\rho _{j}^{H}\}$ to be the set of intermediate states in an honest game (Alice and Bob both following the protocol), define

$F_{j}=\operatorname {Tr} ((Z^{A}(j)\otimes \mathbb {I} \otimes Z^{B}(j))\rho _{j}^{H})$

By the constraints seen in the SDP formulation, $F_{j}\geq F_{j+1}$. Also using our SDP, along with strong duality, $F_{0}$ must be $P_{1,*}P_{*,1}$ Additionally, from the above formula and strong duality on our SDP, we can see that $F_{0}=P_{1,*}P_{*,1}$, and by the definition of a fair coin tossing game, $F_{n}={\frac {1}{2}}$. Therefore $P_{1,*}P_{*,1}\geq {\frac {1}{2}}$, which means that the minimum value we can get for $P_{1,*}$ and $P_{*,1}$ is ${\frac {1}{\sqrt {2}}}$. This gives us a bias of $\varepsilon ={\frac {1}{\sqrt {2}}}-{\frac {1}{2}}$.

Multiparty coin flipping

Multiparty coin flipping generalizes the idea of Alice and Bob securely flipping a coin to $k$ parties flipping a coin. As before, if all parties are honest, a multiparty coin flip should output 0 or 1 with equal probability. Additionally, all parties should agree on the outcome, denoted $b$, of the coin toss. Cheating is generalized from one player diverging from the protocol and the other being honest to having $g\geq$ parties play honestly and the remaining $k-g$ cheating. If at least $g$ players follow the protocol, the bias is bounded

$\operatorname {Pr} [b=0]\in [{\frac {1}{2}}-\varepsilon ,{\frac {1}{2}}+\varepsilon ]$

In the classical setting, nontrivial protocols (those in which $\varepsilon <{\frac {1}{2}}$) exist with unconditional security only when the majority of players are honest. In a general classical setting, a bias of ${\frac {1}{2}}-\Omega (\delta ^{1.65})$ can be achieved when ${\frac {g}{k}}\geq {\frac {1}{2}}+\delta$.

However, quantum multiparty coin flipping has nontrivial protocols for any nonzero fraction of honest players. Dishonest players are afforded infinite computational abilities, so long as they obey quantum mechanics, as well as unlimited communication with the other dishonest players. Messages between two parties are also considered secure, so that dishonest players can read the message space only if dictated by the coin flipping protocol.

A common primitive used in classical multiparty communication is a broadcast. However, in the quantum setting, this is generally impossible. However, a variant can be used along with two-party coin tosses to construct a quantum multiparty coin flipping protocol.

Quantum multiparty coin flipping protocol

The quantum broadcast channel used here is a channel that maps the space $\mathbb {C} ^{2}$ to $\mathbb {C} ^{2k}$ (a one qubit to k qubit channel). This channel's action can be seen by it's action on a general qubit state $\operatorname {Broadcast} (\alpha |0\rangle +\beta |1\rangle )=\alpha |0\rangle ^{\otimes k}+\beta |1\rangle ^{\otimes k}$. Each of the k qubits will then be distributed to each of the parties who are to receive the broadcast. This can be implemented unitarily using CNOT gates.

When all parties are honest, this channel has the following properties:

• One quantum broadcast can be simulated with $2k-1$ uses pairwise quantum channels
• One classical broadcast can be simulated with one quantum broadcast
• One use of a pairwise quantum channel can be simulated using $k+1$ quantum broadcasts.

Additionally, if exactly one party follows the broadcast protocol honestly, replacing any of these actions with their simulated counterparts will not give the dishonest parties any advantage.

A quantum multiparty coin flipping protocol between parties labelled $1,\ldots ,k$ can then be constructed as follows  :

1. For $i=1,\ldots ,k-1$, have parties $i$ and $i+1$ perform a two party weak coin toss. The winner will advance to the next stage of the protocol, and the loser will not.
2. If the number of parties is odd, the party with the highest label will advance to the next round automatically.
3. When only two parties remain, they use a two party strong coin tossing protocol to determine the outcome of the overall game.

Recall that a weak coin toss is possible with arbitrarily small bias, and a strong coin toss is possible with bias arbitrarily close to ${\frac {1}{2}}-{\frac {1}{\sqrt {2}}}$. So the probability of a particular honest player advancing to the final round is $P_{H}={\frac {(1-2\varepsilon )^{\log k}}{k}}$, and the probability of a particular cheating player advancing to the final round is $P_{C}={\frac {(1+2\varepsilon )^{\log k}}{k}}$.

If a game has only one honest player, analysis is simple: the total bias for the game will be

$P_{H}({\frac {1}{2}}-{\frac {1}{\sqrt {2}}}+\varepsilon )+(1-P_{H})={\frac {1}{2}}-\Omega ({\frac {1}{k}})$

To generalize to the case of multiple good players, the lightest-bin protocol can be implemented from the classical multiparty coin tossing procedure. This procedure works as follows to select a committee of $c$ parties:

1. Each of the $k$ players publicly assign themselves to a random bin, $B_{0}$ or $B_{1}$
2. If bin $B_{0}$ contains less than $\operatorname {Half} (k,c)$ parties, they advance to the next round. Otherwise the parties in $B_{1}$ advance to the next round.
3. Repeat this process until $c$ parties remain.

Here, $\operatorname {Half} (k,c)$ is a function approximately equal to $k/2$ defined as follows: represent $k$ as $2(c+1)i+j$, where $i$ is the largest integer possible so that $2(c+1)i\leq k$. Then $\operatorname {Half} (k,c)=2(c+1)i$.

This selection procedure has the property that if there were originally a fraction of honest parties $\delta$, with probability at least ${\frac {1}{2}}$ a committee of size order ${\frac {1}{\delta }}$ will be selected with at least one honest party.

Thus, the multiparty coin tossing protocol can be modified to first use the lightest-bin protocol to shrink the number of parties to a fraction of order ${\frac {k}{g}}$. With good probability, this will still contain one honest player. Then using the multi-party coin tossing protocol with one honest party, the expected bias is ${\frac {1}{2}}-\Omega ({\frac {g}{k}})$. Thus, the bias for the multiparty coin tossing protocol with multiple good parties is ${\frac {1}{2}}-\Omega ({\frac {g}{k}})$.

Optimal quantum multiparty coin flipping

For any specific coin flipping protocol, let the probabilities $\{p_{i,b}\}$ represent the largest probability that party $i$ can be convinced of outcome $b$ by the other players, and let $p_{b}$ be the probability of outcome $b$ when all parties play honestly. Clearly $\prod _{i}p_{i,b}\geq p_{b}$, as the probabilities must be equal when all parties play honestly.

If $q$ represents the maximum probability that any party can force a particular output,

$q^{k}\geq \prod _{i}p_{i,b}\geq {\frac {1}{2}}\Rightarrow q\geq \left({\frac {1}{2}}\right)^{1/k}\geq 1-O\left({\frac {1}{k}}\right)$

Grouping together the parties into $k'=k/g$ parties acting together, the optimal bias a protocol can achieve is

$\varepsilon =1-O\left({\frac {g}{k}}\right)$

Therefore, the protocol presented above is asymptotically optimal.

See also

• Bit commitment
• Coin flipping
• Randomized communication complexity
• Oblivious transfer
• Quantum cryptography
• Quantum interactive proofs