# 1/13: Beaver's Protocol

- Chapter 23.2 of https://toc.cryptobook.us/book.pdf

## The Big Idea
Consider that we want to deal with

$$(y_1, \cdots, y_m) = f(x_1, \cdots, x_n)$$

Similar to ideas in ZKP, we first write $f$ as an arithmetic circuit, composed of addition, multiplication, constant addition, scalar multiplication. Here, we work over $\mathbb{F}_q$.

So we wish to deal with the four operations, but in an MPC setting.

We first consider a two-party setting. In this case, for each variable $x$, the two parties $P_1, P_2$ have a *share* $x_1, x_2$ such that $x = x_1 + x_2$. Then, addition, constant addition, scalar multiplication can be handled as follows due to linearity.
- addition: each party simply adds the corresponding shares
- constant addition: the first party adds the corresponding constant to the share
- scalar multiplication: each party simply multiplies the scalar to the corresponding shares

This implies that the hardest part to deal with is the multiplication.

To deal with this, a third party, a dealer $D$, provides a *Beaver triple sharing*, i.e.
- $D$ sends $P_1$ three values $a_1, b_1, c_1$
- $D$ sends $P_2$ three values $a_2, b_2, c_2$

such that

$$(a_1 + a_2)(b_1 + b_2) = (c_1 + c_2)$$

such Beaver triples are assigned for each and every multiplication gate.

To deal with a multiplication $z = x \cdot y$ - consider $P_1, P_2$ have

$$x = x_1 + x_2, \quad y = y_1 + y_2$$

we can compute

$$z = (x - a + a)(y - b + b) = (x - a)(y - b) + (x - a) b + a (y-b) + ab$$

so we can have $P_1, P_2$ each compute

$$u_i = x_i - a_i, \quad v_i = y_i - b_i$$

then share it with each other, then have $u = u_1 + u_2$, $v = v_1 + v_2$, then

$$z_1 = uv + ub_1 + va_1 + c_1, \quad z_2 = ub_2 + va_2 + c_2$$

leading to $z_1 + z_2 = z$ as desired.

Here, we see that the communication complexity depends on the number of multiplication gates. For easier writing, we can abstract away this protocol as follows.

For any $x \in \mathbb{F}_q$, we denote $[x]$ by $(x_1, x_2)$ such that $x_1 + x_2 = x$. We note that $P_i$ holds $x_i$.

The protocol can be written as a combination for various subprotocols.
- **Opening $[x]$ to $P_i$**: $P_{3-i}$ sends $x_{3-i}$ to $P_{i}$, allowing $P_i$ to compute $x$
- **Adding two sharings**: Performs $[z] \leftarrow [x] + [y]$
- **Scalar Multiplication**: Performs $[z] \leftarrow c[x]$
- **Constant Addition**: Performs $[z] \leftarrow [x] + c$

We also write dealer's protocol - a random sharing $[x] = (x_1, x_2)$ can be created by choosing $x_1$ at random and setting $x_2 = x - x_1$. The dealer has the following subprotocols.
- **Singleton Sharing**: Compute random sharing $[a]$ of an element $a \in \mathbb{F}_q$
- **Beaver Triple Sharing**: Compute $([a], [b], [c])$ where $a, b$ are random, and $c = ab$.

The Beaver "2.5"-party Protocol works as follows: of course, addition, constant addition, scalar multiplication works in the most natural way as we defined above. The other subprotocols are
- **Input wire handling for $P_i$**
- Consider $x$ is the input for $P_i$. First, $[a]$ is opened to $P_i$.
- Then, $P_i$ sends $x - a$ to $P_{3-i}$, leading to $[x] \leftarrow [a] + \delta$.
- **Multiplication Gate**
- A Beaver triple $([a], [b], [c])$ is used to compute $[z] = [xy]$.
- $[u] \leftarrow [x] - [a]$ and $[v] \leftarrow [y] - [b]$ is computed and opened to all $P_1, P_2$.
- $[z] \leftarrow u[b] + v[a] + [c] + uv$ is computed

## Maliciously Secure Beaver's Protocol (Honest Majority)

