The BGW (Ben-Or, Goldwasser and Widgerson) protocol allows $n$-party SFE with $\lfloor n/2 \rfloor -1$-privacy. The security is information theoretic. We work in the honest-but-curious model (the scheme can be modified to counter other threats).

The BGW protocol works on algebraic circuits. Any Boolean circuit can be converted into a algebraic circuit by replacing $x\wedge y$ with $xy$ and $x\vee y$ with $x+y-xy$.

Let $F(x_1,...,x_n)\in\mathbb{Z}_p[x_1,...,x_n]$. User $i$ has $x_i \in\mathbb{F}_p$ and $F_1 = ... = F_u = F(x_1,...,x_n)$. The communication turns out to be linear in the size of the circuit.

First we describe a couple of tricks that will be needed for the scheme.

Secret Sharing

Let $b\in\mathbb{F}_p$ be a secret. We review a method of $t$-out-of-$n$ secret sharing due to Shamir ['81]. That is any $t$ of the $n$ users can reconstruct $b$ but $t-1$ cannot.

Pick a random degree $t-1$ polynomial such that $f(0)=b$. User $i$ gets the share $b_i = f(i) \in\mathbb{F}_p$ for $i=1,...,n$. If $t$ people get together, they can interpolate to get

\[f(0) = b = \sum_{i=1}^t \lambda_{u_i} b_{u_i}\]

where

\[ \lambda_{u_i} = \frac { \prod_{j=1,j\ne i}^t (0 - u_j) } { \prod_{j=1,j\ne i}^t (u_i - u_j) } \]

Note that interpolation can be done when given $g^{f(u_i)}$ even when the discrete logarithm problem is hard.

The scheme is secure because for any $b'\in\mathbb{F}_p$ and any $t-1$ users, there exists a unique polynomial of degree $t-1$ with $g(0) = b'$ and $g(u_i) = b_{u_i}$.

Proactive Secret Sharing

Suppose $b$ is shared in a $t$-out-of-$n$ fashion, so that user $i$ has $b_i = f(i) \in\mathbb{F}_p$. Every time period, we would like the users to execute a protocol to refresh their shares without changing $b$. The idea is that an adversary would have to compromise $t$ shares within one time period in order to get $b$.

To do this, we can have someone, say user 1, pick random polynomial $g$ of degree $t-1$ such that $g(0) = 0$, and then send $y_j = g(j)$ to user $j$. Each user $j$ then refreshes their share by computing $b_j \leftarrow b_j + y_j$.

This scheme works since $f+g$ is a random polynomial.

A $n$-party SFE for linear transformations

Suppose user $i$ has $x_i \in\mathbb{F}_p$ for $i=1,...,n$. Define the vector $\bar{x} = (x_1,...,x_n)$. Let $A$ be an $n \times n$ matrix over $\mathbb{F}_p$. Define the vector $\bar{y}=(y_1,...,y_n) = A\bar{x}$. We want an SFE protocol with $F_i = y_i$.

Then let $\bar{v_i}$ be the $i$th row of $A$. Then $y_i = \bar{v_i}\bar{x} = \sum_{i=1}^n (v_i)_j x_j$. Benaloh’s protocol is an $(n-2)$-private protocol for $y_i$.

The BGW Protocol

Set $t = \lfloor (n-1) / 2 \rfloor$. For $i=1,...,n$, user $i$ picks a random degree $t$ polynomial $f_i$ with $f_i (0) = x_i$, and sends $f_i(j)$ to user $j$. Each user has a vector of shares. The gates are then evaluted one by one (in topological order).

For an addition gate $z = x + y$: the arguments $x, y$ are already shared in a $(t+1)$-out-of-$n$ fashion, i.e. we have $x_1,...,x_n, y_1,...,y_n$ and user $i$ has $x_i, y_i$. Then each user locally computes $z_i = x_i + y_i$, which means they now hold shares of the answer $z$.

For a multiplication gate $z = xy$: as above, the arguments $x,y$ are already shared. Then each user $i$ computes $z_i = x_i y_i$, which means $z_1,...,z_n$ are points on a polynomial $h = fg$ of degree $2t$. Let $h(x) = h_0 + h_1 x +...+ h_{2t} x^{2t}$, so $z_i = h(i)$. We have $2t + 1 \le n$ by definition of $t$, thus $n$ parties can interpolate $h$.

Define $h'(x) = h_0 + h_1 x + ... + h_t x^t$ (i.e. truncate $h$). Then we want to convert the shares $(z_1,...,z_n)$ to $(z'_1 = h'(1),...,z'_n =h'(n))$

This transformation is linear, because we can find three matrices $A, B, C$ such that $ABC (z_1,...,z_n) = (z'_1,...,z'_n)$ as follows. $C$ is the interpolation matrix (Fourier transform) that computes the coefficients of $h$ from $z_1,...,z_n$. $B$ is the truncation operator which is the identity matrix with some 1’s replaced by 0’s. $A$ is the evaluation matrix that evalutes $h'$ at $1,...,n$ (another Fourier transform).

Thus Benaloh’s protocol can be used to compute $z'_1,...,z'_n$. Lastly, $h'$ is not random, but this can be fixed by using proactive secret sharing.

So addition gates are free, while multiplication gates require $O(n^2)$ communication, and all operations are done on shared values. After all gates have been processed, every user publishes their share.