# Secret Sharing and Multiplication Triples

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.

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$.
• Well my problem is that reconstruction should work by xoring the shares, i.e. $$[z]_a \oplus [z]_b = ([c]_a \oplus e[x]_a \oplus d[y]_a \oplus ed) \oplus ([c]_b \oplus e[x]_b \oplus d[y]_b \oplus ed) = c \oplus ex \oplus dy \oplus (ed \oplus ed)\neq xy$$
• Now I get it. You are misunderstanding the notation for XOR'ing with a public value. When computing $[p] = [q] \oplus r$ Alice and Bob does not set their shares of $p$ to $p_A = q_A \oplus r$ and $p_B=q_B \oplus r$ respectively. If they did $[p]$ would just be a sharing of $q_A \oplus r \oplus q_B \oplus r = q$. In stead they set $p_A = q_A$ and $p_B = q_B \oplus r$ (you can check that this results in the correct sharing). This is why you get one $ed$ to much. Sep 11, 2016 at 17:41