Additive Secret Sharing

Additive secret sharing provides information-theoretic security, meaning an adversary with unlimited computational power cannot learn anything about the secret from an incomplete set of shares. This is stronger than computational security, which relies on the assumed hardness of mathematical problems. The security guarantee holds as long as at least one share remains undisclosed.

• Formal Guarantee: Any proper subset of shares reveals zero information about the original secret.
• Contrast: Unlike encryption schemes (e.g., Paillier), its security does not depend on unproven computational assumptions.

Shares can be locally manipulated to perform computations on the underlying secret. This is the core property enabling Secure Multi-Party Computation (MPC) and Secure Aggregation in federated learning.

• Local Operations: If each party holds a share of secret x and a share of secret y, they can locally add their shares to obtain a valid share of (x + y).
• Scalar Multiplication: Multiplying a share by a public scalar c yields a share of (c * x).
• Application: In federated learning, clients can locally add a secret mask (share) to their model update. When all masked updates are summed by the server, the masks cancel out, revealing only the aggregate model update.

The original secret is reconstructed by summing all shares. This differs from threshold schemes like Shamir's Secret Sharing, where only a subset of shares (meeting a threshold) is needed.

• Requirement: All n shares (S₁, S₂, ..., Sₙ) are required where Secret = S₁ + S₂ + ... + Sₙ (mod M).
• Implication: It is highly sensitive to participant dropout in MPC protocols. If one party disappears, the secret is permanently lost. Practical protocols like the Bonawitz Protocol for secure aggregation build robustness to dropouts using pairwise masking techniques.

The scheme is exceptionally lightweight, making it suitable for performance-critical environments like edge devices.

• Share Generation: Requires only random number generation and modular subtraction.
• Share Size: Each share is the same size as the original secret (e.g., a 32-bit integer secret produces n 32-bit integer shares).
• Reconstruction: Requires only n-1 modular addition operations.
• Contrast with FHE: Fully Homomorphic Encryption (FHE) supports arbitrary computations but incurs massive computational overhead (often 10,000x slowdown). Additive sharing supports only linear operations but is orders of magnitude faster.

It is the core cryptographic primitive behind the Bonawitz Protocol (Practical Secure Aggregation) used in federated learning frameworks like Google's TensorFlow Federated.

• Process:
  1. Each client's model update is secret-shared among all other clients or a central coordinator.
  2. Clients add pairwise masks (derived from shared secrets) to their updates before sending.
  3. The server sums all received masked updates. Due to the linear homomorphism property, the masks cancel out in the sum, revealing only the aggregate update.
• Guarantee: The server learns nothing about any individual client's contribution, only the sum.

The mathematics of additive secret sharing are defined over a finite algebraic structure, typically integers modulo a prime p or modulo 2^k. This ensures the sum of shares wraps around correctly and remains within a defined range.

• Modular Arithmetic: Secret = (Share₁ + Share₂ + ... + Shareₙ) mod M.
• Choice of Modulus M: Critical for correctness. In machine learning, M must be large enough to prevent wrap-around from distorting the sum of model parameters (e.g., a large integer like 2³² or 2⁶⁴).
• Example: For a secret value 7 split modulo 11, possible shares could be 3, 9, and 6, since (3 + 9 + 6) mod 11 = 18 mod 11 = 7.

Beyond model training, Additive Secret Sharing enables multiple organizations to perform joint statistical analyses on their combined datasets without revealing their private inputs. For example, several hospitals can compute the average patient age or the prevalence of a condition across their collective populations.

• Each hospital secretly shares its local sum and count.
• Using Secure Multi-Party Computation (MPC) protocols built on secret sharing, the parties compute the global average.
• No hospital learns another's raw data, only the final, aggregated statistic. This is essential for collaborative research under strict regulations like HIPAA or GDPR.

This technique allows a client to obtain a prediction from a machine learning model without revealing their input data to the model owner, and without the model owner revealing their proprietary model parameters. The client's private data and the server's model weights are each split into secret shares. Computation (the forward pass of the neural network) is performed distributively on these shares by multiple non-colluding servers. The final prediction is reconstructed only for the client. This use case is crucial for confidential AI services in finance or healthcare, where both the query and the model are sensitive assets.

Additive Secret Sharing is not used in isolation but as a fundamental component to construct more complex Privacy-Enhancing Technologies (PETs).

• Multi-Party Computation (MPC): Serves as the basic secret-sharing scheme for generic secure computation circuits.
• Fully Homomorphic Encryption (FHE): Some FHE schemes, like the BFV or CKKS schemes, are conceptually related, performing operations on ciphertexts that correspond to addition on the underlying plaintexts.
• Verifiable Secret Sharing (VSS): Extends the basic scheme, allowing parties to verify that shares are consistent, preventing a malicious dealer from corrupting the protocol.

This modularity makes it a versatile tool in the cryptographic engineer's toolkit.

A key engineering advantage of Additive Secret Sharing in federated settings is its natural robustness to client dropout. In mobile or edge networks, devices frequently go offline. In a well-designed protocol using pairwise masking, each client's secret share is masked with a key shared with another client. If a client drops out, its masking key is never revealed, and its contribution remains protected. However, the masks from participating clients still cancel out in the aggregate sum, allowing the server to compute a correct aggregate from the subset of clients that completed the round. This property is critical for practical deployment at scale.

Additive Secret Sharing is often combined with Differential Privacy (DP) to provide a defense-in-depth privacy posture. In a federated learning pipeline:

1. Each client clips their local update (gradient clipping) to bound its sensitivity.
2. The client adds calibrated noise (e.g., from a Gaussian distribution) to achieve Local Differential Privacy (LDP).
3. This noised update is then protected via Additive Secret Sharing before transmission.

This combination ensures privacy even if the cryptographic protocol is compromised (cryptographic failure) or if the aggregating server is malicious (honest-but-curious adversary), as the data is already noised. The secret sharing protects the noised value from inspection during transmission.