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 $\mathrm{xy}$ and $x\vee y$ with $x+y-\mathrm{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\prime \in {\mathbb{F}}_{p}$ and any $t-1$ users, there exists a unique polynomial of degree $t-1$ with $g(0)=b\prime $ 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

`$n$`

Suppose user $i$ has ${x}_{i}\in {\mathbb{F}}_{p}$ for $i=1,...,n$. Define the vector $\stackrel{\u203e}{x}=({x}_{1},...,{x}_{n})$. Let $A$ be an $n\times n$ matrix over ${\mathbb{F}}_{p}$. Define the vector $\stackrel{\u203e}{y}=({y}_{1},...,{y}_{n})=A\stackrel{\u203e}{x}$. We want an SFE protocol with ${F}_{i}={y}_{i}$.

Then let $\stackrel{\u203e}{{v}_{i}}$ be the $i$th row of $A$. Then ${y}_{i}=\stackrel{\u203e}{{v}_{i}}\stackrel{\u203e}{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=\mathrm{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=\mathrm{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\prime (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{\prime}_{1}=h\prime (1),...,z{\prime}_{n}=h\prime (n))$

This transformation is linear, because we can find three matrices $A,B,C$ such that $\mathrm{ABC}({z}_{1},...,{z}_{n})=(z{\prime}_{1},...,z{\prime}_{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\prime $ at $1,...,n$ (another Fourier transform).

Thus Benaloh's protocol can be used to compute $z{\prime}_{1},...,z{\prime}_{n}$. Lastly, $h\prime $ 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.