本站原创
摘要：随着计算机的快速进展与网络的普及，信息化进程中的信息安全保障不足日益凸现，作为信息安全的支撑，得到了国际社会的高度重视。格公钥是目前抗量子计算攻击的体制中，最受关注的探讨领域。格数学不足、格计算复杂论述不足的探讨及格体制的设计与浅析，已经逐步成为抗量子计算的公钥体制论述的核心探讨内容。一方面，格中的困难不足是公钥设计的重要选择，另一方面，求解格中困难不足的算法是一种重要的浅析工具，已成功浅析与了多个公钥体制。由此探讨格中困难不足的求解算法具有重要的论述价值与实际作用。本论文探讨求解格中最短向量不足和求解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提出的多最面算法，大大提升了算法的效率（如对某组参数提升了2~(32)）。并且将Gama, Nguyen和Regev提出的极度裁剪技术运用在LWE不足上，进一步降低了算法复杂度，该提升在论述上是指数阶的。关键词：公钥学论文格浅析论文最短向量不足论文随机筛法论文LWE不足论文
摘要3-4
Abstract4-9
第1章 引言9-17
1.1 选题背景及作用9-11
1.2 国内外探讨进展11-16
1.3 本论文的结构安排16-17
第2章 预备知识17-27
2.1 格基本知识17-20
2.2 利用Voronoi细胞求最短向量不足20-23
2.3 基本数学知识23-25
2.4 LWE不足25-27
2.4.1 离散高斯分布25-26
2.4.2 LWE不足介绍26-27
第3章 改善的Nguyen-Vidick算法27-41
3.1 Nguyen-Vidick启发式筛法27-29
3.2 两层筛法29-30
3.3 复杂度浅析30-40
3.3.1 中心点数上界定理32-33
3.3.2 中心点数上界定理的证明33-40
3.4 小结40-41
第4章 逐次最小长度间有着gap的格的最短向量不足41-61
4.1 LWE嵌入格的λ2-gap估计41-45
4.2 BDD到uSVP不足的归约45-48
4.3 降维最短向量算法48-59
4.3.1 求近似最短向量不足的筛法48-55
4.3.2 有着λεn+1-gap格的降维最短向量算法55-58
4.3.3 多gap格的降维最短向量算法58-59
4.4 小结59-61
第5章 LWE不足的改善算法61-79
5.1 最面算法及其变体62-65
5.1.1 Babai最面算法62-63
5.1.2 多最面算法63-64
5.1.3 随机化的多最面算法64-65
5.2 针对LWE不足的枚举算法65-73
5.2.1 求解LWE的枚举算法66-67
5.2.2 求解LWE的裁剪枚举算法67-73
5.3 小结73-79
第6章 结论和探讨计划79-81