Shamir's Secret Sharing

Shamir's Secret Sharing (SSS) is a foundational (k, n) threshold cryptographic scheme in computation and algorithms that divides a secret S into n distinct cryptographic shares s₁, s₂, ..., s_n such that any subset of k or more shares can deterministically reconstruct S, whereas any subset of k − 1 or fewer shares reveals zero Shannon entropy information about S. Published by Israeli cryptographer Adi Shamir (co-inventor of the RSA cryptosystem) in 1979—simultaneously with and independently of George Blakley's hyperplane-intersection threshold scheme—Shamir's construction relies on the fundamental algebraic theorem that k points with distinct horizontal coordinates uniquely determine a polynomial of degree at most k − 1 over a finite field.

Within computational complexity theory and modern cryptography, storing a root cryptographic private key on a single machine creates a single point of compromise (if stolen) and a single point of failure (if destroyed), whereas replicating the same key across n servers multiplies the attack surface by n. Shamir's (k, n) threshold scheme resolves both hazards simultaneously with unconditional information-theoretic security: even an adversary with unbounded quantum computing power who compromises k − 1 custodians faces a uniform prior over every candidate secret S′ ∈ GF(q). Furthermore, because polynomial evaluation is a linear homomorphism, Shamir's Secret Sharing forms the mathematical core of secure multiparty computation (BGW protocol), threshold digital signatures, and zero-knowledge proof protocols.

Share Generation via Random Degree-(k − 1) Polynomials

Let GF(q) be a finite field of order q > n, where in practice q is chosen either as a prime p > max(S, n) (arithmetic modulo p) or as the binary extension field GF(2⁸) or GF(2¹²⁸) for byte-aligned implementation. To split a secret S ∈ GF(q) among n participants with reconstruction threshold k (1 ≤ k ≤ n < q):

1. Constant-Term Secret Embedding: Set the constant coefficient a₀ of a degree-(k − 1) polynomial f(x) ∈ GF(q)[x] equal to the secret:

1. Uniform Random Higher-Order Coefficients: Sample k − 1 coefficients a₁, a₂, ..., a_k−1 independently and uniformly at random from GF(q) using a cryptographically secure random number generator, defining the secret polynomial:

1. Evaluation at Non-Zero Public Abscissas: Assign each participant i ∈ {1, 2, ..., n} a distinct, non-zero public field element x_i ∈ GF(q) \ {0} (commonly x_i = i when q = p is prime) and distribute the point pair:

Evaluating f(x_i) via Horner's rule (f(x) = a₀ + x(a₁ + x(a₂ + ...))) requires k − 1 field multiplications and k − 1 field additions per share. Crucially, the evaluation coordinate x = 0 must never be assigned to any participant, because f(0) = a₀ = S would expose the raw secret in a single share.

Secret Reconstruction via Lagrange Polynomial Interpolation

Given any subset of k distinct shares {(x_j1, y_j1), (x_j2, y_j2), ..., (x_jk, y_jk)}, there exists a unique polynomial f(x) ∈ GF(q)[x] of degree ≤ k − 1 passing through all k points:

where ℓ_m(x) is the m-th Lagrange basis polynomial, satisfying ℓ_m(x_jm) = 1 and ℓ_m(x_jr) = 0 for all r ≠ m. Because only the constant term S = f(0) is required to recover the secret, one evaluates the Lagrange basis directly at x = 0:

where division in GF(q) is multiplication by the modular multiplicative inverse (x_jr − x_jm)⁻¹ mod q (computed via the Extended Euclidean Algorithm in O(log q) time). The secret S is then a linear combination of the k share values y_jm:

Perfect Secrecy Against k − 1 Colluding Parties

Suppose an adversary holds k − 1 distinct shares (x₁, y₁), ..., (x_k−1, y_k−1). For any hypothesized candidate secret S′ ∈ GF(q) at x₀ = 0, augmenting the k − 1 known points with the k-th point (0, S′) yields a system of k linear equations in the k unknown coefficients (a₀, a₁, ..., a_k−1):

• Row 0 (at x = 0): 1 · a₀ + 0 · a₁ + ... + 0 · a_k−1 = S′
• Row i (for i = 1 .. k − 1): 1 · a₀ + x_i a₁ + x_i² a₂ + ... + x_i^k−1 a_k−1 = y_i

The coefficient matrix V of this k × k system is a Vandermonde matrix over the k distinct abscissas {0, x₁, ..., x_k−1}, whose determinant is rigorously non-zero in GF(q):

