Secret Sharing

The strongest security guarantee in cryptography. An adversary with unlimited computational power learns absolutely nothing about the secret from an unauthorized subset of shares. This is in contrast to computational security, which relies on the hardness of mathematical problems.

• Shannon Entropy: The conditional probability of the secret given the shares remains uniform.
• No assumptions: Security does not depend on P ≠ NP or the difficulty of factoring large integers.
• Example: In Shamir's scheme, any set of fewer than t points reveals zero information about the polynomial's constant term.

A secret is divided into n shares such that any t or more shares can reconstruct the secret, while any t-1 or fewer reveal nothing. This (t, n)-threshold structure eliminates single points of failure and enables flexible governance.

• Availability: The secret survives the loss of up to n - t shares.
• Confidentiality: The secret remains hidden even if up to t - 1 share holders are compromised.
• Use Case: A (3, 5) scheme for a corporate signing key requires any 3 of 5 executives to authorize a transaction.

Shares from two different secrets can be added together locally by each participant to produce a valid share of the sum. This property is the engine behind secure multi-party computation.

• Addition: [a] + [b] = [a + b] where [x] denotes a secret-shared value.
• Scalar Multiplication: c * [a] = [c * a] for any public constant c.
• Multiplication: Requires interaction (e.g., Beaver triples) as it is not a linear operation.
• Impact: Enables Secure Aggregation in federated learning without a trusted third party.

The size of each individual share relative to the original secret. Ideal secret sharing schemes achieve a share size exactly equal to the secret size, minimizing storage and communication overhead.

• Ideal: Shamir's scheme produces shares the same size as the secret.
• Non-Ideal: Some verifiable or robust schemes produce larger shares due to appended proofs or redundancy.
• Trade-off: Compact shares reduce bandwidth in distributed protocols but may lack properties like Verifiability.
• Benchmark: For a 256-bit AES key, each share in an ideal scheme is also 256 bits.

A mechanism to defend against mobile adversaries who can compromise different parties over time. Shares are periodically refreshed without changing the underlying secret, invalidating any shares an attacker may have accumulated.

• Share Refresh: New random polynomials are generated that still encode the same constant term.
• Window of Vulnerability: An attacker must compromise t shares within a single epoch to succeed.
• Application: Critical for long-lived secrets like certificate authority root keys or blockchain validator keys.
• Protocol: Each party generates a random polynomial with a zero constant term and distributes shares to be added to existing shares.

An extension ensuring that a malicious dealer cannot distribute inconsistent shares that prevent reconstruction. Verifiable Secret Sharing (VSS) adds cryptographic commitments so participants can audit the dealer.

• Commitment Scheme: The dealer publishes a public commitment (e.g., a Pedersen commitment) to the polynomial's coefficients.
• Share Validation: Each participant can verify their share against the commitment without revealing it to others.
• Byzantine Fault Tolerance: Essential when parties do not trust each other or the dealer.
• Protocol Example: Feldman's VSS uses homomorphic commitments over a discrete logarithm group.

An enhancement of standard secret sharing where the dealer distributes shares and provides a cryptographic proof that allows participants to verify the consistency and validity of their shares without revealing the secret itself. This defends against a malicious dealer who might distribute inconsistent shares that prevent reconstruction. VSS is critical in adversarial settings like distributed ledgers and secure multiparty computation protocols.

Pre-computed, secret-shared multiplication triples used in secure multi-party computation to enable efficient, non-interactive multiplication of secretly shared values. Each triple consists of three values (a, b, c) where c = a * b, with each value itself secret-shared among parties. During an MPC protocol, parties consume these triples to multiply shared inputs without expensive cryptographic operations, dramatically improving performance.

A class of protocols that allows a central server to compute the sum of model updates from multiple clients in federated learning without inspecting any individual contribution. Secret sharing underpins many secure aggregation implementations: each client secret-shares its update among peers, who collaboratively sum the shares. The server receives only the aggregate, ensuring that individual training data cannot be reverse-engineered from gradient updates.

A scheme where shares are periodically refreshed without changing the underlying secret. Participants generate new random polynomials that encode the same secret and distribute new shares, rendering any old shares that an adversary may have slowly accumulated useless. This counters mobile adversaries—attackers who can compromise different parties over time but never exceed the threshold simultaneously.