โ† Wiki Index / Computation & Algorithms / Fully Homomorphic Encryption
๐Ÿ’ป Computation & Algorithms

Fully Homomorphic Encryption

Fully homomorphic encryption is an advanced encryption paradigm that permits arbitrary computational circuits to be evaluated directly on encrypted data without decryption, resolving a thirty-year open problem in cryptography.

Fully Homomorphic Encryption (FHE) is a transformative cryptographic paradigm in computation and algorithms that enables arbitrary computational circuitsโ€”comprising both addition and multiplication operationsโ€”to be executed directly on encrypted data without ever requiring decryption or exposure of the secret key. First conceptualized in 1978 by Ron Rivest, Leonard Adleman, and Michael Dertouzos under the moniker privacy homomorphisms shortly after the creation of the RSA cryptosystem, the challenge of constructing a fully homomorphic scheme persisted as one of the most famous open problems in computer science for three decades until American cryptographer Craig Gentry presented the first working construction in his landmark 2009 doctoral dissertation.

Within modern distributed computing, FHE resolves the fundamental conflict between data privacy and computational utility. Rather than requiring sensitive medical records, biometric signatures, or financial ledgers to be decrypted in cloud server memory during processing, FHE allows untrusted servers to evaluate machine learning models, search queries, or statistical regressions directly over ciphertexts, producing an encrypted output that only the private key holder can decrypt.

Theoretical Taxonomy: Homomorphism Classifications

Homomorphic encryption schemes are classified into three distinct categories based on their functional evaluation capacity:

  1. Partially Homomorphic Encryption (PHE): Supports the evaluation of only a single algebraic operation (either addition or multiplication) for an unlimited number of operations. Prominent examples include unpadded RSA and ElGamal encryption (multiplicative), and the Paillier cryptosystem (additive).
  2. Somewhat Homomorphic Encryption (SWHE): Supports the evaluation of both addition and multiplication operations simultaneously, but only for a strictly bounded computational circuit depth. As homomorphic multiplications execute, mathematical noise accumulates in the ciphertext until it overflows the decryption threshold, corrupting the underlying plaintext.
  3. Fully Homomorphic Encryption (FHE): Capable of evaluating arbitrary circuits of unlimited depth by incorporating an algorithmic refresh mechanism (termed bootstrapping) that resets ciphertext noise before it causes decryption failures.

Craig Gentry's Breakthrough: The Bootstrapping Theorem

The core theoretical breakthrough that allowed Craig Gentry to construct the first FHE scheme in 2009 was Bootstrapping: the process of homomorphically evaluating the cryptosystem's own decryption circuit using an encrypted secret key.

The Mechanism of Bootstrapping

In lattice-based somewhat homomorphic schemes (such as those based on Learning With Errors), a ciphertext c encrypting message m contains an internal noise vector e. When two ciphertexts are added, their noise adds linearly: eadd โ‰ˆ e1 + e2. When two ciphertexts are multiplied, their noise grows multiplicatively: emult โ‰ˆ e1 ยท e2. After a few multiplication levels, the noise exceeds the modulus threshold, and decryption fails.

Gentry observed that decryption is itself an arithmetic circuit with inputs given by the ciphertext c and the secret key sk:

m = Dec(sk, c)

If a somewhat homomorphic encryption scheme possesses enough depth capacity to evaluate its own decryption circuit plus one additional multiplication gate (a property termed bootstrappable), it can refresh noisy ciphertexts indefinitely:

  1. The user publishes an encrypted version of their secret key: csk = Encpk(sk).
  2. To refresh a noisy ciphertext cnoisy, the untrusted evaluator evaluates the decryption function homomorphically:

cclean = Eval(Dec, csk, cnoisy)

  1. The evaluation executes the decryption algorithm inside the encrypted domain. The output is a brand new ciphertext cclean that encrypts the identical message m, but whose noise level has been reset to the baseline noise generated by the decryption circuit evaluation.

By repeatedly applying bootstrapping after every multiplication gate, any somewhat homomorphic scheme is transformed into a fully homomorphic encryption scheme of unlimited computational depth.

