Homomorphic Encryption

The defining property of homomorphic encryption is the ability to perform mathematical operations—addition, multiplication, or both—directly on encrypted data. The result, when decrypted, matches the output of performing those same operations on the original plaintext. This means a cloud server can train a diagnostic model on encrypted patient records without ever seeing the underlying Protected Health Information (PHI).

• Partially Homomorphic Encryption (PHE): Supports only one operation type (e.g., addition-only with Paillier, multiplication-only with RSA)
• Somewhat Homomorphic Encryption (SHE): Supports limited sequences of both operations before noise accumulation corrupts the ciphertext
• Fully Homomorphic Encryption (FHE): Supports arbitrary computation on encrypted data with no theoretical limits, first proven possible by Craig Gentry in 2009

Modern homomorphic encryption schemes derive their security from hard mathematical problems on ideal lattices—specifically the Ring Learning With Errors (RLWE) problem. This involves adding carefully calibrated noise to linear equations over polynomial rings, making it computationally infeasible for an adversary to recover the plaintext even with quantum computing resources. The noise grows with each homomorphic operation, which is why bootstrapping—a technique that refreshes ciphertexts by homomorphically evaluating the decryption circuit—is essential for achieving fully homomorphic encryption. This post-quantum security property makes FHE a future-proof choice for long-lived clinical data.

Bootstrapping is the cryptographic technique that transforms a somewhat homomorphic encryption scheme into a fully homomorphic one. As homomorphic operations accumulate, the embedded noise grows until decryption becomes unreliable. Bootstrapping homomorphically evaluates the decryption circuit itself on the encrypted data, producing a fresh ciphertext encrypting the same plaintext but with reset noise levels. This process is computationally expensive—often dominating FHE runtime—but recent advances like programmable bootstrapping in schemes such as TFHE allow simultaneous noise reduction and function evaluation, dramatically improving practical efficiency for federated learning workloads.

Four major FHE scheme families dominate practical implementations, each optimized for different workloads:

• BGV/BFV: Integer arithmetic schemes ideal for exact computations like encrypted database queries and counting statistics in clinical trials
• CKKS: Approximate arithmetic scheme supporting encrypted real-number operations, making it the preferred choice for neural network training where floating-point precision is acceptable
• TFHE: Gate-level scheme optimized for ultra-fast bootstrapping of individual bits, excelling at decision trees and non-linear activation functions

Selecting the appropriate scheme depends on the precision requirements and computational graph of the federated model being trained.

To amortize the substantial computational overhead of homomorphic encryption, modern schemes leverage Single Instruction Multiple Data (SIMD) packing. This technique encodes multiple plaintext values—often thousands—into a single ciphertext, allowing a single homomorphic operation to process all values simultaneously. In the context of federated learning, this means an entire vector of model weights or a batch of encrypted patient features can be processed in parallel. The CKKS scheme is particularly well-suited for this, enabling efficient encrypted matrix multiplications that form the backbone of neural network training on ciphertexts.

Homomorphic encryption introduces significant computational overhead compared to plaintext operations—typically 4-6 orders of magnitude slower. However, hardware acceleration and algorithmic optimizations are rapidly closing this gap. Key advances include:

• GPU/FPGA acceleration: Parallelizing polynomial arithmetic on specialized hardware
• Ciphertext maintenance operations: Key switching, modulus switching, and relinearization to manage noise growth without full bootstrapping
• Packing strategies: Optimizing SIMD slot utilization to maximize throughput per ciphertext operation
• Hybrid approaches: Combining FHE with secure multi-party computation (SMPC) for operations that are inefficient under pure FHE