Verifiable Secret Sharing

Imagine five trustees each hold one fragment of a company's master encryption key. Any three together can reconstruct it, but no two can — this is Shamir Secret Sharing, invented by Adi Shamir in 1979. The dealer picks a random polynomial $f(x)$ of degree $t-1$ whose constant term is the secret $s$, and hands each trustee $i$ the value $f(i)$.

The scheme is mathematically elegant, but it has a silent flaw: the dealer can cheat. Nothing stops a malicious dealer from handing out inconsistent share values — shares that no single polynomial could have produced — so that when any $t$ trustees later try to reconstruct the secret, they get garbage or a value the dealer fabricated.

Verifiable Secret Sharing (VSS) fixes this. First proposed by Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch in 1985, and then made practical by Paul Feldman in 1987, VSS gives every shareholder a way to check their own share against a set of public commitments without ever learning the secret itself.

The idea is disarmingly simple: the dealer publishes encrypted "fingerprints" of every coefficient of $f$, and each shareholder runs a short verification equation. If the equation passes, the share is genuine. If it fails, the dealer is caught — publicly and undeniably.

The demo below runs a simplified Feldman VSS over small integers so every number stays readable. The dealer holds a secret, commits to it publicly, and distributes shares to five participants. Toggle Dealer cheats to make the dealer tamper with one share — then watch the commitment check catch the lie.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label class="cheat-toggle">
    <input type="checkbox" id="cheatToggle">
    <span>{{lbl_cheat}}</span>
  </label>
  <button id="reshareBtn" type="button">{{btn_reshare}}</button>
</div>
<div class="commit-panel">
  <div class="panel-title">{{lbl_commitments}}</div>
  <div id="commitList" class="commit-list"></div>
</div>
<table class="shares-table">
  <thead>
    <tr>
      <th>{{th_participant}}</th>
      <th>{{th_share}}</th>
      <th>{{th_status}}</th>
    </tr>
  </thead>
  <tbody id="sharesBody"></tbody>
</table>
<div id="verdict" class="verdict"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; align-items: center; gap: .8rem; margin-bottom: .8rem; flex-wrap: wrap; }
.cheat-toggle { display: flex; align-items: center; gap: .4rem; cursor: pointer; font-weight: 600; }
.cheat-toggle input { accent-color: #c92f3c; width: 16px; height: 16px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
.panel-title { font-weight: 700; font-size: .85rem; color: #555; margin-bottom: .35rem; }
.commit-panel { background: #f4f7fa; border: 1px solid #d0d9e3; border-radius: 8px;
                padding: .55rem .75rem; margin-bottom: .7rem; }
.commit-list { display: flex; gap: .5rem; flex-wrap: wrap; }
.commit-chip { background: #dce6f0; border-radius: 6px; padding: .25rem .55rem;
               font: 600 12px ui-monospace, monospace; color: #1d3557; }
.shares-table { width: 100%; border-collapse: collapse; margin-bottom: .6rem; }
.shares-table th { background: #e8eef3; font-size: .8rem; text-align: left;
                   padding: .35rem .6rem; border-bottom: 2px solid #c6d4df; }
.shares-table td { padding: .38rem .6rem; border-bottom: 1px solid #e2e8ed;
                   font: 500 13px ui-monospace, monospace; }
.shares-table tr:last-child td { border-bottom: none; }
.tag { display: inline-block; border-radius: 5px; padding: .15rem .45rem;
       font: 700 11px system-ui; }
.tag-ok { background: #d4f4e2; color: #0a7d33; }
.tag-bad { background: #fde8e8; color: #c92f3c; }
.verdict { font-weight: 700; font-size: .95rem; min-height: 1.4em; margin-top: .2rem; }
.verdict.ok { color: #0a7d33; }
.verdict.bad { color: #c92f3c; }

// Code not found

Notice the asymmetry. Checking a share requires only one multiplication and one comparison — it is instant. Cheating without being caught would require the dealer to forge a commitment that matches a wrong share, which is computationally infeasible when real large-prime arithmetic is used (as in Feldman's original scheme based on the hardness of discrete logarithms).

This problem is solved. Paul Feldman's 1987 scheme is the canonical answer, and it works as follows.

Let $p$ be a large prime and $g$ a generator of a cyclic group of order $q$ where computing discrete logarithms is hard. The dealer chooses coefficients $a_0, a_1, \dots, a_{t-1}$ (with $a_0 = s$ the secret) and publishes the commitments:

$$C_k = g^{a_k} \bmod p \quad \text{for } k = 0, 1, \dots, t-1$$

Each shareholder $i$ receives $s_i = f(i) = a_0 + a_1 \cdot i + \cdots + a_{t-1} \cdot i^{t-1} \pmod{q}$ and verifies:

$$g^{s_i} \equiv \prod_{k=0}^{t-1} C_k^{i^k} \pmod{p}$$

If the dealer tampers with $s_i$, the left side no longer matches the right — caught. The security rests on the discrete-log assumption: given $g^a \bmod p$, recovering $a$ is believed to be hard (see discrete logarithms).

Pedersen VSS (Torben Pedersen, 1991) strengthens this to be information-theoretically hiding — even an unbounded adversary cannot learn the secret from the commitments — by using two generators and a blinding factor. The tradeoff is that the reconstruction step becomes slightly more involved.

Both variants share the same efficiency profile: the dealer broadcasts $t$ group elements, and each holder performs $O(t)$ modular exponentiations for verification. Everything scales linearly in the threshold $t$.

Once you can share a secret verifiably, a remarkable set of protocols becomes possible:

• Distributed key generation (DKG): no single party ever holds the full private key. Validators in Ethereum's proof-of-stake and threshold signature schemes use VSS-based DKG so that the key exists only implicitly, spread across nodes.
• Threshold signatures: $t$ of $n$ nodes each contribute a partial signature; the group signature is assembled without any one node learning the signing key. Used in hardware security modules, custody wallets, and certificate authorities.
• Secure multi-party computation (MPC): VSS is the primitive that lets $n$ parties jointly compute a function of their private inputs without revealing those inputs to each other.
• Verifiable random functions and lotteries: the randomness source is shared so no single party can bias the output, yet the result is publicly verifiable.
• Nuclear and governmental split keys: physical embodiment of VSS — codes distributed among multiple custodians so no individual can launch unilaterally.

The common thread: VSS replaces "trust the dealer" with "verify the dealer" — shifting the security model from faith to mathematics. See also factoring and discrete logarithms for the hardness assumptions VSS ultimately relies on.

Verifiable Secret Sharing is one of cryptography's neatest tricks: by publishing a handful of group elements — commitments that hide the coefficients but bind the dealer to them — every shareholder can run a single equation and know their piece is genuine. The dealer cannot lie without being caught, even though nobody learns the secret until reconstruction day.

Feldman's 1987 construction turned a theoretical guarantee into a practical tool, and today VSS sits invisibly inside the threshold cryptography that protects blockchain validators, hardware security modules, and distributed key ceremonies around the world. Every time you trust a system that "no single party controls," there is almost certainly a VSS variant running underneath.