Efficient algorithms for ideal lattices, with 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.**