Homomorphic Encryption

Supports unlimited operations of a single type—either addition or multiplication—on ciphertexts.

• Additive PHE: Allows encrypted addition. Example: Paillier cryptosystem.
• Multiplicative PHE: Allows encrypted multiplication. Example: RSA (unpadded) or ElGamal.
• Use Case: Secure e-voting where only tallying (addition) is required without decrypting individual votes.

Supports limited operations of both addition and multiplication, but only up to a certain circuit depth before noise corrupts the ciphertext.

• Noise Growth: Each operation increases inherent noise; exceeding a threshold makes decryption impossible.
• Efficiency: More computationally efficient than fully homomorphic schemes for shallow circuits.
• Example: Early lattice-based schemes like BGN (Boneh-Goh-Nissim) support arbitrary additions but only one multiplication.

Supports unlimited computations of arbitrary complexity on encrypted data. The holy grail of encrypted computation.

• Bootstrapping: A technique introduced by Gentry (2009) that recursively refreshes ciphertext noise, enabling unbounded depth.
• Schemes: Modern FHE includes BGV, BFV (integer arithmetic), and CKKS (approximate real-number arithmetic).
• Performance: Historically slow, but hardware acceleration and algorithmic optimizations have reduced overhead to near-real-time for specific tasks.

A practical variant of FHE that supports computation up to a pre-determined multiplicative depth without bootstrapping.

• Parameter Selection: The encryption parameters are chosen based on the known circuit depth beforehand.
• Efficiency Gain: Avoids the massive computational cost of bootstrapping when the function is known in advance.
• Application: Ideal for private inference in neural networks where the layer depth is fixed.

Modern HE schemes base their security on hard mathematical problems in lattice cryptography, specifically the Ring Learning With Errors (RLWE) problem.

• Quantum Resistance: Lattice problems are believed to be hard for both classical and quantum computers.
• Noise Addition: Security relies on adding small, random noise to ciphertexts, making them indistinguishable from random.
• Standardization: NIST is actively standardizing lattice-based algorithms for post-quantum cryptography.

Techniques that dramatically improve throughput by encrypting a vector of plaintexts into a single ciphertext, enabling Single Instruction, Multiple Data (SIMD) operations.

• Packing: Maps a vector of values to a single ciphertext via the Chinese Remainder Theorem (CRT).
• Parallelism: A single homomorphic addition or multiplication operates on all packed slots simultaneously.
• Amortization: Reduces the per-operation cost to a fraction of the cost of operating on scalar ciphertexts.

The primary application of HE in federated learning is secure aggregation. Clients encrypt their local model updates using a public key before transmission. The central server performs homomorphic addition on the encrypted vectors to compute a global update. The server never possesses the decryption key, ensuring that individual client contributions remain confidential even if the server is compromised. This directly mitigates gradient leakage and model inversion attacks.

PHE schemes, such as the Paillier cryptosystem, support only one type of operation (addition or multiplication) an unlimited number of times. In federated learning, the FedAvg algorithm requires only weighted addition of model updates, making additive PHE a computationally efficient choice. PHE is often preferred over Fully Homomorphic Encryption (FHE) for production systems due to its lower computational overhead and ciphertext expansion.

FHE enables arbitrary computations on encrypted data, supporting both addition and multiplication. While this allows for more complex server-side logic beyond simple averaging, current FHE schemes like CKKS and TFHE introduce significant latency. In federated learning, FHE is used when the aggregation protocol requires non-linear operations or when the model architecture demands encrypted inference on the server.

To prevent a single point of failure, HE in federated learning is often combined with threshold cryptography. The private decryption key is split into shares distributed among multiple non-colluding parties. Decryption of the final aggregated model requires a quorum of these parties to cooperate. This ensures that no single entity can unilaterally decrypt individual client updates, enforcing a robust Byzantine Fault Tolerance posture.

HE introduces substantial computational cost and ciphertext expansion. To make it practical, systems employ optimizations like:

• Packing: Batching multiple plaintext values into a single ciphertext via Single Instruction, Multiple Data (SIMD) operations.
• Approximate Arithmetic: Using schemes like CKKS that operate on approximate fixed-point numbers, which aligns well with the noise-tolerant nature of neural network weights.
• Hardware Acceleration: Offloading polynomial multiplication to GPUs or FPGAs.

A common enterprise pattern combines HE with Secure Multi-Party Computation (SMPC) and Differential Privacy (DP). For example, clients might use DP-SGD to add local noise to updates, encrypt the noisy result with HE, and then rely on SMPC protocols for the threshold decryption ceremony. This layered defense provides formal privacy guarantees even if the cryptographic assumptions of one layer are broken.