5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$$ $\endgroup$ – user39260 Sep 11 '16 at 17:34
  • $\begingroup$ 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. $\endgroup$ – Guut Boy Sep 11 '16 at 17:41
  • $\begingroup$ @user39260 it appears you have created multiple accounts. See here for how to merge them. $\endgroup$ – mikeazo Sep 12 '16 at 2:04
  • $\begingroup$ @GuutBoy could you please take a quick look at the follow up question I posted here $\endgroup$ – z.karl Jul 26 '17 at 16:07

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.