并行的NTRU格规约算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (28): 62-64.

并行的NTRU格规约算法

吴立强1，杨晓元1，2，郝斌3，刘镇3

1.武警工程学院电子技术系网络与信息安全武警部队重点实验室，西安 710086
2.西安电子科技大学网络信息安全教育部重点实验室，西安 710071
3.武警工程学院电子技术系网络与信息安全研究所，西安 710086

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-10-01 发布日期:2011-10-01

Parallel reduction on NTRU lattice

WU Liqiang1，YANG Xiaoyuan1，2，HAO Bin3，LIU Zhen3

1.Key Laboratory of Network & Information Security under the Chinese Armed Police Force，Electronic Department，Engineering College of the Armed Police Force，Xi’an 710086，China
2.Key Laboratory of Network & Information Security of the Ministry of Education，Xidian University，Xi’an 710071，China
3.Institute of Network & Information Security under the Chinese Armed Police Force，Electronic Department，Engineering College of the Armed Police Force，Xi’an 710086，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-10-01 Published:2011-10-01

摘要/Abstract

摘要： 在高维NTRU格中，BKZ算法为了获取较好的规约效果不得不采用大分块，但同时也使运行时间急剧增加。设计了一种msBKZ规约算法，对一组初始基左乘随机幺模矩阵变换出多组基，分别采用小块BKZ（k<18）线程规约，筛选出规约效果最好的那组进行“短代替”后作为初始基，重复该过程以此逐步逼近格中的最短向量。实验表明msBKZ比大块BKZ（k=23）的规约效率至少提高一倍。

关键词: 数论研究组（NTRU）, 格基规约, 并行算法

Abstract: 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）.

Key words: Number Theory Research Unit（NTRU）, lattice-reduction, parallel algorithm

吴立强1，杨晓元1，2，郝斌3，刘镇3. 并行的NTRU格规约算法[J]. 计算机工程与应用, 2011, 47(28): 62-64.

WU Liqiang1，YANG Xiaoyuan1，2，HAO Bin3，LIU Zhen3. Parallel reduction on NTRU lattice[J]. Computer Engineering and Applications, 2011, 47(28): 62-64.

[1]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[2]	朱超，吴素萍. 特征点检测DoG并行算法[J]. 计算机工程与应用, 2020, 56(10): 36-43.
[3]	陈亚中1，李振军1，李荣华1，毛睿1，乔少杰2. TSCAN：利用并行策略改进的图结构聚类算法[J]. 计算机工程与应用, 2019, 55(1): 76-83.
[4]	王德政1，张益农1，杨帆2. 基于MapReduce的并行PLS过程监控算法实现[J]. 计算机工程与应用, 2018, 54(24): 61-65.
[5]	孙劲光1，吴素红2. 基于空间分割与椭球包围盒的碰撞检测算法[J]. 计算机工程与应用, 2016, 52(4): 217-222.
[6]	喻津1，周浩杰2，柴志雷1. 一种基于众核架构的稠密光流并行计算方法[J]. 计算机工程与应用, 2016, 52(16): 186-191.
[7]	曾博1，2，雷友诚1，王丛知2，邱维宝2，冯歌2，曾成志2，杨戈2，郑海荣2. 基于CUDA的声辐射力弹性成像算法研究[J]. 计算机工程与应用, 2015, 51(18): 249-254.
[8]	李敏1，2，宋曰聪1，吴斌3，彭保3. 基于Beowulf机群中改进粒子滤波的3D人体运动跟踪[J]. 计算机工程与应用, 2015, 51(14): 17-22.
[9]	王艾昕. 基于SIMD结构的矩形行列式并行算法研究[J]. 计算机工程与应用, 2012, 48(25): 48-51.
[10]	李文敬，刘之家，蓝贞雄. 无约束最优化问题的BFGS松弛异步并行算法[J]. 计算机工程与应用, 2012, 48(17): 44-47.
[11]	刘佳昆，周永权. 具有主从结构的并行人工萤火虫群优化算法[J]. 计算机工程与应用, 2012, 48(14): 33-37.
[12]	王震1，孙卫1，蔺小林2. 多自由度Vanderpol振子极限环计算[J]. 计算机工程与应用, 2012, 48(13): 230-233.
[13]	杨梅1，李志民1，曹大勇2. CUDA架构下大规模稠密线性方程组的并行求解[J]. 计算机工程与应用, 2011, 47(32): 27-30.
[14]	汪保，孙秦. 求解非线性方程组的一种并行算法[J]. 计算机工程与应用, 2011, 47(2): 49-51.
[15]	于方. 三角网格表面任意两点间并行近似测地线算法[J]. 计算机工程与应用, 2011, 47(10): 197-200.