Lattice Reduction in Cryptography and Number Theory

密码学和数论中的格约化

• 批准号: 2302699
• 负责人: Daniel Martin
• 金额: $ 23.27万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2023-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2302699&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嵌入。该项目的很大一部分就在于密码学和数论之间的交叉点。PI正在研究一种新的算法，用于在理想格中找到短向量，以及一个单独的格族，它可能是有效的（像理想格），但具有硬度保证（不像理想格）。这些追求有可能进一步推动我们朝着后量子安全网络空间的方向发展，它们带有许多编码和计算组件，为学生参与提供了机会。研究中的新算法推广了PI最近提出的复连分数算法，该算法的新颖之处在于它在非欧虚二次环上起作用。广义（任意数域）的版本发现非零元素的输入理想，有一个相对较小的绝对域范数。这将寻找短理想格向量的任务减少到用狄利克雷对数单位格近似的任务，这与输入理想无关。PI算法的速度和输出质量关键取决于从相关数域中初始选择的某个有限整数集。一个“好的”初始集的存在可能取决于字段，PI打算确定哪些字段比其他字段更适合算法。多重二次域和分圆域特别令人感兴趣。(It已经知道理论量子计算机可以有效地找到相对于场范数较小的理想元素; PI的算法是经典的，而不是量子的。该项目的另一个主要目标是仔细研究“同时近似格”在密码学中的潜在用途。PI已经表明，在任意格中找到短向量的问题归结为在同时近似格中找到短向量。这是理想晶格目前不具备的硬度保证。同时近似与一般格的好处是定义它们所需的整数数量：只比格的维数多一个。这可能会提高基于格的密码系统的效率，但PI必须首先确定定义同时近似格的整数必须大多少，以保持与其通用对应物相同的安全级别。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。