Difficulty: Intermediate | Prerequisites: Modular arithmetic, polynomial basics, finite fields (Z_q)
Secret sharing is one of the core building blocks of modern cryptography. The idea is straightforward: split a secret (say, a password or a key) into n pieces, distributed among n people, so that any k of them can reconstruct the secret but any fewer than k learn nothing at all. This is called a (k, n)-threshold scheme.
The mathematical engine behind Shamir's version of this scheme is Lagrange interpolation, a method for reconstructing a polynomial from a set of points. If you are comfortable with modular arithmetic and basic polynomial algebra over finite fields, you have what you need. These topics sit at the intersection of algebra and cryptography and appear regularly in EECS 376 exams.
Shamir's secret sharing hides a secret as the constant term of a random polynomial over a finite field. Given enough shares (points on the polynomial), Lagrange interpolation reconstructs the polynomial and recovers the secret. Fewer than the threshold number of shares reveals nothing, because every possible secret is equally consistent with what you have.
(k, n)-threshold secret sharing scheme
A scheme where a secret is split into n shares such that any k shares suffice to reconstruct the secret, but any k − 1 or fewer shares reveal no information about it. Think of it as a lock that needs exactly k keys turned at once.
Shamir's Secret Sharing
A specific (k, n)-threshold scheme that encodes the secret as the constant term (a₀) of a random polynomial of degree k − 1 over a finite field Z_q. In simple terms, you hide the secret inside a polynomial and hand out points on the curve.
Lagrange interpolation
A method for finding the unique polynomial of degree at most n − 1 that passes through n given points. In simple terms, it is the standard way to reconstruct a polynomial when you know enough of its values.
Lagrange basis polynomial, L_i(x)
The polynomial that equals 1 at x_i and 0 at every other x_j. Each basis polynomial isolates one share's contribution to the full reconstruction. Think of it as a selector: it "picks out" one point and ignores the rest.
Finite field Z_q (integers mod q)
The set {0, 1, 2, ..., q − 1} with addition and multiplication done modulo a prime q. All arithmetic in Shamir's scheme lives here, which keeps values bounded and ensures every nonzero element has a multiplicative inverse.
Modular inverse
The element b such that a × b ≡ 1 (mod q). Required when dividing in Z_q, since you multiply by the inverse instead of dividing. For example, dividing by 24 in Z₃₁ means multiplying by 22, because 24 × 22 ≡ 1 (mod 31).
Share (or secret share)
A point (i, f(i)) on the secret polynomial, given to one participant. On its own, a single share tells you nothing about the secret.
You have five shares over Z₃₁: (1, 16), (2, 23), (3, 19), (4, 26), (5, 5). The threshold is k = 5, so all five shares are needed. The secret is f(0), the constant term of a degree-4 polynomial.
For each share (x_i, y_i), build L_i(x), the polynomial that equals 1 at x_i and 0 at every other x_j.
The general formula:
L_i(x) = ∏ (over all j ≠ i) of (x − x_j) / (x_i − x_j)
All arithmetic is mod 31. Division means multiplying by the modular inverse.
L₁(x): Numerator = (x−2)(x−3)(x−4)(x−5). Denominator = (1−2)(1−3)(1−4)(1−5) = (−1)(−2)(−3)(−4) = 24. The inverse of 24 mod 31 is 22 (since 24 × 22 = 528 = 17 × 31 + 1). So L₁(x) = 22(x⁴ − 14x³ + 71x² − 154x + 120), reduced mod 31 to 22x⁴ + 2x³ + 12x² + 22x + 5. Evaluating at x = 0: L₁(0) = 5.
L₂(x): Denominator = (2−1)(2−3)(2−4)(2−5) = (1)(−1)(−2)(−3) = −6. The inverse of −6 mod 31 is the inverse of 25 mod 31, which is 5 (since 25 × 5 = 125 = 4 × 31 + 1). Reduced: 5x⁴ + 28x³ + 16x² + 23x + 21. L₂(0) = 21.
L₃(x): Denominator = (3−1)(3−2)(3−4)(3−5) = (2)(1)(−1)(−2) = 4. Inverse of 4 mod 31 is 8 (since 4 × 8 = 32 ≡ 1). Reduced: 8x⁴ + 28x³ + 20x² + 27x + 10. L₃(0) = 10.
L₄(x): Denominator = (4−1)(4−2)(4−3)(4−5) = (3)(2)(1)(−1) = −6. Using the same inverse as L₂. Reduced: 5x⁴ + 7x³ + 19x² + 5x + 26. L₄(0) = 26.
L₅(x): Denominator = (5−1)(5−2)(5−3)(5−4) = (4)(3)(2)(1) = 24. Same inverse as L₁. Reduced: 22x⁴ + 28x³ + 26x² + 16x + 1. L₅(0) = 1.
The reconstructed polynomial is f(x) = Σ y_i × L_i(x). To find the secret, evaluate at x = 0:
f(0) = 16 × L₁(0) + 23 × L₂(0) + 19 × L₃(0) + 26 × L₄(0) + 5 × L₅(0)
f(0) = 16 × 5 + 23 × 21 + 19 × 10 + 26 × 26 + 5 × 1
f(0) = 80 + 483 + 190 + 676 + 5 = 1434
1434 mod 31 = 8
The secret is 8.
Given k − 1 shares (i, y_i) with distinct i values and any secret s ∈ Z_q, there is exactly one polynomial f of degree < k such that f(0) = s and f(i) = y_i for all i.
This is what makes the threshold sharp. With k shares, there is exactly one polynomial (and one secret). With k − 1 shares, every possible secret is consistent with some polynomial through those points, so no information leaks.
The k − 1 shares plus the point (0, s) give k points in total. A polynomial of degree at most k − 1 is determined by k points (if it exists), and Lagrange interpolation guarantees existence.
For uniqueness, suppose two polynomials f₁ and f₂ both pass through all k points. Define g(x) = f₁(x) − f₂(x). Then:
g has degree at most k − 1
g has k zeros: at 0, x₁, x₂, ..., x_{k−1}
Over Z_q (with q prime), a nonzero polynomial of degree k − 1 can have at most k − 1 zeros. Since g has k zeros, g must be the zero polynomial. Therefore f₁(x) = f₂(x).
The bound on zeros of polynomials over prime fields is doing the heavy lifting. This is a fact from algebra that you should know cold: a nonzero polynomial of degree d over Z_p has at most d roots.
For any secret s ∈ Z_m, any share index 1 ≤ i ≤ n, and any value a ∈ Z_m, the probability that share s_i equals a is exactly 1/m. Every individual share is uniformly random, regardless of the secret.
This is the security guarantee. If an individual share were more likely to take some values than others, an adversary holding one share could narrow down the secret. Uniform distribution means a single share is completely useless on its own.
The scheme considered here splits the secret additively: pick s₁, s₂, ..., s_{n−1} uniformly at random from Z_m, and set s_n = s − (s₁ + s₂ + ... + s_{n−1}) mod m.
For the first n − 1 shares, uniformity is immediate: they are chosen uniformly by construction.
For the last share s_n, you need two facts:
Claim 1: The sum of n uniformly random elements of Z_m, taken mod m, is itself uniformly distributed over Z_m.
Proof by induction. Base case: one element is trivially uniform. Inductive step: if x is uniform over Z_m and x_{k+1} is an independent uniform element, list all m² possible values of (x + x_{k+1}) mod m. Each element of Z_m appears exactly m times in the table (each row is a cyclic shift of {0, 1, ..., m−1}), so the sum is uniform.
Claim 2: If x is uniform over Z_m and c is a constant in Z_m, then (c − x) mod m is also uniform over Z_m.
The map x → (c − x) mod m is a bijection on Z_m. Proof by contradiction: if two distinct values x_i ≠ x_j mapped to the same output, then c − x_i ≡ c − x_j (mod m), which forces x_i = x_j. (The three cases in the homework solution just verify this for the different sign ranges of c − x.) Since a bijection preserves the uniform distribution, the claim follows.
Combining: s₁ + ... + s_{n−1} is uniform (Claim 1), so s − (s₁ + ... + s_{n−1}) mod m is uniform (Claim 2). Therefore Pr[s_n = a] = 1/m.
Secret polynomial:
f(x) = a₀ + a₁x + a₂x² + ... + a_{k−1}x^{k−1}, where a₀ = s (the secret) and a₁, ..., a_{k−1} are chosen uniformly at random from Z_q.
Lagrange basis polynomial:
L_i(x) = ∏ (j ≠ i) (x − x_j) / (x_i − x_j), all operations mod q.
Reconstruction formula:
f(x) = Σ (i = 1 to k) y_i × L_i(x). The secret is f(0) = Σ y_i × L_i(0).
Modular inverse (Fermat's little theorem):
a^{−1} ≡ a^{q−2} (mod q), valid when q is prime and a ≢ 0 (mod q).
Secret sharing is used in key management systems where no single person should hold an entire cryptographic key. For instance, a company might split its master encryption key among five executives so that any three can authorize a transaction. This is how some cryptocurrency custody solutions protect private keys. Lagrange interpolation itself appears any time you need to reconstruct a signal or dataset from sampled points, from error-correcting codes to numerical analysis.
Students often forget to reduce intermediate results mod q and end up with enormous numbers that look wrong. Every step of the computation should be reduced mod q as you go.
Students sometimes think they can divide directly in Z_q. You cannot. Division means multiplying by the modular inverse. If you write "divide by 24 mod 31," you mean "multiply by 22."
A common error is believing that k − 1 shares "partially reveal" the secret. They do not. The uniform distribution proof shows that every possible secret is equally likely given k − 1 shares.
Students sometimes confuse the degree of the polynomial with the number of shares. The polynomial has degree k − 1, and you need k shares (points) to reconstruct it.
⚠️ You will likely be asked to compute f(0) from a set of shares using Lagrange interpolation. Practise the full mechanical process, including modular inverses.
⚠️ The uniqueness proof (why k points determine a unique polynomial of degree < k over Z_q) is a standard exam question. Know the argument: difference polynomial g has too many zeros for its degree.
⚠️ The uniform distribution argument (Pr[s_i = a] = 1/m) is a classic "prove the security property" question. The two-claim structure (sum of uniforms is uniform; constant minus uniform is uniform) is the standard approach.
⚠️ Be ready to explain why k − 1 shares reveal nothing. The answer: for any secret value, there exists a unique polynomial consistent with those k − 1 shares plus that secret, so all secrets are equally likely.
True or false: In a (3, 5)-threshold scheme, any 2 shares are enough to recover the secret. (False: you need at least 3.)
Fill in the blank: The secret is encoded as the ______ term of the polynomial. (constant, i.e. a₀ = f(0))
True or false: Dividing by 6 in Z₃₁ means multiplying by 6^{29} mod 31. (True: by Fermat's little theorem, 6^{−1} ≡ 6^{31−2} mod 31.)
Fill in the blank: A nonzero polynomial of degree d over a prime field has at most ______ roots. (d)
True or false: A single share in Shamir's scheme reveals partial information about the secret. (False: each share is uniformly distributed regardless of the secret.)
Q: Given shares (1, 3), (2, 7), (3, 4) over Z₁₁ in a (3, 3)-threshold scheme, what is the secret?
A: Compute L₁(0), L₂(0), L₃(0) using the Lagrange formula mod 11, then f(0) = 3 × L₁(0) + 7 × L₂(0) + 4 × L₃(0) mod 11. Working through the inverses: L₁(0) = (0−2)(0−3) / (1−2)(1−3) = 6 / 2 = 3 (since 2^{−1} = 6 in Z₁₁). L₂(0) = (0−1)(0−3) / (2−1)(2−3) = 3 / (−1) = 3 × 10 = 8 mod 11. L₃(0) = (0−1)(0−2) / (3−1)(3−2) = 2 / 2 = 1. So f(0) = 3×3 + 7×8 + 4×1 = 9 + 56 + 4 = 69 = 3 mod 11. The secret is 3.
Q: Explain why k − 1 shares give no information about the secret in a (k, n)-threshold scheme.
A: For any value of the secret s, the k − 1 shares plus the point (0, s) form k points. Since a polynomial of degree < k is uniquely determined by k points, every value of s yields a different valid polynomial through the same k − 1 shares. So all secrets are equally likely, and the shares reveal nothing.
Q: Why must the modulus q be prime in Shamir's scheme?
A: The scheme relies on the fact that a nonzero polynomial of degree d over Z_q has at most d roots, which holds when q is prime (so Z_q is a field). Over non-prime moduli, polynomials can have more roots than their degree, which breaks the uniqueness argument.
Q: In the additive secret sharing proof, why is the map x → (c − x) mod m a bijection on Z_m?
A: If two inputs x_i ≠ x_j mapped to the same output, then c − x_i ≡ c − x_j (mod m), which implies x_i ≡ x_j (mod m), a contradiction. Since the map is an injection from a finite set to itself, it is a bijection.
Secret sharing connects directly to the graph non-isomorphism protocol and interactive proofs (also in HW 12), where randomness and information hiding play the same structural role. The polynomial root-counting argument used in the uniqueness proof reappears in error-correcting codes (Reed-Solomon codes are essentially Shamir's scheme repurposed for redundancy rather than secrecy). The modular arithmetic and finite-field techniques here are foundational for public-key cryptography topics later in the course.
Shamir secret sharing, Lagrange interpolation, polynomial interpolation, threshold cryptography, (k,n)-threshold scheme, secret reconstruction, finite field arithmetic, Z_q, modular inverse, Fermat's little theorem, polynomial root bound, information-theoretic security, additive secret sharing, EECS 376, foundations of computer science, University of Michigan