Generations of FHE Architectures

Over the past fifteen years, FHE research progressed through four distinct structural generations:

First Generation (2009โ€“2011)

First-generation systems originated with Gentry's ideal-lattice construction and the subsequent DGHV scheme operating over the integers. These initial schemes established theoretical feasibility by demonstrating the bootstrapping theorem, proving that evaluation of the decryption circuit refreshes accumulated noise. However, early prototypes suffered from substantial ciphertext expansion, requiring multi-megabyte public keys and computationally demanding bootstrapping operations that required minutes to hours to refresh an individual encrypted bit.

Second Generation: BGV and BFV (2011โ€“2013)

Formulated by Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan (BGV) and Junfeng Fan and Frederik Vercauteren (BFV). These schemes operate on polynomial rings over lattices (Ring-LWE).

  • Modulus Switching: Instead of constantly bootstrapping, second-generation schemes scale down the ciphertext modulus after each multiplication level, transforming the exponential noise growth into linear growth and allowing leveled FHE (evaluating circuits of depth L without any bootstrapping).
  • SIMD Batching: Exploiting the Chinese Remainder Theorem over polynomial quotient rings (Smartโ€“Vercauteren batching), a single ciphertext encrypts a vector of thousands of plaintext slots, evaluating operations on all slots simultaneously in parallel.

Third Generation: GSW and TFHE (2013โ€“2016)

Formulated by Craig Gentry, Amit Sahai, and Brent Waters (GSW) and advanced by Ilaria Chillotti et al. (TFHE). GSW eliminates expensive key switching matrices by representing ciphertexts as square matrices under the approximate eigenvector framework. TFHE (Torus Fully Homomorphic Encryption) achieves ultra-fast gate-level bootstrapping: bootstrapping an encrypted Boolean NAND gate executes in approximately 10 to 20 milliseconds on standard processors, enabling arbitrary Boolean logic evaluation.

Fourth Generation: CKKS (2017)

Introduced by Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. CKKS supports fixed-point approximate arithmetic over vectors of real or complex numbers. Unlike discrete schemes that treat noise as unwanted corruption, CKKS treats cryptographic noise as floating-point rounding error, providing optimal efficiency for privacy-preserving machine learning, neural network inference, and statistical data science.

Industrial Applications and Performance Frontiers

Modern FHE architectures are deployed across several high-privacy technical domains:

  • Encrypted Neural Network Inference: A client encrypts a medical image (such as an MRI scan) with CKKS and transmits it to a cloud server. The server runs a pre-trained deep convolutional neural network over the ciphertexts and returns the encrypted diagnosis, ensuring that the cloud server never observes the patient data and the patient never accesses the proprietary model weights.
  • Private Information Retrieval (PIR): Clients query massive databases without revealing which records they are accessing, preventing search query tracking.
  • Encrypted Database Analytics: Financial institutions compute joint fraud detection heuristics and risk assessments across institutional boundaries without sharing raw customer financial data.

Comparison of Modern FHE Schemes

SchemeArchitectural ParadigmPlaintext DomainPrimary StrengthsStandard Software Libraries
BFV / BGVRing-LWE (Second Gen)Exact Integers (โ„คt)Exact arithmetic, SIMD vector packingMicrosoft SEAL, PALISADE, OpenFHE
CKKSRing-LWE (Fourth Gen)Complex / Real Vectors (โ„‚n/2)Fast approximate arithmetic for Machine LearningOpenFHE, SEAL, Lattigo
TFHERing-GSW / Torus (Third Gen)Individual Boolean Bits / Small IntegersSub-second gate bootstrapping; arbitrary branchingTFHE-rs, Concrete

References

  1. Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 169-178.
  2. Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory, 6(3), 1-36.
  3. Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. Advances in Cryptology โ€” ASIACRYPT 2017, 409-437.
  4. Chillotti, I., Gama, N., Georgieva, M., & Izabachรจne, M. (2020). TFHE: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1), 34-91.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision