# 1/17: GMW, BGW, BMR

- Chapter 3 of https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf

## GMW Protocol

Consider a $n$-party boolean arithmetic circuit. For each input bit, secret sharing is done

$$b = s_1 \oplus s_2 \cdots \oplus s_n$$

We assume we have AND, NOT, XOR gates.
- NOT: The first party just flips the corresponding share
- XOR: Each party XOR's the corresponding shares

This leads to the hard part, which is AND. Here, the identity

$$a \land b = (a_1 \oplus \cdots \oplus a_n) \land (b_1 \oplus \cdots \oplus b_n) = \left( \oplus_{i=1}^n (a_i \land b_i) \right) \oplus \left( \oplus_{i \neq j} (a_i \land b_j) \right)$$

is used - so each party XOR's the corresponding share, and each pair of parties $(P_i, P_j)$ should run a protocol to compute a share of $(a_i \land b_j) \oplus (a_j \land b_i)$. This can be done as follows - $P_i$ generates a random bit $r$, then generates the table $(r \oplus (a_i \land b_j) \oplus (a_j \land b_i))$ for all four possiblilities of $(b_i, b_j)$. Then, the two parties go through a 1-out-of-4 Oblivious Transfer, for $P_j$ to receive a matching share for $r$ and $(P_i, P_j)$. We again see that multiplication is hard.

## BGW Protocol

Here, an element $v \in \mathbb{F}_q$ is shared via Shamir secret sharing, using a degree $t$ polynomial $p$ such that $p(0) = v$. This of course leads to a $t+1$-out-of-$n$ secret sharing.

In this case, addition is once again easy - the shares are additive, so each party can just add up the shares. The issue is once again multiplication. If we have two shares

$$p(0) = a, \quad q(0) = b$$

where each party $P_i$ has $p(i), q(i)$ - to compute a share of $ab$ one could consider $r(x) = p(x)q(x)$. However, this polynomial is of degree at most $2t$, so the threshold is now larger. To avoid this degree blowup, we add a degree reduction stage.

Note that

$$r(0) = \sum_{i=1}^{2t+1} \lambda_i r(i)$$

holds for public, easily computable constants $\lambda_i$. Therefore, one could
- compute $r(i) = p(i) \cdot q(i)$
- each party run a $t+1$-out-of-$n$ secret sharing for $r(i)$
- sums up the shares with weights $\lambda_i$ to get a $t+1$-out-of-$n$ share for $r(0) = ab$

Note that $2t + 1$ parties do have to participate in this process.

## BMR Protocol

Now we aim to extend Garbled Circuits to $n$-parties. We start with the Garbled Circuits generation algorithm, and go through what certain parts are intended to do.

Consider a PRG $F: \{0,1\}^{\kappa + 1} \rightarrow \{0,1\}^{n \cdot \kappa + 1}$.

For each wire $w_i$, each $P_j$ chooses the sublabel for the wire

$$w_{i, j}^b = (k_{i, j}^b, p_{i, j}^b) \in \{0, 1\}^{\kappa + 1}, \quad p_{i,j}^0 + p_{i,j}^1 = 1$$

and a "flip-bit" share $f_{i, j} \in \{0, 1\}$. They also compute $F(w_{i,j}^0), F(w_{i,j}^1)$.

For each gate, in parallel, the $n$ parties gather to compute the garbled table in a MPC manner. Say a boolean gate has input $w_a, w_b$ and output $w_c$. First, the pointer bits are computed as

$$p_a^0 = \oplus_{j=1}^n p_{a, j}^0, \quad p_a^1 = 1 - p_a^0$$

and similarly for wires $w_b$ and $w_c$. The flip bits are computed similarly via XOR.

The garbled table is computed, for $v_a, v_b \in \{0, 1\}$, as

$$e_{v_a, v_b} = w_c^{g(v_a, v_b) \oplus f_c} \oplus_{j=1}^n (F(i, w_{a, j}^{v_a \oplus f_a}) \oplus F(i, w_{b, j}^{v_b \oplus f_b}))$$

where $w_c^0 = w_{c, 1}^0 || \cdots || w_{c, n}^0 || p_c^0$ and similarly for $w_c^1$. This value is positioned in entry $(p_a^{v_a}, p_b^{v_b})$ - and the table as well as the active wire labels is sent to $P_1$ for evaluation.

The flip bit is added to guarantee that no one knows the actual underlying plaintext value.