We all know Shamir’s -Secret Sharing Scheme: A dealer fixes a group and selects a random polynomial of degree at most over this group. He sets the constant coefficient equal to your secret , then distributes arbitrary evaluations of this polynomial as shares to the parties. Any subset of 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 of the group along with *proofs* or *commitments* for each coefficient of the polynomial . Each party can verify that his share is correct by testing whether

.

However, the shares 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 for some prime . let be its multiplicative group: it is cyclic, and every element has a multiplicative inverse. Let and be two generators of 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 users . User generates a random private key . The corresponding public key satisfies . Every user publishes his public key. A message is encrypted by a sender as . The user can decrypt it as where is the multiplicative inverse of the private key. The user can easily compute the inverse since is cyclic.

**Shares/Commitments Distribution:** The dealer starts just like Shamir’s scheme: he selects a *random* element , finds a random polynomial of degree at most over , sets . The random secret is . Since is random, is random as well.

The dealer publishes the *encrypted* shares using each user’s public key . The commitments are

**Verification:** Upon receiving the encrypted share , the user decrypts this share as . Note that

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

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

**Reconstruction:** Without loss of generality, suppose the first users have pooled their decrypted shares to reconstruct

where the is the th Lagrange basis polynomial defined as

**Extending to Non-random Secrets.** So far, the dealer can communicate his random secret key to any users. This random key can be used as a seed to a publicly agreed upon cryptographic hash function, or a pseudorandom generator . If the dealer has an arbitrary secret , he publishes . When the users deduce , it is easy to find .

It can be done multiplicatively, too. The dealer can publish . Since is random, is random as well. Upon revealing , the parties can find the inverse of in and compute .