Homomorphic Encryption (HE)

The defining characteristic of HE is the homomorphism between plaintext and ciphertext spaces. For an encryption function E and operation ⊙:

• Additive Homomorphism: E(a) ⊕ E(b) = E(a + b)
• Multiplicative Homomorphism: E(a) ⊗ E(b) = E(a × b)

This property allows arbitrary circuits to be evaluated on encrypted data without ever decrypting the inputs. The scheme's structure ensures that operations on ciphertexts map directly to operations on the underlying plaintexts.

HE schemes are categorized by the complexity of computations they support:

• Partially Homomorphic Encryption (PHE): Supports only one operation type (addition or multiplication) an unlimited number of times. Examples include RSA (multiplicative) and Paillier (additive).
• Somewhat Homomorphic Encryption (SHE): Supports both addition and multiplication but only up to a limited circuit depth before noise overwhelms the ciphertext.
• Leveled Fully Homomorphic Encryption (Leveled FHE): Supports arbitrary circuits up to a pre-determined multiplicative depth, using techniques like modulus switching.
• Fully Homomorphic Encryption (FHE): Supports arbitrary computation of unbounded depth, typically achieved through bootstrapping—homomorphically evaluating the decryption circuit to refresh ciphertext noise.

All practical HE schemes rely on Learning With Errors (LWE) or Ring-LWE hardness assumptions, embedding a small noise term during encryption for security.

• Noise Growth: Each homomorphic operation, especially multiplication, causes the noise to grow. If noise exceeds a threshold, decryption fails.
• Bootstrapping: Introduced by Gentry (2009), this technique evaluates the decryption circuit homomorphically, producing a fresh ciphertext encrypting the same plaintext with reduced noise. This enables unbounded computation.
• Modulus Switching: A lighter-weight technique that scales down the ciphertext modulus to control noise growth without full bootstrapping, used in schemes like BGV and BFV.

HE introduces significant computational and storage overhead compared to plaintext computation:

• Ciphertext Expansion: Ciphertexts can be 10,000x to 1,000,000x larger than the plaintext they encrypt.
• Performance Slowdown: Operations on encrypted data are typically 10^4 to 10^6 times slower than equivalent plaintext operations.
• Hardware Acceleration: Modern implementations leverage FPGAs, GPUs, and specialized ASICs to reduce latency. Libraries like Microsoft SEAL, IBM HElayers, and OpenFHE provide optimized routines.
• Batching: Techniques like SIMD packing encode multiple plaintext values into a single ciphertext, enabling parallel computation and amortizing overhead.

HE provides a unique trust model distinct from other privacy technologies:

• Data-in-Use Protection: Unlike TLS (data in transit) or disk encryption (data at rest), HE protects data during active computation.
• No Trusted Third Party: The data owner retains sole control of the decryption key. The compute party never sees plaintext inputs, intermediate values, or outputs.
• Indistinguishability Under Chosen-Plaintext Attack (IND-CPA): Standard HE schemes provide semantic security—an adversary cannot distinguish between encryptions of two known plaintexts.
• Post-Quantum Security: Lattice-based HE schemes are believed to be resistant to attacks by quantum computers, unlike RSA and elliptic curve cryptography.

HE is often compared to complementary privacy-preserving techniques:

• Secure Multi-Party Computation (SMPC): Distributes trust across multiple non-colluding parties. SMPC has lower computational overhead but higher communication costs. HE requires no interaction during computation.
• Trusted Execution Environments (TEEs): Hardware-based isolation (e.g., Intel SGX, AMD SEV) offers near-native performance but requires trust in the hardware vendor and is vulnerable to side-channel attacks.
• Differential Privacy (DP): Adds statistical noise to outputs, protecting individual records but degrading accuracy. HE provides exact computation on encrypted data without accuracy loss.
• Federated Learning: Keeps data local but shares model updates. HE can encrypt these updates for secure aggregation, combining the benefits of both approaches.

Enables a client to send an encrypted query to a cloud-hosted machine learning model and receive an encrypted prediction without the cloud provider ever seeing the raw input or the result.

• Fully Homomorphic Encryption (FHE) allows the model to compute linear layers and approximate activation functions directly on ciphertext.
• The model owner retains intellectual property protection for their weights, as the server never decrypts the model.
• Latency remains the primary engineering constraint, with current schemes adding several orders of magnitude of computational overhead compared to plaintext inference.

Aggregates model updates from multiple data owners without exposing individual contributions. HE ensures the central aggregation server computes the weighted average of encrypted gradients.

• Secure Aggregation via HE prevents the server from inspecting any single client's gradient, mitigating gradient leakage attacks.
• Combined with Differential Privacy, this provides a dual-layer defense: DP bounds what can be inferred from the final model, while HE protects data in transit during computation.
• Critical for healthcare consortia and financial fraud detection networks where data cannot be pooled centrally.

Allows a client to perform SQL-like operations on an encrypted database hosted by an untrusted third party without revealing the query or the results.

• Partially Homomorphic Encryption (PHE) schemes like Paillier support additive operations, enabling encrypted SUM and COUNT queries.
• Somewhat Homomorphic Encryption (SHE) supports both addition and multiplication up to a bounded depth, sufficient for many analytical workloads.
• This architecture is foundational for secure cloud data warehousing where the database administrator has no access to plaintext records.

Enables multiple research institutions to compute statistical associations across their combined genomic datasets without revealing individual patient variants.

• Each institution encrypts its allele frequency data under a shared public key and transmits ciphertexts to a central compute node.
• The node performs genome-wide association studies (GWAS) using HE operations, returning only encrypted aggregate statistics.
• A threshold decryption protocol ensures no single party can unilaterally decrypt the results, enforcing collaborative governance.

Allows a user to discover which of their contacts are registered on a messaging platform without revealing their entire address book to the server.

• The client encrypts their contact list using HE and sends it to the server.
• The server computes the intersection of the encrypted list with its user database homomorphically, returning only the encrypted matches.
• This protocol eliminates the privacy risk of bulk contact upload, a known attack vector in social applications.

Enables competing financial institutions to jointly train anti-money laundering (AML) models on their combined transaction data without exposing customer records.

• Banks encrypt transaction features under a consortium-wide HE scheme and submit ciphertexts to a shared detection model.
• The model computes risk scores on encrypted data, flagging suspicious patterns that span multiple institutions—patterns invisible to any single bank.
• Satisfies data sovereignty requirements by ensuring raw data never crosses jurisdictional boundaries in plaintext form.