Editing Fast Quantum Byzantine Agreement (section)

==Protocol Description==
This pseudocode is based on the reference [[Quantum Byzantine Agreement#References|(1)]].

====Fast Byzantine Agreement====
'''Input:''' Each player starts with an input bit <math>b_i</math> and the number of players <math>n</math> and a security parameter <math>k</math>. <br>
'''Output:''' Each player outputs a bit <math>d_i</math>. With high probability, <math>d_i = d</math> for all players <math>i</math> (agreement) and some <math>d \in \{b_i\}_i</math> (validity).

Protocol for each player <math>i</math>:

'''Repeat''' forever (until something is returned):
# ''Subroutine <math>P_r(b_i)</math>:'' (this flips the oblivious common coin if no 2/3 majority is reached)
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players;
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then''' set <math>b_i = 0</math>; '''elseif''' <math>x > 2n/3</math>, '''then''' set <math>b_i = 1</math>; '''else''' set <math>b_i = QOCC(n,k)</math> '''end''';
# ''Subroutine <math>P_0(b_i)</math>:'' (classical routine - biases towards 0 and finishes if 0 is the agreement value)
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players;
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then return''' <math>0</math>; '''elseif''' <math>x > 2n/3</math>, '''then''' set <math>b_i = 1</math>; '''else''' set <math>b_i = 0</math> '''end''';
# ''Subroutine <math>P_1(b_i)</math>:'' (classical routine - biases towards 1 and finishes if 1 is the agreement value)
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players;
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then''' set <math>b_i = 0</math>; '''elseif''' <math>x > 2n/3</math>, '''then return''' <math>1</math>; '''else''' set <math>b_i = 1</math> '''end''';


====Quantum Oblivious Common Coin (QOCC)====
'''Input:''' Each player starts with the number of players <math>n</math> and a security parameter <math>k</math>. <br>
'''Output:''' Each player outputs a random bit <math>v_i</math>. With at least probability <math>p</math>, <math>v_i = x</math> for all <math>i</math> and all <math>x \in \{0,1\}.</math>

Protocol for each player <math>i</math>:

# Prepare state <math>|{\psi}\rangle = \left(\sum_{i=1}^n |{i}\rangle \right)^{\otimes n} </math>
# Share and verify <math>|{\psi}\rangle</math> with a VQSS scheme (with security parameter <math>k</math>). During the verification phase, use a (classical) gradecast scheme instead of a broadcast scheme (this change is named GradedQSV in [[Quantum Byzantine Agreement#References|(1)]]). Let <math>FP</math> denote the set of players that were caught cheating as a dealer.
# Measure each share of player <math>j</math> to obtain a random integer <math>s_{i,j}</math>.
# Use gradecast to share the numbers <math>s_{i,j}, j=1,...,n</math>. Add the dishonest players in the gradecast scheme to <math>FP</math>. Receive <math>s_{l,j}</math>, from each player <math>l=1,...,n, l \neq i</math>.
# '''if''' <math>j \in FP</math> '''then''' set <math>S_j = \perp</math> '''else''' set <math>S_j = \sum_{l \notin FP} s_{lj} \mod n</math>
# '''if''' <math>S_j = 0</math> for some <math>j</math>, '''then return''' 0; '''else return''' 1.