Pedersen's Construction

We describe a VSS protocol from Pedersen [Ped91]. This scheme provides perfect information theoretic security against any adversary with unbounded computational power.

Share The dealer chooses two polynomials $p(x)=a_0+a_1x+a_2x^2+...+a_tx^t$ and $p'(x)=b_0+b_1x+b_2x^2+...+b_tx^t$ such that $a_0=s$. Then he compute $s_i=p(i)$ and $s_i'=p'(i)$. The dealer then broadcasts $C_i=g^{s_i}h^{s_i'}$. Then he gives the party $P_i$ the tuple $(s_i,s_i')$. This allows $P_i$ to check if $(s_i,s_i')$ is a valid share by checking that

$$g^{s_{i}}h^{s_{i}'} \stackrel{?}{=} \prod_{k=0}^{t}(C_{k})^{i^k} (*).$$

If a party $P_i$ receives a share that does not satisfy $(*)$, he will complains against the dealer. The dealer must reveal the share $(s_i,s_i')$ that satisfies for each complaining party $P_i$. If any of the revealed shares does not satisfy $(1)$ the equation, the dealer is marked invalid.

Reconstruct Each participant submits $(s_i,s_i')$. Everyone can verify if $P_i$ submitted the correct shares by checking if $1$ is satisfied. If $P_i$ receives more than $t$ complaints, then he is disqualified. Given $t+1$ valid shares, $s_1,s_2,...,s_{t+1}$ from parties $P_{x_1},P_{x_2},...,P_{x_{t+1}}$, the secret $s$ can be computed as: $$s= \sum_{i=0}^{t}s_i \left(\prod_{\substack{j=0 \ j\neq i}}^{t}\dfrac{x_j}{x_j-x_i}\right).$$

The security proof of the protocol can be found in [Ped91].