Shamir Secret Sharing

The core mechanism of SSS: a secret is encoded as the constant term of a random polynomial of degree t-1. Any t distinct points (shares) uniquely determine the polynomial via Lagrange interpolation, while t-1 or fewer shares reveal absolutely no information about the secret.

• Information-theoretic security: The scheme is unconditionally secure, not reliant on computational hardness assumptions
• Perfect secrecy: Fewer than t shares provide zero statistical advantage over guessing
• Example: A (3,5) scheme splits a key among 5 participants; any 3 can reconstruct it, but any 2 cannot

SSS is additively homomorphic: the sum of shares from different secrets produces a valid share of the sum of those secrets. This property is critical for secure aggregation in federated learning.

• Clients can mask their model updates with secret-shared masks
• The server sums all masked updates; the masks cancel out in the aggregate
• Enables pairwise masking protocols where each pair of clients agrees on a shared secret
• The server learns only the aggregate model update, never individual contributions

SSS naturally handles client dropouts in distributed protocols. If a client disconnects before revealing its share, the remaining participants can still reconstruct the secret as long as the threshold is met.

• Robustness: Protocol proceeds with any subset of size t or greater
• Dynamic membership: New shares can be issued without changing the secret by evaluating the polynomial at new points
• Practical application: In federated learning rounds, if 30% of clients drop out, the server can still unmask the aggregate from surviving clients
• Contrast with simple XOR-based secret sharing, which fails if any share is lost

Each share in SSS is exactly the same size as the original secret. This is optimal for information-theoretic secret sharing schemes and critical for bandwidth-constrained federated learning deployments.

• No expansion: A 256-bit secret produces 256-bit shares
• Scalable: Share size remains constant regardless of the total number of participants n
• Communication overhead: In secure aggregation, each client transmits only one masked update vector, not n separate shares
• Compare with replication-based approaches that require O(n) storage per participant

Standard SSS assumes an honest dealer distributing correct shares. Verifiable Secret Sharing (VSS) extends SSS with cryptographic commitments that allow participants to verify share consistency without revealing the secret.

• Uses Pedersen commitments or Feldman's scheme to publish polynomial commitments
• Prevents a malicious dealer from distributing inconsistent shares that prevent reconstruction
• Essential for malicious security models in secure aggregation
• Enables participants to detect cheating before the reconstruction phase begins

Shares can be periodically refreshed without changing the underlying secret, a technique called proactive secret sharing. This defends against mobile adversaries that slowly compromise shares over time.

• Each refresh cycle: new random polynomial with same constant term is generated
• Old shares become cryptographically useless after refresh
• Adversary must compromise t shares within a single epoch to recover the secret
• Used in long-lived secure aggregation systems to maintain forward secrecy of historical updates

A protocol enabling a central server to compute the sum of model updates from multiple clients without inspecting any individual contribution. It relies heavily on Shamir Secret Sharing for dropout resilience: if a client disconnects, their secret-shared mask can still be reconstructed by a quorum of remaining users, ensuring the round completes without exposing private vectors.

An enhancement of standard secret sharing that prevents a malicious dealer from distributing inconsistent shares. VSS adds a commitment scheme to the polynomial coefficients, allowing each participant to verify their share is a valid point on the original polynomial. This is critical for Byzantine Fault Tolerance in adversarial settings where the dealer cannot be trusted.

The mathematical engine of Shamir's reconstruction phase. Given k distinct points on a polynomial of degree k-1, Lagrange interpolation uniquely reconstructs the original polynomial and its constant term (the secret). The formula computes a weighted sum of the y-values, where weights depend solely on the x-coordinates. This ensures any subset of shares smaller than the threshold reveals absolutely no information.

A simpler scheme where a secret s is split into n random values that sum to s modulo a prime. Unlike Shamir's threshold scheme, additive sharing requires all shares for reconstruction (n-out-of-n). It is computationally lighter and often used in Secure Multi-Party Computation (MPC) for honest-majority settings, but lacks the graceful degradation of Shamir's approach when parties drop out.

A lifecycle management protocol that periodically refreshes shares without changing the underlying secret. Each participant generates a new random polynomial with a zero constant term and distributes sub-shares. After aggregation, old shares become useless. This defends against mobile adversaries who slowly compromise nodes over time, a critical property for long-lived cryptographic custody systems.

A public-key scheme where the decryption key is distributed using techniques analogous to Shamir's sharing. A ciphertext can only be decrypted when a threshold number of parties cooperate. Unlike secret sharing, which protects a static secret, threshold encryption protects a function (decryption) and is used in distributed key generation for blockchain validators and privacy-preserving machine learning inference.