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

LWE可以概括为：给定一个矩阵‘ a ’和一个向量‘ b ’模‘ q ’，决定‘ b ’是否均匀，或者‘ b = a * s + e ’对于一个小误差‘ e ’。因此，问题本质上是解决一个以q为模的有噪声的线性方程组。Regev表明，这个问题和假定的困难问题一样难。这个问题已经成为现代密码学结构的核心组成部分。现代网络安全依赖于加密算法，如RSA加密和数字签名以及Diffie-Hellman密钥交换。众所周知，这些算法背后的困难数学问题可以在量子计算机上有效地解决。虽然量子计算机的出现已经被多次承诺，但该领域的最新发展已经说服了许多参与者，特别是那些具有长期安全使命的参与者，积极寻求承诺后量子安全的替代算法。因此，后量子密码学最近已经从密码学的小众领域发展成为主流关注。随着美国标准机构NIST宣布将举办一场后量子方案竞赛，该领域有望在未来几年成为密码学研究的核心领域。LWE是使用量子计算机抵抗攻击的难题的核心候选问题之一，基于LWE的互联网通信密钥交换算法的第一个建议是可用的。完全同态加密，即使用加密数据进行计算的能力，自Gentry的开创性工作中提出第一个解决方案以来，已经取得了相当大的进展。这类方案的最新一代已经变得足够高效，以至于第一个原型应用程序正在开发中，比如利用基因组数据进行隐私保护计算。所有这些构造都依赖于求解LWE的难度。虽然Regev的证据表明，随着参数的增加，解决LWE并不比解决人们普遍认为很难的问题容易，但这并不能解决我们应该选择多大的参数来提供针对现实世界攻击的安全性的问题。这个项目的目的是为这个问题提供更精细的答案，让我们更有信心依靠LWE。

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.