一种基于分块采样方法的格基约减算法

作者：曹金政; 程庆丰^*

来源：密码学报, 2019, 6(01): 73-82.

DOI：10.13868/j.cnki.jcr.000284

• 格
• 随机采样算法
• I-RS算法

基于格理论构造的密码方案普遍被认为可以抵抗量子计算攻击,最近几年发展更是迅猛.格密码的安全性依赖于格中困难问题,如最短向量问题等,而要解这些问题需要高效的格基约减算法.国内外学者针对格中困难问题已提出了多种基于枚举法的格基约化算法,如LLL算法、BKZ算法和随机采样算法(RS)等.本文针对最短向量问题的求解,主要对RS算法进行了分析,并指出了其不足之处在于过大的随机性导致格性质倒退及需要生成大量向量导致复杂度过高.本文基于以上分析,进一步结合了分块的思想和插入指数等方法,提出了改进型随机采样约减算法,简称I-RS算法.该算法通过在局部格中的随机化采样和调整基向量的排列顺序改进格基的内部性质,进而提升约减效果.初步的理论分析表明, I-RS算法在O(n3(k/6)k/4)的时间内明显改进了输出格基的长度性质,其中2k是分块的大小.实验表明,新算法比RS算法和BKZ算法在约减效果和稳定性等方面有所提升,输出向量长度较BKZ算法缩短20%,近似因子在BKZ算法的0.95倍以下.

• 单位
  信息工程大学