Because V is invertible over GF(q), every candidate secret S′ ∈ GF(q) corresponds to one unique choice of the random coefficients (a₁, ..., a_k−1) ∈ GF(q)^k−1, which was chosen with uniform probability 1 / q^k−1. Thus, conditioned on k − 1 shares, every S′ ∈ GF(q) remains equally likely with posterior probability Pr[S = S′ | s₁, ..., s_k−1] = 1/q = Pr[S = S′], achieving Claude Shannon's criterion for perfect secrecy (H(S | s₁, ..., s_k−1) = H(S)) on par with the one-time pad.

Additive Homomorphism, BGW Multiplication, and Proactive Secret Sharing

Because polynomial evaluation and Lagrange interpolation are linear operators over GF(q), if two secrets S₁ = f(0) and S₂ = g(0) are shared using degree-(k − 1) polynomials at the same participant abscissas x_i, then each participant i can compute a share of the linear combination αS₁ + βS₂ locally without communication:

In the Ben-Or–Goldwasser–Wigderson (BGW, 1988) multiparty computation protocol, two shared secrets S₁ and S₂ can even be multiplied when 2k − 1 ≤ n: multiplying local shares f(x_i) · g(x_i) produces points on a degree-(2k − 2) polynomial (f · g)(x) with constant term S₁ · S₂, followed by a single round of Gennaro–Rabin–Rabin degree-reduction resharing back to degree k − 1.

Furthermore, Herzberg, Jarecki, Krawczyk, and Yung (1995) introduced Proactive Secret Sharing: participants periodically generate a random degree-(k − 1) polynomial δ(x) with zero constant term (δ(0) = 0) and add δ(x_i) to their existing shares (s_i′ = f(x_i) + δ(x_i)). The updated shares still interpolate to f(0) + δ(0) = S, but old shares captured by an attacker in previous epochs become algebraically incompatible with new shares.

Verifiable Secret Sharing (Feldman and Pedersen VSS)

In standard Shamir's Secret Sharing, a malicious Byzantine fault dealer could distribute inconsistent shares that do not lie on a single degree-(k − 1) polynomial, or a malicious participant could submit a forged share y_i′ during reconstruction (shifting the interpolated secret by (y_i′ − y_i) ℓ_i(0)). Feldman's Verifiable Secret Sharing (1987) solves both attacks by having the dealer broadcast commitments C_j = g^a_j mod P in a cyclic group where the discrete logarithm problem (as in Diffie–Hellman key exchange and elliptic-curve cryptography) is hard, allowing every participant i to verify its share y_i via:

Conversely, viewing the n evaluations (f(x₁), ..., f(x_n)) of a degree-(k − 1) polynomial as a codeword of a Reed–Solomon error-correcting code of length n and dimension k allows the Berlekamp–Welch algorithm to detect up to n − k corrupted shares and correct up to ⌊(n − k)/2⌋ malicious shares automatically.

Why is it fatal to implement Shamir's Secret Sharing over ordinary integers instead of a finite field GF(q)?

If the polynomial f(x) = S + a₁ x + ... + a_k−1 x^k−1 is evaluated over ordinary integers ℝ or ℤ without modular reduction in a finite field GF(q), even a single share (x₁, f(x₁)) leaks modular information about S because f(x₁) ≡ S (mod x₁), and the magnitude of f(x_i) leaks bounds on the coefficients. Modular arithmetic in a prime field GF(p) or binary Galois field GF(2^m) ensures that a₁ x₁ mod q is a uniform one-time pad over the entire field for every x₁ ≠ 0.

Can the threshold k or the number of participants n be changed without reconstructing the secret in one place?

Yes. New shares s_n+1 = (x_n+1, f(x_n+1)) can be issued to new participants by having k existing shareholders compute masked partial Lagrange contributions toward f(x_n+1), and the threshold k can be raised or lowered via multiparty polynomial resharing without any single party ever learning S = f(0).

1. Shamir, A. (1979). "How to share a secret." Communications of the ACM, 22(11), 612–613. https://doi.org/10.1145/359168.359176
2. Blakley, G. R. (1979). "Safeguarding cryptographic keys." Proceedings of the 1979 AFIPS National Computer Conference, Vol. 48, 313–317. https://doi.org/10.1109/AFIPS.1979.98
3. Feldman, P. (1987). "A practical scheme for non-interactive verifiable secret sharing." Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS 1987), 427–438. https://doi.org/10.1109/SFCS.1987.4
4. Ben-Or, M., Goldwasser, S., & Wigderson, A. (1988). "Completeness theorems for non-cryptographic fault-tolerant distributed computation." Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC '88), 1–10. https://doi.org/10.1145/62212.62213
5. Pedersen, T. P. (1991). "Non-interactive and information-theoretic secure verifiable secret sharing." Advances in Cryptology — CRYPTO '91, LNCS Vol. 576, 129–140. https://doi.org/10.1007/3-540-46766-1_9