DLOG ⇒ Verifiable secret sharing (VSS)

Standard model · Ped91 · security loss: none: hiding is perfect, and two sets of accepted shares interpolating different secrets yield ${\log }_{g}h$

Statement

Let $g,h$ generate a group $\mathbb{G}$ of prime order $q$, with ${\log }_{g}h$ unknown to the dealer. To share $s\in {\mathbb{Z}}_q$ among $n$ parties with threshold $k$, the dealer picks a degree-$(k-1)$ Shamir polynomial $f(X)={\sum }_j{a}_j{X}^j$ with $f(0)=s$ and a random polynomial $f^{\prime }(X)={\sum }_j{b}_j{X}^j$ of the same degree, broadcasts the Pedersen commitments $E_j=g^{a_j}{h}^{b_j}$ to their coefficients, and sends party $i$ its share $(f(i),f^{\prime }(i))$ privately. Each party checks its share against the commitments without interacting with the others. This is a non-interactive verifiable secret sharing scheme: fewer than $k$ parties get no Shannon information about $s$, and every $k$ parties holding accepted shares reconstruct the same secret unless the dealer can compute ${\log }_{g}h$, so verifiability holds if DLOG is hard in $\mathbb{G}$ — Ped91.

Sketch

Party $i$ accepts iff $g^{f(i)}{h}^{f^{\prime }(i)}={\prod }_{j=0}^{k-1}{E}_j^{i^j}$. Because the $b_j$ are uniform, the commitments together with any $k-1$ shares have a distribution independent of $s$. Two sets of $k$ accepted shares interpolating different secrets give two openings $(s,t)\ne (s^{\prime },t^{\prime })$ of $E_0$, hence ${\log }_{g}h=(s-s^{\prime })/(t^{\prime }-t)\mathrm{mod}q$.

Notes

• Commitments to the individual shares alone do not let a party check that all shares lie on one polynomial of degree $k-1$; the check above uses the homomorphism of the commitments to the coefficients — folklore.