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

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’}$$?

• Who decides what the "correct" secret is? – fkraiem Jul 6 at 10:36
• @fkraiem I edited the question. – tinker Jul 6 at 10:39
• More generally you could say that the dealer sends each party, along with its share, a commitment to the secret (probably one that is perfectly hiding, so that you don't break the information-theoretic security of the secret sharing). – fkraiem Jul 6 at 10:50
• @fkraiem: and when does the commitment get opened (and by whom)? Does that mean that someone asks the dealer when the secret is opened "prove that this was the secret you were thinking of"? – poncho Jul 6 at 15:10

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.

• Thanks. Why does the same approach does not work for additively sharing, without polynomial as in Shamir's case? – tinker Jul 6 at 16:06
• Actually, I believe it probably can be adapted - I just started with the more general case... – poncho Jul 6 at 20:26
• @tinker: the easiest way to adapt it would be the have the dealer publish commitments for all shares he generates (and so he publishes $n$ commitments), and for everyone he gives a share to, he opens that commitment. – poncho Jul 6 at 21:50
• What does the commitment guarantee here? I mean if the dealer commits to an incorrect share for party 1, and then opens this incorrect share, the party alone does not know whether he received correct or wrong share, right? So, later if the parties come together and share between themselves $g^{s_i}$, meaning the public shares, to compute $g^s = g^{s_i} \cdots g^{s_n}$, this will fail, but they don't know whether actually the dealer gave a wrong share to one of the parties, or one of the parties actually sent them a wrong public share $g^{s_i}$. I guess there is no way to guarantee this. – tinker Jul 7 at 11:53
• For the (n,n) xor-based SS scheme, there really aren't any possible values of 'incorrect shares' that the dealer can create (unless you have some predetermined idea about a valid shared secret) - as all possible combinations are valid, we cannot detect invalid ones. What we can do is detect if a player gets the share '2', and then claims he got a '5' - by insisting that everyone reveal their commitment opening, everyone can ensure that everyone else is submitting the shares they actually received. – poncho Jul 7 at 16:59