Homomorphic Encryption

Core Idea

Homomorphic encryption (HE) allows computation on encrypted data without decrypting it. Partially homomorphic schemes support one operation (RSA: multiplication; Paillier: addition). Fully homomorphic encryption (FHE), first achieved by Gentry (2009), supports arbitrary computations — both addition and multiplication, and therefore any circuit. The key technique is bootstrapping: using the scheme to homomorphically evaluate its own decryption circuit, refreshing noisy ciphertexts. Modern FHE schemes (BGV, BFV, CKKS, TFHE) are based on lattice problems (LWE/RLWE) and are ~10,000x slower than plaintext computation, but improving rapidly. Applications include private cloud computation, encrypted machine learning, and private database queries.

Explainer

Homomorphic encryption (HE) is the holy grail of encrypted computation: perform arbitrary computations on encrypted data without ever decrypting it. The cloud sees only ciphertexts, performs operations that correspond to additions and multiplications on the underlying plaintexts, and returns an encrypted result that only the data owner can decrypt. The cloud learns nothing — not the inputs, not the intermediate values, not the output. This enables private cloud computing, encrypted machine learning inference, and secure data analysis without trusting the compute provider.

The distinction between partial and full homomorphism is critical. Partially homomorphic schemes have existed for decades: RSA supports multiplication (E(a) * E(b) = E(ab)), Paillier supports addition (E(a) * E(b) = E(a+b)), and ElGamal supports multiplication. But supporting only one operation limits the computable functions to linear combinations (Paillier) or monomial products (RSA). Fully homomorphic encryption (FHE) supports both addition and multiplication, which is sufficient for any computation (since AND and XOR form a complete Boolean basis, and these correspond to multiplication and addition modulo 2).

Craig Gentry achieved the first FHE construction in 2009, solving a problem open since Rivest, Adleman, and Dertouzos posed it in 1978. The central challenge is noise growth: lattice-based ciphertexts carry a small error term that grows with each operation. Addition increases noise linearly, multiplication quadratically. After enough operations, the noise exceeds the decryption threshold and the ciphertext becomes garbled. Gentry's breakthrough was bootstrapping: homomorphically evaluating the scheme's own decryption circuit to "refresh" a noisy ciphertext into a fresh one with reduced noise. This requires the scheme to be powerful enough to compute its own decryption (a somewhat circular requirement that Gentry resolved using a technique called squashing). Bootstrapping converts a leveled HE scheme (supporting a fixed number of operations) into a fully homomorphic one (supporting arbitrary computations).

Modern FHE schemes — BGV, BFV, CKKS, and TFHE — are based on the Learning with Errors (LWE) and Ring-LWE problems, providing security believed to resist quantum attacks. BGV and BFV compute exact integer arithmetic (useful for database queries, financial computations). CKKS computes approximate real-number arithmetic (useful for machine learning, where small precision loss is acceptable). TFHE evaluates Boolean circuits gate by gate with fast bootstrapping (useful for arbitrary computations). Performance remains the main barrier: current FHE is roughly 10,000x slower than plaintext computation for optimized applications, with ciphertexts thousands of times larger than plaintexts. But the field is improving rapidly — hardware accelerators, better algorithms, and application-specific optimizations are making practical deployment feasible for specific use cases like encrypted inference, private set intersection, and confidential analytics.