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}\]


\[ \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.

Ben Lynn 💡