Homomorphic Encryption

Supports unlimited operations of a single type on encrypted data—either addition or multiplication, but not both.

• RSA Encryption: Multiplicatively homomorphic; ciphertext multiplication yields the product of plaintexts.
• Paillier Cryptosystem: Additively homomorphic; allows encrypted values to be summed without decryption.
• Use Case: Secure e-voting where encrypted tallies are aggregated without revealing individual votes.

PHE schemes are computationally efficient and widely deployed in production systems requiring specific arithmetic operations on ciphertexts.

Permits both addition and multiplication on ciphertexts, but only for circuits of limited depth.

• Limitation: Each operation introduces noise; after a threshold number of multiplications, decryption fails.
• BGN Cryptosystem: Supports arbitrary additions and a single multiplication.
• Trade-off: More flexible than PHE but cannot evaluate arbitrarily complex functions.

SHE serves as a stepping stone to fully homomorphic schemes and is suitable for applications with bounded computational complexity, such as statistical averages.

Enables arbitrary computation on encrypted data with unlimited additions and multiplications, theoretically allowing any function to be evaluated without decryption.

• Gentry's Blueprint: First FHE construction in 2009 using ideal lattices and a bootstrapping technique to refresh ciphertext noise.
• Bootstrapping: Recursively encrypts a ciphertext and evaluates the decryption circuit homomorphically, resetting noise levels.
• Modern Schemes: CKKS (approximate arithmetic for real numbers), BGV/BFV (exact integer arithmetic), and TFHE (fast bootstrapping for binary gates).

FHE remains computationally intensive but is rapidly approaching practical viability for privacy-preserving machine learning inference.

A practical variant of FHE that supports bounded-depth circuits without bootstrapping, parameterized by a multiplicative depth L chosen at key generation.

• Efficiency: Avoids the computational overhead of bootstrapping by pre-determining circuit depth.
• BGV and BFV: Operate on integer plaintexts with modulus switching to manage noise growth.
• CKKS: Handles approximate fixed-point arithmetic, ideal for neural network inference where exact precision is unnecessary.

Leveled schemes are the dominant approach for production FHE deployments, as bootstrapping remains a significant performance bottleneck.

All lattice-based HE schemes accumulate noise with each homomorphic operation, threatening decryption correctness.

• Noise Budget: A finite resource consumed by operations; multiplication grows noise exponentially faster than addition.
• Modulus Switching: Scales ciphertext to a smaller modulus, reducing noise proportionally without decryption.
• Key Switching: Converts a ciphertext under one key to another, enabling multi-key computation and relinearization after multiplication.
• Bootstrapping: The ultimate noise reset mechanism, homomorphically evaluating the decryption circuit to produce a fresh ciphertext.

Effective noise management is the central engineering challenge in designing practical HE applications.

HE combines with Secure Multi-Party Computation (MPC) protocols to enable collaborative computation where inputs remain encrypted and distributed.

• Threshold FHE: Distributes decryption key shares among parties, requiring a quorum to decrypt results.
• Hybrid Models: Use MPC for non-linear operations (comparisons, activation functions) and HE for linear algebra, optimizing for each primitive's strengths.
• Use Case: Federated learning where multiple hospitals jointly train a diagnostic model on encrypted patient data without revealing individual records.

This integration addresses HE's limitation in evaluating non-polynomial functions, enabling end-to-end privacy-preserving machine learning pipelines.