Coordination

Consensus

In the Byzantine setting the focus is often on detectable agreement.

• algorithm for quantum byzantine agreement:

  • constant expected number of rounds compared for the randomized (adaptive adversary)
  • States: ${\sum }_{a=1}^{n^3}|a,\dots ,a⟩$
  • Byzantine needs verifiable (can agree that secret can be recovered) secret sharing for random numbers

• Improved Consensus in Quantum Networks

  • somehow requires fewer Bell pairs

Detectable Byzantine agreement (DBA)

Classical presentation is given in:

• Correctness all honest players commonly accept or reject the protocol. If all accept, then the protocol achieves broadcast
• Completeness if no player is corrupted, all accept
• Fairness if any honest player rejects, then the adversary gets no information about the sender's input

Further problem decomposition is presented in Detectable Byzantine Agreement Secure Against Faulty Majorities introducing

Detectable Precomputation:

• Correctness: all honest players commonly accept or reject the protocol. If all accept, then strong broadcast will be achievable
• Completeness if no player is corrupted, all accept
• Independence any honest player's input value need not be known

Quantum solutions

Protocols based on correlated lists:

• A Quantum solution to the Byzantine agreement problem

  • for weak agreement (or detectable broadcast), where a single faulty player may force everyone to abort
  • States: $|A⟩=|0,1,2⟩+|1,2,0⟩+|2,0,1⟩-|0,2,1⟩-|1,0,2⟩-|2,1,0⟩$ (Aharonov tri-partite qutrit states)
  • N = 3, f = 1

• Experimental demonstration of a quantum protocol for Byzantine agreement and liar detection says that the key is to construct secret and correlated lists

  • Based on the list $l_A$, $l_B$, and $l_C$ that are correlated and are produced from 4-qubit entangled states
  • States: $|{\Psi }^{(4)}{⟩}_{\mathrm{abcd}}=2|0011⟩-|0101⟩-|0110⟩-|1001⟩-|1010⟩+2|1100⟩$
  • N = 3, f = 1

• Quantum detectable Byzantine agreement for distributed data trust management in blockchain:

  • a lot of pairwise interaction among the lieutenants and the general
  • States: $|000⟩\pm |111⟩$, $|010⟩\pm |101⟩$, $|011⟩\pm |100⟩$ (GHZ-like)
  • N > f + 1

• Quantum Byzantine Agreement for Any Number of Dishonest Parties

  • trusted quantum source
  • States: ${\sum }_j|j⟩\otimes |j+i_1\text{ mod }d⟩\otimes ...|j+i_n\text{ mod }d⟩$ (multi-partite qudits)
  • N > f + 1
  • gives counterexamples for two other works (not listed here) to be incorrect

• A Quantum Detectable Byzantine Agreement Protocol using only EPR pairs

  • States: $|00⟩+|11⟩$ (EPR pairs)
  • N > f + 1

Protocols based on quantum signatures (which are to a large degree also based on correlated lists):

• Beating the fault-tolerance bound for byzantine agreement

  • Recusrive algorithm, similar to the one in LSP
  • Unlike LSP, signatures cannot be verified by all the parties
  • N > 2 f

Other works

• Quantum Distributed Consensus: not quite a "consensus" as the outcome is _always random

Cryptography

Digital signatures

• Quantum Digital Signatures

  Consider a set of sufficiently orthogonal (but not orthogonal) functions: $F=|f_1⟩,|f_2⟩,\dots ,|f_N⟩$,

  NB $N$ is much higher than $2^n$, where $n$ is the number of qubits

  • public key: generate $k_0$ and $k_1$ and set public key as $(F,(0,f_{k_0^1}),(1,f_{k_1^2}),\dots ,(0,f_{k_0^l}),(1,f_{k_1^l}))$
  • signing: $b\mapsto (b,k_b^1,\dots ,k_b^l)$
  • verifying: reverse test checking that all the functions computed right plus two thresholds: $c_1$ and $c_2$

• Quantum Digital Signatures without Quantum Memory

  There're coherent states $|\alpha ⟨$ and $|-\alpha ⟨$, s.t. it's efficient to:

  • check they're the same (null-port must be zero)
  • symmetrize two states (giving $|(\alpha +\beta )/2⟨$)
  • identify what's the symmetrized state is

  The protocol (Alice is sending to Bob and Charlie):

  • private key are random sequences of signs $P{K}^k=(b_1^k,\dots ,b_L^k)$ for $k\in \{0,1\}$ and $b\in \{-1,1\}$

  • public key are the two sequences of quantum states $|b_l^k\alpha ⟨$

  • preparation:

    • Bob and Charlie use QDS multiport to a) check if they get the same state b) symmetrize input
    • Bob and Charlie measure output from multiport to identify what was the sign

  • signature: Alice releases $(b,P{K}^b)$

  • verification:

    • check that there's equivocation is unlikely (occurrences of null-port being non-zero is low)

    • check that there's an expected number of unambiguous measurement outcomes (when doing the second step)

    • number of mismatches with the private key should not be too large

      NB thresholds for this step are different for Charlie and Bob, which is necessary if Alice tries to make one accept and another reject

Verifiable Secret Sharing

See Secure Multi-party Quantum Computation.

Implementations