# GMW Multiplication AND for 2 parties

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

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.

• Hi, @kelalaka you are right. It should be the \bigoplus – rakshit naidu Apr 15 '20 at 14:16
• This is the equation, imgur.com/a/NhFNaSb – rakshit naidu Apr 15 '20 at 14:21

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

• Thanks a lot, @Occams_Trimmer. This made so much sense. – rakshit naidu Apr 16 '20 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.

• 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? – rakshit naidu Apr 16 '20 at 5:24
• 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. – Hasan Iqbal Apr 16 '20 at 10:46
• What algorithms can be used to encrypt A's entries? – rakshit naidu Apr 16 '20 at 13:04
• There are many public key encryption schemes that can be used. RSA for example. – Hasan Iqbal Apr 16 '20 at 13:28
• Thanks a lot @Hasan Iqbal ! – rakshit naidu Apr 16 '20 at 19:45