Sharing without giving everyone the secret
A single copy of a secret can be lost; giving a copy to everyone lets any one holder disclose it. A threshold scheme addresses a different question: distribute shares so that any sufficiently large group can reconstruct, while a smaller group gains no information from its shares.
Definition 8.1.1
(Polynomial threshold scheme)
Let be a prime and choose integers . Work in the field ; let the public participant identifiers be , distinct and nonzero in that field. A secret can have any distribution. Independently of , choose the coefficients uniformly and independently from . Define
Participant receives the share .
The degree is at most : the highest coefficient is allowed to be zero. Arithmetic throughout is modulo .
Common mistake
(Identifiers are field elements, not integers)
The condition is what keeps the identifiers distinct and nonzero modulo . Over , identifiers and are the same field element, so two such shares are one interpolation point, and identifier is the forbidden point , whose share is .
Reconstruction from any shares
Theorem 8.1.2
(Threshold reconstruction)
Any distinct participant shares uniquely determine and hence .
Proof
(Uniqueness by counting roots, existence by Lagrange)
If two polynomials of degree at most agree at distinct field elements, their difference has roots but degree at most . It must be zero. Existence follows by Lagrange interpolation: given for , distinct ,
Every denominator is nonzero, hence invertible in the field. Setting gives the secret. More than honest shares contain such a subset.
Worked example 8.1.3
(A three-of-four scheme over )
Take , , and, for illustration only, , , . Then gives shares . From the first three, the Lagrange weights at zero are , and , giving
The specific coefficients here are shown to check arithmetic; an actual dealer must sample them afresh and uniformly rather than fixing them in advance.
Worked example 8.1.4
(Another triple of shares, other weights)
From the shares at , the weights at zero are , and ; they sum to , as weights reproducing the constant polynomial must. Then
the same secret, as uniqueness requires.
Common mistake
(Lagrange weights belong to a particular subset)
The weights depend on which identifiers are used. Reusing the weights of the subset on the shares at gives , not the secret . Recompute the weights for every subset of shares.
Why fewer shares reveal no information
Theorem 8.1.5
(Perfect privacy)
For any fixed set of participant identifiers and any , the following fixed-secret experiment gives a uniform share-value vector on : set and draw the coefficients as above. Hence the vector is independent of for any prior distribution on .
Proof
(Each observation has the same number of coefficient vectors)
For the claim is immediate. For , fix a candidate secret and arbitrary values for coefficients . The equations at the distinct nonzero identifiers determine uniquely. Their coefficient matrix has determinant
which is nonzero. Thus each requested share vector has exactly coefficient vectors out of , and probability in the experiment with secret fixed to . These identical fixed-secret laws give independence under any prior. For an observed-share event of positive probability, Bayes' rule consequently leaves the prior distribution of unchanged; it does not make a nonuniform prior uniform.
Proof X-ray
Possibility is weaker than probability
It is not enough to say that every candidate secret fits the observed shares. The key move is to fix the coefficients that the observers cannot see and solve for the remaining : this turns a probability question into a count of equally likely coefficient vectors, the same count for every observation and every candidate secret. Uniform and independent coefficients are used exactly here, to turn counts into probabilities. Distinct nonzero identifiers are used for the nonzero determinant: a zero identifier gives a zero row, and its share is the secret itself. The argument closes without any assumption on the prior of , because the share law is computed with fixed.
Worked example 8.1.6
(Two shares fit every secret equally)
For the two shares in the example, every candidate is compatible with exactly one polynomial . The equations and give , hence , so and modulo seven. For example gives , while gives the original polynomial. For each fixed candidate secret, the corresponding coefficient pair is drawn with probability ; an observer's posterior still depends on the observer's prior.
Counterexample mode
Randomness must not be reused
If two secrets use the same nonconstant coefficients, the same participant can subtract the two share values to obtain the difference of the secrets. Over with and reused for secrets and , participant holds and , and : one share from each sharing reveals the difference although . The single-sharing guarantee does not by itself imply privacy across several sharings; fresh independent coefficients avoid this particular reuse leak. Shares also require secure distribution and storage; this construction alone does not authenticate shares or prevent a malicious participant from supplying a false one.
Exercises
Quick check
(Over , use , , and . Find the shares and reconstruct from the first two.)
Solution · Answer
The shares are . For a line, modulo eleven.
Quick check
(For , , fix a secret and sample coefficients as above. What is the probability of any specified pair of share values at two fixed participant identifiers?)
Solution · Answer
It is for every secret, by the counting proof.
Quick check
(Why is identifier forbidden? Why must identifiers be distinct?)
Solution · Answer
A share at equals outright. Repeated identifiers do not supply distinct interpolation points and also violate the determinant argument.
Quick check
(Does seeing fewer than shares make a heavily biased prior on uniform? Explain.)
Solution · Answer
No. The share vector is independent of , so the posterior equals the prior whenever the observed event has positive probability.
Further reading
Adi Shamir, “How to Share a Secret” (1979) introduces the polynomial threshold construction.