Secret Sharing

In a perfect secret sharing scheme, an unauthorized subset of shares provides absolutely no information about the secret. This is not computational security reliant on hard math problems; even an attacker with infinite computing power cannot determine the secret if they lack the threshold number of shares. This is a stronger guarantee than standard encryption.

• Perfect Secrecy: The conditional probability of the secret given the shares equals the prior probability.
• Entropy Preservation: The mutual information between the secret and an unauthorized set of shares is exactly zero.

The secret can be efficiently reconstructed only when a quorum of shares is combined. This is defined by the (t, n) threshold, where t is the minimum number of shares required out of n total participants.

• Flexible Access Structures: General schemes allow arbitrary monotone boolean formulas (e.g., 'Alice AND Bob' OR 'Charlie').
• Deterministic Recovery: Combining t valid shares always yields the original secret without error.
• Graceful Degradation: The system remains secure if up to t-1 shares are lost or destroyed.

Each individual share must appear as a uniformly random string to an observer. No single share should leak the length or structure of the secret, nor should it be distinguishable from a random value of the same size.

• Uniform Distribution: Shares are drawn from a uniform probability distribution over the share space.
• Padding and Masking: In schemes like Shamir's, the secret is hidden as the constant term of a random polynomial, making shares look like random points on a graph.

Many secret sharing schemes, particularly Shamir's, are additively homomorphic. Computations on the shares translate directly to computations on the underlying secrets without reconstruction.

• Share Addition: Adding corresponding shares from two different secrets locally produces a valid share of the sum of the secrets.
• Secure Aggregation: This property is critical for Federated Learning, allowing a central server to sum model updates without ever decrypting individual client contributions.

To defend against mobile adversaries who slowly compromise nodes over time, shares can be periodically refreshed without changing the underlying secret. This is known as Proactive Secret Sharing (PSS).

• Share Renewal: New, independent polynomial shares are generated and distributed to participants.
• Zero-Sum Updates: The sum of the update shares is zero, so the old shares are invalidated but the reconstructed secret remains identical.
• Window of Vulnerability: Limits the time an attacker has to compromise t shares before they become obsolete.

Verifiable Secret Sharing (VSS) extends the basic scheme to prevent a malicious dealer from distributing inconsistent shares that cannot reconstruct a valid secret.

• Commitment Schemes: The dealer broadcasts cryptographic commitments to the polynomial coefficients.
• Share Validation: Each participant can independently verify that their received share lies on the committed polynomial without revealing the share to others.
• Byzantine Resilience: This is essential for Secure Multi-Party Computation where participants cannot trust the dealer or each other.

Secret sharing enables a central server to compute the sum of model updates without ever inspecting individual client gradients. Each client splits its update into masked shares and distributes them to peers. The server only sees the aggregated sum after shares are combined, providing information-theoretic privacy against honest-but-curious servers.

• Prevents gradient leakage and reconstruction of private training data
• Eliminates the need for a fully trusted central aggregator
• Used in production systems like Google's Federated Learning of Cohorts

Combining secret sharing with verifiable secret sharing (VSS) allows honest nodes to detect malicious participants submitting poisoned updates. Each share includes a cryptographic commitment, enabling peers to verify share consistency before aggregation. This thwarts model poisoning attacks where adversaries manipulate local updates to corrupt the global model.

• Detects Byzantine behavior during the sharing phase
• Ensures share integrity without revealing the underlying update
• Compatible with robust aggregation rules like Krum and Trimmed Mean

Federated learning systems face unreliable clients that disconnect mid-round. Shamir's Secret Sharing with a (t, n)-threshold scheme allows reconstruction from any t out of n shares. If clients drop out, the surviving subset can still complete secure aggregation without restarting the protocol, maintaining liveness in decentralized training.

• Tolerates up to n - t client failures per round
• Eliminates straggler bottlenecks in synchronous aggregation
• Critical for mobile federated learning with intermittent connectivity

In cross-silo federated learning, organizations within a consortium may not trust a single aggregator. Hierarchical secret sharing distributes trust across multiple intermediate aggregators. Each institution splits its update among regional nodes, which then aggregate shares before passing partial sums to a global coordinator.

• Prevents collusion between aggregators and participants
• Aligns with regulatory requirements for multi-jurisdictional data
• Supports multi-party computation (SMPC) for complex aggregation functions

Long-lived federated learning tasks face the risk of mobile adversary attacks where attackers slowly compromise nodes over time. Proactive secret sharing periodically refreshes shares without changing the underlying secret, invalidating any shares accumulated by an adversary before they reach the reconstruction threshold.

• Defends against gradual node compromise over extended training rounds
• Maintains forward secrecy of historical model updates
• Essential for continuous learning systems operating over months or years

Resource-constrained edge devices can participate in secure federated learning using lightweight secret sharing schemes optimized for low compute overhead. Techniques like randomized secret sharing and sparse secret sharing reduce communication costs while preserving the privacy guarantees of full sharing protocols.

• Minimizes bandwidth consumption on IoT and mobile devices
• Compatible with quantized model updates for efficient transmission
• Enables secure training on microcontrollers with < 512KB RAM

The foundational algorithm developed by Adi Shamir in 1979. It encodes a secret as the constant term of a random polynomial of degree t-1 over a finite field. Each participant receives a distinct point on the polynomial. Reconstruction requires any t shares to solve for the coefficients via Lagrange interpolation, while t-1 shares reveal absolutely no information about the secret. This provides information-theoretic security, meaning it is secure against adversaries with unlimited computational power.

An extension of standard secret sharing that prevents a malicious dealer from distributing inconsistent shares. VSS protocols require the dealer to publish cryptographic commitments to the polynomial coefficients. Participants can then non-interactively verify that their received share is consistent with the committed polynomial without revealing the share itself. This is critical in Byzantine fault-tolerant systems where the dealer cannot be trusted.

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 to peers. By summing these updates, old shares are invalidated. This defends against mobile adversaries who slowly compromise nodes over time, ensuring the secret remains secure as long as fewer than t shares are compromised within a refresh epoch.

The practical application of secret sharing to distribute cryptographic operations. Instead of reconstructing a private key to sign a transaction, a threshold signature scheme (TSS) allows a quorum of t parties to collaboratively produce a valid signature without any single party ever holding the full key. This eliminates the single point of compromise in wallet security and is widely used in institutional digital asset custody.

A broader cryptographic paradigm that generalizes secret sharing. SMPC allows multiple parties to jointly compute a function over their private inputs while keeping those inputs mutually secret. Secret sharing serves as the wire-level encoding in protocols like SPDZ and BGW, where data is shared additively among parties who then perform secure addition and multiplication gates to evaluate arbitrary circuits without revealing intermediate states.

A gold standard of cryptographic strength achieved by Shamir's scheme. Unlike computationally secure systems that rely on the hardness of factoring or discrete logarithms, information-theoretic security guarantees that an adversary with infinite computing power cannot break the scheme. The ciphertext (or shares) provides zero statistical correlation to the plaintext (secret). This property is crucial for long-term secrets that must remain secure against future advances in quantum computing.