Section: Application Domains

Lattice-Based Cryptography

In 1996, Ajtai  [55] showed that, up to that point, lattices were used only as tools in cryptanalysis, but they could actually be used to construct cryptographic primitives. He indeed proposed a cryptographic primitive which security is based on the worst-case hardness of lattice problems: if one succeeds in breaking the primitive, even with some small probability, then one can also solve any instance of a certain lattice problem. This nice property makes lattice-based cryptographic constructions very attractive. In contrast, virtually all other cryptographic constructions are based on some average-case assumption. Furthermore, we currently do not have too many alternatives to traditional number-theoretic based cryptography such as RSA. Such alternatives will be needed in case an efficient algorithm for factoring integers is ever found. In fact, efficient quantum algorithms for factoring integers and computing discrete logarithms already exist  [76] . Although large-scale quantum computers are not expected to exist for at least a decade, this fact should already be regarded as a warning. There are currently no known quantum algorithms for lattice problems, which makes these problems very hard to solve. In addition, the computations involved in lattice-based cryptography are very simple and often require only modular additions, which make them efficient for users.

For all these reasons, lattice-based cryptography has recently become a hot topic, and we started to work on it.