并行的NTRU格规约算法  

Parallel reduction on NTRU lattice

作　　者：吴立强[1] 杨晓元[1,2] 郝斌[3] 刘镇[3] 

机构地区：[1]武警工程学院电子技术系网络与信息安全武警部队重点实验室,西安710086 [2]西安电子科技大学网络信息安全教育部重点实验室,西安710071 [3]武警工程学院电子技术系网络与信息安全研究所,西安710086

出　　处：《计算机工程与应用》2011年第28期62-64,88,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60842006)~~

摘　　要：在高维NTRU格中,BKZ算法为了获取较好的规约效果不得不采用大分块,但同时也使运行时间急剧增加。设计了一种msBKZ规约算法,对一组初始基左乘随机幺模矩阵变换出多组基,分别采用小块BKZ(k<18)线程规约,筛选出规约效果最好的那组进行"短代替"后作为初始基,重复该过程以此逐步逼近格中的最短向量。实验表明msBKZ比大块BKZ(k=23)的规约效率至少提高一倍。In order to get shorter vector in high-dimension NTRU lattice, BKZ has to set the block size large, so the running time increases as well.A msBKZ algorithm is proposed and it works as follows.An initial base is transformed into many bases by left multiplying some random unimodular matrixes.They are reduced by BKZ threads with small block size. The best base is chosen and made as the new initial base after ＂short vector replacement＂.In this way the shortest vector is approached step by step.Experiments with the new msBKZ algorithm show that it is at least twice as effective as BKZ （k=23）.

关 键 词：数论研究组(NTRU) 格基规约 并行算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]