I am looking into the GMW protocol's evaluation for multiplication in 2 parties. I have referred to different materials on it but I didn't exactly understand how $a_i b_j + a_j b_i$ is calculated in a 2 party setting.

As you know multiplication in GMW is given as $$(a_1\oplus a_2\oplus \cdots \oplus a_n)(b_1\oplus b_2\oplus \cdots\oplus b_n) = \bigoplus_i(a_i b_i) \bigoplus_{i<j}(a_i b_j \oplus a_j b_i).$$

Finding the first term in this equation is easy where we just multiply $a_i$ and $b_i$ share. I have trouble understanding the second term which involves Oblivious Transfer.


A more accessible explanation can be found in these lecture notes.

The idea is to "simulate" multiplication using OT. The OT is run twice, in the first run with Party $0$ as the sender and Party $1$ as the receiver, and in the second run with the roles reversed. The first run proceeds as follows:

  1. Party $0$ selects a random bit $r_0$ and $r_0\oplus a_0$ as the input to the OT
  2. Party $1$ sets $b_1$ as the selection bit. It is not hard to see that Party $1$ effectively computes $r_0\oplus a_0\cdot b_1$: if $b_1=0$, it obtains $r_0$ and otherwise it obtains $r_1\oplus a_0$.

Similarly, in the second run, Party $0$ computes $r_1\oplus a_1\cdot b_0$.

Now, Party $0$'s share is $$a_0b_0\oplus r_0\oplus (r_1\oplus a_1\cdot b_0)$$ whereas Party $1$'s share is $$a_1b_1\oplus r_1\oplus (r_0\oplus a_0\cdot b_1).$$ It is not hard to see that when XORed, they yield $(a_0\oplus a_1)\cdot(b_0\oplus b_1)=a\cdot b$.

An alternative method to do multiplication is to use Beaver's trick [B]. An explanation can be found here.

[B] Beaver, Efficient multiparty protocols using circuit randomization, Crypto 91

| improve this answer | |
  • $\begingroup$ Thanks a lot, @Occams_Trimmer. This made so much sense. $\endgroup$ – rakshit naidu Apr 16 at 5:31

Let's say you are party $I$, and your friend is party $J$, secret values are $a$ and $b$. The result of the multiplication would look like:

$$ a.b = (a_i \oplus a_j) . (b_i\oplus b_j) = (a_ib_i) \oplus (a_ib_j) \oplus (a_jb_i) \oplus (a_jb_j) $$ $I$ and $J$ already have these shares and need no communication for $a_ib_i$ or $a_jb_j$. But for $(a_ib_j)$ and $(a_jb_i)$, they do need other's input. $I$ selects a random value r and creates a table with four entries depending on the values of $I$'s and possible values of $J$ with entries $e$ like $r \oplus a_ib_j \oplus a_jb_i$.

$$ \begin{align} a_j = 0,b_j &= 0: e = r \\ a_j = 0,b_j &= 1: e = r \oplus a_i \\ a_j = 1,b_j &= 0: e = r \oplus b_i \\ a_j = 1,b_j &= 1: e = r \oplus a_i \oplus b_i \\ \end{align} $$

Although these entries look confusing, note that $J$ already knows $a_j$ and $b_j$ values. And any if these entries are $0$, then look at the equation $r \oplus a_ib_j \oplus a_jb_i$. This would have one or two entries evaluate to $0$. That is why the table was constructed that way. Clearly, if $I$ and $J$ engages in a 1-out-of-4 Oblivious Transfer protocol now, then $J$ can only retrieve one entry from the table. So $I$ would be having the random number $r$ and $J$ would be having the computed value xor'ed with $r$. Meaning they share the multiplication result but not the result itself.

| improve this answer | |
  • $\begingroup$ Hi @Hasan Iqbal, thank you for the explanation. I have another follow-up question. How does party B know what value to "choose" from Party A in the 1-out-of-4 OT protocol? $\endgroup$ – rakshit naidu Apr 16 at 5:24
  • $\begingroup$ Hi @rakshitnaidu , A would encrypt all four of these entries. However, B knows only a_j and b_j. So he would only be able to decrypt one entry of the table. $\endgroup$ – Hasan Iqbal Apr 16 at 10:46
  • $\begingroup$ What algorithms can be used to encrypt A's entries? $\endgroup$ – rakshit naidu Apr 16 at 13:04
  • $\begingroup$ There are many public key encryption schemes that can be used. RSA for example. $\endgroup$ – Hasan Iqbal Apr 16 at 13:28
  • $\begingroup$ Thanks a lot @Hasan Iqbal ! $\endgroup$ – rakshit naidu Apr 16 at 19:45

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.