论文部分内容阅读
随着计算机的快速发展与网络的普及,信息化进程中的信息安全保障问题日益凸现,密码作为信息安全的支撑,得到了国际社会的高度重视。格公钥密码是目前抗量子计算攻击的密码体制中,最受关注的研究领域。格数学问题、格计算复杂理论问题的研究及格密码体制的设计与分析,已经逐步成为抗量子计算的公钥密码体制理论的核心研究内容。一方面,格中的困难问题是公钥密码设计的重要选择,另一方面,求解格中困难问题的算法是一种重要的密码分析工具,已成功分析与破解了多个公钥密码体制。因此研究格中困难问题的求解算法具有重要的理论价值与实际意义。本文探讨求解格中最短向量问题和求解LWE问题的随机算法,得到了三项研究成果。在求解最短向量问题方面做了两个工作,工作之一是提出了一种新的启发式随机筛法,改进了Nguyen和Vidick提出的求最短向量问题的启发式算法,把时间复杂度从20.415n+o(n)降到20.3836n+o(n)。关键技术是用两层筛减少比较次数,对时间和空间实现了部分平衡。算法复杂度的估计基于球覆盖理论和多重积分。工作之二是针对逐次最小长度间存在gap的格,提出了一种降维的求解最短向量问题的算法。算法首先利用随机筛法得到足够多的短向量,再利用这些短向量恢复出降维的子格,通过求解子格的最短向量问题找到原格的最短向量。算法的复杂度由gap出现的位置和大小决定。此外对一类重要的密码格,LWE(Learning with Errors)问题基于的嵌入格的λ2gap给出了下界估计,分析了利用求嵌入格的最短向量求解LWE问题的难度。进而从gap的角度入手,在某些参数下改进了BDD问题到uSVP问题的归约。本文的第三个工作是对求LWE问题的算法进行研究。采用随机化的技术,改进了此前实际中求解LWE问题的最优算法,即2011年,Lindner和Peikert提出的多最近平面算法,大大提高了算法的效率(如对某组参数提高了232)。并且将Gama, Nguyen和Regev提出的极度裁剪技术应用在LWE问题上,进一步降低了算法复杂度,该提高在理论上是指数阶的。