Lattice Reduction in Cryptography and Number Theory

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

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.