A short history of lattice reduction in cryptography: from direct applications to FHE.

After the discovery of the LLL lattice reduction algorithm in 1982, it quickly became an handy tool for cryptanalysts. In particular, it was used as a weapon of choice against knapsack-based cryptosystems. More generally, at that time, lattice reduction was mostly used to find linear relations between integers or vectors of integers. This is a very direct application but it already showed the power of the LLL algorithm as a cryptographic tool. Interestingly, in order to analyze the performance of lattice reduction in this context, it was pretty standard to assume that a lattice reduction oracle was available and to prove that a given system could broken with such an oracle. The underlying heuristic assumption was that in practice, the behavior of LLL closely approximated the reduction oracle. This heuristic was motivated by the fact that for the lattice dimensions that were tractable at that time, the result of LLL was usually good enough to make attacks developped in the reduction oracle setting pratical.

In 1996, the discovery of Coppersmith's small root algorithms was a major change that greatly renewed the interest of cryptanalysts in lattice reductions. After this breakthrough, the technique was used in a variety of cryptanalyses, allowing to break some special, speed-optimized, constructions of RSA keys or to leverage side-channel techniques leaking partial information on keys into full-fledged attacks. More surprisingly, it was also used constructively as a tool to understand the security of RSA-OAEP. A very strong property of Coppersmith's small root algorithms it that it is no longer necessary to assume the existence of a reduction oracle and that LLL itself can provably be used in the method.

Droping the reduction oracle is a very important progress. Indeed, around the same time, it became clear that lattice reduction remains a difficult problem. From a complexity theoretic viewpoint, Ajtai showed that the problem of finding a shortest non-zero lattice vector is NP-hard for randomized reduction. From a constructive cryptographic viewpoint, the first cryptosystems based on the hardness of lattice related problems started to appear. Since then lattice-based cryptography underwent steady progress. A major success of the field was the discovery by Gentry of the first fully homomorphic encryption scheme based on ideal lattices.