论文部分内容阅读
基于格理论构造的密码方案普遍被认为可以抵抗量子计算攻击,最近几年发展更是迅猛.格密码的安全性依赖于格中困难问题,如最短向量问题等,而要解这些问题需要高效的格基约减算法.国内外学者针对格中困难问题已提出了多种基于枚举法的格基约化算法,如LLL算法、BKZ算法和随机采样算法(RS)等.本文针对最短向量问题的求解,主要对RS算法进行了分析,并指出了其不足之处在于过大的随机性导致格性质倒退及需要生成大量向量导致复杂度过高.本文基于以上分析,进一步结合了分块的思想和插入指数等方法,提出了改进型随机采样约减算法