Secret Sharing and Threshold Cryptography: Shamir, Additive Shares, and Threshold Decryption

Abstract

This article develops secret sharing, the building block of secure multi-party computation and threshold cryptography. It presents Shamir's scheme: a secret is hidden as the constant term of a random polynomial of degree one less than the reconstruction threshold, each party receives one evaluation point, any threshold-sized subset reconstructs the secret by interpolation, and any smaller subset learns nothing at all — an information-theoretic guarantee. It then covers additive sharing and, crucially, computing on shares: linear operations are performed locally on shares without any communication, while multiplication requires interaction, which is the seed of MPC's ability to evaluate arbitrary functions over shared data. It turns to threshold cryptography, where a signing or decryption key is split so that any threshold of parties can jointly sign or decrypt without any one ever holding the whole key, eliminating the single point of compromise and standardized in the NIST threshold-cryptography effort. It closes on why this matters and the AI stakes: distributed key custody, secure aggregation, and the sharing layer that federated learning is built on. The theme: secret sharing turns a secret into distributed shares that a threshold can use and a minority cannot, which is simultaneously a resilience tool and the substrate MPC computes on.

The engine underneath much of secure multi-party computation is a deceptively simple primitive: secret sharing. It splits a secret into pieces, called shares, and hands one to each party such that a chosen threshold of them can reconstruct the secret while any smaller group learns absolutely nothing. From this one idea flow two large capabilities — the ability to compute on shared data without revealing it, which powers MPC, and threshold cryptography, where a key is split so no single party can use it alone. This article builds Shamir's scheme, shows how computation happens on shares, and develops threshold signing and decryption.

Shamir's secret-sharing scheme hides a secret using a polynomial. To share a secret among several parties with a reconstruction threshold, one picks a random polynomial whose constant term is the secret and whose degree is one less than the threshold, then gives each party the value of that polynomial at a distinct point. The secret is the polynomial evaluated at zero, which no party is given directly; each holds only one point on the curve.

The mathematics of polynomial interpolation makes the threshold behavior exact. A polynomial of degree one less than the threshold is uniquely determined by exactly threshold-many points, so any threshold-sized subset of parties can pool their shares and interpolate to recover the polynomial and hence the secret. But any group with fewer than the threshold has too few points to pin down the polynomial: for every possible value of the secret there is a consistent polynomial through their shares, so their shares reveal nothing whatsoever about it. This is an information-theoretic guarantee — it holds against an adversary with unlimited computing power, not merely a bounded one.

The scheme is also flexible and robust. The threshold and the number of parties are chosen independently, so one can require, say, any three of five custodians to reconstruct a key; shares can be added or refreshed without changing the secret; and losing shares below the threshold destroys no security while losing them below reconstructability only affects availability. This clean separation — a tunable threshold, perfect privacy below it, guaranteed reconstruction at or above it — is why Shamir sharing is the default sharing primitive.

The secret is the constant term of a random polynomial; each party gets one point, and any threshold-many interpolate it back.

\[p(x) = s + a_1 x + a_2 x^2 + \dots + a_{t-1} x^{t-1}, \qquad \text{share}_i = p(i), \quad s = p(0)\]

\[\text{any } t \text{ shares} \Rightarrow \text{interpolate } p, \qquad \text{any } t-1 \text{ shares} \Rightarrow \text{no information about } s\]

Additive shares and computing on them

A simpler variant, additive sharing, splits a secret into random pieces that sum to it: each party holds a random value, and the shares together add up to the secret, so any single share is uniformly random and reveals nothing while all shares together reconstruct. Additive and Shamir sharing are the two workhorses, and both share the essential property that a strict subset of shares carries no information about the secret. What makes them the foundation of MPC is not just hiding a value but computing on it.

The key fact is that linear operations can be done on shares locally, with no communication. If each party adds its shares of two secrets, the resulting shares reconstruct to the sum of the secrets; if each party scales its share by a public constant, the shares reconstruct to the scaled secret. So additions and multiplications by public constants — the entire linear part of a computation — are free and non-interactive: the parties transform their shares in place and never reveal anything. This is why linear algebra, and thus much of machine learning, maps naturally onto secret-shared computation.

Multiplication of two secret-shared values is the hard case, because the product of shares is not a share of the product, and computing it requires interaction between the parties — classically using pre-shared correlated randomness known as Beaver triples to turn a multiplication into a few local operations plus one round of communication. This asymmetry — free linear operations, interactive multiplications — is the defining cost structure of share-based MPC, and it means the number and depth of multiplications, not additions, drive a protocol's communication. Computing any function reduces to these two operations on shares, which is how secret sharing becomes general secure computation.

\[\text{Local: } \text{share}(a) + \text{share}(b) = \text{share}(a+b), \qquad c \cdot \text{share}(a) = \text{share}(c \cdot a)\]

\[\text{Interactive: } \text{share}(a) \times \text{share}(b) \to \text{share}(ab) \;\text{ needs communication (Beaver triples)}\]

Threshold cryptography

Secret sharing applied to a cryptographic key gives threshold cryptography: instead of one party holding a signing or decryption key, the key is split into shares across several parties, and any threshold of them can jointly perform the operation without the whole key ever being assembled in one place. A threshold signature lets any threshold-sized subset of custodians produce a valid signature; threshold decryption lets any such subset decrypt a ciphertext — in both cases through a protocol on their key shares, never by reconstructing the key itself.

