Secret Sharing

A (t, n)-threshold scheme divides a secret into n shares distributed among participants. Any t or more shares can reconstruct the secret, while any t-1 or fewer shares reveal absolutely no information. This provides information-theoretic security—the guarantee holds even against adversaries with unlimited computational power. For example, a (3, 5)-threshold scheme requires any 3 of the 5 shareholders to cooperate for reconstruction.

Shamir's scheme encodes the secret as the constant term of a random polynomial of degree t-1 over a finite field. Each share is a point (x, y) on the polynomial curve. Reconstruction uses Lagrange interpolation to recover the unique polynomial from t points. The finite field arithmetic ensures that fewer than t points define an infinite number of possible polynomials, making the secret unconditionally undetermined.

In secure aggregation protocols, secret sharing enables robustness to client dropouts. Each client's model update is split into shares distributed to other clients. If a client disconnects before completing the round, the server can still reconstruct the aggregate sum by collecting shares of the dropped client's mask from the surviving participants. This ensures a single straggler does not block the entire training round.

Standard secret sharing assumes an honest dealer. VSS extends the scheme with cryptographic commitments that allow each participant to verify their share's consistency without revealing the secret. This prevents a malicious dealer from distributing invalid shares that would prevent correct reconstruction. VSS is essential in Byzantine fault-tolerant systems where participants cannot trust a central distributor.

A simpler variant where a secret s is split into n random shares that sum to s modulo some integer. Reconstruction requires all n shares—this is an (n, n)-threshold scheme. While less flexible than Shamir's, additive sharing is computationally lightweight and enables secure multi-party computation (MPC) operations directly on shares. It is commonly used in privacy-preserving machine learning for efficient linear operations.

In long-lived systems, an adversary may slowly compromise shares over time. Proactive secret sharing periodically refreshes shares without changing the underlying secret. Each participant generates new random sub-shares and distributes them, allowing old shares to be discarded. This mobile adversary defense ensures that an attacker must compromise t shares within a single refresh epoch to breach confidentiality.

The canonical threshold scheme that encodes a secret as a constant term of a random polynomial of degree t-1 over a finite field. Each share is a distinct point (x, f(x)) on the polynomial. Reconstruction requires any t shares to solve for the polynomial coefficients via Lagrange interpolation, while t-1 shares reveal absolutely no information about the secret. This provides information-theoretic security—the guarantee holds against adversaries with unbounded computational power.

An enhancement of standard secret sharing that protects against a malicious dealer who may distribute inconsistent shares. VSS protocols require the dealer to broadcast cryptographic commitments to the polynomial coefficients, allowing each participant to verify that their received share is consistent with the committed polynomial. This prevents a corrupt dealer from causing reconstruction failure or manipulating the secret. Essential for secure aggregation in adversarial settings where clients cannot trust a central coordinator.

The property that allows a secure aggregation round to complete successfully even when a subset of clients disconnects, crashes, or goes offline mid-protocol. In secret-sharing-based aggregation, dropout resilience is achieved by having surviving clients reveal the shares of the departed parties' pairwise masks. The server can then reconstruct those masks and subtract them from the aggregate, recovering the correct sum. This is critical for federated learning at scale, where client availability is inherently unreliable.

A broader cryptographic paradigm that enables multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. Secret sharing serves as the core encoding mechanism in information-theoretic MPC protocols such as GMW and BGW. In these protocols, inputs are secret-shared among participants, computation proceeds via interactive share manipulation, and the final output is reconstructed. MPC generalizes secure aggregation to arbitrary functions beyond summation.

A specific technique used in practical secure aggregation protocols where each pair of clients (u, v) agrees on a shared pseudorandom mask. Client u adds the mask to its update, while client v subtracts it. When the server sums all updates, these pairwise masks cancel out, revealing only the aggregate. This relies on Diffie-Hellman key agreement for mask setup and pseudorandom generators (PRGs) for efficient mask expansion. Secret sharing is used to reconstruct masks for dropped-out clients.

A public-key encryption scheme where the decryption key is split into shares distributed among multiple parties. A ciphertext can only be decrypted when a threshold number of parties cooperate to perform a distributed decryption protocol. Unlike secret sharing, which protects a secret at rest, threshold encryption protects data in ciphertext form and enables collaborative decryption without ever reconstructing the full private key in one location. Used as an alternative to secret sharing for server-mediated aggregation.