PQCrypto 2013、IACR 2014、Springer 2015上的内容有些许区别，这里选取时间上更新的版本。
作者通过应用一种量子搜索算法（QSA）在各种启发式算法、可证明筛法算法中，得到求解格上SVP的改进后的渐进量子结果。使用量子计算机的情况下，可证明了可以在时间里找到一个最短向量。
分别改进了
- Pujol, X., Stehle, D.: Solving the shortest lattice vector problem in time . Cryptology ePrint Archive, Report 2009/605 (2009)
- Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: STOC, pp. 351–358 (2010)
给出的经典时间复杂度。
启发式上，作者期望在的时间复杂度上找到一个最短向量，改进了：
- Laarhoven, T., De Weger, B.: Sieving for shortest lattice vectors in time 2 using spherical locality-sensitive hashing. Submitted (2015)
给出的经典时间复杂度。 （Laarhoven也是在改进自己的过去的成果）
作者指出，量子复杂性将成为基于SVP问题的后量子密码系统参数选择的重要指南。
1. Introduction
本段指出在大规模量子计算机诞生后将重新定义计算安全密码学。
- 基于整数分解的公钥密码
- 离散对数问题
- 实二次数域的主理想问题
- 提供基于椭圆曲线同源的系统的指数级攻击
- 加快穷举搜索
- 计数
- 寻找碰撞和爪子(claw)
等问题提供量子算法加速。
目前在对一套小系统（后量子密码学）进行研究，以取代被大规模量子计算机打破的系统。对于可能发生的量子或经典攻击，后量子密码系统受到严密的审查是至关重要的的。这样的系统能够增强人们对这些系统抵抗量子攻击的信息，并允许我们在这些系统的真实情况下调整安全参数。
后量子密码学里的其中一类的系统是将其安全性基于格困难问题。自20世纪90年代以来，基于格的密码学领域有很多研究成果，分别有
- 加密方案
- NTRU: a ring-based public key cryptosystem
- Trapdoors for lattices: simpler, tighter, faster, smaller
- On lattices, learning with errors, random linear codes, and cryptography
- 数字签名方案
- Lattice signatures and bimodal Gaussians.
- Trapdoors for hard lattices and new cryptographic constructions.
- Lattice signatures without trapdoors.
- 全同态加密
- Fully homomorphic encryption without bootstrapping.
- Fully homomorphic encryption using ideal lattices.
支撑这些系统安全性的每个格问题都可以规约为最短向量问题。
[77] Lattice-based cryptography. Master’s thesis, Eindhoven University of Technology
也可以说是最短向量问题的决策变体可以被归结为这类格问题的平均情况。详见
[77] [49] Solving hard lattice problems and the security of lattice-based cryptosystems.
介绍的最后一段讲述本文研究求解SVP的最著名算法和量子算法如何加速这些算法。通过挑战和改进这些算法的最佳渐进复杂度，本文增加了对基于格的方案的安全性的置信度。理解这些算法对密钥大小和其它安全参数的选择至关重要。例如离散对数的指数级改进的算法导致硬件上的DH系统部署的中断。
1.1 Lattices
格是离散子群。给定个线性无关的向量组成，定义为使用生成的格，则称集合是格的基。这个基不唯一。对向量进行幺模矩阵变换可得到新的基。
在格里，一般使用范数(欧式范数)，用表达。
范数是指向量中非零元素的个数，如果用L0规则化一个参数矩阵W，就是希望W中大部分元素为0，实现稀疏 范数是指向量中各个元素的绝对值之和 范数是指向量各元素的平方和然后开方 https://www.jianshu.com/p/73748dc4dea1】
对于任意向量 ，有，则称向量 是格的一个最短非零向量。记长度为。
这里的反斜杠的意思是：相对差集 反斜杠的符号为U \ A，是在集合U中，但不在集合A中的所有元素， 相对差集｛1，2，3} \ {2，3，4}为{1}
这里的要表达意思的应该是格里的向量不为0. 和一些教科书的写不太一样。
基的基本域写成。
简单的基础解释，大佬的链接如下：
这里就是讲述格理论中的一个问题：最短向量问题（SVP）。许多应用中可以使用一个合理的短向量来代替最短向量。近似因子为（）的最短向量问题，要求找到一个非零格向量，。 这里的意思就是与真正的最短向量的长度有倍的差别，和上文写法是联系起来的。
给出了找最短向量的原因：
- 椭圆曲线密码体系的构造
- Accelerated verification of ECDSA signatures.
- Exponentiation in pairing-friendly groups using homomorphisms.
- Faster point multiplication on elliptic curves with efficient endomorphisms.
- 背包密码体制的破解
- Improved low-density subset sum algorithms.
- Solving low-density subset sum problems.
- Handbook of Applied Cryptography.
- The knapsack problem in cryptography.
- 低指数RSA
- Small solutions to polynomial equations, and low exponent RSA vulnerabilities.
- Short RSA keys and their generation.
- 证明DH方案的困难性
- Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes.
对于选定适当的格，最短向量问题似乎是很困难的，借此可能构造成新的公钥密码体系的基础。
1.2 Finding short vectors (寻找短向量)
近似最短向量问题（aSVP）是格密码分析中不可或缺的。对于的值，越小的情况，这个问题已知是NP-hard问题（即1.1的 的的情况一致，如该值等于1即找到了最短向量，但这是很困难的）。对于某些指数大的，存在多项式时间内解决的算法，例如著名的算法。其它的一些算法为了获得更好的花费了额外的时间，
例如：
- 深度插入LLL
Lattice basis reduction: improved practical algorithms and solving subset sum problems.
- BKZ算法
目前最先进的经典最短向量查找方法是，是由算法加上改进的求解低维格上问题的算法子程序组成。该算法目前在SVP和格挑战(http://latticechallenge.org/svp-challenge)占主导地位，随机抽样RSR算法尚未被纳入是因为尚无改进的记录(?)
2003年，Ludwig使用量子算法加快了原始RSR算法，通过量子搜索代替一个从大列表中随机抽样的样本，实现了量子算法在渐进上比经典算法更快。（[55]A faster lattice reduction method using quantum search.) 论文提到了量子计算的可用性还会影响到基于格的密码体系的安全性，涵盖NTRU。
1.3 Finding shortest vectors (寻找最短向量)
尽管通常只要找到一个短向量就足够了，但BKZ算法及其变体都需要一个低维精确的SVP求解器作为子程序。下面简要讨论寻找最短向量的三类主要算法。
枚举法：
寻找最短向量的经典方法是枚举法。为了找到一个最短向量，在原点周围的一个巨球里枚举所有格向量。如果输入的基是lattice basis经过LLL得到的LLL-reduced，那么计算的时间复杂度为， 是格的维度。Kannan算法对输入基使用了更强的预处理，使得能够在时间里运行。两种方法都是用-多项式空间。
筛法：
筛法是一种可以在时间里求解SVP的概率算法。有几种不同的筛法，但它们都依赖于通过将所有向量存储在一个长列表中，以某种方法削减短向量的空间。（意思上很好理解）这个列表在维中必是指数级的，但可以证明这些算法也能在单指数时间内运行，不似超指数superexponential（枚举的情况）。最近的工作表明(2015)，在使用理想格的时候，筛法的时间和空间复杂度都有所改善，SVP格挑战里当前最高记录依然是由筛法解决的（截至2022也是）。
沃罗诺伊图的单元计算：
这是一种基于构造点阵Voronoi单元的确定性求解的SVP算法。在时间复杂度为里该算法能够构造出精确的空间来描述格的Voronoi单元。该算法也可以同时求解SVP和CVP。在2014年底都是求解高维SVP最佳时间复杂度。
经过简单了解，在2019年的成果有关于该算法的CPU+GPU异构和大规模并行平台的计算加速。这是在经典计算中攻击基于格的密码系统使用了比较新的技术（CUDA）去进行。 10.1109/ACCESS.2019.2939142
离散高斯分布采样：
Solving the shortest vector problem in time via discrete Gaussian sampling. 这篇论文在2015年发表，介绍了这种新的技术，广泛地利用了格上的离散高斯分布。通过从一个非常宽的离散高斯分布（标准差比较大）中初始采样个格向量，随后迭代组合和平均采样，生成格上更窄的离散高斯分布的样本，标准差的降低，直至所得到的分布的多个样本集合很可能包含一个格的最短非零向量。该算法可证明在时间和空间内运行。
实际应用：Voronoi单元算法和离散高斯分布采样算法在经典的渐进时间复杂度都优于枚举法。但实际使用上选择的是LLL算法的Gama等人的改进版本。该版本没有使用Kannan的更强预处理的版本，因而时间复杂度是。但是，指数中隐藏的常数较大、以及其他算法的指数级空间复杂度，对于大多数实际的，枚举法实际上比其他方法更快。这样的事实也说明其它的方法还是比较新的，还有未被探索到的，因此对这些其他方法的进一步研究可能打破当前的平衡。
1.4 Quantum search 量子搜索
本文研究如何利用量子算法（Grover量子搜索算法）来加速上面概述的SVP算法。
给定长度为N的列表L和一个函数，找到使得的元素（这个元素可能是不存在的）。这里假设可以在单位时间内被评估。
尽管是简介，我认为这里写的还是太短了，也不太适合量子计算的描述（编程角度），Grover算法的解释在IBM、Microsoft等量子计算文档里介绍的更详细。
经典算法随着经典计算机的出现，找到这样一个元素的自然方式就是遍历整个列表，直至找到这个元素。这样平均需要时间。对常数因子是最优的，因为没有任何一种经典算法能够在小于时间里找到这样的元素。
Grover算法可以将找到该元素时间降低到。对常数因子是最优的，任何量子算法都至少需要时间。
这里描述本篇论文使用表达搜索这个元素的动作。找到了返回true，没找到就是false。这样可以使得对每个算法的经典版本和量子版本提供一个描述。（这里就是简述）
1.5 RAM model 随机存取存储器模型
这里假设一个RAM模型，列表中的第条可以在固定时间（或多项式时间）被查询。如果是虚拟的，其中第个元素可以在与的长度成多项式的时间内被计算出，那么查找时间不会是个问题。
若是一个非结构化的数值列表（非结构化数据不可以通过键值获取相应信息），对于经典计算，类似RAM的模型通常在实践中是有效的。然而有一些基本的理由可以去质疑它 （Cost analysis of hash collisions: will quantum computers make SHARCs obsolete? 大意是专用的分解密码的硬件在大型量子计算机诞生后会变得过时、落后。这里就是使用量子计算机挑战哈希碰撞），有一些实际的计算架构不适用于假设。在量子计算下，一个实用的类RAM的量子存储器的实现特别有挑战性（仍在发展https://doi.org/10.1103/PhysRevLett.125.260504）。后面三篇论文是一些作者研究的量子算法的局限性。
一些算法（量子游走，中文读物https://zhuanlan.zhihu.com/p/153561937）必须在常规量子存储器（量子叠加态存储器）中存储一个大数据库。相比之下，量子搜索(经典)个字符实际需要将N个值存储在量子可寻址的经典存储器中和个量子比特中。
量子可寻址的经典存储器在实现上可能比常规量子比特更容易。量子搜索，量子电路上只需要个量子比特就能实现，不用存储在内存中。
本文使用的量子搜索算法需要将大小为的列表存储在可量子寻址的经典存储器中，量子比特和次搜索。
上面的内容还是去看量子算法会比较好。
https://www.phy.pku.edu.cn/jhchen/files/Q-11.pdf 北京大学《量子信息物理原理》课程讲稿
在本篇的工作中，考虑了经典算法的经典RAM存储器和量子搜索算法的类RAM的量子可寻址经典存储器。这既是未来研究评估更实用的量子体系结构影响的第一步，也是确定基于格的密码学参数在选择时，应能够抵抗潜在的量子算法攻击。未来的工作可以是找到和利用先进的量子搜索算法，类似基于量子行走的搜索算法[69]。
1.6 Contributions 贡献
基础内容都知道的话直接从这里看起就好。
本文中，作者表明量子算法可以显著加快文献中的各种筛法算法的速度。时间指数中的常数一般会减少约25%，从而改善了求解最短向量问题的最佳可证性（精确和近似）和最佳启发式渐进结果的改进。
这里13年没有，14年才加进去的，也很奇怪这个为什么写的是
本文重点是筛法，但也简要考虑了将量子搜索算法应用于其它方法，并指出为什么应用同样的技术并不容易让这些算法有显著的加速。
在作者的第一版论文提交后，有人提出利用离散高斯采样的新方法可以将时间复杂度提高到。由于应用了量子搜索的筛法在时间复杂度上渐进高于这个结果。这意味着量子计算上筛法不再是精确求解SVP的最佳可证算法（渐进）。在后面9.3章节讨论了量子搜索对离散高斯抽样可能产生的影响。（只要经典上有更快的，就从量子算法的角度尝试是否能够改进它）
图中可以看出HashSieve和SphereSieve算法的量子时间复杂度和空间复杂度之前取得了不错的平衡，对于其它算法来说，两个复杂度都会随着参数的改变而增加。
1.7 Outline
第二节，考虑当前最好的筛法：ListSieve-Birthday。将量子搜索应用到该算法中，得到了最佳的可证明量子时间复杂度。
第三、四节，最重要的两个启发式筛法：NV-Sieve、GaussSieve。
第五节，展示如何将量子搜索应用到HashSieve算法中，得到最佳的启发式量子时间复杂度。
第八节，讨论其它筛法的量子加速。
第九节，讨论为什么量子搜索没有导致Voronoi cell算法和枚举算法的时间复杂度有大的渐进改进。
2. The provable ListSieve-Birthday algorithm of Pujol and Stehlé
Pujol和Stehlé利用生日悖论，展示了原始ListSieve算法（可证明SVP）的时间复杂度指数中的常数可以减少近25%。
2.1 Description of the algorithm
该算法分三个步骤：
- 生成一个具有范数的长的格向量列表，约束条件是在 和 之间。这个“哑元”列表是出于技术原因而使用，使得可证明。用于生成此列表的样本数被当做一个随机变量，这也是为了使某些证明技术发挥作用。
除了实际的格向量以外，为了生成这个列表，还考虑了不在格中且最多距离的稍加扰动/干扰（perturbed）的向量。这依然是为了使证明有效而做出了技术修改。实验表明没有这种扰动向量，算法也能正常工作。
- 生成后，生成一个新的短格向量列表。生成这些向量的过程与类似(没写T是啥)，有两个例外是：所有采样的格向量都被添加进；使用“哑元”列表中的向量进行向量约简。后者保证中的向量都是独立同分布。
- 当生成后，希望它有两个完全不同的格向量，它们最多相距 （最短非零向量长度1.1）。我们搜索里一对接近的它向量，然后返回差值。
以上意思极简概述就是，在生成的列表中找到一对，它们距离的差越接近越好，那么就算是找到最短向量。
- 选取一个随机数记为
- 初始化空列表
- 如果没有理解错的话，循环次地执行下面程序
- 从选取一个扰动向量，这里的的选取分别在2.2、2.3有解释
- 使用的基本域模这个扰动向量得到向量
- 当搜索的条件满足时执行下面程序
2-10：L
11-18：从L中约减出来的S
19：寻找差值十分接近的向量，满足则返回。
行4. 是个球，元素从中随机选取。 图例以后再改好了。
2.2 Classical complexities
复杂度分析