BGW SFE

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

where

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}\).

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.

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

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.