0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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 $$

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.