Efficient algorithms for ideal lattices, with applications

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

• 批准号: RGPIN-2019-04209
• 负责人: Tran, Ha
• 金额: $ 1.17万
• 依托单位: Concordia University of Edmonton
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675727
• 关键词: 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的合作。放大图片作者：Jiang H.放大图片作者：Le V. Luyen，奥利弗W.放大图片作者：Jennilke，Amaro Barreal，Alex Karrila，大卫A. Karpuk and Camilla Hollanti.**