Homomorphic Encryption (HE)

Supports unlimited operations of a single type—either addition or multiplication, but not both. This limitation makes PHE simple and efficient for specific use cases.

• Additive PHE (e.g., Paillier): Allows encrypted values to be summed. Ideal for tallying encrypted votes or aggregating financial transactions.
• Multiplicative PHE (e.g., ElGamal): Allows encrypted values to be multiplied. Useful for secure key exchange and anonymous credential systems.
• Performance: Extremely fast with low ciphertext expansion, making it practical for high-throughput production systems.
• Healthcare Application: Securely aggregating patient counts across hospitals without revealing individual records.

Supports both addition and multiplication, but only for a limited number of operations. The circuit depth is bounded by the noise budget inherent in the ciphertext.

• Noise Growth: Each homomorphic operation, especially multiplication, increases the noise embedded in the ciphertext. Once noise exceeds a threshold, decryption fails.
• Limited Circuit Depth: Suitable for evaluating low-degree polynomials, such as computing statistical means or training simple linear models on encrypted data.
• Efficiency: More computationally expensive than PHE but significantly faster than Fully Homomorphic Encryption (FHE).
• Use Case: Computing predictive risk scores from encrypted patient vitals where the algorithm is a shallow arithmetic circuit.

Supports arbitrary computation on encrypted data by enabling an unlimited number of both additions and multiplications. This is the 'holy grail' of encrypted computation.

• Bootstrapping: A revolutionary technique introduced by Craig Gentry in 2009 that 'refreshes' the ciphertext noise, allowing for unlimited circuit depth. This is the core mechanism that elevates SHE to FHE.
• Turing Complete: In theory, any computable function can be evaluated homomorphically, enabling general-purpose computation on encrypted data.
• Performance Overhead: Historically 1,000,000x slower than plaintext computation, though modern schemes (CKKS, TFHE) have reduced this to roughly 1,000x for specific workloads.
• Healthcare Application: Training a deep neural network for diagnostic imaging on encrypted patient scans aggregated from multiple hospitals.

A practical variant of FHE that supports arbitrary computation up to a pre-determined multiplicative depth without bootstrapping. This avoids the extreme cost of bootstrapping for circuits of known depth.

• Pre-defined Circuit: The scheme parameters are generated to support exactly the number of multiplications required by the target algorithm, optimizing performance.
• No Bootstrapping: By eliminating the need for noise refresh, leveled schemes like BGV and BFV achieve much higher throughput than bootstrapped FHE.
• Packing and Batching: Leverages Single Instruction, Multiple Data (SIMD) techniques to pack thousands of plaintext values into a single ciphertext, enabling parallel homomorphic computation.
• Use Case: Running a fixed-architecture convolutional neural network for inference on encrypted medical images, where the network depth is known at compile time.

Modern FHE is implemented through distinct mathematical schemes, each optimized for different data types and computation patterns.

• BGV/BFV (Integer Arithmetic): Operate on integers modulo a plaintext modulus. Ideal for exact arithmetic, such as counting, sums, and database queries. BFV is often preferred for its simpler noise management.
• CKKS (Approximate Arithmetic): Operates on real and complex numbers with fixed-point approximation. The standard for machine learning inference, enabling encrypted floating-point operations on vectors.
• TFHE (Gate-Level Logic): Optimized for evaluating individual binary gates (AND, XOR) on encrypted bits. Provides the fastest bootstrapping (microseconds per gate), making it ideal for decision trees and lookup tables.
• Scheme Switching: Emerging research focuses on dynamically switching between schemes mid-computation to leverage the strengths of each for different parts of an algorithm.

All practical HE schemes rely on learning with errors (LWE) or ring-LWE problems, embedding a small 'noise' term into the ciphertext for security. Managing this noise is the central engineering challenge.

• Noise Budget: A finite resource consumed by each homomorphic operation. Multiplication grows noise much faster than addition. Exceeding the budget corrupts the plaintext.
• Relinearization: A key-switching technique applied after multiplication to reduce the ciphertext size back to two ring elements, preventing exponential growth.
• Modulus Switching: A noise management technique that scales down the ciphertext modulus to proportionally reduce the absolute noise magnitude, effectively resetting the noise budget without bootstrapping.
• Bootstrapping: The ultimate noise reset mechanism that homomorphically evaluates the decryption circuit itself, producing a 'fresh' ciphertext with a full noise budget. This is the most computationally expensive operation in FHE.