A Publicly Verifiable Secret Sharing Scheme

We all know Shamir’s $(t,n)$-Secret Sharing Scheme: A dealer fixes a group $\mathbf{Z}_p$ and selects a random polynomial $P(x)$ of degree at most $t-1$ over this group. He sets the constant coefficient equal to your secret $\sigma$, then distributes $n$ arbitrary evaluations of this polynomial as shares to the $n$ parties. Any subset of $t$ parties can pool their shares and reconstruct the polynomial via Lagrange interpolation.

What if we don’t want to trust the dealer nor the parties? Feldman’s Verifiable Secret Sharing Scheme allows the dealer to publish, in addition to the regular Shamir-shares, a generator $g$ of the group $\mathbf{Z}_p^*$ along with $t$ proofs or commitments $c_j$ for each coefficient of the polynomial $P(x)$. Each party can verify that his share is correct by testing whether

$\displaystyle g^{P(i)}\, \overset{?}{=} \, \prod_j{c_j^{i^j}} \bmod p$.

However, the shares $p(i)$ are still private. What if we want everyone to be able to verify the correctness of all shares without knowing what the shares are? This is achieved by a Publicly Verifiable Secret Sharing Scheme, such as the one developed by Berry Schoenmaker, assuming the discrete log problem is hard.

This scheme has semblances with Shamir’s scheme, except the users (parties) get a function of the polynomial evaluations instead of the evaluations themselves.

First, we show how the protocol works for a random secret. Later we’ll show how to make it work for an arbitrary secret.

Set up: Fix a group $\mathbf{Z}_p$ for some prime $p$. let $F = \mathbf{Z}_p$ be its multiplicative group: it is cyclic, and every element has a multiplicative inverse. Let $g$ and $e$ be two generators of $F$ chosen independently so that no one knows the discrete log of one with respect to the other, assuming that the discrete log problem is hard.

User’s public/private keys: There are $n$ users $u_i, i = 1, \cdots, n$. User $u_i$ generates a random private key $x_i \in F$. The corresponding public key $y_i$ satisfies $y_i = e^{x_i}$. Every user publishes his public key. A message $e^m$ is encrypted by a sender as $y_i^m$. The user $u_i$ can decrypt it as $(y_i^m)^{1/x_i} = e^{x_im/x_i} = e^m$ where $1/x_i$ is the multiplicative inverse of the private key. The user $u_i$ can easily compute the inverse $1/x_i$ since $F$ is cyclic.

Shares/Commitments Distribution: The dealer starts just like Shamir’s scheme: he selects a random element $s \in F$, finds a random polynomial $P(x) = \sum_j{a_j x^j}$ of degree at most $t-1$ over $F$, sets $P(0) \rightarrow s$. The random secret is $e^s$. Since $s$ is random, $e^s$ is random as well.

The dealer publishes the encrypted shares $Y_i = y_i^{P(i)}$ using each user’s public key $y_i$. The $n$ commitments are

$\displaystyle X_i = \prod_{j=0}^t{g^{a_j i^j}}.$

Verification: Upon receiving the encrypted share $y_i^{P(i)} = e^{x_iP(i)}$, the user $u_i$ decrypts this share as $\sigma_i = e^{P(i)}$. Note that

$\displaystyle X_i = g^{\sum_j{a_j^{i^j}}} = g^{P(i)}.$

Hence the dealer can prove to anyone his knowledge of $P(i)$, without revealing $P(i)$, via Chaum and Pedersen’s  scheme

$\displaystyle \mathrm{DLEQ}(g, \underbrace{X_i}_{ = g^{P(i)}}, e, \underbrace{Y_i}_{=e^{P(i)}})$

for proving the knowledge of the discrete log $P(i)$. Notice that the verifier does not need to know the private key of the user $u_i$ to be able to verify his share.

Reconstruction: Without loss of generality, suppose the first $t$ users have pooled their decrypted shares $\{\sigma_j\}$ to reconstruct

$\displaystyle \prod_{j=1}^t{\sigma_j^{\lambda_j(0)}} = e^{\sum_j{\lambda_j(0) P(j)}} =e^{P(0)} = e^s\, ,$

where the $\lambda_j(x)$ is the $j$th Lagrange basis polynomial defined as

$\displaystyle \lambda_j(x) := \prod_{k \neq j}{\frac{x-x_k}{x_j - x_k}}\,.$

Extending to Non-random Secrets. So far, the dealer can communicate his random secret key $k = e^s$ to any $t$ users. This random key $k$ can be used as a seed to a publicly agreed upon cryptographic hash function, or a pseudorandom generator $H$. If the dealer has an arbitrary secret $S$, he publishes $W=S + H(k)$. When the $t$ users deduce $k$, it is easy to find $S = W + H(k)$.

It can be done multiplicatively, too. The dealer can publish $W = S k$. Since $k$ is random, $W$ is random as well. Upon revealing $k$, the parties can find the inverse of $k$ in $F$ and compute $S = W\cdot k^{-1}$.