Homomorphic Encryption

The Core Idea

Standard encryption requires decryption before you can compute on data - and that decryption moment is the vulnerability. Homomorphic encryption skips it entirely: computation happens directly on encrypted data, and the encrypted result decrypts to the same answer you'd get from the plaintext.

Three Tiers

• Partially Homomorphic (PHE) - supports one operation only (RSA: multiplication; Paillier: addition)
• Somewhat Homomorphic (SHE) - both operations, but only up to a limited depth before noise corrupts the result
• Fully Homomorphic (FHE) - unlimited computation, no ceiling

The 31-Year Gap

Rivest, Adleman, and Dertouzos posed the question in 1978 - the same year RSA was published. Nobody could build it.

In 2009, Stanford PhD student Craig Gentry finally did, using a technique called bootstrapping to refresh ciphertexts before noise made them undecryptable. The catch: Gentry's original scheme took 30 minutes per bit operation. Provably possible, practically unusable.

What Closed the Gap

Modern schemes - BFV, BGV, CKKS - optimized FHE for different workloads. CKKS handles approximate floating-point math, making it the default for machine learning on encrypted data. Microsoft SEAL and IBM HElib, both open-sourced in 2018, brought this from research paper to usable library.

Real Use Cases

• Banks run fraud detection on encrypted transactions without a third party ever seeing account details.
• Hospitals run cross-institution genomic research without exposing any single dataset.
• Encrypted ballots can be tallied without decrypting a single vote.

Still Not Free

Performance improved from 30 minutes per operation to milliseconds - but FHE remains slower than plaintext computation, and bootstrapping is still the most expensive step in the pipeline.

Read full article here: https://www.weejix.com/topic/homomorphic-encryption