What Is Homomorphic Encryption?

Homomorphic Encryption (HE) allows computations to be performed directly on encrypted data, producing an encrypted result that, when decrypted, equals the result of performing the same operations on the plaintext. "Compute on ciphertext without decrypting."

Imagine placing numbers inside a locked box with special gloves built into the sides. You can manipulate the numbers through the gloves (add, multiply) without ever opening the box. Only the key owner can see the result when they unlock the box.

Partially Homomorphic Encryption supports one operation type unboundedly: RSA (textbook) is multiplicatively homomorphic: Enc(m1)*Enc(m2) = Enc(m1*m2). Paillier is additively homomorphic: Enc(m1)*Enc(m2) = Enc(m1+m2). Used in e-voting, private information retrieval.

Somewhat Homomorphic Encryption supports both addition and multiplication, but only for a limited number of multiplications (circuit depth). Noise grows with each multiplication; after a threshold, decryption fails. First construction by Gentry (2009).

Fully Homomorphic Encryption supports arbitrary computations (any Boolean/arithmetic circuit) on encrypted data. Gentry (2009) showed FHE is possible via "bootstrapping" — homomorphically evaluating the decryption circuit to refresh the ciphertext and reset noise.

Most HE schemes are lattice-based (BGV, BFV, CKKS). Encryption adds noise to ciphertext. Addition: noise grows additively. Multiplication: noise grows multiplicatively. Bootstrapping: homomorphically decrypt the ciphertext, resetting noise to initial level. Bootstrapping is expensive.

FHE is still 10^6x slower than plaintext computation. Encrypting 1 32-bit integer requires kilobytes of ciphertext. Bootstrapping takes seconds per gate. Practical FHE targets specific workloads: machine learning inference, database queries, genome analysis.

Most HE schemes are based on the Learning With Errors (LWE) or Ring-LWE (RLWE) hard problem, which is believed to be quantum-resistant. Breaking HE requires solving RLWE — no known quantum algorithm provides significant speedup against it.

SEAL (Microsoft, supports BFV/CKKS), HEAAN (Seoul National University, CKKS), OpenFHE (open-source, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV). All are research-grade; production deployments are rare and domain-specific.

Medical genomics: query a gene database without revealing your genome. Encrypted ML inference: cloud runs a neural network on your data without seeing it. Private analytics: aggregate statistics over encrypted user data. Financial risk computation on confidential portfolios.

HE: single party computes on data encrypted by another party. MPC: multiple parties jointly compute without revealing their inputs to each other. Hybrid: use HE for offline preprocessing, MPC for interactive protocols. Trade-offs: HE = high latency; MPC = communication overhead.

What is the key limitation of Somewhat Homomorphic Encryption (SHE)?

Homomorphic Encryption enables computation on ciphertext. PHE supports one operation; SHE supports limited depth; FHE supports arbitrary circuits via bootstrapping. Based on LWE/RLWE hard problems. Next: the LWE mathematical foundation.