Toward fully homomorphic

Fully homomorphic encryption (FHE)

A partially homomorphic scheme can only perform one operation. Yet any computation reduces to additions and multiplications. So a scheme was needed that accepts both. This was the holy grail of cryptography for thirty years.

The definition of FHE

A fully homomorphic scheme (Fully Homomorphic Encryption, FHE) makes it possible to perform on the ciphertexts both additions and multiplications, in an arbitrary number.

Why are these two operations enough? Because with addition and multiplication modulo 2, we reconstruct the logic gates XOR and AND, and with these gates we build any circuit, hence any computation. An FHE scheme can therefore, in principle, evaluate a complete program on encrypted data.

Gentry's breakthrough (2009)

The problem remained open from 1978 until 2009, the year Craig Gentry presented the first FHE scheme in history, in his thesis. His construction rests on lattices (in French réseaux euclidiens), a mathematical structure some of whose problems are believed to be hard, even for a quantum computer.

The noise problem

To be secure, these schemes add a bit of random noise to each ciphertext. This noise is small at the start, but it accumulates with each operation:

an addition increases the noise moderately;
a multiplication makes it grow much faster.

If the noise exceeds a certain threshold, decryption becomes wrong: the message is lost. So you can only chain a limited number of operations.

noise level
   |
threshold ─ ─ ─ ─ ─ ─ ─ ─●─ ─ ─ ─ ─ ─  (beyond: wrong decryption)
   |              ╱
   |           ╱
   |        ╱
   |     ╱
   |  ╱
   |╱_______________________ operations
      op  op  op  op  op

Bootstrapping: the brilliant idea

Gentry's decisive contribution is bootstrapping. The idea: have the scheme evaluate its own decryption, homomorphically. The result is a new ciphertext of the same message, but whose noise has been reset to a low level.

very noisy ciphertext  --[ bootstrapping ]-->  same message, noise reset

Once the noise is reset to zero, you can start again and continue computing. By repeating bootstrapping, you chain an unlimited number of operations — which makes the scheme fully homomorphic, and not merely for a few operations.

In summary