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 jth 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}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s