To make this protocol secure when at most one of $P_1, P_2, D$ are corrupt, we use *authenticated sharings*. Authenticated sharing $[[x]]$ consists of three ordinary sharings, $([x], [x^{(1)}], [x^{(2)}])$, which is valid if $x^{(1)} = K^{(1)}x$ and $x^{(2)} = K^{(2)}x$ holds. All subprotocols remain the same, although $[[z]] \leftarrow [[x]] + c$ requires $[z^{(1)}] \leftarrow [x^{(1)}] + c[K^{(1)}]$ and $[z^{(2)}] \leftarrow [x^{(2)}] + c[K^{(2)}]$.

The idea behind is that if one player is malicious, the other could end up with values $x + \delta$ and $x^{(i)} + \delta^{(i)}$ when it was supposed to end up with $x$ and $x^{(i)}$. The verification will check

$$K^{(i)}(x + \delta) = x^{(i)} + \delta^{(i)}$$

which would hold with at most $1/q$ probability since no one knows $K^{(i)}$ until the end.

The dealer would need to provide additional singleton sharings $[K^{(1)}]$ and $[K^{(2)}]$, and change all sharings provided to an authenticated version of them. (Beaver triples as well) The dealer reliably opens $K^{(i)}$ with $P_i$ and $P_i$ only - as $P_{3-i}$ does not know $P_i$, they must participate in the protocol correctly by our previous analysis. The remaining case to deal with is malicious $D$.

So the dealer gives $P_1$

$$a_{11}, \cdots, a_{m1}, b_{11}, \cdots, b_{m1}, c_{11}, \cdots, c_{m1}$$

and gives $P_2$

$$a_{12}, \cdots, a_{m2}, b_{12}, \cdots, b_{m2}, c_{12}, \cdots, c_{m2}$$

and they have to check that

$$(a_{k1} + a_{k2}) (b_{k1} + b_{k2}) = (c_{k1} + c_{k2})$$

hold for all $k$. We wish to guarantee that if $D$ is corrupt and $P_1, P_2$ are honest, then if $P_1, P_2$ finish the protocol without aborting then with overwhelming property $D$ had to send correct values that pass the check. Also, if one of $P_1, P_2$ is corrupt and $D$ is honest, then the verification protocol does not lead to the corrupt party learning about the hoenst party.

This is, actually, *exactly* same as the usual PLONK-like algorithm with the additional rows added for hiding. Therefore, we only present the algorithm here, as analysis is very similar. [Recall that the number of additional rows corresponds to the number of evaluations](https://eprint.iacr.org/2022/086.pdf).

$D$ chooses $a_{01}, a_{02}, b_{01}, b_{02}$ such that

$$(a_{01} + a_{02}) (b_{01} + b_{02}) = (c_{01} + c_{02})$$

then $D$ runs interpolation to find $A_1, A_2, B_1, B_2$ of degree $\le m$ such that

$$A_i(k) = a_{ki}, \quad B_i(k) = b_{ki}$$

and computes $C(X) = (A_1(X) + A_2(X))(B_1(X) + B_2(X))$. $D$ then chooses $c_{k1}, c_{k2}$ such that $C(k) = c_{k1} + c_{k2}$ for $0 \le k \le 2m$. Then $D$ sends all $a_{ki}, b_{ki}, c_{ki}$ values to $P_i$ accordingly.

Now $P_i$ can run interpolation once again to recover $A_i, B_i, C_i$ of degree $\le m, \le m, \le 2m$. The goal for the $P_1, P_2$ is to verify the fact that

$$(A_1(X) + A_2(X))(B_1(X) + B_2(X)) = (C_1(X) + C_2(X))$$

to do so, $P_1$ chooses $r \in \mathbb{F}_q \setminus \{0, \cdots m\}$ and sends to $P_2$. Each party computes

$$\alpha_i \leftarrow A_i(r), \quad \beta_i \leftarrow B_i(r), \quad \gamma_i \leftarrow C_i(r)$$

and sends it to the other party - then both verify

$$(\alpha_1 + \alpha_2)(\beta_1 + \beta_2) = (\gamma_1 + \gamma_2)$$

while precise security proofs is much difficult (due to MPC's security definitions and so on) one sees that the $a_{01}, a_{02}, b_{01}, b_{02}$ is exactly the additional row for zero-knowledge. The dealer's corruption case is also exactly like the soundness proof in ZKP - the usual Schwartz-Zippel arguments work. Indeed, the success probability is at most $2m/(q-m-1)$.