Shamir Secret Sharing

Shamir Secret Sharing

Mathematical Definition

Choose a prime p larger than n, and represent the secret s as an integer from 0 to p−1. Select t−1 coefficients independently and uniformly from that same field. A dealer forms:

All arithmetic is modulo p, including division: dividing by a nonzero value means multiplying by its modular inverse. For instance, 2⁻¹=9 modulo 17 because 2×9=18, whose remainder is 1. Distinct share coordinates make interpolation denominators nonzero. A composite modulus does not supply a field: modulo 15, the nonzero value 5 has no inverse. That is why the experiment rejects composites rather than drawing a plausible result.

Zero coefficients are allowed, including the leading coefficient. The polynomial has degree at most t−1; forcing a nonzero leading coefficient changes the uniform coefficient distribution. The receiver does not know the dealer’s coefficients. Seeing them in this teaching display is additional information outside the secrecy model.

Key Concepts

Recovering the constant with Lagrange weights

For a selected set J of at least t distinct valid points, compute a weight for each selected x_i. Evaluating the interpolation basis at zero yields:

Using more than t honest shares also works: the same underlying polynomial has degree below the number of interpolation points. The module uses every selected share, and exposes each weight and contribution. It does not read the dealer’s stored secret to produce the receiver result.

Worked example: any three of five

Take p=17, t=3, and f(x)=10+4x+2x². Direct substitution gives shares (1,16), (2,9), (3,6), (4,7), (5,12). For the first three, the weights are 3, −3, 1, represented in the field as 3,14,1. Their contributions are 16×3=14, 9×14=7, and 6×1=6 modulo 17. The sum 27 reduces to 10.

Choose shares 1,3,5 instead. Their weights become 4,3,11, and the contributions become 13,1,13. Again 27 reduces to 10. The weights depend on the selected coordinates, so switching subsets changes the calculation while preserving the recovered secret. Trying all ten triples illustrates the threshold guarantee without assuming only the first three can cooperate.

Why two shares leave every secret possible

Keep only (1,16) and (2,9). The original polynomial is compatible, but so is g(x)=2x+14x² modulo 17: g(1)=16 and g(2)=60=9, while g(0)=0. Another compatible polynomial is 16+12x+5x²: at x=1 it gives 33=16, at x=2 it gives 60=9, and its secret is 16.

More generally, if m<t shares are available, add the point (0,c) for any candidate c. Those m+1 distinct points admit an interpolating polynomial of degree at most m, which is below t. Thus every field value remains possible. The candidate slider constructs exactly this polynomial from the selected shares and the candidate. Unselected shares impose no constraints.

Possibility alone does not prove perfect secrecy. For any fixed secret and m observed shares, the m independent linear constraints on t−1 random coefficients leave exactly p^t−1−m coefficient choices. This count is equal for every secret, so the probability of that share observation does not depend on the secret. An observer learns nothing beyond any prior information they already had. With no shares, a constant candidate polynomial is sufficient; with one share, a line is sufficient, even if the dealer used a quadratic.

Experiment boundaries

The controls deliberately use tiny primes from 5 through 31 and at most six shares. Secrets and active coefficients must lie in 0..p−1. Inputs are not silently reduced modulo a newly selected field: changing p can make an existing value invalid. The requirement n<p keeps x=1..n distinct and avoids x=0, which would directly disclose the secret. A threshold larger than the number of shares cannot be satisfied and is shown as invalid.

The secret zero is valid. A polynomial that happens to be constant does not reduce the publicly promised threshold when its randomly chosen coefficients are unknown. If an observer is separately told those coefficients are zero, that extra information changes what they can infer. Editable, visible coefficients in this module are for checking arithmetic; they are not a production privacy mechanism.

Historical Context

Adi Shamir published “How to Share a Secret” in Communications of the ACM in November 1979. The polynomial construction makes the cooperation threshold a mathematical property of the encoding. Original paper, DOI 10.1145/359168.359176.

Real-world Applications

• Recovery procedures: distribute shares across independent custodians so a threshold can restore a secret after some shares become unavailable.
• Shared control: require several parties to cooperate before reconstructing sensitive material, with explicit policies for distribution and recovery.
• Threshold cryptography: protocols can compute over secret shares without first rebuilding the whole key; simple reconstruction alone does not implement those protocols. NISTIR 8214, section 2.4.

Basic Shamir shares do not authenticate their owner or detect malicious replacement. Interpolating corrupted shares can return a wrong value. A deployed system needs suitable randomness, protected share storage and transport, and an integrity or verifiable-sharing design. The experiment generates honest shares and makes no claim to implement those safeguards.

Related Concepts

• RSA Encryption — also uses modular arithmetic, with a different security goal and a composite modulus.
• Hamming Error Correction — adds redundancy to recover from noise; threshold secrecy alone does not correct corrupted shares.
• Entropy & Information Theory — provides the language for expressing that insufficient shares do not reduce uncertainty about the secret.
• Polynomial Interpolation — recovers a bounded-degree polynomial from distinct samples; finite-field division replaces real-number division here.