shamir-pedersen-verifiable-secret-sharing

Answer

The core problem is a subtle mismatch between the polynomial arithmetic field and the group order used for Pedersen commitments. When working over Z_P^* (multiplicative group modulo a prime P), Fermat's little theorem causes exponents to reduce modulo P-1, not P. If the polynomial coefficients live in Z_P, the verification equation g^{f(i)}·h^{r(i)} = ∏ C_k^{i^k} breaks because the left side uses exponents reduced mod P while the right side (via exponentiation) uses exponents reduced mod P-1.

Fix: Separate concerns by using two primes: Q for the polynomial field and P = K·Q + 1 for the commitment group, with generators g,h in the unique order-Q subgroup of Z_P^*. Since both g and h have order exactly Q, exponentiation automatically reduces exponents modulo Q, matching the polynomial arithmetic.

Key Implementation

'use strict';
const crypto = require('crypto');

// ── Domain parameters ──────────────────────────────────────────────────
const Q = 2n ** 127n - 1n;       // Polynomial field modulus (Mersenne prime)
const K = 114n;                   // P = K·Q + 1 is also prime
const P = K * Q + 1n;             // Commitment group modulus

// Generators of the order-Q subgroup:  g = 2^K mod P,  h = 29^K mod P
const G = modPow(2n, K, P);
const H = modPow(29n, K, P);

// ── Arithmetic helpers ─────────────────────────────────────────────────
function modPow(base, exp, mod) {
  let r = 1n, b = base % mod, e = exp;
  while (e > 0n) { if (e & 1n) r = (r * b) % mod; b = (b * b) % mod; e >>= 1n; }
  return r;
}
function modInv(a, p) {
  let [or, r] = [((a % p) + p) % p, p], [os, s] = [1n, 0n];
  while (r) { const q = or / r; [or, r] = [r, or - q * r]; [os, s] = [s, os - q * s]; }
  return ((os % p) + p) % p;
}
function randField(p) {
  const buf = crypto.randomBytes(Math.ceil(p.toString(16).length / 2) + 4);
  return buf.reduce((v, b) => (v << 8n) + BigInt(b), 0n) % p;
}

// ── Polynomial helpers (over Z_Q) ─────────────────────────────────────
function evalPoly(c, x, m) {
  let r = 0n;
  for (let k = c.length - 1; k >= 0; k--) r = (r * x + c[k]) % m;
  return r;
}
function randomPolynomial(constant, degree) {
  const c = [((constant % Q) + Q) % Q];
  for (let k = 1; k <= degree; k++) c.push(randField(Q));
  return c;
}

// ── Pedersen commitments ──────────────────────────────────────────────
function computeCommitments(f, r) {
  return f.map((a_k, k) => (modPow(G, a_k, P) * modPow(H, r[k], P)) % P);
}

function verifyShare(index, share, blinding, commitments) {
  const lhs = (modPow(G, share, P) * modPow(H, blinding, P)) % P;
  let rhs = 1n, pow = 1n;
  for (const Ck of commitments) {
    rhs = (rhs * modPow(Ck, pow, P)) % P;
    pow = (pow * index) % P;
  }
  return lhs === rhs;
}

// ── Dealer ─────────────────────────────────────────────────────────────
function dealer(secret, t, n) {
  if (t > n) throw new Error('t must be ≤ n');
  const deg = t - 1;
  const fC = randomPolynomial(secret, deg);
  const rC = randomPolynomial(randField(Q), deg);
  const comms = computeCommitments(fC, rC);
  const shares = [];
  for (let i = 1n; i <= n; i++)
    shares.push({ index: i, share: evalPoly(fC, i, Q), blinding: evalPoly(rC, i, Q) });
  return { secret, t, n, fCoeffs: fC, rCoeffs: rC, commitments: comms, shares };
}

// ── Combiner (Lagrange at x=0 over Z_Q) ────────────────────────────────
function lagrangeCoeffAtZero(xj, xs) {
  let r = 1n;
  for (const xk of xs) {
    if (xk === xj) continue;
    r = (r * xk * modInv(((xk - xj) % Q + Q) % Q, Q)) % Q;
  }
  return r;
}
function reconstruct(shares) {
  const xs = shares.map(s => s.index);
  let secret = 0n;
  for (let j = 0; j < shares.length; j++)
    secret = (secret + shares[j].share * lagrangeCoeffAtZero(xs[j], xs)) % Q;
  return (secret + Q) % Q;
}

// ── Verification API ──────────────────────────────────────────────────
const verify = (i, s, b, c) => verifyShare(i, s, b, c);
const verifyAll = ({ commitments, shares }) =>
  shares.every(s => verifyShare(s.index, s.share, s.blinding, commitments));

module.exports = { Q, P, G, H, modPow, modInv, randField, evalPoly,
  randomPolynomial, computeCommitments, verifyShare, dealer, reconstruct,
  verify, verifyAll };

Why This Works

Since g^Q ≡ 1 mod P and h^Q ≡ 1 mod P, exponentiation always reduces exponents modulo Q, exactly matching the polynomial arithmetic.