Homomorphic Encryption

Overview

Homomorphic encryption (HE) allows computation on encrypted data without decryption. Given Enc(m_1) and Enc(m_2), one can compute Enc(f(m_1, m_2)) for some function f without learning m_1 or m_2. This enables outsourced computation on sensitive data with provable privacy.

Partially Homomorphic Encryption (PHE)

PHE schemes support a single operation (addition or multiplication) on ciphertexts.

RSA (Multiplicative)

For RSA encryption Enc(m) = m^e mod N: Enc(m_1) * Enc(m_2) = (m_1 * m_2)^e mod N = Enc(m_1 * m_2)

Textbook RSA is multiplicatively homomorphic. This property is actually a vulnerability (malleability) in standard encryption settings, which is why RSA-OAEP adds randomized padding.

Paillier (Additive)

Based on the Decisional Composite Residuosity (DCR) assumption. For N = pq:

• Public key: N, g (where g has order N in Z*_{N^2})
• Enc(m, r) = g^m * r^N mod N^2

Homomorphic addition: Enc(m_1) * Enc(m_2) = Enc(m_1 + m_2 mod N)

Scalar multiplication: Enc(m)^k = Enc(k*m mod N)

Paillier is IND-CPA secure under DCR. Widely used in electronic voting (tallying encrypted votes), private set intersection protocols, and federated learning (aggregating encrypted gradients).

Other PHE Schemes

• ElGamal: Multiplicatively homomorphic. (g^r, m*h^r) for h = g^x.
• Exponential ElGamal: Additively homomorphic by encoding messages in the exponent: Enc(m) = (g^r, g^m * h^r). Decryption requires solving discrete log (feasible only for small m).
• Goldwasser-Micali: XOR-homomorphic (additive in Z_2). Based on quadratic residuosity.

Somewhat Homomorphic Encryption (SHE)

SHE supports both addition and multiplication, but only for a limited number of operations. Each ciphertext carries noise that grows with operations -- especially multiplication, which roughly squares the noise. When noise exceeds a threshold, decryption fails.

A leveled HE scheme supports circuits of a predetermined depth L by setting parameters large enough to accommodate L levels of multiplicative noise growth.

Fully Homomorphic Encryption (FHE)

FHE supports arbitrary computation (any Boolean circuit or arithmetic circuit of unbounded depth) on encrypted data.

Gentry's Blueprint (2009)

Craig Gentry's breakthrough established the first FHE scheme:

1. Construct SHE: Build a scheme supporting limited depth
2. Squashing: Modify decryption circuit to be expressible within the scheme's homomorphic capacity
3. Bootstrapping: Homomorphically evaluate the decryption circuit on the ciphertext to refresh (reduce) noise

Bootstrapping: The key insight. Given ciphertext c with high noise encrypting m under key sk:

1. Encrypt the secret key: {Enc(sk_i)} (bootstrapping key)
2. Homomorphically decrypt: compute Enc(Dec(c)) = Enc(m) using the encrypted secret key
3. Result: fresh ciphertext with low noise

Bootstrapping requires circular security: the scheme must remain secure even when the secret key is encrypted under itself. This assumption is not provable from standard assumptions but is widely believed.

BGV (Brakerij-Gentry-Vaikuntanathan)

Leveled FHE based on the Ring-LWE problem.

Structure: Ciphertexts are vectors over polynomial rings R_q = Z_q[x]/(x^n + 1). Plaintext space: R_t for small modulus t.

Key techniques:

• Modulus switching: Reduce ciphertext modulus q -> q' to manage noise growth. Effectively divides the noise by q/q', enabling deeper circuits without bootstrapping (leveled mode).
• Key switching: Transform a ciphertext under one key to another. Essential after multiplication (which doubles the ciphertext dimension).
• Batching (SIMD): Pack n/2 plaintexts into one ciphertext using the CRT decomposition of R_t. Operations apply element-wise to all slots simultaneously. Rotation operations permute slots.

Noise management: Addition increases noise additively; multiplication increases multiplicatively. Modulus chain q_0 > q_1 > ... > q_L allows L multiplication levels.

BFV (Brakerij/Fan-Vercauteren)

Similar to BGV but uses scale-invariant noise management. Plaintexts encoded as m + t*e (noise in low-order bits rather than high-order). Slightly simpler to implement; performance comparable to BGV.

Difference from BGV: BFV uses a fixed modulus and manages noise through the encoding scheme, while BGV switches moduli. BFV is generally simpler but BGV can be more efficient for deep circuits.

CKKS (Cheon-Kim-Kim-Song)

