Efficient algorithms for ideal lattices, with applications

理想晶格的高效算法及其应用

• 批准号: RGPIN-2019-04209
• 负责人: Tran, Ha
• 金额: $ 1.17万
• 依托单位: Concordia University of Edmonton
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=737484
• 关键词: Efficient; algorithms; ideal; lattices; applications

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.

理想格是由数域或函数域的(分数)理想产生的。它们的显著性质可用于计算数域或函数域的重要不变量，如其类数和调整子，因而成为计算数论中的一个重要对象。此外，理想格由于其潜在的结构可以实现各种强大而有用的构造，因此在密码学和编码理论中得到了广泛的应用。我的长期目标是研究理想格的性质，改进和发展理想格上的算法，并研究它们在计算数论、后量子密码学和信息论中的进一步应用。具体地说，我期望得到以下研究成果：为理想格构造一套与其最短向量的分布和枚举相关的高效算法以及基减算法；解决归约理想格上的一些相关问题，然后应用于计算类数和数域的单位组，并在除数类组中建立快速算术；逼近大小函数并证明其最大值；创建构造密码系统时应避免的理想格显式族以及被确定为适合于抗量子密码学的理想格集合；构造适合于码设计的理想格和产生陪集编码的全面子格的算法。我们的研究将提供计算数论、后量子密码学和编码理论之间的联系，并为这些领域带来强大的应用。在计算数论中，我们在约化理想格上的工作将有助于提高计算类数和数域的调整器的效率。它也是在函数域的除数类群上建立有效的算术算法的重要工具，它导致了不可约光滑平面曲线的雅可比的快速算法，并在算术几何中有许多应用。在后量子密码学中，我们关于理想格的最短向量分布的结果将有助于确定当前涉及格的密码系统的缺陷。此外，它们还将给出构造安全密码系统的最佳候选理想格的判据。在编码理论方面，我们的研究将有助于构造适合于编码设计的理想格，并产生适合陪集编码的理想子格。此外，我们对尺度函数的研究将为函数域和数域之间的相似性，以及代数数论和代数几何之间的相似性提供证据。我在本应用程序中使用“我们”来表示我与Jens D.Bauch、田鹏、Dung H.Duong、Le V.Luyen、Oliver W.Gnilke、Amaro Barreala、Alex Karrila、David A.Karpuk和Camilla Hollanti的合作。