一种格上SVP问题求解的快速分块筛法

Quick Block Lattice Sieving to Solve SVP

针对现有筛法在通过向量约减构造短向量列表过程中消耗大量时间的问题,基于降维思想,提出一种新型的分块筛法。通过对原始格基分块对应生成多个低维子格,分别在子格上做筛法,获得子格短向量列表;将在子格中得到的短向量列表作为原始格上筛法的初始向量列表,能够较好地提高约化效率,从而更快找到原始格上的最短向量。分块筛技术在对新向量的约减速度与效果上优势更明显,实验数据表明分块筛在运行时间上可以达到平均7.1%的提高。

We propose a new lattice sieving algorithm,the Block lattice sieve,based on the idea of rank reduction,in order to solve the problem that the existing lattice sieving algorithms cost lots of time during the process of constructing a short-vector list by vector reductions.By dividing the original lattice basis into several low-dimensional sub-blocks,we execute the sieve algorithms on each block independently to get many short vectors included in the lists;the short-vector list obtained in the blocks is used to initialize the original lattice sieving list,which can improve the reduction efficiency better and find the shortest vector on the original lattice faster.The Block lattice sieving has an obvious advantage in the speed and effect when reducing the new sampled lattice vector.The experimental data shows that the Block lattice sieve can achieve an average increase of 7.1%in running time.