Additive Homomorphic Encryption (AHE)

The core property: Dec(Enc(m₁) ⊗ Enc(m₂)) = m₁ + m₂. There exists an operation ⊗ on ciphertexts that, when applied, produces a new ciphertext decrypting to the sum of the original plaintexts. The server never sees m₁ or m₂, only their encrypted forms and the encrypted sum.

• Example: A server holding Enc(5) and Enc(3) can compute Enc(8) without ever decrypting.
• Mechanism: Typically based on the Decisional Diffie-Hellman assumption in groups where the discrete log is hard.

AHE schemes inherently support scalar multiplication: multiplying a ciphertext by a known plaintext constant k yields an encryption of k * m. This is derived from repeated application of the additive homomorphism.

• Formula: Dec(Enc(m)ᵏ) = k * m
• Use Case: Computing weighted averages in federated learning, where each client's update is scaled by its dataset size before aggregation.
• Limitation: This is multiplication by a known constant, not multiplication of two encrypted values.

AHE schemes must be semantically secure (IND-CPA): an adversary cannot distinguish between encryptions of two chosen plaintexts. This implies probabilistic encryption—encrypting the same message twice produces different ciphertexts.

• Mechanism: Achieved by injecting a random nonce or blinding factor during encryption.
• Critical Implication: Prevents dictionary attacks. An eavesdropper seeing Enc(0) and Enc(1) cannot tell them apart, protecting model update values in transit.

AHE is malleable—a feature, not a bug. An adversary can transform Enc(m) into Enc(m + x) without decryption. This is the intended functionality for secure aggregation.

• Risk: In isolation, malleability enables chosen-ciphertext attacks.
• Mitigation: Secure aggregation protocols combine AHE with zero-knowledge proofs or authenticated encryption on the communication channel to ensure ciphertexts are only manipulated by the legitimate aggregator according to protocol rules.

AHE is a partially homomorphic encryption (PHE) scheme. It supports only one operation (addition) an unlimited number of times.

• AHE (Additive): Unlimited additions. Examples: Paillier, Exponential ElGamal.
• MHE (Multiplicative): Unlimited multiplications. Example: RSA (unpadded).
• FHE (Fully Homomorphic): Supports both additions and multiplications, enabling arbitrary circuits. Examples: CKKS, TFHE. FHE is far more computationally expensive than AHE.
• Trade-off: AHE is lightweight and practical for aggregation; FHE is heavy but enables private inference.

Two primary constructions dominate practical use:

• Paillier Cryptosystem: Based on the Composite Residuosity Class Problem. Provides additive homomorphism over integers modulo n. Ciphertext expansion is 2x the plaintext size.
• Exponential ElGamal: A variant of standard ElGamal where encryption encodes gᵐ instead of m. Homomorphic addition computes g^(m₁+m₂). Decryption requires solving a discrete logarithm, limiting it to small message spaces (e.g., 32-bit values).

Both are quantum-vulnerable; post-quantum AHE based on Learning With Errors (LWE) is an active research area.

The primary use case for AHE in ML. Each client encrypts their local model update (gradient vector) using the server's public key. The server performs homomorphic addition on all ciphertexts to compute the encrypted global sum, then decrypts only the final aggregate. This ensures the server never inspects any individual client's contribution, defending against gradient leakage attacks that can reconstruct private training data from raw updates.

AHE allows two organizations to compute the size of the overlap between their datasets without revealing the actual intersecting elements or any non-matching records. Each party encrypts their set elements, the other party homomorphically computes a polynomial evaluation, and the result reveals only the intersection count. This is critical for healthcare informatics and fraud detection consortia where revealing raw identifiers is prohibited by regulation.

Beyond ML training, AHE enables privacy-safe computation of basic statistics on distributed sensitive data:

• Encrypted Sum: Total revenue across competing business units without exposing individual unit performance.
• Encrypted Average: Compute the mean of patient vitals across hospitals by homomorphically summing encrypted values and dividing the decrypted total by the known count.
• Encrypted Variance: Two-pass protocols using AHE for sums of squares enable private standard deviation calculations.

AHE forms the cryptographic backbone of privacy-preserving voting systems. Each vote is encrypted as a 0 or 1 (or a more complex preference vector) using an additively homomorphic scheme. The tallying authority sums all ciphertexts homomorphically and decrypts only the final total. This guarantees ballot secrecy while enabling public verifiability of the count. Threshold decryption ensures no single authority can decrypt individual votes.

