理想格上格基的快速三角化算法研究

奥鹏网院作业

理想格上格基的快速三角化算法研究
张 洋*①② 刘仁章③ 林东岱①
①(中国科学院信息工程研究所信息安全国家重点实验室 北京 100093)
②(中国科学院大学网络空间安全学院 北京 100049)
③(卫士通摩石实验室 北京 100166)
摘 要：为了提高理想格上格基的三角化算法的效率，该文通过研究理想格上的多项式结构提出了一个理想格上格基的快速三角化算法，其时间复杂度为O(n3log2B)，其中n是格基的维数，B是格基的无穷范数。基于该算法，可以得到一个计算理想格上格基Smith标准型的确定算法，且其时间复杂度也比现有的算法要快。更进一步，对于密码学中经常所使用的一类特殊的理想格，可以用更快的算法将三角化矩阵转化为格基的Hermite标准型。
关键词：理想格；Hermite标准型；Smith标准型；三角化
1 引言
Hermite标准型和Smith标准型是两种定义在整数矩阵上的重要标准型，它们在很多方面都有应用，比如，Hermite标准型可以用于解丢番图方程[1]，整数规划[2]和格上的计算问题[3]，Smith标准型可以用来确定有限生成阿贝尔群的基础理论中的不变常量[4]。而计算Hermite标准型和Smith标准型通常来说需要将格基三角化以后才能进行。所以为了提高计算Hermite标准型和Smith标准型的算法的效率，提高矩阵三角化算法的效率有很重要的意义。
从另一个角度来看，格是数论中很重要的概念，而基于格的密码学由于其高效、多功能和潜在抗量子攻击等性质吸引了众多密码学家的注意。对于同一个格而言，由于所有的格基都有相同的Hermite标准型，所以一般在基于格的公钥密码体制中将Hermite标准型作为公钥[5]。
为了提高基于格的密码算法的效率，密码学家提出了理想格的概念。理想格相比于一般的格拥有更多的代数结构，可以加速运算并减少空间存储。目前已经有一些算法在理想格上运行比在一般格上要快，比如Lyubashevsky等人[6]在理想格上给出了更快的Gram-Schmit正交化和高斯采样算法(循环格)。但是目前还没有理想格上对三角化的加速算法。







Fast Triangularization of Ideal Latttice Basis
ZHANG Yang①② LIU Renzhang③ LIN Dongdai①
①(State Key Laboratory of Information Security, Institute of Information Engineering,Chinese Academy of Sciences, Beijing 100093, China)
②(School of Cyber Security,University of Chinese Academy of Sciences, Beijing 100049, China)
③(Westone Cryptologic Research Center, Beijing 100166, China)
Abstract: To improve the efficiency of the triangularization of ideal lattice basis, a fast algorithm for triangularizing an ideal lattice basis is proposed by studying the polynomial structure, which runs in time O(n3log2B), where n is the dimension of the lattice, B is the infinity norm of lattice basis. Based on the algorithm, a deterministic algorithm for computing the Smith Normal Form (SNF) of ideal lattice is given,which has the same time complexity and thus is faster than any previously known algorithms. Moreover, for a special class of ideal lattices, a method to transform such triangular bases into Hermite Normal Form (HNF)faster than previous algorithms will be present.
Key words: Ideal lattice; Hermite Normal Form (HNF); Smith Normal Form (SNF); Triangularization
中图分类号：TP309.7; O157.4
文献标识码：A
文章编号：1009-5896(2020)01-0098-07
DOI: 10.11999/JEIT190725
收稿日期：2019-09-19；改回日期：2019-11-15；网络出版：2020-01-01
*通信作者： 张洋 zhangyang9091@iie.ac.cn