Difficulty: Intermediate | Prerequisites: modular arithmetic, polynomial basics, finite fields (Z_q)
Big Picture
Secret sharing sits at the intersection of cryptography and algebra. The core question: how do you split a secret among n people so that any k of them can reconstruct it, but fewer than k learn nothing at all? Shamir's scheme answers this by encoding the secret as the constant term of a random polynomial, then handing out points on that polynomial as shares. Lagrange interpolation is the mathematical tool that lets any k shareholders reconstruct the polynomial (and therefore the secret) from their points. You need comfort with modular arithmetic over Z_q to follow the worked examples.
TL;DR
Shamir's secret sharing hides a secret as the y-intercept of a degree-(k-1) polynomial over a finite field. Each participant gets a distinct point on that polynomial. Any k points uniquely determine the polynomial via Lagrange interpolation, recovering the secret; fewer than k points give no information about it.
(k, n)-Threshold Secret Sharing
A scheme in which a secret is distributed among n participants such that any k or more of them can reconstruct the secret, but any group of fewer than k learns nothing about it.
Think of it as a lock that requires exactly k different keys turned at the same time. Fewer keys, and the lock does not budge at all.
Shamir's Secret Sharing
A specific threshold scheme that encodes the secret s as the constant term (a_0) of a random polynomial f(x) of degree k-1 over a finite field Z_q. Each participant i receives the share (i, f(i)).
In simple terms, you hide the secret as the y-intercept of a curve, and hand out points on that curve.
Lagrange Interpolation
A method for reconstructing a unique polynomial of degree at most n-1 that passes through n given points. Used here to recover f(x) from k shares and evaluate f(0) = s.
Think of it as reverse-engineering the equation of a curve when you know enough points on it.
Lagrange Basis Polynomial, L_i(x)
The polynomial that equals 1 at x_i and 0 at every other x_j. The full interpolating polynomial is built as a weighted sum of these basis polynomials.
In simple terms, each basis polynomial is a building block that "activates" at exactly one share's x-value and stays silent at all others.
Modular Inverse
For a non-zero element a in Z_q, the modular inverse a^{-1} is the element b such that a * b ≡ 1 (mod q). Needed whenever Lagrange interpolation requires division.
Think of it as the finite-field version of dividing: instead of 1/a, you find the number that multiplies with a to give 1 under the modulus.
Z_q (Integers Modulo q)
The set {0, 1, 2, ..., q-1} with addition and multiplication performed modulo a prime q. Every non-zero element has a multiplicative inverse, making this a finite field.
In simple terms, arithmetic that wraps around at q, like a clock with q hours. Using a prime ensures division always works.
Setup. Choose a prime q. The secret s lives in Z_q. Pick k-1 random coefficients a_1, ..., a_{k-1} from Z_q.
Polynomial construction. Form f(x) = s + a_1 * x + a_2 * x^2 + ... + a_{k-1} * x^{k-1}. The secret is the constant term, f(0) = s.
Share distribution. Give participant i the share s_i = (i, f(i)) for i = 1, ..., n. Each person gets a distinct point on the polynomial.
Reconstruction. Any k participants pool their shares and use Lagrange interpolation to reconstruct f(x), then evaluate f(0) to recover s.
Security guarantee. Fewer than k shares leave the secret completely undetermined: for any guess of s, there exists a consistent polynomial.
Given k shares (x_1, y_1), ..., (x_k, y_k), the interpolating polynomial is:
f(x) = sum over i from 1 to k of y_i * L_i(x)
where each L_i(x) is the Lagrange basis polynomial for point i.
To find the secret, evaluate at x = 0:
s = f(0) = sum over i from 1 to k of y_i * L_i(0)
Given: Three shares over Z_37: (2, 5), (4, 11), (13, 21). The password requires 3 shares (so k = 3, meaning the underlying polynomial has degree 2).
Step 1: Build L_1(x) for the point (2, 5).
L_1(x) = [(x - 4)(x - 13)] / [(2 - 4)(2 - 13)]
Numerator: (x - 4)(x - 13) = x^2 - 17x + 52
Denominator: (-2)(-11) = 22
Need 22^{-1} mod 37. Since 22 * 32 = 704 = 19 * 37 + 1, so 22^{-1} ≡ 32 (mod 37)
L_1(x) = 32(x^2 - 17x + 52) = 32x^2 - 544x + 1664
Reduce mod 37: 32x^2 + 11x + 36
Step 2: Build L_2(x) for the point (4, 11).
L_2(x) = [(x - 2)(x - 13)] / [(4 - 2)(4 - 13)]
Denominator: (2)(-9) = -18 ≡ 19 (mod 37)
Need 19^{-1} mod 37. Since 19 * 2 = 38 ≡ 1 (mod 37), so 19^{-1} ≡ 2 (mod 37)
Numerator: x^2 - 15x + 26
L_2(x) = 2(x^2 - 15x + 26) = 2x^2 - 30x + 52 ≡ 2x^2 + 7x + 15 (mod 37)
Step 3: Build L_3(x) for the point (13, 21).
L_3(x) = [(x - 2)(x - 4)] / [(13 - 2)(13 - 4)]
Denominator: (11)(9) = 99 ≡ 25 (mod 37)
Need 25^{-1} mod 37. Since 25 * 3 = 75 = 2 * 37 + 1, so 25^{-1} ≡ 3 (mod 37)
Numerator: x^2 - 6x + 8
L_3(x) = 3(x^2 - 6x + 8) = 3x^2 - 18x + 24 ≡ 3x^2 + 19x + 24 (mod 37)
Step 4: Combine.
f(x) = 5 * L_1(x) + 11 * L_2(x) + 21 * L_3(x)
Evaluate at x = 0 to find the password:
5 * L_1(0) = 5 * 36 = 180 ≡ 180 - 4*37 = 180 - 148 = 32 (mod 37)
11 * L_2(0) = 11 * 15 = 165 ≡ 165 - 4*37 = 165 - 148 = 17 (mod 37)
21 * L_3(0) = 21 * 24 = 504 ≡ 504 - 13*37 = 504 - 481 = 23 (mod 37)
s = f(0) = 32 + 17 + 23 = 72 ≡ 72 - 37 = 35 (mod 37)
The password is 35.
Secret-sharing polynomial:
f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{k-1} x^{k-1}, \quad a_0 = sLagrange basis polynomial:
L_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}Reconstruction formula:
f(x) = \sum_{i=1}^{k} y_i \cdot L_i(x)Secret recovery (evaluate at 0):
s = f(0) = \sum_{i=1}^{k} y_i \cdot L_i(0)Modular inverse rule:
For prime q and non-zero a in Z_q, the inverse a^{-1} satisfies a * a^{-1} ≡ 1 (mod q). By Fermat's little theorem, a^{-1} ≡ a^{q-2} (mod q). In the HW 12 example over Z_37, 22^{-1} ≡ 32 because 22 * 32 = 704 ≡ 1 (mod 37).
Given k-1 shares (i_1, y_1), ..., (i_{k-1}, y_{k-1}) and any candidate secret s in Z_q, there is exactly one polynomial of degree < k passing through all k points (the k-1 shares plus the point (0, s)). This is because k points uniquely determine a polynomial of degree at most k-1.
Conversely, with only k-1 shares, for every possible value of s there is a consistent polynomial. The shares constrain the polynomial to a one-dimensional family parameterised by s, and every s in Z_q is equally consistent. An attacker with k-1 shares has no information advantage.
Fix k-1 points and any secret s. You have k constraints on a polynomial with k coefficients (a_0 = s, plus k-1 equations f(i_j) = y_j). This is a system of k-1 linear equations in k-1 unknowns (a_1, ..., a_{k-1}), since a_0 is fixed at s. The coefficient matrix is a Vandermonde matrix with distinct evaluation points, which is always invertible over Z_q. Therefore the system has a unique solution.
Secret sharing schemes protect cryptographic keys, nuclear launch codes (the classic example), and corporate signing keys. In practice, Shamir's scheme underpins multi-party key management in cryptocurrency wallets and threshold signature protocols.
Students often think that having k-1 shares gives you "most" of the secret. It does not. k-1 shares leave every possible secret equally likely; you learn literally zero bits of information.
Students sometimes forget to reduce intermediate results mod q, leading to wildly wrong answers in Lagrange interpolation. Every arithmetic step, including subtraction in the denominator, must be reduced mod q.
Students confuse "dividing by a" with "multiplying by a^{-1} mod q." In Z_q there is no division operator. You must compute the modular inverse first, then multiply.
Students occasionally assume the polynomial is always degree exactly k-1. Technically, the leading coefficient could be zero, making the degree less than k-1. The scheme guarantees degree < k, not degree = k-1.
⚠️ You will almost certainly be asked to compute a Lagrange interpolation by hand over some Z_q. Practise the modular inverse step until it is automatic.
⚠️ The security proof (k-1 shares reveal nothing) is a standard exam question. Know the Vandermonde argument.
⚠️ Be careful with negative numbers in modular arithmetic. -18 mod 37 is 19, not -18.
⚠️ The reason we work over Z_q with q prime (not over the integers) is that we need every non-zero element to have a multiplicative inverse.
True or False: With a (3, 5)-threshold scheme, any 2 shareholders can reconstruct the secret. False.
Fill in the blank: The secret is encoded as the ______ of the polynomial. Constant term (a_0 = f(0)).
True or False: L_i(x_i) = 1 and L_i(x_j) = 0 for j ≠ i. True.
Fill in the blank: To divide by 22 in Z_37, you multiply by ______. 32 (the modular inverse of 22 mod 37).
True or False: A degree-2 polynomial is uniquely determined by 2 points. False. You need 3 points.
Q: In a (k, n)-threshold scheme over Z_q, why must q be prime?
A: Because Z_q is a field only when q is prime, meaning every non-zero element has a multiplicative inverse. Without inverses, Lagrange interpolation breaks down (you cannot divide).
Q: You are given shares (1, 3) and (2, 7) from a (3, 5)-threshold scheme over Z_11. Can you determine the secret?
A: No. You have only 2 shares but need k = 3. For every possible secret s in Z_11, there exists a unique degree-2 polynomial passing through (0, s), (1, 3), and (2, 7). All secrets are equally likely.
Q: Compute L_1(0) for shares with x-values 2, 4, 13 over Z_37.
A: L_1(0) = [(0 - 4)(0 - 13)] / [(2 - 4)(2 - 13)] = [(-4)(-13)] / [(-2)(-11)] = 52 / 22 = 52 * 32 mod 37 = 1664 mod 37 = 36.
Q: State the reconstruction formula for the secret s given k shares.
A: s = f(0) = sum from i = 1 to k of y_i * L_i(0), where L_i(0) = product over j ≠ i of (0 - x_j) / (x_i - x_j), all mod q.
Q: Prove that k-1 shares reveal no information about the secret in a (k, n)-threshold scheme.
A: Fix any k-1 shares. For any candidate secret s, the k points (0, s) together with the k-1 shares uniquely determine a polynomial of degree < k (Vandermonde matrix is invertible). So every s is consistent with exactly one polynomial, and all secrets are equally likely.
This material connects to polynomial identity testing: if two polynomials of degree < k agree on k points, they are identical, which is the mathematical foundation for why reconstruction works.
It also links to zero-knowledge proofs (Problem 2 in this homework). Secret sharing is a building block in many cryptographic protocols, including secure multi-party computation.
Related Terms / Search Tags
Shamir secret sharing, Lagrange interpolation, threshold cryptography, polynomial interpolation, modular inverse, finite field arithmetic, Z_q, Vandermonde matrix, secret reconstruction, (k n) threshold scheme, EECS 376, Foundations of Computer Science, University of Michigan