The security benefit is the elimination of a single point of compromise. With one key holder, stealing that one key breaks everything; with a threshold key, an attacker must compromise a threshold-many parties simultaneously to forge a signature or decrypt, and compromising fewer yields nothing. This turns key custody from an all-or-nothing target into a distributed one that tolerates the compromise of a minority, which is why threshold schemes protect high-value keys — certificate authorities, cryptocurrency custody, root signing keys — and why the NIST threshold-cryptography effort is standardizing them.

Threshold cryptography and MPC are the same idea at different scopes: both keep a secret split so that a minority learns nothing and a threshold can act, and both compute on the shares rather than reconstructing the secret. A threshold signature is essentially a special-purpose MPC protocol for the signing function, and secure aggregation — summing many parties' values so only the total is revealed — is a threshold-flavored MPC for addition. Seeing them as one family clarifies that secret sharing is the common substrate on which distributed trust is built.

A single key is one point of failure; a threshold key requires compromising a threshold of parties to misuse.

Why it matters, and the AI stakes

Secret sharing gives two things at once, which is why it is so central. As a resilience tool, it removes single points of failure from key custody and secret storage, tolerating the loss or compromise of a minority of shareholders. As a computational substrate, it lets mutually distrustful parties compute on data none of them will reveal, by transforming shares locally for linear steps and interacting only for multiplications. The same primitive underlies both a bank's threshold-protected signing key and a consortium's private joint computation.

The information-theoretic privacy of Shamir sharing also gives it a quiet post-quantum advantage. The guarantee that fewer than a threshold of shares reveals nothing holds against any adversary regardless of computing power, so the sharing layer itself has no quantum vulnerability — there is no hard problem for a quantum computer to solve. Threshold schemes built on top may use public-key primitives that must be made post-quantum, but the secret-sharing core is durable by construction, aligning with the series' theme that symmetric and information-theoretic foundations are the ones that endure.

For AI, secret sharing is the layer collaborative learning is built on. Secure aggregation in federated learning has each participant secret-share its model update so the server can reconstruct only the sum of all updates — the aggregate needed for training — while learning no individual contribution, exactly the additive-sharing computation described above. Distributed key custody protects the keys guarding models and data; threshold decryption lets a group jointly access protected model assets without any one party holding the key. Every one of these is secret sharing in action, and it is why this primitive, humble as it looks, is the foundation on which the private-set-intersection and machine-learning protocols of the coming articles — and collaborative AI generally — are constructed. Split the secret, compute on the shares, reconstruct only what was agreed: that is the pattern the rest of MPC elaborates.

📌

One primitive, two powers. Secret sharing splits a value so a threshold can use it and a minority learns nothing — information-theoretically. That gives resilience (no single point of key compromise, via threshold signing and decryption) and computation (linear operations free on shares, multiplications interactive), which is the substrate MPC and secure aggregation are built on.

Key takeaways

Shamir sharing hides a secret as the constant term of a random degree t-1 polynomial; any t shares interpolate it, and any t-1 reveal nothing — information-theoretically.
Additive sharing splits a secret into random pieces that sum to it; both schemes make any strict subset of shares carry no information.
Linear operations on shares (addition, scaling by a public constant) are local and free; multiplication of two shared values requires interaction (Beaver triples).
This free-linear, interactive-multiplication structure is MPC's cost signature, making multiplicative depth and count drive communication.
Threshold cryptography splits a signing or decryption key so any threshold jointly operates without assembling the key, removing the single point of compromise.
For AI, secret sharing underlies secure aggregation in federated learning and distributed key custody, and its information-theoretic core is inherently post-quantum.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Applying secret sharingchecklist

Questions for a sharing-based design.

What reconstruction threshold and party count fit the trust model?
Is Shamir (threshold interpolation) or additive (sum) sharing the right fit?
Are the needed operations mostly linear (free) or multiplication-heavy (interactive)?
Should a key be threshold-split to remove a single point of compromise?
Does the information-theoretic sharing core give the post-quantum durability required?

🚀The sharing mental modelquickstart

Three facts to hold onto.

Below threshold: shares reveal nothing; at threshold: reconstruct exactly.
Linear operations are free on shares; multiplications need interaction.
Threshold keys remove the single point of compromise.

🔒Distributed-secret stancepolicy

A stub recording the sharing decision.

secret_sharing:
  scheme: [shamir, additive]
  threshold: t_of_n
  privacy: information_theoretic
  compute_on_shares:
    linear: local_free
    multiplication: interactive_beaver
  threshold_keys:
    signing: t_of_n
    decryption: t_of_n
    single_point_of_failure: removed

Illustrative documentation template, not a product config.

Glossary

Secret sharing: Splitting a secret into shares so a threshold of parties can reconstruct it while fewer learn nothing.
Shamir secret sharing: A scheme hiding the secret as the constant term of a random polynomial; any threshold-many evaluation points reconstruct it.
Additive sharing: Sharing a secret as random pieces that sum to it; any single share is uniformly random.
Computing on shares: Performing operations on shares directly — linear steps locally, multiplications interactively — without revealing the secret.
Beaver triple: Pre-shared correlated randomness that turns a secret-shared multiplication into local operations plus one communication round.
Threshold cryptography: Splitting a key so any threshold of parties can jointly sign or decrypt without assembling the whole key.
Secure aggregation: Summing many parties' values via sharing so only the total is revealed, used in federated learning.