Efficient algorithms for ideal lattices, with applications

理想格产生于数域或函数域的（分数）理想。它们具有显著的性质，可用于计算数域或函数域的重要不变量，如类数和调节器，因此是计算数论中的一个重要对象。此外，理想格在密码学和编码理论中被广泛应用，因为它们的底层结构可以实现各种强大而有用的结构。我的长期目标是研究理想格的性质，改进和发展它们的算法，并研究它们在计算数论、后量子密码学和信息论问题中的进一步应用。特别是，我希望有以下研究成果：构建一套与最短向量的分布和枚举相关的理想格的有效算法以及基约简算法；在简化理想格上解决了一些相关问题，并将其应用于数域的类数和单位群的计算，建立了除数类群的快速算法；逼近大小函数并证明其最大值；创建一个明确的理想格族，这些理想格族应该避免用于构建密码系统，并创建一组理想格，这些理想格被确定为适合于抗量子密码术；构造适合编码设计的理想格，并给出了一种生成圆角子格的算法。我们的研究将提供计算数论、后量子密码学和编码理论之间的联系，并为这些领域带来强大的应用。在计算数论中，我们对简化理想格的研究将有助于提高类数的计算效率和数域的调节器。它也是构建高效的函数域群除数类算法的重要工具，它能快速求解不可约光滑平面曲线的雅可比矩阵，在算术几何中有广泛的应用。在后量子密码学中，我们关于理想格的最短向量分布的研究结果将有助于确定当前包含格结构的密码系统的缺陷。此外，他们还将给出构建安全密码系统的最佳候选理想格的标准。在编码理论方面，我们的研究将有助于构建适合于编码设计的理想格，并为协集编码产生圆整的理想子格。此外，我们对大小函数的研究将为函数域和数域之间的相似性，以及代数数论和代数几何之间的相似性提供证据。我在这个申请中使用“我们”来表示我与Jens D. Bauch、Tian Peng、Dung H. Duong、Le V. Luyen、Oliver W. Gnilke、Amaro Barreal、Alex Karrila、David A. Karpuk和Camilla Hollanti的合作。

Ideal lattices arise from (fractional) ideals of number fields or function fields. They form a significant object in computational number theory for their remarkable properties that can be applied to compute important invariants of a number field or a function field, such as its class number and regulator. Moreover, ideal lattices are widely used in cryptography and coding theory due to their underlying structures that enable a variety of powerful and useful constructions. My long-term goals are to investigate properties of ideal lattices, improve and develop algorithms on them as well as study their further applications to problems in computational number theory, post-quantum cryptography, and information theory. In particular, I expect to have the following research outcomes: Constructing a suite of efficient algorithms for ideal lattices related to the distribution and enumeration of its shortest vectors as well as basis reduction algorithms; solving some related problems on reduced ideal lattices, then applying to compute class numbers and unit groups of number fields and building fast arithmetic in the divisor class group; approximating the size function and proving its maximum; creating an explicit family of ideal lattices that should be avoided for construction of cryptosystems and a collection of ideal lattices that are identified to be suitable for quantum-resistant cryptography; constructing suitable ideal lattices for code design and an algorithm to produce well-rounded sublattices for coset coding. Our research will provide a connection between computational number theory, post-quantum cryptography and coding theory as well as bring powerful applications to these fields. In computational number theory, our work on reduced ideal lattices will help to improve the efficiency of computing the class number and the regulator of a number field. It is also an essential tool for building efficient algorithms for arithmetic in the divisor class group of function fields, that results in a fast arithmetic on Jacobians of irreducible smooth plane curves and has many applications in arithmetic geometry. In post-quantum cryptography, our results on the distribution of shortest vectors of ideal lattices will help to determine flaws of current cryptosystems whose constructions involve lattices. Moreover, they will give criteria of the best candidate ideal lattices to build secure cryptosystems. In coding theory, our study will help to construct suitable ideal lattices for code design and to produce well-rounded ideal sublattices for coset coding. In addition, our research on the size function will yield evidence for similarities between function fields and number fields, and furthermore between algebraic number theory and algebraic geometry. I use "we" in this application to indicate my collaborations with Jens D. Bauch, Tian Peng, Dung H. Duong, Le V. Luyen, Oliver W. Gnilke, Amaro Barreal, Alex Karrila, David A. Karpuk and Camilla Hollanti.