格上的最短向量求解等困难问题是数论发展最基本的问题之一，包括求解最短向量问题、最近向量问题及这些问题派生出的各种变体和理想格上的上述问题求解等．当前，无论是基本的格密码设计，还是基于错误向量学习(LWE)和环上的错误向量学习(RLWE)设计的多种密码体制，它们所基于的求解格上困难问题理论上都可以规约为搜索格上的最短向量或良好的格基问题[1]，因此格基约减是求解格上困难问题最基本的方法．目前已知算法的中求解格上困难问题普遍要用到格基约减算法，例如经典的Lenstra-Lenstra-Lovasz算法(LLL算法)[2]、Schnorr-Euchner算法(BKZ算法)[3]及其多种改进版本[4-5]，这些算法已经作为求解格上困难问题最实用的工具．格上困难问题有很多种类，其中最短向量问题(SVP)的求解作为格上最困难的问题，经过长期的研究，已经形成了比较系统的求解方法．目前，求解SVP的算法可以大致分为精确输出最优向量算法和近似逼近最优格基算法[1]．在近似求解算法方面，最著名也是目前用途最广的格基约减算法是LLL算法[2]，它以近似因子为((1+ε)4/3)(n-1)/2输出包含最短向量优化格基，其中：ε为一个极小量；n为格的维数．LLL算法在后续的格密码设计和其他空间数学应用中发挥了基础性作用，在数值计算等众多具体算法方面也广泛应用．在LLL算法的基础上，文献[6]利用对偶格的约减进一步降低了近似因子．在给定的具体格实例求解中，适用性最好的是BKZ算法[3]．文献[7]在此基础上提出了改进的BKZ算法(BKZ2.0)，通过调整格基分块的值和归约的方向，优化了BKZ算法的执行过程．目前，求解approx-SVP最好的近似因子是2O(nloglogn/logn)的SVP．SVP的精确求解算法主要通过备选向量枚举和向量空间随机筛选两种基本方法．文献[8-9]设计了求解SVP的枚举算法，时间复杂度是2O(n2)．文献[10]的Hanrot算法复杂度达到nn/2e+O(n)，其中e为算法的单次枚举规模．文献[11]提出在格点的Voronoi细胞结构上，将求解格上困难问题转化为利用预处理技术求解相关向量问题．该算法在解决格上主要困难的时间复杂度为22n+O(n)，但在空间存储上，其空间复杂度约为2n+O(n)．随机筛选法方面，文献[12]提出了AKS筛法，首次得到单指数的格基约减算法，其时间复杂度为2O(n)．文献[13]提出了基于随机初始向量选择的启发式筛法，使时间复杂度和空间复杂度分别为20.415n+O(n)和20.2075n+O(n)．文献[14]提出两层筛的启发式筛法，结合随机初始向量的AKS筛法，达到时间复杂度20.3836n+O(n)和空间复杂度20.2557n+O(n)．文献[15]提出了一种须要预计算的近似求解CVP算法(approx-CVPP)．文献[16]给出了更完整的算法．理论上，随机筛法比枚举有更好的算法复杂度上界，然而实际中，随机筛法从概率上可能比枚举算法复杂度更高，且不能实现算法可行性的理论证明．长期以来，在不依赖量子算法的情况下，现有算法比较难以取得突破性进展主要有两个方面的原因：一方面，当前性能最好的算法是基于经典LLL算法的改进算法，使用分块、裁剪等优化技术可以取得一些可操作性上的平衡，然而在给定格结构未知的情况下，算法往往具有很大的随机性；另一方面，在精确输出上，格基约减的好坏直接决定了枚举和裁剪手段的结果好坏，不够理想的格基使得绝大多数枚举算法在现有计算水平下失去意义．本研究在回顾了格上困难问题发展背景的基础上，通过对现有格上困难问题求解方法的梳理，分析讨论了格基约减的主要手段和算法，重点对比分析了经典设置下LLL算法、BKZ算法和随机抽样算法(RS算法)的优缺点及相互关系．在此基础上，总结了格基约减算法和精确SVP算法的一般求解思路．由于在这个思路下，理论上求解速度已经难以有质的突破，因此本研究基于格上的假设结论，提出了另外三个更智能的格基约减猜想性算法．通过加入不同的约束条件，进一步提高格基约减的效率，并从理论上分析了其最劣势情况下的计算复杂度．1 格上困难性问题定义及其求解1.1　格的描述定义1[1] Rn为n维实数域，令b1T,b2T,⋯，bnT∈Rn为Rn上的一组线性无关的向量，矩阵B=[b1|b2|⋯|bn]，则集合Λ=ℒ(B)={y∈Rm    s.t.∃s∈Zm,y=Bs=∑i=1sibi}，称为由B生成的n维格向量空间，秩为n，即ℒ(B)中包含了由b1T,b2T,⋯,bnT的线性组合生成的所有向量的集合，且其中每个向量的坐标均在R中．定义2[17] 任意一组可以生成格的线性无关的向量集合都称为格的基，格的基中向量个数称为格的维度．任意两组这样的向量中，向量个数相同．定义3［18］ 对于一个素数q，A∈Zqn×m和u∈Zqn，可以定义以下三种基本的格：Λq(A):={e∈Zm   s.t. ∃s∈Zqn,ATs=e (mod q)}；Λq⊥(A):={e∈Zm   s.t. Ae=0  (mod q)}；Λqu(A):={e∈Zm   s.t. Ae=u  (mod q)}．除了上述基本的格构造，当前在密码体制构造中使用最多的是利用空间映射构造性质更好的格，如理想格[1,19]和对数格[16]等．定义4［1,20］ (规范化嵌入构造的格)令σ1,σ2，⋯,σn为n个从任意数域K到复数域C的映射，且满足当i∈{1,2,⋯,r1}时，σi:K→R；当i∈{r1+1,r1+2,⋯,r2}时，σi=σ¯i+r2，那么∀a∈K，在σ1,σ2，⋯,σn作用下产生的向量(σ1(a)，σ2(a),⋯,σr1(a)，Re(σri+1(a))，Im(σr1+1(a))，Re(σri+2(a))，Im(σr1+2(a))，…，Re(σr2(a))，Im(σr2(a))T∈Rn构成一个格．当上述a取自模q的整数环时，可以构造一个理想格，满足格的理想的偏序包含关系；当a∈Zq时，若取映射关系为Zq上的多项式，则可以构造不同类型的RLWE问题．1.2　格上困难问题定义格上困难问题主要包含如下几类[1,16,18,21]．最短向量问题(SVP)．对于给定的格L，寻找一个非零向量u∈L，使得对任意非零向量s∈L，满足||u||≤||s||．γ-近似最短向量问题(SVP-γ)．对于给定的格L，寻找一个非零向量u∈L，使得对任意非零向量s∈L，满足||u||≤γ||s||．逐次最小长度问题(SMP)．对于给定的秩为n的格L，寻找n个线性无关的向量si，满足λi(L)=||si||(i=1,2,⋯,n)．最短线性无关向量问题(SIVP)．对于给定的秩为n的格L，寻找n个线性无关的向量si∈L，满足||si||≤λn(L)(i=1,2,⋯,n)．最近向量问题(CVP)．对于给定的格L和向量t∈Rm，寻找一个非零向量v∈L，满足对任意非零向量u∈L，||v-t||≤||u-t||．2 格基约减算法2.1　假设与基本方法在求解近似SVP问题上，目前基于格上许多假设的实验数据明显优于理论数据．常用的重要假设如下．假设1 假定求解SVP是NP困难的，且在n维的格中最短向量v的长度期望为||v||L=[Γ(1+n/2)det(L)1/n]/π，其中Γ(∙)为实数域上的伽马函数；det(L)为L的行列式．该假设经常应用在向量的启发式搜索算法中．假设2 假定格L上的元素是稠密、均匀(规范化后)和相互独立存在的，在半径为r的球空间中至少存在2nλ1(2)(L)/r个元素，其中λ1(2)(L)为格L的2范数．格基约减算法的基本思想是在一个格L中，利用以上两个假设设计相应算法，寻找一组具有良好性质的格基B={b1,b2,⋯,bn}来表示该格空间．目前比较实用的基本方法有枚举法和筛法．枚举法一般作为一种确定性算法使用，可以直接输出待求的最短向量，因此枚举法通常认为是精确性SVP算法．但目前SVP的枚举算法复杂度都在很高的指数级别上，一般作为其他算法的辅助算法使用，例如配合LLL算法或BKZ算法，在约减后的格基上进一步使用某种枚举算法．筛法是一种概率算法[12]，按照最短向量的存在假设进行空间的裁剪，使待求解的格被逐渐分解为子格，以降低算法复杂度．在算法理论领域，量子算法相比于经典算法，其速度和处理上限都是后者无法比拟的，尤其在搜索算法中(如Grover算法)，规模为n的问题复杂度最多可以降低到O(n)．例如在量子设置中，理论上枚举280格空间的元素，单线程的计算步骤最多可以降低到240个，但目前量子算法一般通过模拟器的方式实现，不仅难度较大，而且须额外处理输入和输出的编码和测量问题．因此对于求解格上困难问题，使用经典算法和量子算法的研究统一具有重要的意义．2.2　算法分析与比较a. LLL算法．主要步骤是进行格基向量最大程度的正交化，然后通过交换向量位置实现格基向量按照长度排序．算法返回普通格基向量进行施密特正交化产生后的较短向量组成的一组基向量．算法中向量交换的条件是通过逼近因子直接判定，因而计算正交化系数是算法的基本步骤，也是最耗费时间的环节．在空间消耗方面，算法只须保存两组格基和普通格基的正交化系数．LLL算法的缺点也非常明显．一方面，在向量排序上，通过简单交换是粗糙的，同样一个向量可能会出现大量的重复向不同的方向交换；另一方面，算法须要根据当前格基决定的空间逐个计算出正交化结果，然后两两相互比较长度，这会直接导致算法整体效率低．在后续的改进算法中，常使用格基分块、裁剪舍弃或抽样舍弃等手段提高算法性能和效率．b. BKZ算法．首次在格基约减算法中引入了向量分块处理的思想，通过局部优化的方式逐渐获得较高的整体性能．BKZ算法的局部优化继承了LLL算法的约减方法，同时结合了枚举算法与裁剪算法，可以加快局部格基优化的效率．首先在输入参数中指定一个固定分块β的值，该值很大程度上影响了算法执行的效率．然后使用枚举算法搜索分块中的正交化系数，找到满足∑s=jk(∑i=skukui,s)2||bs*||2最小的一组系数，其中：uk和ui,s为枚举过程中的系数组合，k为{j+β,n}中的较大者；bs*为待约减的格基．找到局部最优的正交化系数后，将得到的一个较短向量插入到分块的末尾．最后调用局部的LLL算法，对包含较短向量的前部分向量进行约减．在上述步骤中，BKZ算法通过牺牲部分准确度提高了算法的整体效率，但BKZ算法中β的选择具有较大的随机性，如果选择不好，那么有可能退化到LLL算法．由于使用了枚举及分块相互覆盖的局部优化，因此BKZ算法在性能上有可能不如LLL算法高效，BKZ算法的枚举算法也可能会借助向量数据库进行查询搜索，空间消耗明显增加．c. RS算法．文献[22]依据对格基上短向量的假设和大量的统计分析，提出一种可操作性强的短向量采样算法(SA)．SA算法以较大的概率产生包含较短格基向量的样本空间，可以用于快速约减．借助SA采样算法提出了直接用于格基约减的随机采样算法(RS)，优化产生BKZ算法中的插入向量b=∑i=1nμibi*(μi∈R)．取u=1+(2k)log2(||b1||/||b2||)，则μi满足：当in-u时，μn=1，|μi|≤1/2；当n-u≤in-1时，|μi|≤1．与LLL算法和BKZ算法相比，RS算法从直接生成性质好的短向量出发，找到目标短向量，其随机性更大，本质是一种更大程度的向量裁剪．虽然RS算法可以较大概率得到性质更好的格基向量，也可以在时间复杂度和空间复杂度上实现任意的平衡，但是对于给定的一组普通格基，RS算法的采样过程也存在较大的不确定性，即在实践过程中可能通过重复多次的运行RS算法才能找到一组性质较好的格基，给算法的效率带来了较大不确定性．2.3　算法的一般形式已知的格基约减算法无论采用枚举和筛选的基本思想，还是采用预计算、抽样、局部优化和向量裁剪等加速技术，本质上均属于使用某一种查询路径逐渐接近最优格基．总结现有的格基规约算法求解SVP或近似SVP问题的一般步骤如下．a. 选择LLL算法或BKZ算法对格上的一组基B={b1,b2,⋯,bn}进行初步的约减(或称为预计算)，得到一组比较有序的、近似正交的基B'={b1',b2',⋯,bn'}；b. 选择改进的BKZ算法或RS算法对B'={b1',b2',⋯,bn'}进行基于分块的格基约减，得到足够稀疏的一组格基B″={b1″,b2″,⋯,bn″}；c. 在稀疏基B″={b1″,b2″,⋯,bn″}上再次使用LLL算法，得到范数足够小的或最小的格基B˙={b˙1,b˙2,⋯,b˙n}．3 智能筛选算法实现基于约减的基本步骤，提出智能筛选模型．根据三种不同的优化短向量出现概率的思路，实现了三种不同的智能筛选算法．基于假定1的推论，提出第一个约减思路(基于最优路径筛选法)，即在现有的普通格空间或理想格空间中，已知一组初步约减后的基，根据高斯启发式，判断是否存在一个基的样本空间，符合已知的分布．如果存在或通过假设检验近似存在，那么在这个基的空间里进一步改进随机抽样算法，寻找一定区域范围内的基．上述思路相当于在RS算法基础上通过寻找RS算法中的最优采样路径，进一步抽样强化近似因子．通过重复调用该算法得到给定格上求解的最优路径(如BKZ算法的下标选择路径，成倍降低算法复杂度指数)．算法1 基于最优路径分布的智能筛选算法输入 一组格基{b1,b2,⋯,bn}∈Zn，选择δ1输出 最优路径约减格基{b1',b2',⋯,bn'}BEGINWHILE ||b1||/||b1*||λ，DOb←SA(b1,b2,⋯,bn);SET {b1,b2,⋯,bi-1,b,bi,bi+1,⋯,bn-1}；b'←SA(b1,⋯,bn)；β=|min{j:||πj(b)δ||bj*||2,n+1||}-min{j:||πj(b')δ||bj*||2,n+1||}|;{b1',b2',⋯,bn'}←BKZ((b1,b2,⋯,bn,β))；RETURN {b1',b2',⋯,bn'}．END在算法1中，SA(b1,b2,⋯,bn)为在输入格基上调用短向量采样算法；BKZ((b1,b2,⋯,bn,β))为在输入格基上调用分块为β的BKZ算法；h(b)函数为从1到n逐个比较πj(b)δ||bj*||2，返回最小值，πj(b)用于返回第j个向量的长度．引理1 算法1中输出的向量b满足||b||2/||b1||2≤[kqk-1+(qk+3qn-u-1)/(1-q)]/[12E(|b̂-||v||L|2)]的概率为P{||b||2/||b1||2≤[kqk-1+(qk+3qn-u-1)／(1-q)]/[12E(|b̂-||v||L|2)]}≥q(2k)/2，其中：b1为当前搜索的一组格基；b̂为最近一次采样的一组正交向量；q为实数，满足3/4≤q≤1；k为BKZ算法中的单次枚举规模；u满足1≤u≤log2 q；E(∙)为向量欧氏距离的均值．证明 由文献[23]中引理2可知，向量b满足||b||2/||b1||2≤[kqk-1+(qk+3qn-u-1)/(1-q)]/12，当假定1成立时，将采样位置限定在|b̂|与||v||L之间，即||b||/||b1||在文献[23]中引理2的基础上缩减||b|-||v||L|，在n次下标替换后，||b||2/||b1||2缩减的均值为E(|b̂-||v||L|2)．证毕．通过引理1可知，算法1理论上可以得到比BKZ算法和RS算法更逼近的结果．基于假定2的推论，提出第二个约减思路(逆向验证求解法)，即若L上向量呈现稠密、独立和均匀分布，则对于普通整数格可以利用规范的正交格基向量，构造关于普通格基的矩阵方程，根据结果的秩判定是否得到了包含相对较优的格基．算法2 逆向求解智能验证算法输入 一组格基B={b1,b2,⋯,bn}∈Zn，λ∈Z， λ1输出 最优路径约减格基{b1',b2',⋯,bn'}BEGIN{a1,a2,⋯,an}←SA({b1,b2,⋯,bn})；X←[b1,b2,⋯,bn]*[a1,a2,⋯,an]-1WHILE ||b1||/||b1*||λ，DOFOREACH ai,bj in {a1,a2,⋯,an},X：IF i=j，THEN ai←${1,-1}n；ELSE ai←0．IF ord(X)=n，THEN{b1',b2',⋯,bn'}←BKZ({b1,b2,⋯,bn,β})；X，B←{b1',b2',⋯,bn'}，{a1,a2,⋯,an}．ELSE{a1,a2,⋯,an}←SA({b1,b2,⋯,bn})．RETURN {b1',b2',⋯,bn'}.END引理2 对任意稀疏的正交短向量基A={a1,a2,⋯,an}，一组格基B={b1,b2,⋯,bn}，令X∈Rn×n，满足ATS=BT，若A的秩ord(A)=n，则A在B上，且||S||||B||．进一步，对于给定的逼近长度λ，存在不可忽略的概率找到S，并且满足||S||≤λ．证明 若存在A={a1,a2,⋯,an}使得对于SA算法的输出格基X={x1,x2,⋯,xn}满足ATS=BT，其中||S||||B||，则利用高斯消元算法输出ord(A)，若ord(A)n，则重新选择S，直到ord(A)=n．重复上述步骤k次，直到||S||≤λ，计算P{||Sk||≤λ}≥∏i=1kP{||Si||≤||Si-1||}．又因为每次迭代为独立抽样，所以有P{||Sk||≤||Sk-1||,||Sk-1||≤||Sk-2||,⋯,||S1||≤||B||}．设事件P{||Si||≤||Si-1||}的置信下界为η，因此对任意逼近长度λ，存在正整数k使得P{||Sk||≤λ}≥ηk，其中由于稀疏的正交短向量组成的A使得k≪3n．通过引理2可知，算法2能够在亚指数时间复杂度下找到与已知算法性能近似的结果．在假定2的基础上，提出第三个约减思路(近似最短向量智能筛选法)：首先定义一个用于描述向量正交性的变量T，在概率上当T→0时，称之为性质好的正交性．为简化计算，构造多项式函数f(x)=∑i=0naixi和g(x)=∑i=0nbixi，其中ai和bi为输入格基中任意两组向量的坐标．令T=∑-∞∞am∙ sin(mx)bnsin(nx)+o(x)，即fx和gx的傅里叶级数展开式，则寻找正交的向量a和b问题可以转化为寻找正交的f(x)和g(x)，满足f(1)g(1)=0．在近似求解算法中，可以使用T值的逼近来寻找近似正交的函数．算法3 近似最短向量智能筛选法输入 一组BKZ约减后格基B={b1,b2,⋯, bn}∈Zn，λ∈Z,λ1输出 筛选后的格基{b1',b2',⋯,bn'}BEGINa,b←$SA({b1,b2,⋯,bn})；ε←∑i=0nsin(nx),x→1；WHILE abε，DOPOP a,b；a,b←$SA({b1,b2,⋯,bn})；B←{b1,b2,⋯,bn}∈Zn；WHILE ||b1||/||b1*||λ，DO{b1',b2',⋯,bn'}←BKZ({b1,b2,⋯,bn,β})；RETURN {b1',b2',⋯,bn'}.END算法3中ε为逼近正交的阈值．引理3 对于任意整数向量a,b∈ℒ(B)，存在一组正交的函数基{σ1,σ2,⋯,σn,⋯}，以任意精度满足ab=0的一个充分条件是以a,b为系数的任意周期多项式函数正交．证明 设定义在ℒ上的周期为q的函数f(x)和g(x)，满足∫0qf(x)g(x)dx=0，令x=1，则有∫0qf(1)g(1)dx=0，展开后得∫0qTdx=∫0q[∑-∞∞amsin(mx)bnsin(nx)+o(x)]dx=0.由傅里叶级数的性质可知∫0qTdx一致收敛于∫0qf(1)g(1)dx=0，因此对任意正数ε∫0qf(x)∙ g(x)dx，存在T满足|∫0qTdx-∫0q(∑-∞∞amsin(mx)bn∙ sin(nx)+o(x))dx|ε，式中后项为前项收敛过程中的高阶逼近，即给定ε时，T的结果决定了a,b近似正交的程度．由此可以实现以任意精度正交，证毕．通过调用SA算法产生一个较短向量的样本库，计算出该样本库中任意两组向量的T值，将不满足近似条件的向量从样本库中剔除，从而可以批量产生性质较好的近似正交的短向量，实现过程如算法3．也可以根据实际需求，有针对性地选择不同T值范围内的格向量．4 测试与分析在Darmstadt挑战格[24]上对算法1～3进行了测试，并与BKZ算法和RS算法两种主流的求解算法进行了性能对比．硬件环境为Intel Core i5@3.4 GHz，4 GiB内存，编译环境为C++，算法在NTL和fplll库上实现．在参数选择上，为了方便对比，取BKZ算法维数分块为β=20，维数为60～80，δ=0.1，λ4 000．表1为在文献[23]计算结果的基础上，将近似约减后的格基作为算法1～3的输入得到的结果．表2为剔除了BKZ算法和RS算法运行时间后得出的算法1～3运行时间．10.13245/j.hust.5.T001表1输出结果比较格的维数BKZ算法RS算法算法1算法2算法3602 634λ(2)2 374λ(2)2 191λ(2)1 889λ(2)2 140λ(2)702 385λ(2)2 429λ(2)2 245λ(2)3 618λ(2)2 239λ(2)803 767λ(2)3 356λ(2)2 868λ(2)4 702λ(2)3 133λ(2)10.13245/j.hust.5.T002表2时间消耗比较格的维数BKZ算法RS算法算法1算法2算法36018.0529.3349.8417.3728.587067.6528.35114.1219.0589.208065.56190.61212.5252.63298.27s从表1可知：与RS算法的结果相比，算法1结果缩短了10%～15%，但算法的性能稳定性还须要进一步讨论．算法2直接测试所求的向量是否服从分布，没有借助BKZ算法进行约减，因此结果具有极大的随机性，尤其是在较高维度上的性能不如现有算法．算法3在RS算法的基础上做了进一步智能约减，在性能上有了较明显的均衡提升，对维度的变换与RS算法基本一致．从表2的算法执行时间复杂度上看，算法2远远优于其他算法，但同时也存在运行时间不稳定的问题．算法1和算法3属于进一步约减的算法，比BKZ算法和RS算法更耗时，若从普通格基开始约减，则算法1和算法3更加耗时．5 结语本研究重点围绕格上最短向量求解问题，梳理和对比分析了现有格基约减算法的进展和优缺点，深入挖掘了SVP问题求解的一般途径．在此基础上，提出了一系列求解途径的新猜想(假设)，并从理论上证明这些猜想在提高效率的同时，没有显著提高算法的求解复杂度．同时通过对比现有的格空间分析理论和格基约减算法，指出求解格上困难问题的计算复杂度可能比理论上更低，并通过实验结果证实．随着后互联网、量子计算机和人工智能时代的到来，格上的安全性理论还将面临许多未知的挑战．在新计算工具的影响下，格基约减和最短向量精确输出方面将会出现更高效的算法．这些算法将促进格密码体制的进一步发展，为其安全性基础提供更加可靠的支撑．