Bit Security of Learning with Errors for Post-Quantum Cryptography and Fully Homomorphic Encryption

LWE can be summarised as: given a matrix `A` and a vector `b` modulo `q`, decide if `b` is uniform or if `b = A * s + e` for some small error `e`. Hence, the problem is essentially to solve a noisy linear system of equations modulo `q`. It was shown by Regev that this problem is as hard as assumed-to-be-hard problems. The problem has become a central building block of modern cryptographic constructions.

1. Modern cybersecurity relies on cryptographic algorithms such as RSA encryption and digital signatures as well as the Diffie-Hellman key exchange. It is well-known that the hard mathematical problems underlying these algorithms can be solved efficiently on a quantum computer. While the advent of quantum computers has been promised many times before, recent developments in the area have convinced many actors, especially those with a long-term security mission, to actively seek alternative algorithms which promise post-quantum security. As a result, post-quantum cryptography has recently developed from a niche area of cryptography to a mainstream concern. With the American standards body NIST announcing it would hold a competition for post-quantum proposals, the field is posed to become a central area of cryptographic research in the coming years. LWE is one of the central candidates for a hard problem withstanding attacks using quantum computers and first proposals for key exchange algorithms for Internet communication based on LWE are available.

2. Fully homomorphic encryption, the ability to compute with encrypted data, has progressed considerably since a first solution was proposed in Gentry's seminal work. The most recent generation of such schemes have become efficient enough to the point that first prototype applications, such as privacy-preserving computations with genome data, are being developed. All such constructions rely on the difficulty of solving LWE.

While it is encouraging to have Regev's proof that solving LWE is no easier than solving problems widely believed to be hard as we increase parameters, this does not settle the question of how big we should choose our parameters to provide security against real world attacks. The purpose of this project is to provide more refined answers to this question, allowing us to rely on LWE with more confidence.

Cryptography is inherently an applicable subject, and there is a continuous transfer of knowledge and techniques from the more theoretical side of the field to the more applied side. This process can be seen with the Learning with Errors problem itself. Here, the initial theoretical ideas were published in cryptography and theoretical computer science conferences, but then further developed and applied to scenarios where such cryptography enables new functionality such as post-quantum cryptography and fully homomorphic encryption, with research now being published at general cybersecurity conferences. Similarly, first attempts at standardisation are being launched.

This project will aid this development further by increasing our confidence in the security of specific parameter sets for LWE. In particular, it is expected that the results of this project will have a direct impact on standardisation and deployment efforts for lattice-based cryptography currently underway.

Furthermore, due to the strong focus on reliable research software in this project and the utility of lattice-reduction beyond the field of post-quantum cryptography or homomorphic encryption, the research proposed here is also likely to affect other areas of engineering or mathematics relying on such tools.