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、Tian Peng、Dung H. Duong、Le V. Luyen、Oliver W. Gnilke、Amaro Barreal、Alex Karrila、David A. Karpuk 和 Camilla Hollanti 的合作。