How can one prove correctness of shared secrets in secret sharing schemes?

Question

Assume we are in a centralized secret sharing setting, where one party generates the shares, and distributes them to other parties. How can the distributor who creates the shares prove to the parties that they received the correct share?

Imagine the parties later share their shares or some other information between themselves to check whether the shares indeed combine to the correct value. But if this fails, it means one or more of the shares were wrong. Can one identify which shares were indeed wrong? And if yes, how does one know whether the distributor gave a wrong share to a party, or if this party deviated from the protocol and sampled a random share himself/herself?

For simplicity we can assume that shares are additive, and they are generated as $s_1,\ldots,s_{n-1} \gets \mathbb{Z}_p$, and $s_n = s - \sum^{n-1}_{i=1} s_i$, for a secret value $s$ that we want to share. And we are in n-out-of-n setting.

Also we can imagine that the distributor is the one that samples $s$ and then sends $g^s$ to other parties, so they can just combine their shares in the exponent to check whether it is equal to $g^s$. Which again opens a door for distributor to cheat, what if it sends wrong value, such as $g^{s’}$?

Answer 1

Here is one possible approach:

• The dealer generates a group suitable for a Pedersen commitment scheme (namely, an Elliptic Curve with prime order $p$, and two elements $G, H$ where no one knows the discrete log of $H$ with respect to $G$) - we can do this in a multiplicative group; I just find the additive notation a bit easier in this case, as the notation for the math on the commitments matches that of the uncommitted values.

• The dealer selects a Shamir Secret Sharing polynomial (the constant term the shared secret, the rest of the coefficients random) over $GF(p)$; he also creates a Pedersen commitment for each coefficient $c_i$ (using a random value $r_i$), and publishes it (and so he publishes the values $c_iG + r_iH$), along with a series of NIZKPs that he knows the values $c_i$ that he committed to

• The dealer generates shares for each one; with user $x$, he generates the share $z = c_nx^n + c_{n-1}x^{n-1} + … + c_0x^0$ and also generates a NIZPF that $x^n(c_nG + r_nH) + x^{n-1}(c_{n-1}G + r_{n-1}H) + … + x^0(c_0G + r_0H)$ is a commitment to $z$; he sends $z$ and the NIZKP to the user.

Each user can verify (based on the public NIZKPs) that the dealer has committed to a single group-wide polynomial. In addition, based on the NIZKP that the dealer gives to each user, they can verify that their share is consistent with that group-wide polynomial.