Secret Sharing and Multiplication Triples

Question

I do not understand the multiplication technique using triples and secret shares of the inputs. Could somebody explain me where I'm wrong? It works like this: The inputs are secret shared in XOR shares.

Alice holds $[x]_a$ and $[y]_a$ and a share of a multiplication triple $[a]_a,[b]_a,[c]_a$ s.t. $a \cdot b = c$. Bob holds the other shares.

Now multiplication is supposed to work as follows:

Both parties do the following: $$[d] = [x] \oplus [a]$$

$$[e] = [y] \oplus [b]$$

Both parties reveal their shares of $[d]$ and $[e]$ to each other. Then both calculate $$ [z] = [c] \oplus e[x] \oplus d[y] \oplus ed $$

To reveal the result of their computation one party sends the other party its secret shares.

My questions:

How is reconustruction working? If I XOR the two shares of $z$, the last bit ($... \oplus ed$) cancels out. I have seen this trick in many lecture notes and in all of them they analyze the correctness for showing that $xy = c \oplus ex \oplus dy \oplus ed$, but I don't see how this directly relates to the shares.

Answer 1

If you understand that $xy = c \oplus ex \oplus dy \oplus ed$ I am not sure what else is there to understand?

I wonder if you have understood how the $[x]$ notation works? $[x]$ means that $x$ is XOR shared between between Alice and Bob (I.e., Alice has $x_A$ and Bob has $x_B$, so that $x = x_A \oplus x_B$). When we write $[e] = [x]\oplus[a]$ this that Alice and Bob computes an XOR secret sharing of the value $e = x \oplus a$. Simlarly, if we write [f] = e[x], this means Alice and Bob compute an XOR sharing of $f = ex$. So by extension if $xy = c \oplus ex \oplus dy \oplus ed$ then $[z]$ means we have computed an XOR sharing of $z = xy$.