Efficient algorithms for ideal lattices, with applications

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

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

理想的晶格来自数字字段或功能字段的（分数）思想。它们在计算数理论中形成了一个重要的对象，以其出色的属性，可以应用于计算数字字段或函数字段的重要不变性，例如其类数和调节器。此外，理想的晶格由于它们的基础结构，可实现各种强大而有用的结构，因此广泛用于加密和编码理论。 我的长期目标是研究理想晶格的特性，改进和开发它们的算法，并研究其在计算数理论，量词后密码学和信息理论中的进一步应用。 特别是，我期望具有以下研究结果：为与其最短载体的分布和枚举以及基础还原算法相关的理想晶格构建一套有效的算法；解决了减少理想晶格的一些相关问题，然后申请计算数字字段的类数字和单位组，并在部门班级组中构建快速算术；近似尺寸功能并证明其最大值；建立一个明确的理想晶格家族，应避免使用密码系统的构建和一系列理想的晶格，这些晶格被确定为适合量子耐量子的密码学；为代码设计构建合适的理想晶格和一种算法，以生成全面的sublattices用于coset编码。 我们的研究将提供计算数理论，量词后加密和编码理论之间的联系，并为这些领域带来强大的应用。在计算数理论中，我们在减少理想晶格方面的工作将有助于提高计算班级数量和数字字段的调节器的效率。它也是为算术级的算术算法构建有效算法的必不可少的工具，它导致对不可减少平滑平面曲线的雅各布人快速算术，并且在算术几何学中具有许多应用。在量子后加密术中，我们关于理想晶格最短矢量的分布的结果将有助于确定当前构建涉及晶格的当前密码系统的缺陷。此外，他们将提供最佳候选理想晶格的标准，以构建安全的密码系统。在编码理论中，我们的研究将有助于为代码设计构建合适的理想晶格，并为固定编码提供全面的理想sublattices。此外，我们对尺寸函数的研究将产生证据表明功能场和数字字段之间的相似性，以及代数数理论和代数几何形状之间的相似之处。 我在此应用程序中使用“我们”来指示我与Jens D. Bauch，Tian Peng，Dung H. Duong，Le V. Luyen，Oliver W. Gnilke，Amaro Barreal，Alex Karrila，David A. Karrila，David A. Karpuk和Camilla Hollanti。