Fast Quantum Byzantine Agreement: Difference between revisions

Fast Quantum Byzantine Agreement (edit)

Revision as of 18:28, 23 May 2019

1,178 bytes added , 23 May 2019

→‎Pseudocode

Bob

Write

262

edits

@@ Line 57: / Line 57: @@
 ====Fast Byzantine Agreement====
-'''Input:''' Each player starts with an input bit <math>b_i</math> and the number of players <math>n</math>. <br>
+'''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)</math> '''end''';
+## 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;
@@ Line 73: / Line 75: @@
 ====Quantum Oblivious Common Coin (QOCC)====
-'''Input:''' Each player starts with the number of players <math>n</math>. <br>
+'''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>r_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).
+'''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.
 ==Further Information==