Introduction to Verifiable Secret Sharing

Introduction

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.

Catch the Cheating Dealer

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.

<!-- VSS demo: dealer publishes commitments, participants verify their shares -->
<div class="controls">
  <label class="cheat-toggle">
    <input type="checkbox" id="cheatToggle">
    <span>Dealer cheats</span>
  </label>
  <button id="reshareBtn" type="button">Re-run</button>
</div>
<div class="commit-panel">
  <div class="panel-title">Public commitments (dealer broadcasts these)</div>
  <div id="commitList" class="commit-list"></div>
</div>
<table class="shares-table">
  <thead>
    <tr>
      <th>Participant</th>
      <th>Share value</th>
      <th>Verification</th>
    </tr>
  </thead>
  <tbody id="sharesBody"></tbody>
</table>
<div id="verdict" class="verdict"></div>

/* Styles for the VSS demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Simplified Feldman VSS over small integers for clarity
// Real VSS uses 2048-bit primes; here we use P=23 so values stay readable

// Small prime for the demo; real schemes use large safe primes
const P = 23;
// Generator g=5 has order 22 mod 23 (primitive root)
const G = 5;
// Fast modular exponentiation (square and multiply)
function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

// Shamir secret sharing: secret is the constant term of a degree-(t-1) polynomial
// Evaluate polynomial with coefficients `coeffs` at point x modulo mod
function evalPoly(coeffs, x, mod) {
  let v = 0, xp = 1;
  for (let k = 0; k < coeffs.length; k++) {
    v = (v + coeffs[k] * xp) % mod;
    xp = (xp * x) % mod;
  }
  return v;
}

const N_SHARES = 5;
// Any 3 of 5 shares can reconstruct the secret
const THRESHOLD = 3;

function runScheme(cheat) {
  // The secret to be shared
  const secret = 7;
  // Random polynomial coefficients a1, a2 (degree-2 for threshold 3)
  const a1 = 3, a2 = 2;
  const coeffs = [secret, a1, a2];

  // Feldman commitments: C_k = g^(a_k) mod P
  const C = coeffs.map(a => modPow(G, a, P));

  // Generate one share per participant
  const shares = [];
  for (let i = 1; i <= N_SHARES; i++) {
    let si = evalPoly(coeffs, i, P - 1);
    // Cheating dealer: tamper with participant 3's share
    if (cheat && i === 3) si = (si + 5) % (P - 1);
    shares.push({ i, si });
  }

  // Verify each share against the public commitments
  const results = shares.map(({ i, si }) => {
    const lhs = modPow(G, si, P);
    // RHS = product of C_k^(i^k) mod P for k=0..t-1
    let rhs = 1;
    for (let k = 0; k < C.length; k++) {
      rhs = (rhs * modPow(C[k], modPow(i, k, P - 1), P)) % P;
    }
    return { i, si, ok: lhs === rhs, lhs, rhs };
  });

  return { C, results, secret };
}

function render() {
  const cheat = document.getElementById('cheatToggle').checked;
  const { C, results } = runScheme(cheat);

  // Render commitment chips
  const cl = document.getElementById('commitList');
  cl.innerHTML = C.map((c, k) =>
    `<span class="commit-chip">C<sub>${k}</sub> = ${c}</span>`
  ).join('');

  // Render shares table with verification tags
  const tbody = document.getElementById('sharesBody');
  tbody.innerHTML = results.map(r => {
    const tagClass = r.ok ? 'tag-ok' : 'tag-bad';
    const tagText = r.ok ? 'VALID' : 'INVALID';
    return `<tr>
      <td>${r.i}</td>
      <td>${r.si}</td>
      <td><span class="tag ${tagClass}">${tagText}</span></td>
    </tr>`;
  }).join('');

  // Render overall verdict
  const allOk = results.every(r => r.ok);
  const vd = document.getElementById('verdict');
  if (allOk) {
    vd.textContent = 'All 5 shares verified — the dealer was honest.';
    vd.className = 'verdict ok';
  } else {
    const bad = results.filter(r => !r.ok).map(r => r.i).join(', ');
    vd.textContent = fmt('Cheating detected on participant(s) %bad% — commitment check failed.', { bad: bad });
    vd.className = 'verdict bad';
  }
}

document.getElementById('cheatToggle').addEventListener('change', render);
document.getElementById('reshareBtn').addEventListener('click', render);
render();

<!-- VSS demo: dealer publishes commitments, participants verify their shares -->
<div class="controls">
  <label class="cheat-toggle">
    <input type="checkbox" id="cheatToggle">
    <span>Dealer cheats</span>
  </label>
  <button id="reshareBtn" type="button">Re-run</button>
</div>
<div class="commit-panel">
  <div class="panel-title">Public commitments (dealer broadcasts these)</div>
  <div id="commitList" class="commit-list"></div>
</div>
<table class="shares-table">
  <thead>
    <tr>
      <th>Participant</th>
      <th>Share value</th>
      <th>Verification</th>
    </tr>
  </thead>
  <tbody id="sharesBody"></tbody>
</table>
<div id="verdict" class="verdict"></div>

/* Styles for the VSS demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Simplified Feldman VSS over small integers for clarity
// Real VSS uses 2048-bit primes; here we use P=23 so values stay readable

// Small prime for the demo; real schemes use large safe primes
const P = 23;
// Generator g=5 has order 22 mod 23 (primitive root)
const G = 5;
// Fast modular exponentiation (square and multiply)
function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

// Shamir secret sharing: secret is the constant term of a degree-(t-1) polynomial
// Evaluate polynomial with coefficients `coeffs` at point x modulo mod
function evalPoly(coeffs, x, mod) {
  let v = 0, xp = 1;
  for (let k = 0; k < coeffs.length; k++) {
    v = (v + coeffs[k] * xp) % mod;
    xp = (xp * x) % mod;
  }
  return v;
}

const N_SHARES = 5;
// Any 3 of 5 shares can reconstruct the secret
const THRESHOLD = 3;

function runScheme(cheat) {
  // The secret to be shared
  const secret = 7;
  // Random polynomial coefficients a1, a2 (degree-2 for threshold 3)
  const a1 = 3, a2 = 2;
  const coeffs = [secret, a1, a2];

  // Feldman commitments: C_k = g^(a_k) mod P
  const C = coeffs.map(a => modPow(G, a, P));

  // Generate one share per participant
  const shares = [];
  for (let i = 1; i <= N_SHARES; i++) {
    let si = evalPoly(coeffs, i, P - 1);
    // Cheating dealer: tamper with participant 3's share
    if (cheat && i === 3) si = (si + 5) % (P - 1);
    shares.push({ i, si });
  }

  // Verify each share against the public commitments
  const results = shares.map(({ i, si }) => {
    const lhs = modPow(G, si, P);
    // RHS = product of C_k^(i^k) mod P for k=0..t-1
    let rhs = 1;
    for (let k = 0; k < C.length; k++) {
      rhs = (rhs * modPow(C[k], modPow(i, k, P - 1), P)) % P;
    }
    return { i, si, ok: lhs === rhs, lhs, rhs };
  });

  return { C, results, secret };
}

function render() {
  const cheat = document.getElementById('cheatToggle').checked;
  const { C, results } = runScheme(cheat);

  // Render commitment chips
  const cl = document.getElementById('commitList');
  cl.innerHTML = C.map((c, k) =>
    `<span class="commit-chip">C<sub>${k}</sub> = ${c}</span>`
  ).join('');

  // Render shares table with verification tags
  const tbody = document.getElementById('sharesBody');
  tbody.innerHTML = results.map(r => {
    const tagClass = r.ok ? 'tag-ok' : 'tag-bad';
    const tagText = r.ok ? 'VALID' : 'INVALID';
    return `<tr>
      <td>${r.i}</td>
      <td>${r.si}</td>
      <td><span class="tag ${tagClass}">${tagText}</span></td>
    </tr>`;
  }).join('');

  // Render overall verdict
  const allOk = results.every(r => r.ok);
  const vd = document.getElementById('verdict');
  if (allOk) {
    vd.textContent = 'All 5 shares verified — the dealer was honest.';
    vd.className = 'verdict ok';
  } else {
    const bad = results.filter(r => !r.ok).map(r => r.i).join(', ');
    vd.textContent = fmt('Cheating detected on participant(s) %bad% — commitment check failed.', { bad: bad });
    vd.className = 'verdict bad';
  }
}

document.getElementById('cheatToggle').addEventListener('change', render);
document.getElementById('reshareBtn').addEventListener('click', render);
render();

Result

Console

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).

The Real Complexity

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$ .

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/verifiable-secret-sharing/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Verifiable Secret Sharing

Splitting a secret so every holder can check their piece