并行的NTRU格规约算法

Parallel reduction on NTRU lattice

在高维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）.