]> Cryptography - BGW SFE

The BGW (Ben-Or, Goldwasser and Widgerson) protocol allows n-party SFE with n/2 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 xy with xy and xy with x+yxy.

Let F(x 1 ,...,x n) p[x 1 ,...,x n]. User i has x i𝔽 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𝔽 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 t1 cannot.

Pick a random degree t1 polynomial such that f(0 )=b. User i gets the share b i=f(i)𝔽 p for i=1 ,...,n. If t people get together, they can interpolate to get

f(0 )=b= i=1 tλ u ib u i


λ u i= j=1 ,ji t(0 u j) j=1 ,ji t(u iu 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𝔽 p and any t1 users, there exists a unique polynomial of degree t1 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)𝔽 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 t1 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 jb 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𝔽 p for i=1 ,...,n. Define the vector x=(x 1 ,...,x n). Let A be an n×n matrix over 𝔽 p. Define the vector y=(y 1 ,...,y n)=Ax. We want an SFE protocol with F i=y i.

Then let v i be the ith row of A. Then y i=v ix= i=1 n(v i) jx j. Benaloh's protocol is an (n2 )-private protocol for y i.

The BGW Protocol

Set t=(n1 )/2 . 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 iy i, which means z 1 ,...,z n are points on a polynomial h=fg of degree 2 t. Let h(x)=h 0 +h 1 x+...+h 2 tx 2 t, so z i=h(i). We have 2 t+1 n by definition of t, thus n parties can interpolate h.

Define h(x)=h 0 +h 1 x+...+h tx 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.