Collaborative Research: CISE-ANR: CNS Core: Small: Cryptographic Hardness of Module Lattices

公钥密码术几乎用于所有形式的现代通信，以提供身份验证和隐私。然而，大规模通用量子计算机的可用性将破坏目前部署的公钥加密机制的安全性，包括保护当今绝大多数互联网流量的协议。鉴于量子计算的稳步发展和进步，研究抵抗量子计算机攻击的公钥密码学的数学和复杂性理论基础是至关重要和紧迫的。该项目的目标是研究量子抗公钥密码学的主要候选者的安全性，其安全性取决于与称为模格的数学对象相关的某些计算问题的计算困难性。除了进一步理解可能在不久的将来广泛使用的密码协议外，该项目还将生成理论计算机科学界和安全界都感兴趣的教育材料。更详细地说，抗量子公钥密码学的主要候选者依赖于在具有不同模块结构的格上找到短非零向量（SVP）的问题的假定棘手性。该项目旨在更清楚地了解这一问题和相关问题。该项目计划通过开发不同模格问题之间的改进约简和改进的专用算法来实现这一目标。具体方向包括（1）研究理想格上的SVP算法（即，对应于数域的整数环上的理想的格），导致逼近因子低于当前最佳逼近因子（没有对数字字段进行预处理）大约为2^{sqrt（n）}，其中n是晶格维度;（2）理解在密码学上重要的SVP的NTRU变体的精确复杂性，其与SVP的其他平均情况版本的关系，和潜在的攻击;（3）更好地理解理想晶格上的SVP之间的表观硬度“转变”（即，秩-1模格，这似乎比任意格上的SVP明显容易）和秩-2模格上的SVP（其硬度对于许多密码方案的安全性是必要的）;（4）继续为有效和稳健的开放作出贡献，格算法和代数数论的源软件。该奖项反映了NSF的法定使命，并通过评估被认为值得支持使用基金会的知识价值和更广泛的影响审查标准。

Public-key cryptography is used in nearly all forms of modern communication to provide authentication and privacy. However, the availability of large-scale general-purpose quantum computers will undermine the security of currently deployed public-key cryptographic mechanisms, including protocols protecting the vast majority of today’s Internet traffic. Given the steady progress and advances in quantum computing, it is critical and pressing to investigate the mathematical and complexity-theoretic foundations for public-key cryptography that resists attacks by quantum computers. The goal of this project is to study the security of the primary candidates for quantum-resistant public-key cryptography, whose security rests on the computational intractability of certain computational problems related to mathematical objects called module lattices. In addition to furthering the understanding of cryptographic protocols that are likely to be in widespread use in the near future, the project will generate educational materials that will be of interest both to the theoretical computer science community and to the security community. It will also generate open-source software for lattice algorithms and algebraic number theory.In more detail, the primary candidates for quantum-resistant public-key cryptography rely on the presumed intractability of the problem of finding short non-zero vectors (SVP) over lattices with different module structures. This project aims to provide a clearer understanding of this problem and related problems. The project plans to achieve this by developing both improved reductions between different module lattice problems and improved dedicated algorithms. Specific directions include (1) investigating algorithms for SVP over ideal lattices (i.e., lattices that correspond to ideals over the ring of integers of a number field) that lead to an approximation factor below the current best approximation factor (without pre-processing on the number field) of roughly 2^{sqrt(n)}, with n being the lattice dimension; (2) understanding the precise complexity of the cryptographically important NTRU variant of SVP, its relation with other average-case versions of SVP, and potential attacks; (3) better understanding the apparent hardness “transition” between SVP over ideal lattices (i.e., rank-1 module lattices, which seems to be significantly easier than SVP over arbitrary lattices) and SVP over rank-2 module lattices (whose hardness is necessary for the security of many cryptographic schemes); and (4) continuing to contribute to efficient and robust open-source software for lattice algorithms and algebraic number theory.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.