Example of a Two-party GMW Protocol

Question

I have been looking for a concrete example of GMW protocol for two parties. I was trying with the following example for computing $XOR$ of two parties:

1. A's secret bit is $a = 0$, B's secret bit is $b = 1$.
2. A chooses a random string of length 2, namely $a_1a_2 = 00$, so that $a = a_1 \oplus a_2 = 0 \oplus 0 = 0$. B does the same, his secret string is $b_1b_2 = 01$, so that $b = b_1 \oplus b_2 = 1$.
3. A sends the second bit of her secret string, $a_2$ to B. B sends the first part of his secret string $b_1$ to A.
4. A now has $a = 0, a_1 = 0, b_1 = 0$. B has $b = 1, a_2 = 0, b_2 = 1$.
5. Now, GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both. However, as you can clearly see, in this particular example, they are not the same. A's xor is 0, B's is 1.

I think I have a misunderstanding somewhere, but I don't know where. Help, please?

Answer 1

GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both.

I highlighted the part that is incorrect. They started with secret shares of $a=0$ and secret shares of $b=1$. Now they have secret shares of the XOR $c= a \oplus b =1$.

Only if the secret value $c$ is zero will their shares be the same (and of course, they have no way of knowing whether this is the case). In your example $c=1$ so their shares will be opposite.

Basically, you can see that $c_1$ and $c_2$ are valid secret shares of $a \oplus b$ since: $$ c_1 \oplus c_2 = (a_1 \oplus b_1) \oplus (a_2 \oplus b_2) = (a_1 \oplus a_2) \oplus (b_1 \oplus b_2) = a \oplus b $$