Verifiable Secret Sharing (VSS)

This is the defining property of VSS. Each participant can cryptographically verify that their share is consistent with all other shares and was generated from a single, valid secret. This prevents a malicious dealer from distributing inconsistent shares, which would make secret reconstruction impossible. Verification typically uses commitment schemes (like Pedersen commitments) or digital signatures.

VSS maintains the core secrecy guarantee of its underlying secret sharing scheme (e.g., Shamir's). Any group of participants smaller than the threshold t learns zero information about the original secret. This holds even if the dealer is malicious, as the verification process does not leak the secret. The secret is only revealed when at least t honest participants combine their shares.

A VSS protocol is robust if it guarantees that honest participants will successfully reconstruct the correct secret, even in the presence of a bounded number of malicious participants (beyond the dealer). This requires the protocol to identify and exclude invalid shares during the reconstruction phase, often using error-correcting codes or by having participants provide proofs of share validity.

In classical secret sharing, the dealer must be fully trusted. VSS fundamentally changes this trust model. The dealer can be an untrusted entity. The protocol ensures that if the dealer acts maliciously, they will be detected by the honest participants during the verification phase, and the protocol will abort before any corrupted state is used. This is critical for decentralized systems.

VSS protocols typically operate in two distinct phases:

• Distribution Phase: The dealer splits the secret, sends shares to participants, and broadcasts cryptographic commitments to the polynomial coefficients.
• Verification Phase: Each participant verifies their share against the public commitments. If verification fails, they broadcast a complaint. A sufficient number of complaints proves dealer malfeasance. This structure cleanly separates share issuance from validation.

In federated learning's Secure Aggregation, VSS is used as a sub-protocol within schemes like the Bonawitz Protocol. Clients use VSS to distribute secret keys for pairwise masking. This allows the server to compute the sum of masked model updates while ensuring that if a client drops out, their secret can be reconstructed by other clients to remove their mask, guaranteeing correctness despite failures.

The foundational threshold scheme upon which VSS is built. A secret (e.g., a private key or model update) is encoded into a polynomial of degree t. Shares are points on this polynomial. Any t+1 shares can reconstruct the secret via Lagrange interpolation, but any t or fewer shares reveal zero information. VSS adds a verification layer on top of this basic splitting mechanism.

The broader cryptographic framework for collaborative computation on private data. VSS is a core building block within MPC protocols. In federated learning, secure aggregation can be implemented as an MPC protocol where each client's update is a private input, and the sum is the computed function. VSS ensures that the shares of these inputs are consistently distributed at the protocol's outset.

A class of algorithms designed to tolerate malicious clients in federated learning. While VSS verifies the dealer, Byzantine robustness focuses on the clients' contributions. These methods often use statistical techniques (like coordinate-wise median or trimmed mean) to filter out adversarial updates. VSS can be combined with such schemes to ensure the integrity of the secret-sharing phase before robust aggregation occurs.

A cryptographic method where one party (the prover) can prove a statement's truth to another (the verifier) without revealing any information beyond the statement's validity. In advanced VSS schemes, ZKPs can be used by the dealer to prove that the distributed shares are consistent and valid according to the protocol's rules, without revealing the secret or the polynomial coefficients, providing even stronger guarantees.

A simpler secret-sharing scheme where a secret value s is split into shares that sum to s. For example, s = s1 + s2 + s3. It's often used in efficient secure aggregation protocols like the Bonawitz Protocol, where client updates are masked with additive shares of zero. VSS is more general and robust, providing verifiability and a threshold structure, whereas additive sharing typically requires all shares to reconstruct.

A hardware-based security alternative to cryptographic protocols like VSS. A TEE (e.g., Intel SGX) creates an isolated, encrypted enclave on a processor. Code and data inside are protected from the host OS. In federated learning, clients could send encrypted updates to a TEE on the aggregation server, which decrypts and sums them securely. VSS provides a cryptographic, hardware-independent method to achieve similar trust guarantees for the distribution phase.