Homomorphic Encryption (HE)

A class of HE schemes that supports unlimited operations of a single type—either addition or multiplication, but not both—on ciphertexts.

• RSA: Unpadded RSA is multiplicatively homomorphic.
• Paillier: Supports additive homomorphism; widely used in secure aggregation for federated learning.
• ElGamal: Multiplicatively homomorphic; forms the basis for many voting protocols.

PHE is computationally lightweight and practical for production systems that only need to compute sums or products over encrypted data.

A scheme that supports both addition and multiplication but only for circuits of limited multiplicative depth. Each multiplication increases the noise embedded in the ciphertext.

• The noise budget is consumed with each operation.
• Once the noise exceeds a threshold, decryption fails.
• SHE is the precursor to Fully Homomorphic Encryption (FHE).

SHE is useful for evaluating shallow arithmetic circuits, such as computing averages or low-degree polynomial functions over encrypted data.

The holy grail of encrypted computation: FHE supports arbitrary computation (unlimited additions and multiplications) on ciphertexts. This is enabled by a critical procedure called bootstrapping.

• Bootstrapping: Homomorphically evaluating the decryption circuit itself to reset the noise level, enabling unbounded depth.
• Gentry's Blueprint: Craig Gentry's 2009 lattice-based construction proved FHE was theoretically possible.
• Modern Schemes: CKKS, BGV, BFV, and TFHE are the dominant fourth-generation schemes.

FHE enables a hospital to run a proprietary diagnostic AI model on encrypted patient data without ever decrypting it.

A practical variant of FHE that can evaluate circuits up to a pre-determined multiplicative depth without bootstrapping. The parameters are chosen at setup to accommodate a specific computation.

• Eliminates the massive computational cost of bootstrapping.
• The scheme parameters grow with the circuit depth.
• If the depth is exceeded, decryption fails.

Leveled FHE is the standard for production deployments where the algorithm's complexity is known in advance, such as evaluating a fixed neural network architecture.

All modern practical HE schemes derive their security from hard problems on mathematical lattices, specifically the Ring Learning With Errors (RLWE) problem.

• RLWE: Distinguishing noisy linear equations over polynomial rings is computationally infeasible, even for quantum computers.
• Post-Quantum Secure: Lattice-based cryptography is a leading candidate for NIST's post-quantum standardization.
• Worst-Case to Average-Case Reduction: Breaking RLWE is provably as hard as solving the shortest vector problem in ideal lattices.

This foundation ensures that HE-encrypted medical data remains secure against both classical and future quantum adversaries.

HE ciphertexts contain a small amount of random noise that ensures security. Each homomorphic operation—especially multiplication—causes this noise to grow.

• Additive Noise Growth: Slow and linear; many additions are cheap.
• Multiplicative Noise Growth: Exponential; the primary constraint on circuit depth.
• Noise Budget: A finite resource that must be tracked; exceeding it corrupts the plaintext.

Techniques like modulus switching and scale-invariant schemes manage noise without bootstrapping, optimizing performance for federated learning aggregation.

A cryptographic protocol that distributes computation across multiple parties where each holds a private input. No single party can see the others' data, yet they jointly compute a function. Unlike HE, which operates on encrypted data at rest, SMPC relies on interactive communication between parties. Secret sharing is the foundational primitive, splitting data into meaningless shares. Often combined with HE in hybrid models for federated learning.

The most powerful and computationally intensive variant of HE. FHE supports unlimited additions and multiplications on ciphertexts, enabling arbitrary computation on encrypted data. This is achieved through a technique called bootstrapping, which refreshes the ciphertext noise. Current FHE schemes (CKKS, BGV, TFHE) are orders of magnitude slower than plaintext, making them suitable for low-latency, high-value computations like private inference.

A restricted form of HE that supports only one type of operation—either addition or multiplication—but not both. RSA and ElGamal are multiplicatively homomorphic, while Paillier is additively homomorphic. PHE is orders of magnitude faster than FHE and is practical for specific use cases like encrypted vote tallying (Paillier) or private set intersection. It lacks the expressiveness for general computation.

An intermediate scheme that supports a limited number of both additions and multiplications. SHE can evaluate low-degree polynomials before the noise in the ciphertext grows too large and decryption fails. It is more efficient than FHE because it avoids the costly bootstrapping step. SHE is ideal for applications with a known, shallow computation depth, such as evaluating specific statistical models on encrypted data.

The mathematical foundation underlying all modern practical HE schemes. It relies on the hardness of computational problems on mathematical lattices, such as the Learning With Errors (LWE) and Ring-LWE problems. These problems are believed to be resistant to attacks by quantum computers, making lattice-based HE a post-quantum cryptographic primitive. The noise added in HE ciphertexts is a direct instantiation of the LWE error distribution.

A hardware-based alternative to HE that provides a secure enclave within a CPU. Data is decrypted and processed in plaintext inside a hardware-isolated black box, invisible to the host OS. Intel SGX and AMD SEV are examples. TEEs offer native performance but require hardware root of trust and are vulnerable to side-channel attacks. HE provides a purely mathematical, software-based trust model without hardware dependency.