Homomorphic Encryption (HE)

The defining property of HE: performing mathematical operations directly on encrypted data without first decrypting it. When the resulting ciphertext is decrypted, the output matches the result of the same operations applied to the original plaintext. This preserves data confidentiality during active processing by an untrusted third party, such as a cloud server.

HE schemes are categorized by their computational depth:

• Partially Homomorphic Encryption (PHE): Supports only one operation type (e.g., addition or multiplication) an unlimited number of times. RSA is a classic example for multiplication.
• Somewhat Homomorphic Encryption (SHE): Supports both addition and multiplication but only for a limited number of operations before noise corrupts the ciphertext.
• Fully Homomorphic Encryption (FHE): Supports arbitrary computation (both addition and multiplication) an unlimited number of times, typically achieved through a bootstrapping procedure that refreshes the ciphertext noise.

All practical HE schemes rely on adding a small amount of random noise to the plaintext during encryption for security. Each homomorphic operation, especially multiplication, causes this noise to grow. If the noise exceeds a threshold, decryption fails. Bootstrapping is a technique introduced by Gentry that homomorphically evaluates the decryption circuit itself, resetting the noise level to a baseline and enabling unlimited computation, making FHE possible.

Modern, efficient HE schemes (like BGV, BFV, and CKKS) base their security on hard mathematical problems over lattices, most notably the Ring Learning With Errors (RLWE) problem. This is a significant advantage because lattice-based cryptography is currently believed to be resistant to attacks by large-scale quantum computers, making these HE schemes strong candidates for post-quantum cryptography.

To amortize computational cost, many HE schemes support Single Instruction, Multiple Data (SIMD) operations. This technique, often called batching or packing, allows a single ciphertext to encode a vector of hundreds or thousands of plaintext values. A single homomorphic addition or multiplication on two such ciphertexts performs the operation element-wise on all packed values simultaneously, dramatically increasing throughput for parallelizable workloads.

The choice of scheme depends on the application:

• BFV / BGV: Designed for exact integer arithmetic. Ideal for computations requiring precise results, such as financial transactions or private set intersection.
• CKKS: Supports approximate arithmetic on real and complex numbers. It treats noise as part of a least-significant-bit error, making it perfect for machine learning inference and other fixed-point numerical computations where perfect precision is not required.

A restricted form of HE that supports a limited number of operations before the noise in the ciphertext grows too large and decryption fails. SHE is often a stepping stone to FHE.

• Practical use: Sufficient for many ML inference tasks with known, fixed-depth circuits
• Efficiency: Significantly faster than FHE because bootstrapping is not required
• Example: Evaluating a fixed-depth neural network where the number of sequential layers is bounded

Schemes that support only one type of operation (addition or multiplication) an unlimited number of times, but not both.

• Additive PHE: Paillier cryptosystem — allows encrypted addition, used in electronic voting and private aggregation
• Multiplicative PHE: ElGamal and unpadded RSA — allow encrypted multiplication
• Deployment: Much more practical than FHE and already used in production systems for privacy-preserving analytics

A complementary paradigm to HE where multiple parties jointly compute a function over their private inputs without revealing them to each other. HE and MPC are often combined for optimal efficiency.

• Garbled circuits: Yao's protocol for secure two-party computation of Boolean circuits
• Secret sharing: Additive and Shamir sharing as the basis for information-theoretic MPC
• Hybrid models: Use HE for linear operations and MPC for non-linear activations in private ML inference

The mathematical foundation underlying most modern HE schemes. Security is based on the hardness of lattice problems like Learning With Errors (LWE) and its ring variant Ring-LWE.

• Post-quantum security: Lattice problems are believed to be hard for both classical and quantum computers
• Noise-based encryption: Ciphertexts contain a small 'error' term that grows with each homomorphic operation
• NIST standardization: Lattice-based schemes form the core of post-quantum cryptography standards (e.g., CRYSTALS-Kyber)

A hardware-based alternative to HE that provides confidential computing by isolating sensitive computation within a secure enclave. Data is decrypted only inside the CPU and remains encrypted in memory.

• Implementations: Intel SGX, AMD SEV, ARM TrustZone
• Comparison to HE: TEEs offer near-native performance but require trust in the hardware vendor; HE provides mathematical guarantees without hardware trust
• Hybrid architectures: Use TEEs for performance-critical sections and HE for data-in-transit protection