Quantum Byzantine agreement

• A verifiable secret sharing protocol: A (n,k) secret sharing protocol allows a set of n players to share a secret, s such that only a quorum of k or more players can discover the secret. The player sharing (distributing the secret pieces) the secret is usually referred to as the dealer. A verifiable secret sharing protocol differs from a basic secret sharing protocol in that players can verify that their shares are consistent even in the presence of a malicious dealer.

1. Round 1 generate the GHZ state ${\displaystyle |\mathrm {Coin} _{i}\rangle ={\tfrac {1}{\sqrt {2}}}|0,0,\ldots ,0\rangle +{\tfrac {1}{\sqrt {2}}}|1,1,\ldots ,1\rangle }$ on ${\displaystyle n}$ qubits and send the ${\displaystyle k}$th qubit to the ${\displaystyle k}$th player keeping one part
2. Generate the state ${\displaystyle |\mathrm {Leader} _{i}\rangle ={\tfrac {1}{n^{3/2}}}\sum \nolimits _{a=1}^{n^{3}}|a,a,\ldots ,a\rangle }$ on ${\displaystyle n}$ qudits (quantum-computing components consistent of multiple qubits), an equal superposition of the numbers between 1 and ${\displaystyle n^{3}}$. Distribute the ${\displaystyle n}$ qudits between all the players[1]
3. Receive the quantum messages from all players and wait for the next communication round, thus forcing the adversary to choose which messages were passed.
4. Round 2: Measure (in the standard base) all ${\displaystyle \mathrm {Leader} _{j}}$ qubits received in round I. Select the player with the highest leader value (ties broken arbitrarily) as the "leader" of the round. Measure the leader's coin in the standard base.
5. Set the output of the QuantumCoinFlip protocol: ${\displaystyle v_{i}}$ = measurement outcome of the leader's coin.

To generate a random coin assign an integer in the range [0,n-1] to each player and each player is not allowed to choose its own random ID as each player ${\displaystyle P_{k}}$ selects a random number ${\displaystyle s{_{k}^{i}}}$ for every other player ${\displaystyle P_{i}}$ and distributes this using a verifiable secret sharing scheme.

At the end of this phase players agree on which secrets were properly shared, the secrets are then opened and each player ${\displaystyle P_{i}}$ is assigned the value

${\displaystyle s_{i}=\sum \,{s_{k}^{i}}{\text{for all secrets properly shared}}\mod n}$

This requires private information channels so we replace the random secrets by the superposition ${\displaystyle |\phi \rangle ={\tfrac {1}{\sqrt {n}}}\sum \nolimits _{a=0}^{n-1}|a\rangle }$. In which the state is encoded using a quantum verifiable secret sharing protocol (QVSS).[5] We cannot distribute the state ${\displaystyle |\phi ,\phi ,\ldots \phi \rangle }$ since the bad players can collapse the state. To prevent bad players from doing so we encode the state using the Quantum verifiable secret sharing (QVSS) and send each player their share of the secret. Here again the verification requires Byzantine Agreement, but replacing the agreement by the grade-cast protocol is enough.[6][7]

A grade-cast protocol has the following properties using the definitions in [6] Informally, a graded broadcast protocol is a protocol with a designated player called “dealer” (the one who broadcasts) such that:

1. If the dealer is good, all the players get the same message.
2. Even if the dealer is bad, if some good player accepts the message, all the good players get the same message (but they may or may not accept it).

A protocol P is said to be achieve graded broadcast if, at the beginning of the protocol, a designated player D (called the dealer) holds a value v, and at the end of the protocol, every player ${\displaystyle P_{i}}$ outputs a pair ${\displaystyle (\mathrm {value} _{i},\mathrm {confidence} _{i})}$ such that the following properties hold: ${\displaystyle (\forall i,\mathrm {confidence} _{i}\in \{0,1,2\})}$

1. If D is honest, then ${\displaystyle \mathrm {value} _{i}}$ = v and ${\displaystyle \mathrm {confidence} _{i}}$ = 2 for every honest player ${\displaystyle P_{i}}$.
2. For any two honest players ${\displaystyle P_{i}}$ and ${\displaystyle P_{j},}$ ${\displaystyle \vert \mathrm {confidence} _{i}-\mathrm {confidence} _{j}\vert \leq 1}$.
3. (Consistency) For any two honest players ${\displaystyle P_{i}}$ and ${\displaystyle P_{j}}$, if ${\displaystyle \mathrm {confidence} _{i}>0}$ and ${\displaystyle \mathrm {confidence} _{j}>0}$, then ${\displaystyle \mathrm {value} _{i}=\mathrm {value} _{j}}$.

For ${\displaystyle t<{\tfrac {n}{4}}}$ the verification stage of the QVSS protocol guarantees that for a good dealer the correct state will be encoded, and that for any, possibly faulty dealer, some particular state will be recovered during the recovery stage. We note that for the purpose of our Byzantine quantum coin flip protocol the recovery stage is much simpler. Each player measures his share of the QVSS and sends the classical value to all other players. The verification stage guarantees, with high probability, that in the presence of up to ${\displaystyle t<{\tfrac {n}{4}}}$ faulty players all the good players will recover the same classical value (which is the same value that would result from a direct measurement of the encoded state).