Engineering / Mathematics — Polynomial Algorithms
Mutual Independence and Secret Sharing
Shamir's threshold secret sharing, its information-theoretic security, and the independence property that underlies it.
Executive summary
Shamir's scheme splits a secret into shares such that any k of them reconstruct it and any k minus one reveal nothing whatever. The mechanism is polynomial interpolation over a finite field.
The security is information theoretic: fewer than k shares are mutually independent of the secret, so an adversary with unlimited computing power learns nothing.
Learning objectives
- State the sharing and reconstruction procedures.
- Prove the independence property.
- Identify the practical requirements and failure modes.
01The scheme
Shamir threshold secret sharing
secret s, threshold k, participant count nn shares, any k of which recover s- Choose a prime power q exceeding the number of participants and the secret space.
- Encode the secret s as an element of F_q.
- Draw a₁, ..., a_{k−1} uniformly at random from F_q.
- Form the polynomial f(X) = s + a₁X + ... + a_{k−1}X^{k−1}.
- Give participant i the pair (xᵢ, f(xᵢ)) for distinct non-zero xᵢ.
- To reconstruct, interpolate any k shares and evaluate at 0.
O(k) to share, O(k²) to reconstructThe secret is the constant term, recovered as f(0). Since k points determine a polynomial of degree below k uniquely, any k shares suffice.
02Why fewer than k shares reveal nothing
Perfect security
For any k − 1 shares and any candidate secret s, exactly one polynomial of degree below k is consistent with those shares and has constant term s.
Hence the shares are independent of the secret, and the conditional distribution of the secret given them is uniform.
The proof is interpolation again. Adding the point (0, s) to k − 1 shares gives k points, determining a unique polynomial. Every candidate secret is equally consistent, so the shares carry no information about which is correct.
03Practical requirements
- Fresh randomness per sharing. Reusing coefficients across two secrets lets an adversary holding shares of both subtract and recover information.
- Distinct non-zero evaluation points. The point 0 is the secret itself and must never be issued as a share. Duplicate points give duplicate information rather than progress towards the threshold.
- A field large enough. The field must exceed both the participant count and the secret space, since shares are field elements.
- No integrity guarantee. A participant submitting a false share corrupts the reconstruction silently, since any k points interpolate to something.
Threshold cryptography builds on the same idea, distributing a private key so that a threshold of parties can jointly sign without any of them ever holding the whole key.
04Frequently asked questions
Why is the field required rather than working modulo a composite?
Because interpolation requires dividing by differences of evaluation points, and those differences must be invertible. Over a composite modulus some differences would be zero divisors and reconstruction would fail.
Can the threshold be changed after sharing?
Not without redistributing. The threshold is fixed by the polynomial degree at sharing time. Proactive schemes refresh shares periodically and can change parameters during a refresh.
How large are the shares?
Each share is one field element, so roughly the size of the secret. This is optimal for a perfectly secure scheme — information theory requires each share to be at least as large as the secret.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 408-409.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.