SaTC: CORE: Small: Towards a scientific theory of lattice reduction

随着量子计算时代的临近，我们的社会迫切需要为其对网络安全的巨大影响做好准备。由于量子计算机将能够破解我们今天严重依赖的所有主要密码系统，因此有必要开发新的量子耐受密码系统，而美国国家理工学院标准研究所正在开发后量子密码标准。基于格子的密码学代表了这类量子抵抗密码系统中最有前途的家族之一。然而，尽管到目前为止已经取得了成功，但对于基于格子的密码学的基本组成部分，即格子和约简算法是如何工作的，仍然严重缺乏了解。这种知识鸿沟在许多方面都是有害的，例如基于格的系统的性能妥协，对其安全性的不准确和不可靠的评估，甚至对基于格的密码学本身的想法的潜在威胁。本提案的目标是通过为基于格的密码学发展坚实的理论基础来应对这些问题。我们的理论将被系统地应用于改进基于格的密码学的实践，并科学地评估基于格的系统的安全性，从而为人类为量子时代做准备做出贡献。这个项目主要由两个部分组成，这两个部分将结合成一个完整的分析格化简算法。首先，该项目将改进用于研究晶格向量统计的数论工具。这最初是由西格尔、施密特和罗杰斯在1940-50年代的S的工作中率先提出的，但当前基于格的密码学的实践要求将这些工具扩展到更广泛的上下文，以便能够处理在一般数域上定义的格，或者计算较低等级的子格，而不仅仅是格矢量。它们将用于取代高斯启发式，以便提供对晶格行为的更准确的预测。其次，最近PI发现格子归约算法可能被解释为统计物理学中的沙堆模型，这两个起源非常不同的系统的行为方式非常相似。这为减少算法的科学研究提供了一种令人兴奋和有前途的方法，这正是本项目将追求的：将沙堆的物理理论应用于减少算法。一旦这个项目确定了这两组结果的解释和预测能力，该项目将把它们应用于修订基于格子的密码系统的安全估计和当前参数选择的实践，特别是正在进行的NIST后量子标准化过程中基于格子的密码系统。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

As the era of quantum computing draws near, there is an imminent need for our society to prepare for its immense impact on cybersecurity. Since quantum computers will be capable of breaking all the main cryptosystems we are heavily relying on today, it is necessary to develop new cryptosystems that are quantum-resistant, and the National Institute of Standard of Technology is the process to develop the post-quantum cryptographic standards. Lattice-based cryptography represents one of the most promising families of such quantum-resistant cryptosystems. However, despite its successes so far, there has been a severe lack of understanding as to how the basic components of lattice-based cryptography, namely lattices and reduction algorithms, operate. This knowledge gap is harmful in a number of ways, such as the compromise of the performance of lattice-based systems, the inaccurate and unreliable evaluation of their security, and even the potential threat to the very idea of lattice-based cryptography itself. The goal of the present proposal is to confront these problems by developing a solid theoretical foundation for lattice-based cryptography. Our theory will be applied systematically to improve the practice of lattice-based cryptography and to scientifically assess the security of lattice-based systems, thereby contributing to humanity's effort to prepare for the quantum era.This project largely consists of two parts that will be combined into one for a complete analysis of lattice reduction algorithms. First, the project will refine the number-theoretic tools used to study the statistics of lattice vectors. This was originally pioneered by the works of Siegel, Schmidt, and Rogers in the 1940-50's, but the current practice of lattice-based cryptography calls for the extensions of those tools to broader contexts, so as to be able to handle lattices defined over a general number field, or count sublattices of lesser rank rather than just lattice vectors. They will serve to replace the Gaussian heuristic in order to provide more accurate predictions of lattice behavior. Second, recently the PIs found that lattice reduction algorithms may be interpreted as sandpile models from statistical physics, and these two systems of very different origins behave in a remarkably similar way. This provides an exciting and promising approach to a scientific study of reduction algorithms, which is exactly what this project will pursue: apply the physical theory of sandpiles to reduction algorithms. Once this project establishes the explanatory and predictive power of both sets of results, the project will apply them to revising the security estimates of lattice-based cryptosystems and the current practices in parameter choices, in particular, for the lattice-based cryptosystems in the ongoing NIST post-quantum standardization process.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.