Shamir secret sharing is a cryptographic scheme that divides a secret into shares so that any distinct shares can reconstruct it, while fewer than shares reveal no information about the secret. Introduced by Adi Shamir in 1979, it is a threshold secret-sharing scheme based on evaluating a randomly chosen polynomial over a finite field. Its confidentiality guarantee is information-theoretic: under the scheme’s assumptions, even unlimited computing power cannot extract information about the secret from an insufficient number of shares.
Threshold model
A scheme has a reconstruction threshold and a total of shares, with . The threshold determines both confidentiality and availability:
- Reconstruction: any set of at least valid, distinct shares determines the secret.
- Privacy: any set of fewer than shares has a distribution independent of the secret.
- Loss tolerance: as many as shares may be lost without preventing reconstruction, provided the remaining shares are valid.
For example, a scheme allows any three of five custodians to recover a secret, while one or two custodians learn nothing about its value from their shares alone.
The basic construction assumes an honest dealer: an entity that knows the secret, creates the shares correctly, and distributes them confidentially to their intended holders. It does not by itself verify that the dealer behaved honestly or that participants later submit correct shares.
Mathematical construction
Choosing the field and polynomial
The scheme operates over a finite field , containing elements, where is a prime power. The secret must be represented as an element . There must also be enough nonzero field elements to assign a distinct evaluation point to each participant, so .
A simple version uses arithmetic modulo a prime . The dealer independently samples uniformly random field elements,
and defines the polynomial
Thus, the secret is the constant term:
The polynomial has degree at most . All coefficients, including the highest one, are sampled from the entire field; it is not necessary to force the highest coefficient to be nonzero.
Creating shares
The dealer chooses distinct, nonzero public coordinates . Participant receives
The coordinate identifies the evaluation point and need not be secret. When coordinates are fixed by a protocol, a share may contain only , with its coordinate supplied by the participant’s identifier.
Zero cannot be used as an ordinary share coordinate because is the secret itself. Repeated coordinates do not provide additional independent shares.
Reconstructing the secret
Any evaluations at distinct coordinates uniquely determine a polynomial of degree at most . Using Lagrange interpolation, reconstruction can evaluate that polynomial directly at zero without explicitly recovering every coefficient.
For a set of share indices,
Every operation takes place in the chosen field. Division means multiplication by a multiplicative inverse, not ordinary integer division. The denominators are nonzero because the coordinates are distinct.
Worked example
Consider a scheme over , with secret . Suppose the dealer’s randomly chosen coefficients are and , giving
The resulting shares are:
| Coordinate | Share value |
|---|---|
| 1 | 10 |
| 2 | 2 |
| 3 | 15 |
| 4 | 15 |
| 5 | 2 |
Equal share values at different coordinates are permitted; the coordinates, rather than the values, must be distinct.
For coordinates , the Lagrange coefficients at zero are . Therefore,
Two shares do not determine the secret. For every candidate secret in , exactly one polynomial of degree at most two has that constant term and passes through the two specified points. Because the original coefficients were sampled uniformly, none of these candidate secrets is favored by observing those two shares.
The small field in this example is illustrative; actual field sizes and encodings depend on the application.
Why fewer shares reveal nothing
The privacy guarantee is stronger than saying that reconstruction is computationally difficult. An unauthorized set of shares does not change the probability distribution of the secret.
Suppose an observer obtains shares. For every possible secret , exactly
coefficient vectors produce the observed share values. Consequently, the probability of observing those shares is the same for every secret.
Writing for the secret and for a set of fewer than shares,
whenever the conditioning event has positive probability. This is perfect secrecy for unauthorized sets.
The guarantee does not require the secret itself to be uniformly distributed. It means that the shares add no information beyond an observer’s prior knowledge. Other disclosures—such as a public check value, exposed application data, or leakage from a device—can still reveal information independently of the sharing scheme.
Exact information-theoretic privacy assumes uniform, independent coefficient randomness. An implementation using a cryptographic pseudorandom number generator instead relies on that generator’s computational security for its approximation to ideal randomness.
Efficiency and storage
Each share contains one field element of secret-dependent data, plus its coordinate and any protocol metadata. When the secret is one field element, this makes Shamir sharing an ideal secret-sharing scheme: a share’s field-element payload is the same size as the secret.
However, the total storage across all participants is approximately times the secret’s size, excluding metadata. Sharing is not compression.
Straightforward polynomial evaluation takes field operations to generate all shares. Direct Lagrange reconstruction takes field operations, although precomputed coefficients and faster algorithms can improve particular workloads.
Long secrets can be divided into field-sized blocks and shared block by block, using fresh independent coefficient randomness for each block. Another common design encrypts a larger object and shares only its encryption key. In that design, confidentiality of the object also depends on the encryption scheme and key handling.
Applications and extensions
Distributed custody and recovery
Shamir sharing supports threshold custody of cryptographic keys and recovery secrets. It can distribute recovery authority across people, devices, organizations, or locations rather than placing it in one repository.
Unlike ordinary backup, possession of one copy-like object does not necessarily permit recovery. Unlike splitting a file into consecutive fragments, each subthreshold collection reveals nothing about the shared value under the mathematical assumptions.
Secure multiparty computation
Shamir shares can represent intermediate values in secure multiparty computation, allowing participants to compute jointly without first reconstructing their private inputs.
The scheme is linear. If and share secrets and over the same coordinates, then participants can locally add their share values to obtain shares of :
Multiplication by a public constant is similarly local. Multiplying two shared values is more involved because multiplying their polynomials increases the degree and generally requires an additional protocol.
Threshold cryptography
In threshold cryptography, multiple participants jointly perform operations such as signing or decryption without reconstructing the complete private key at one location.
Shamir sharing is often a building block, but sharing a key alone does not create a threshold signature or threshold decryption protocol. Such systems require additional mechanisms for computation, verification, randomness, and adversarial behavior.
Verifiable and proactive sharing
Verifiable secret sharing adds mechanisms for checking that distributed shares are consistent with a suitable sharing of a secret. The resulting guarantees and assumptions depend on the protocol.
Proactive secret sharing periodically refreshes shares without changing the secret. A basic refresh adds evaluations of a fresh random polynomial whose constant term is zero. Protection against an adversary that compromises participants over time depends on the refresh protocol, corruption limits, and effective erasure of obsolete shares.
Limitations and implementation concerns
Confidentiality does not provide integrity
Basic Shamir sharing does not authenticate shares or detect malicious replacements. With exactly distinct-coordinate submissions, even an incorrect value determines some interpolating polynomial and therefore some reconstructed result.
Message authentication codes, digital signatures, or verifiable-sharing protocols can provide additional checks, depending on the trust model. Authentication establishes a share’s origin and integrity; it does not necessarily prove that a malicious dealer generated it consistently.
Shamir shares are closely related to Reed–Solomon codes. If submitted evaluations contain at most erroneous values and
suitable decoding algorithms can uniquely recover the degree-at-most- polynomial. Ordinary interpolation alone does not provide this correction.
Field arithmetic and encoding
Arithmetic over arbitrary integers, composite moduli, or floating-point numbers is not interchangeable with finite-field arithmetic. Composite moduli can leave nonzero denominators without inverses, while floating-point calculations introduce rounding and do not preserve the scheme’s security argument.
Formats must unambiguously identify the field, threshold, coordinates, and sharing instance. Without this context, shares from different secrets or refresh periods may be accidentally combined.
Randomness and correlated disclosures
Predictable or biased coefficients can undermine confidentiality. Reusing coefficients across different secrets can expose relationships between them. For example, if two sharing polynomials differ only in their constant terms, subtracting their evaluations at the same coordinate reveals the difference between the secrets.
Operational trust boundaries
The threshold protects against obtaining too few valid shares; it does not prevent an authorized threshold coalition from reconstructing the secret. Nor does it protect a secret after reconstruction on a compromised device.
Shares held under common administrative control, stored together, or exposed through the same infrastructure may fail together. Consequently, the effective protection depends on the system’s threat model, distribution of custody, transport security, and handling of reconstructed secrets—not only on the numerical threshold.