User:Tylerni7/Cryptographic coin flipping

In cryptography a coin toss is a cryptographic primitive which allows two parties, Alice and Bob, 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 as follows:

Alice and Bob want to flip a coin by telephone. (They have just divorced, life in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes... I'm flipping the coin.... You lost!"

— Manuel Blum,

Formalism

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

• Under what conditions is such a protocol secure?
• 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.

If Bob cheats, the bias is the amount he can cause Alice's probability distribution deviate from a uniform probability distribution. We say that the bias is equal to $\varepsilon$ if

$P_{0,0}+P_{0,1}\in [{\frac {1}{2}}-\varepsilon ,{\frac {1}{2}}+\varepsilon ]$

Likewise if Alice cheats with bias $\varepsilon$,

$P_{0,0}+P_{1,0}\in [{\frac {1}{2}}-\varepsilon ,{\frac {1}{2}}+\varepsilon ]$

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

It is also 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 measures }}x],\quad P_{*,y}=\max _{\widetilde {A}}\;\operatorname {Pr} [{\text{Bob measures }}y]$

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 game is simply canceled.

Bit commitment

Bit commitment is a related cryptographic primitive in which Alice chooses a bit and later proves to Bob her choice. A scheme of this sort clearly 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 prove to Bob the outcome she obtained. Bob will win the game if his guess was correct, and Alice will win 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 vs quantum coin flipping

In a classical setting (one in which Alice and Bob cannot share quantum information), the security of coin tossing relies on computational difficulty, which allows the use of bit commitment based on one-way functions. Moreover, 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, they can cheat with the help of these resources to obtain a bias of $\varepsilon ={\frac {1}{2}}$, making the game always come out in their favor. This result holds both for strong and weak coin flipping (discussed below).

In the case where the coin tossing protocol allows Alice and Bob to exchange quantum information, protocols exist which are unconditionally robust. That is, their security relies on the laws of physics, and therefore the protocol works so long as Alice and Bob obey physical laws.

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 a quantum coin flipping protocol, a single game can be regarded as an interactive proof between Alice and Bob. Looking at one player in particular, Bob's goal is to prove to Alice that he flipped a coin without cheating, whereas Alice's goal is to verify his proof is correct. Alice and Bob are each allowed to perform any operations they choose, represented as unitary operations $A_{i},B_{i}$, in their respective Hilbert spaces, which we will denote as ${\mathcal {V}},{\mathcal {P}}$ for Alice and Bob, respectively. Additionally, after one party completes a computation, they will send some output to their opponent, using the shared message space ${\mathcal {M}}$.

The states Alice interacts with are always in the Hilbert space ${\mathcal {V}}\otimes {\mathcal {M}}$, and can be denoted as $\rho _{i}$ at round $i$ of a coin flipping exchange. After passing through Alice's unitary for that round, the state can then be written as $\rho '_{i}=A_{i}\rho _{i}A_{i}^{\dagger }$. Using the partial trace, the state in Alice's space can easily be written as $\operatorname {Tr} _{\mathcal {M}}(\rho '_{i})$. When Bob operates on the message space and his own space, Alice's state cannot change. Therefore $\operatorname {Tr} _{\mathcal {M}}(\rho '_{i})=\operatorname {Tr} _{\mathcal {M}}(\rho _{i+1})$. Further, each of the $\rho _{i}$ states can be described as the partial trace over ${\mathcal {P}}$ of a state in the full Hilbert space ${\mathcal {V}}\otimes {\mathcal {M}}\otimes {\mathcal {P}}$. Using the purification theorem, two pure quantum states, $|\psi \rangle ,|\phi \rangle$, in the Hilbert space ${\mathcal {V}}\otimes {\mathcal {M}}\otimes {\mathcal {P}}$ can be constructed, such that $\rho '_{i}=\operatorname {Tr} _{\mathcal {P}}(|\psi \rangle \langle \psi |),\rho _{i+1}=\operatorname {Tr} _{\mathcal {P}}(|\phi \rangle \langle \phi |)$.

The unitary equivalence of purifications then guarantees that for any two pure states, $|\psi \rangle \langle \psi |,|\phi \rangle \langle \phi |$, whose partial traces are equal, there is a unitary operator $U$ such that $|\psi \rangle =(\mathbb {I} \otimes U)|\phi \rangle$. Therefore, Bob is guaranteed a strategy to take $\rho '_{i}$ to $\rho _{i+1}$ by choosing $B_{i}=U$.

At the end of the game, Alice and Bob must each make measurements on their quantum state in order to determine the outcome of the coin toss. Most generally this can be thought of as a positive operator valued measurement (POVM), which has outcomes for the coin returning 0, 1, or perhaps also an abort signal, if cheating is detected. The probability of any particular outcome associated with measurement $E_{i}$ with final state $\rho _{n}$ is then returned with probability $\operatorname {Tr} (E_{i}\rho _{n})$.

With this formulation, it is possible to present any cheating strategy for a player in a quantum coin tossing game as a semidefinite program (SDP). A cheating player seeks to maximize the probability of a certain result $j$ at the end of the game, $\operatorname {Tr} (E_{j}\rho _{n})$, by maximizing over all choices of intermediate states for the opponent $\{\rho _{i}\}$. As noted above, any set of $\rho _{i}$ values in which Alice's values are consistent is achievable by some unitary strategy for Bob, and so Bob need only maximize over all $\rho _{i}$ values.

So the SDP for Bob maximising his chance of winning (by he and Alice obtaining the result 1) can be written as

${\begin{array}{rl}{\displaystyle \max _{\{\rho _{i}\}}}&\operatorname {Tr} (E_{1}\rho _{n})\\{\text{subject to}}&\rho _{0}=|0\rangle \langle 0|,\operatorname {Tr} _{\mathcal {P}}(\rho _{i+1})=\operatorname {Tr} _{\mathcal {P}}(A_{i}\rho _{i}A_{i}^{\dagger })\\&\forall i,\rho _{i}\succeq 0\end{array}}$

And the dual problem can be worked out and simplified to

${\begin{array}{rl}{\displaystyle \min _{Z^{A}\in \operatorname {L} ({\mathcal {V}})}}&\operatorname {Tr} (Z^{A}(0)|0\rangle \langle 0|)\\{\text{subject to}}&Z^{A}(n)=E_{1},\;\forall i,Z^{A}(i)\otimes \mathbb {I} \geq A_{i+1}^{\dagger }(Z^{A}(i+1)\otimes \mathbb {I} )A_{i+1}\\&\forall i,Z^{A}(i){\text{ is Hermetian}}\end{array}}$

Where $Z^{A}$ can be interpreted as sub-goals for Bob--at each step $i$ he wants to maximize $\operatorname {Tr} (Z^{A}(i)\operatorname {Tr} _{\mathcal {V}}(\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 a game in which Alice and Bob are both playing fairly, 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}{2}}-{\frac {1}{\sqrt {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