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

公钥密码术几乎用于所有形式的现代通信，以提供身份验证和隐私。然而，大规模通用量子计算机的出现将破坏目前部署的公钥密码机制的安全性，包括保护当今绝大多数互联网流量的协议。鉴于量子计算的稳步发展和进步，研究公钥密码学的数学和复杂性理论基础以抵御量子计算机的攻击是至关重要和紧迫的。这个项目的目标是研究量子抵抗公钥密码学的主要候选者的安全性，其安全性依赖于与被称为模格的数学对象相关的某些计算问题的计算难解性。除了加深对可能在不久的将来广泛使用的加密协议的理解外，该项目还将编写理论计算机科学界和安全界都感兴趣的教育材料。它还将生成用于格子算法和代数数论的开源软件。更详细地说，量子抵抗公钥密码学的主要候选者依赖于在具有不同模结构的格上寻找短非零向量(SVP)的假定困难问题。该项目旨在对这一问题及相关问题有更清晰的认识。该项目计划通过开发改进的不同模格问题之间的简化和改进的专用算法来实现这一点。具体方向包括(1)研究理想格(即，对应于数域的整数环上的理想的格)上的SVP的算法，该算法导致近似因子低于当前的最佳逼近因子(不在数域上进行预处理)，其中n是格维；(2)了解SVP的密码重要的NTRU变体的精确复杂性，它与SVP的其他平均情况版本的关系，以及潜在的攻击；(3)更好地理解理想格上的SVP(即，秩1模格上的SVP，似乎比任意格上的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.