Fully Homomorphic Encryption Lattices

Short answer: Fully homomorphic encryption lets a party compute on encrypted data and get an encrypted result that decrypts to the right answer. The first candidate scheme came in 2009, and all known schemes are based on lattices or closely related problems, the same family behind many post-quantum proposals. The central technical issue is noise that grows with each operation, handled by bootstrapping. This post summarises tutorials and lecture notes, and does not assess any specific product.

Why lattices

A 2022 arXiv tutorial says lattice-based cryptosystems are believed to be good post-quantum candidates because no known quantum algorithm solves lattice problems significantly better than the best classical algorithms, unlike integer factorisation and elliptic-curve discrete logarithms. It adds that structure in lattice problems has led to significant advances in homomorphic encryption. The tutorial follows the path from the Learning With Errors problem, to Ring LWE, to homomorphic schemes built on them, and does not cover NTRU or homomorphic signatures. It uses a simple public-key scheme introduced by Regev in 2009 to show how security connects to lattice problems.

What the definition says

Lecture notes from a 2022 Simons Institute programme define a scheme as four algorithms, Gen, Enc, Dec and Eval, such that decrypting the evaluation of a function on an encryption of a message gives the function of the message. They give a lattice encryption sketch where a ciphertext is a random matrix and a vector formed from the secret key, the scaled message and a small random noise term. Decryption subtracts the key term, divides, and rounds, which works so long as the noise stays below half the scaling factor.

Noise and bootstrapping

A UC San Diego page on FHE explains that lattice ciphertexts are noisy and the noise grows as homomorphic operations are performed, so arbitrary computations need a way to reduce it. The first candidate scheme was proposed by Gentry at STOC 2009, and current schemes still use bootstrapping as Gentry proposed, applied to different cryptosystems. In the lecture notes, bootstrapping publishes an encryption of the secret key as part of the public key and homomorphically evaluates the decryption function on a ciphertext, which clears its noise. It requires the encryption to be circularly secure. The 2022 tutorial notes that newer schemes follow Gentry in building a somewhat homomorphic scheme first and then bootstrapping, but avoid his squashing technique and use algebraic properties of LWE instances to make the schemes bootstrappable.

A short timeline

The lecture notes list Rivest, Adleman and Dertouzos posing the problem in 1978, Gentry's first candidate in 2009, and Brakerski and Vaikuntanathan's first solution based on standard lattice problems in 2011, followed by a series of schemes with major efficiency gains and several implementation libraries, all lattice-based and using bootstrapping. The UC San Diego page says the first such standard-lattice schemes had superpolynomial approximation factors, later reduced to polynomial. It states the main differences among schemes are the homomorphic multiplication method and the bootstrapping procedure.

What this does not tell you

These references are tutorials and course notes, not performance benchmarks. They do not say how fast any scheme runs or whether a product built on one is ready for a given use.

FAQ

What does homomorphic encryption allow?

Computing on encrypted data so that decrypting the result gives the function of the original data.

Why are lattices used?

They underlie all known fully homomorphic schemes, and no known quantum algorithm solves lattice problems much better than classical ones.

What is bootstrapping?

Homomorphically evaluating decryption to clear accumulated noise from a ciphertext.

When was the first scheme?

Gentry proposed the first candidate in 2009.

Is it practical?

These references do not benchmark performance, so they cannot answer that.