Lattice Reduction in Cryptography and Number Theory

密码学和数论中的格约化

• 批准号: 2336000
• 负责人: Daniel Martin
• 金额: $ 23.27万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2026-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2336000&HistoricalAwards=false
• 关键词: Lattice; Reduction; Cryptography; Number; Theory

Modern cryptography allows us to send private information online by rendering it unreadable except to those who can solve some underlying hard math problem (for which the intended receiver has a helpful "secret key"). But now there is a concern that many commonly used hard problems can be solved efficiently by rapidly developing quantum computers. This has prompted a search for problems that resist quantum attacks, and one promising candidate is that of finding short vectors in a lattice from a given basis. Indeed, there are many newly proposed cryptosystems whose security hinges upon the hardness of lattice reduction, specifically ideal lattice reduction, where the lattice corresponds to the so-called Minkowski embedding of an ideal in a number field. It is at this intersection between cryptography and number theory where a large part of this project lies. The PI is investigating a new algorithm for finding short vectors in ideal lattices as well as a separate family of lattices that might be efficient to work with (like ideal lattices) yet possess a hardness guarantee (unlike ideal lattices). These pursuits have the potential to further our progress toward a post-quantum secure cyberspace, and they come with many coding and computational components that provide opportunities for student involvement. The new algorithm under investigation generalizes a complex continued fraction algorithm recently introduced by the PI, which is novel in that it functions over non-Euclidean imaginary quadratic rings. The generalized (to arbitrary number fields) version finds nonzero elements of an input ideal that have a relatively small absolute field norm. This reduces the task of finding short ideal lattice vectors to the task of approximating with Dirichlet's log unit lattice, which is independent of the input ideal. Both the speed and output quality of the PI's algorithm depend crucially on an initial choice of some finite set of integers from the associated number field. The existence of a "good" initial set likely depends on the field, and the PI intends to determine which fields are more amenable to the algorithm than others. Multiquadratic and cyclotomic fields are of particular interest. (It is already known that a theoretical quantum computer can efficiently find ideal elements that are small with respect to the field norm; the PI's algorithm is classical, not quantum.) Another main goal of this project is to scrutinize the potential use of "simultaneous approximation lattices" for cryptography. The PI has shown that the problem of finding short vectors in an arbitrary lattice reduces to finding short vectors in simultaneous approximation lattices. That is a hardness guarantee not currently possessed by ideal lattices. The benefit of simultaneous approximation versus generic lattices is the number of integers needed to define them: just one more than the dimension of the lattice. This may lead to increased efficiency for lattice-based cryptosystems, but the PI must first determine how much larger the integers defining a simultaneous approximation lattice must be in order to maintain the same level of security as one of its generic counterparts.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.

现代密码学使我们能够通过使其在线发送私人信息，除非可以解决一些基本的硬数学问题的人（对于预期的接收器具有有用的“秘密密钥”）。但是现在有人担心，可以通过快速开发量子计算机来有效地解决许多常用的硬问题。这促使人们寻找抵抗量子攻击的问题，而一个有前途的候选人是从给定的基础上找到晶格中的简短矢量。确实，有许多新提出的密码系统，其安全性取决于晶格降低的硬度，特别是理想的晶格减少，晶格与所谓的Minkowski对应于一个数字字段中理想的Minkowski嵌入。正是在密码学和数字理论之间的相交中，该项目的很大一部分位于该项目。 PI正在研究一种新的算法，用于在理想的晶格中找到短载体以及一个单独的晶格家族，这些晶格可能有效地使用（例如理想的晶格）却具有硬度保证（与理想的晶格不同）。这些追求有可能进一步发展量子后安全的网络空间，并且它们具有许多编码和计算组件，这些编码和计算组件为学生参与提供了机会。正在研究的新算法概括了PI最近引入的一种复杂的持续分数算法，该算法是新颖的，因为它在非欧几里得假想中的二次环上起作用。广义（对任意数字字段）版本找到了具有相对较小的绝对字段标准的输入理想的非零元素。这减少了找到短的理想晶格向量的任务，即用Dirichlet的日志单位晶格近似，该晶格与输入理想无关。 PI算法的速度和输出质量都至关重要地取决于从关联的数字字段中的一些有限整数集的初始选择。 “良好”初始集的存在可能取决于该领域，PI打算确定哪些字段比其他算法更适合该算法。多QuaDratic和colotomic领域特别感兴趣。 （众所周知，理论量化计算机可以有效地找到相对于现场规范很小的理想元素； PI的算法是经典的，而不是量子。）该项目的另一个主要目标是仔细检查“同时近似lattices lattices lattices lattices”的潜在使用。 PI表明，在任意晶格中找到短量矢量的问题减少了在同时近似晶格中找到短向量。这是当前理想晶格目前尚未拥有的硬度保证。同时近似与通用晶格的好处是定义它们所需的整数数：仅比晶格的尺寸多。 This may lead to increased efficiency for lattice-based cryptosystems, but the PI must first determine how much larger the integers defining a simultaneous approximation lattice must be in order to maintain the same level of security as one of its generic counterparts.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.