FHE for approximate arithmetic on real/complex numbers.

Key innovation: Treats encryption noise as part of the computation, encoding real numbers as m + e where e is the noise/error. Plaintext precision degrades gracefully through computation.

Encoding: A vector of real/complex values is encoded via inverse canonical embedding into a polynomial. Supports SIMD operations on n/2 complex (or n real) values simultaneously.

Operations:

• Addition: Standard coefficient-wise
• Multiplication: Polynomial multiplication + rescaling (divide by scale factor to maintain fixed-point precision)
• Rescaling: After multiplication, divide by the scale Delta to keep numbers manageable. Consumes one level of the modulus chain.

Applications: Machine learning inference (neural networks on encrypted data), statistical analysis, genomic computation. CKKS is the go-to scheme for numerical computations.

Bootstrapping in CKKS: Evaluates an approximation to the modular reduction function homomorphically. More complex than BGV/BFV bootstrapping due to approximate nature.

TFHE (Torus FHE)

FHE over the real torus T = R/Z (reals modulo 1).

Key features:

• Gate bootstrapping: Each Boolean gate evaluation includes a bootstrapping step, yielding constant noise regardless of circuit depth. No need for leveled parameter selection.
• Programmable bootstrapping: The bootstrapping procedure can simultaneously apply an arbitrary lookup table function to the plaintext. Enables efficient evaluation of nonlinear functions.
• Speed: Very fast bootstrapping (~10-20 ms per gate on modern hardware). Best for Boolean circuit evaluation and small lookup tables.

Structure: Ciphertexts are TLWE (Torus LWE) samples. Key operations:

• External product with TRGSW ciphertexts (bootstrapping key)
• Blind rotation: homomorphically rotate a test polynomial by the encrypted value
• Key switching and sample extraction

Libraries and Implementations

Microsoft SEAL

C++ library supporting BFV and CKKS. Well-documented, widely used in academia and industry. Includes automatic parameter selection. Does not support bootstrapping natively (leveled only).

OpenFHE (successor to PALISADE/HElib)

C++ library supporting BGV, BFV, CKKS, and TFHE/FHEW. Most comprehensive open-source FHE library. Features:

• Bootstrapping for all supported schemes
• Multi-party HE (threshold FHE)
• Proxy re-encryption
• Hardware acceleration support

Other Libraries

• HElib (IBM): BGV/CKKS with advanced bootstrapping and SIMD
• Lattigo (Tune Insight): Go library for BGV, BFV, CKKS with multi-party extensions
• Concrete (Zama): Rust/Python library for TFHE, includes a compiler from Python to FHE circuits
• TFHE-rs (Zama): Rust implementation of TFHE with programmable bootstrapping

Performance Characteristics

Typical overheads (2024-era hardware):

| Operation | BFV/BGV | CKKS | TFHE | |-----------|---------|------|------| | Key generation | ~100 ms | ~100 ms | ~1 s | | Encryption | ~1 ms | ~1 ms | ~0.1 ms/bit | | Addition | ~0.01 ms | ~0.01 ms | ~0.01 ms | | Multiplication | ~10-50 ms | ~10-50 ms | N/A (gate-level) | | Bootstrapping | ~1-10 s | ~1-10 s | ~10-20 ms | | Ciphertext size | ~1-100 MB | ~1-100 MB | ~1-10 KB/bit |

The ciphertext expansion factor (ciphertext size / plaintext size) is typically 1000-10000x, though SIMD batching amortizes this across many plaintext values.

Applications

• Private machine learning inference: Client encrypts input, server evaluates trained model on ciphertext, returns encrypted prediction. Client decrypts result. Server learns nothing about input or output.
• Encrypted database queries: Search and aggregate over encrypted records without decryption.
• Genomic privacy: Compute on encrypted genomic data for diagnostics without exposing genetic information.
• Financial analytics: Encrypted portfolio analysis, credit scoring, fraud detection across organizations.
• Secure aggregation: Combine encrypted contributions from multiple parties (e.g., federated learning, surveys).

Current Limitations and Research Directions

• Performance: Still 10^4-10^6x slower than plaintext computation. Hardware acceleration (GPU, FPGA, ASIC) and algorithmic improvements are closing the gap.
• Programmability: Writing FHE applications requires expertise in noise management and parameter selection. FHE compilers (Concrete, EVA, Cingulata) aim to automate this.
• Standardization: HomomorphicEncryption.org consortium works on standards. NIST is evaluating FHE for potential standardization.
• Hybrid approaches: Combine FHE with MPC or TEEs to reduce overhead. Use FHE for the most sensitive operations and MPC for the rest.