]> 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 $x\wedge y$ with $\mathrm{xy}$ and $x\vee y$ with $x+y-\mathrm{xy}$.

Let $F\left({x}_{1},...,{x}_{n}\right)\in {ℤ}_{p}\left[{x}_{1},...,{x}_{n}\right]$. User $i$ has ${x}_{i}\in {𝔽}_{p}$ and ${F}_{1}=...={F}_{u}=F\left({x}_{1},...,{x}_{n}\right)$. 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 {𝔽}_{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\left(0\right)=b$. User $i$ gets the share ${b}_{i}=f\left(i\right)\in {𝔽}_{p}$ for $i=1,...,n$. If $t$ people get together, they can interpolate to get

$f\left(0\right)=b=\sum _{i=1}^{t}{\lambda }_{{u}_{i}}{b}_{{u}_{i}}$

where

${\lambda }_{{u}_{i}}=\frac{\prod _{j=1,j\ne i}^{t}\left(0-{u}_{j}\right)}{\prod _{j=1,j\ne i}^{t}\left({u}_{i}-{u}_{j}\right)}$

Note that interpolation can be done when given ${g}^{f\left({u}_{i}\right)}$ even when the discrete logarithm problem is hard.

The scheme is secure because for any $b\prime \in {𝔽}_{p}$ and any $t-1$ users, there exists a unique polynomial of degree $t-1$ with $g\left(0\right)=b\prime$ and $g\left({u}_{i}\right)={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\left(i\right)\in {𝔽}_{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\left(0\right)=0$, and then send ${y}_{j}=g\left(j\right)$ to user $j$. Each user $j$ then refreshes their share by computing ${b}_{j}←{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 {𝔽}_{p}$ for $i=1,...,n$. Define the vector $\stackrel{‾}{x}=\left({x}_{1},...,{x}_{n}\right)$. Let $A$ be an $n×n$ matrix over ${𝔽}_{p}$. Define the vector $\stackrel{‾}{y}=\left({y}_{1},...,{y}_{n}\right)=A\stackrel{‾}{x}$. We want an SFE protocol with ${F}_{i}={y}_{i}$.

Then let $\stackrel{‾}{{v}_{i}}$ be the $i$th row of $A$. Then ${y}_{i}=\stackrel{‾}{{v}_{i}}\stackrel{‾}{x}={\sum }_{i=1}^{n}\left({v}_{i}{\right)}_{j}{x}_{j}$. Benaloh's protocol is an $\left(n-2\right)$-private protocol for ${y}_{i}$.

## The BGW Protocol

Set $t=⌊\left(n-1\right)/2⌋$. For $i=1,...,n$, user $i$ picks a random degree $t$ polynomial ${f}_{i}$ with ${f}_{i}\left(0\right)={x}_{i}$, and sends ${f}_{i}\left(j\right)$ 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 $\left(t+1\right)$-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\left(x\right)={h}_{0}+{h}_{1}x+...+{h}_{2t}{x}^{2t}$, so ${z}_{i}=h\left(i\right)$. We have $2t+1\le n$ by definition of $t$, thus $n$ parties can interpolate $h$.

Define $h\prime \left(x\right)={h}_{0}+{h}_{1}x+...+{h}_{t}{x}^{t}$ (i.e. truncate $h$). Then we want to convert the shares $\left({z}_{1},...,{z}_{n}\right)$ to $\left(z{\prime }_{1}=h\prime \left(1\right),...,z{\prime }_{n}=h\prime \left(n\right)\right)$

This transformation is linear, because we can find three matrices $A,B,C$ such that $\mathrm{ABC}\left({z}_{1},...,{z}_{n}\right)=\left(z{\prime }_{1},...,z{\prime }_{n}\right)$ 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\left({n}^{2}\right)$ communication, and all operations are done on shared values. After all gates have been processed, every user publishes their share.