Lattice Reduction in Cryptography and Number Theory

现代密码学允许我们在线发送私人信息，使其不可读，除了那些能够解决一些潜在的数学难题的人（目标接收者有一个有用的“秘密密钥”）。但现在人们担心，许多常用的难题可以通过快速发展的量子计算机有效地解决。这促使人们寻找抵抗量子攻击的问题，其中一个有希望的候选问题是从给定的基中找到晶格中的短向量。事实上，有许多新提出的密码系统，其安全性取决于格约简的硬度，特别是理想格约简，其中格对应于所谓的理想在数域中的闵可夫斯基嵌入。这是密码学和数论之间的交集，这是这个项目的很大一部分。PI正在研究一种新的算法，用于在理想晶格中寻找短向量，以及一组单独的晶格，这些晶格可能是有效的（如理想晶格），但具有硬度保证（不像理想晶格）。这些追求有可能进一步推动我们向后量子安全网络空间的发展，它们伴随着许多编码和计算组件，为学生参与提供了机会。所研究的新算法推广了PI最近引入的复连分数算法，该算法的新颖之处在于它在非欧几里德虚二次环上起作用。广义（到任意数目的域）版本找到具有相对较小的绝对域范数的输入理想的非零元素。这将寻找短理想晶格向量的任务简化为用狄利克雷对数单位晶格逼近的任务，而狄利克雷对数单位晶格与输入理想无关。PI算法的速度和输出质量都主要取决于从相关的数字字段中选择有限的整数集。“良好”初始集的存在可能取决于字段，PI打算确定哪些字段比其他字段更适合该算法。多二次场和分环场是特别有趣的。（众所周知，理论上的量子计算机可以有效地找到相对于场范数较小的理想元素；PI的算法是经典的，而不是量子的。）该项目的另一个主要目标是仔细研究“同时逼近格”在密码学中的潜在用途。PI表明，在任意晶格中寻找短向量的问题可以简化为在同时逼近晶格中寻找短向量的问题。这是目前理想晶格所不具备的硬度保证。与一般格相比，同时逼近的好处是定义它们所需的整数数量：只比格的维数多一个。这可能会提高基于格的密码系统的效率，但PI必须首先确定定义同步逼近格的整数必须有多大，才能保持与通用对应物相同的安全级别。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.