AHE enables a recommendation server to compute user-item preference scores without learning the user's rating history. The user encrypts their rating vector, the server holds the item matrix in plaintext, and performs homomorphic dot products to generate encrypted recommendation scores. Only the user can decrypt the final result. This prevents the service provider from building shadow profiles on user behavior.

AHE can be combined with other techniques for private neural network inference. While fully homomorphic encryption (FHE) is often too slow for entire networks, AHE is efficient for the linear layers (fully connected and convolutional layers where operations are additions and scalar multiplications). The client encrypts their input, the cloud computes the linear transformations homomorphically, and the client decrypts the output. Non-linear activations are handled client-side or via secure multi-party computation.

The most widely implemented partially homomorphic encryption scheme for additive operations. Paillier provides semantic security based on the decisional composite residuosity assumption. Its key property is the homomorphic addition of plaintexts through multiplication of ciphertexts: E(m1) * E(m2) = E(m1 + m2).

• Key sizes: Typically 2048-4096 bits for production security
• Expansion factor: Ciphertext is 2x the modulus size
• Performance: Encryption requires modular exponentiation; decryption uses the Carmichael function
• Common use: Federated learning aggregation where a server sums encrypted model weight updates without decryption

A cryptographic method that splits a secret value into shares distributed among participants. The secret can only be reconstructed when a threshold of shares is combined. In secure aggregation, secret sharing provides dropout resilience—the sum can still be computed even if some clients disconnect.

• Additive secret sharing: Splits a value x into random shares x1 + x2 = x
• Threshold schemes: Require t of n shares for reconstruction
• Information-theoretic security: No computational assumptions required
• Integration with AHE: Shares can be encrypted under AHE for layered protection against collusion

A protocol enabling a central server to compute the sum of model updates from multiple clients without inspecting any individual contribution. SecAgg combines pairwise masking, secret sharing, and key agreement to ensure that individual updates remain hidden while the aggregate is revealed.

• Threat model: Semi-honest server that follows protocol but attempts to learn individual updates
• Dropout handling: Survives up to a configurable fraction of client dropouts per round
• Communication complexity: O(n²) in naive implementations; optimized to O(n log n) with sparse random graphs
• Relationship to AHE: AHE provides an alternative cryptographic path to the same goal—summing without revealing—but with different trust assumptions and computational trade-offs

A technique where each pair of clients agrees on a shared secret mask using Diffie-Hellman key agreement. Client i adds masks for all pairs where i < j and subtracts masks where i > j. When all updates are summed, the masks cancel out exactly, revealing only the aggregate.

• Key exchange: Each pair performs an ephemeral Diffie-Hellman handshake
• Mask generation: Shared secrets are expanded using a Pseudorandom Generator (PRG)
• Dropout recovery: If a client drops, its pairwise masks would corrupt the sum—secret sharing of seeds enables reconstruction
• Synergy with AHE: Pairwise masking provides information-theoretic hiding; AHE provides cryptographic hiding. They can be composed for defense-in-depth

A public-key encryption scheme where the private decryption key is split among multiple parties. A ciphertext can only be decrypted when a threshold number of parties cooperate. This prevents any single entity—including the server—from decrypting individual contributions.

• Key generation: Distributed protocol produces shares of the secret key; no single party ever holds the full key
• Decryption: Each party produces a decryption share; combining t shares reconstructs the plaintext
• Use with AHE: Clients encrypt updates under a threshold public key; the server aggregates ciphertexts homomorphically; a quorum of trustees decrypts only the final sum
• Lattice-based constructions: Threshold variants of Learning With Errors (LWE) schemes provide post-quantum security

The primary threat that AHE and secure aggregation defend against. Gradient leakage attacks analyze shared model updates to reconstruct private training data. An adversary with access to individual gradients can recover pixel-accurate images or verbatim text from training batches.

• Deep Leakage from Gradients (DLG): Iteratively optimizes dummy inputs to match observed gradients
• Inverting Gradients: Recovers high-fidelity images from ResNet and Vision Transformer gradients
• Defense stacking: AHE prevents the server from seeing individual gradients; gradient clipping and differential privacy bound what can leak even if encryption fails
• Provable guarantee: AHE provides cryptographic (not statistical) privacy—the server learns nothing about individual updates beyond what the aggregate reveals