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.