CAREER: Algebraic Methods for the Computation of Approximate Short Vectors in Ideal Lattices

该项目涉及研究寻找所谓的欧几里得格的短元素的计算难度。这项任务的难度是衡量最有前途的加密协议家族之一的安全性的标准，这些协议被用来抵抗来自量子计算机的攻击。 向这样的协议过渡是密码学社区的当务之急。 事实上，量子安全原语需要在构建大规模量子计算机之前很久就准备好并部署，以考虑加密数据的保质期。 这项研究的结果被传播给了大量的受众，包括愿意采用量子安全原语的工业界人士、大学生和K-12学生。该项目支持为期一周的网络安全夏令营，高中生通过动手活动发现安全和密码学的基础知识。该项目特别关注在作为数域理想的欧几里得格中搜索短向量的难度。 这种特殊的格类，称为理想格，在基于格的密码学中非常流行，因为它允许有趣的优化，包括使用显着更短的密钥。 然而，对具有更多代数结构的更小类别的格的限制也可能意味着搜索短元素不像在一般格中那样困难。 该项目以研究者以往在数域不变量计算方面的工作为基础，研究了在理想格中搜索短元素的代数方法。该奖项反映了NSF的法定使命，通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project involves research into the computational hardness of the search for short elements of the so-called Euclidean lattices. The hardness of this task is the measure of the security of one of the most promising family of cryptographic protocols that are conjectured to resist attacks from quantum computers. The transition toward such protocols is an immediate priority for the cryptography community. Indeed, quantum-safe primitives will need to be ready and deployed long before the construction of large scale quantum computers to account for the shelf life of encrypted data. The results from this research are disseminated to a large audience ranging from industrials willing to adopt quantum-safe primitives, university students, and K-12 students. This project supports a week-long cybersecurity camp for high school students who discover the fundamentals for security and cryptography through hands-on activities.This project specifically focuses on the hardness of the search for short vectors in Euclidean lattices that are ideals of a number field. This special class of lattices, called ideal lattices, is very popular in lattice-based cryptography because it allows interesting optimizations including the use of significantly shorter keys. However, the restriction to a smaller class of lattices having more algebraic structure could also mean that the search for short elements is not as hard as in general lattices. Building on previous work of the investigator on the computation of invariants of number fields, this project investigates the algebraic methods allowing the search for short elements in ideal lattices.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.