Cryptography

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(0)=b$. User $i$ gets the share $b_i=f(i)\in {𝔽}_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\prime \in {𝔽}_p$ and any $t-1$ users, there exists a unique polynomial of degree $t-1$ with $g(0)=b\prime$ 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 {𝔽}_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 {𝔽}_p$ for $i=1,...,n$. Define the vector $\bar{x}=(x_1,...,x_n)$. Let $A$ be an $n\times n$ matrix over ${𝔽}_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 $\overline{v_i}$ be the $i$th row of $A$. Then $y_i=\overline{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=\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(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\prime (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{\prime }_1=h\prime (1),...,z{\prime }_n=h\prime (n))$

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