GMW Multiplication AND for 2 parties

Question

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.

Answer 1

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

Answer 2

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.