# BGW SFE

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.

Ben Lynn blynn@cs.stanford.edu 💡