LWE問(wèn)題的分析策略及格基約減算法綜述

王鐳璋， 張帥領(lǐng)， 王保倉(cāng)

(1.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710071; 2.中國(guó)電子科技集團(tuán)公司 第三十研究所, 四川 成都 610041)

由于格密碼具有抗量子、高效率、最壞情況/平均情況等價(jià)性和豐富的密碼功能等特點(diǎn)引起了學(xué)術(shù)界的廣泛關(guān)注。第一個(gè)基于格的加密方案是由Ajtai等[1]提出的。后來(lái)Regev[2]對(duì)該方案進(jìn)行了簡(jiǎn)化和改進(jìn)。Regev工作的主要成果之一就是引入了帶錯(cuò)誤學(xué)習(xí)問(wèn)題(Learning With Errors, LWE)，該問(wèn)題在密碼構(gòu)造中使用相對(duì)簡(jiǎn)單，并且至少同最壞情況下SVP的變體問(wèn)題一樣難[2]。目前,LWE問(wèn)題已被證明是加密應(yīng)用程序的通用構(gòu)建模塊([Regev05][2]、[GPV08][3]、[BV11][4]和[ABB10][5])。因此，對(duì)LWE問(wèn)題求解算法的深入分析對(duì)深刻理解格密碼安全性非常重要[6]。

對(duì)LWE問(wèn)題的一個(gè)標(biāo)準(zhǔn)求解做法就是用Kannan嵌入[7]將其歸約到某個(gè)格上的唯一最短向量問(wèn)題(unique Shortest Vector Problem，u-SVP)。而求解格上最短向量問(wèn)題的主流做法是采用格基約減算法進(jìn)行求解。格基約減算法作為格密碼分析研究的核心內(nèi)容，其中對(duì)格基約減算法的預(yù)測(cè)和優(yōu)化仍是目前一個(gè)活躍的研究領(lǐng)域[8]。雖然已有的研究在理論上確實(shí)給出了格基約減算法在最壞情況下性能的邊界定理[9-18]，但這些邊界是漸近的，在應(yīng)用于實(shí)際甚至密碼實(shí)例時(shí)不一定嚴(yán)格[11,14,19]。對(duì)這些算法行為的預(yù)測(cè)依賴于啟發(fā)式和近似，其中一些預(yù)測(cè)已知在某些特定的范圍內(nèi)會(huì)失效[11,20]。隨著格基約減算法的標(biāo)準(zhǔn)化，對(duì)其性能的精確估計(jì)也就成為一個(gè)關(guān)鍵的問(wèn)題。

1 預(yù)備知識(shí)

定義1 格：已知m中的n個(gè)線性無(wú)關(guān)的列向量組B={b1,…,bn}(m≥n)，這組向量的所有整系數(shù)線性組合的集合稱為格L，記為

其中，線性無(wú)關(guān)的向量組B稱為格L的一組基。n為格的秩，m為格的維數(shù)。

定義2 最短向量問(wèn)題(SVP)：給定m中秩為n的格L的一組基B，尋找一個(gè)非零向量u∈L(B)，使得u是L(B)是非零最短向量，即u滿足λ1(L)。

2 LWE問(wèn)題的分析策略以及非基于格的求解算法

2.1 LWE問(wèn)題的分析策略

目前，對(duì)于不同類型LWE問(wèn)題的分析方法主要分為4種策略: SIS 策略、BDD 策略、ISIS策略和直接求解(Direct)策略，見(jiàn)圖1。

圖1 LWE分析策略及方法Fig.1 LWE analysis strategies and methods

對(duì)于不同策略下的求解算法主要有4種：組合算法、代數(shù)算法、基于格的原始攻擊和基于格的對(duì)偶攻擊。非基于格的求解算法就是組合算法和代數(shù)算法2種。組合方法一般指BKW算法[21]，該算法可看作一種擴(kuò)展的高斯消元法,一次處理多個(gè)元素，這種算法最大的問(wèn)題是需要指數(shù)多的樣本。 代數(shù)方法是Arora-Ge算法[22]，該方法是一種非線性化方法，同樣需要指數(shù)多的樣本。思想就是將LWE實(shí)例分成單項(xiàng)式相乘的形式，從而通過(guò)求解單項(xiàng)式的根將秘密向量s各個(gè)分量恢復(fù)出來(lái)。算法關(guān)于維數(shù)是指數(shù)的，對(duì)于錯(cuò)誤向量較小的情況可以降到亞指數(shù)級(jí)別。下面對(duì)組合方法和代數(shù)方法分別進(jìn)行詳細(xì)描述。

2.2 非基于格的求解算法

2.2.1 組合算法

組合算法的代表算法是BKW算法，這是一種特殊的對(duì)偶攻擊方法，最早由Avrim Blum，Adam Kalai和Hal Wasserman提出用來(lái)求解LPN問(wèn)題，該算法能夠以亞指數(shù)的時(shí)間復(fù)雜度2O(n/logn)求解LPN問(wèn)題。由于LWE問(wèn)題可看做LPN問(wèn)題從2到q上的擴(kuò)展，因此，擴(kuò)展版本的BKW算法適用于分析不限制樣本量的LWE類問(wèn)題，基本思路是通過(guò)分塊碰撞的思想，借助廣義生日攻擊的方法在指數(shù)多的樣本中挑選出部分樣本使其加和為0，此時(shí)零向量關(guān)于樣本的系數(shù)向量即為對(duì)偶格中的短向量，由本節(jié)中介紹的對(duì)偶攻擊可知，這些對(duì)偶格中的短向量可以用作LWE實(shí)例的區(qū)分器。

具體來(lái)說(shuō)， BKW構(gòu)造短向量vi的方法如下：給定一組樣本2，BKW分解行向量的n個(gè)分量為a個(gè)塊，每個(gè)塊的寬度為b=n/a。算法共分成a個(gè)階段，第i個(gè)階段通過(guò)充分多的上一級(jí)樣本碰撞(加法運(yùn)算)獲得第i塊元素全零的樣本。假設(shè)初始樣本數(shù)量為2aqb，在最優(yōu)的情況下，算法結(jié)束時(shí)可獲得qb個(gè)長(zhǎng)度為的短向量，使用這些短向量做區(qū)分攻擊的方法與對(duì)偶攻擊中的區(qū)分方法類似，即每個(gè)短向量的區(qū)分優(yōu)勢(shì)為ε=exp[-2π22a(σ/q)2]，大約需要1/ε2個(gè)短向量來(lái)獲得不可忽略的區(qū)分成功率，因此，BKW需要通過(guò)調(diào)整分塊方式來(lái)平衡區(qū)分優(yōu)勢(shì)與樣本數(shù)量以獲得最優(yōu)的算法復(fù)雜度。

BKW算法的主要改進(jìn)技術(shù)包括：Albrecht等[23]在PKC 2014上提出的Coded-BKW算法中求解小密鑰版本的LWE問(wèn)題所采用的Lazy Modulus Switching技術(shù)；2015年，文獻(xiàn)[24-25]分別獨(dú)立提出的通過(guò)使用不同大小的分塊平衡BKW算法復(fù)雜度的技術(shù)；2017年，Guo等[26]提出的在BKW算法中結(jié)合篩法的改進(jìn)技術(shù)，該算法是當(dāng)前具有最優(yōu)時(shí)間復(fù)雜度的BKW類算法。

2.2.2 代數(shù)攻擊——Arora-Ge算法

代數(shù)攻擊最早由Arora等[22]提出，適用于不限制樣本量的LWE類問(wèn)題，它的基本思路是：構(gòu)建以錯(cuò)誤e為根的無(wú)噪音非線性多項(xiàng)式方程組，通過(guò)代換所有單項(xiàng)式構(gòu)成線性方程組并求解。具體來(lái)說(shuō)，給定LWE實(shí)例矩陣(A,b=As+e)，根據(jù)錯(cuò)誤分布(高斯分布和小均勻分布等)的性質(zhì)可知錯(cuò)誤分布e在有界區(qū)間[-t,t]中(t∈,d=2t+1

由于BKW算法和Arora-Ge算法需要指數(shù)級(jí)別的實(shí)例數(shù)，而現(xiàn)實(shí)中的格基加密方案至多泄露關(guān)于LWE實(shí)例維數(shù)n的多項(xiàng)式多個(gè)實(shí)例([Regev05]型加密方案至多泄露nlogq個(gè)實(shí)例，[LP11]型加密方案[28]至多泄露2n個(gè)實(shí)例)。因此，針對(duì)實(shí)際方案的攻擊，以上2種求解算法均無(wú)法實(shí)施。針對(duì)實(shí)際方案的攻擊一般使用的是基于格的攻擊方法。

3 基于格的求解方法

針對(duì)判定性LWE問(wèn)題采用SIS策略，歸約到求正交格上短向量。針對(duì)搜索型LWE問(wèn)題，根據(jù)其秘密向量s的模長(zhǎng)大小采用不同的策略。如果是標(biāo)準(zhǔn)型(Standard form)LWE問(wèn)題則采用使用BDD策略的原始攻擊或是Decoding方法；如果是Normal Form LWE或是Binary LWE應(yīng)當(dāng)充分利用秘密向量s的模長(zhǎng)很短這一信息，從而應(yīng)該使用ISIS策略的對(duì)偶攻擊。

3.1 判定性LWE問(wèn)題

3.1.1 SIS策略

3.1.2 BDD策略

[LP11][28]中的Decoding策略強(qiáng)于區(qū)分攻擊，因?yàn)镈ecoding策略直接將噪聲向量e恢復(fù)出來(lái)，實(shí)際也可以視為是求解Search-LWE問(wèn)題的一種方法。但該策略在使用比區(qū)分攻擊質(zhì)量更差的格基時(shí)仍有著一樣甚至更好的優(yōu)勢(shì)。其基本思想是將LWE實(shí)例中將b視作Λq(A)格上BDD問(wèn)題的目標(biāo)向量，然后直接利用最近平面算法找到距離b最近的格點(diǎn)As。該策略成功當(dāng)且僅當(dāng)錯(cuò)誤向量e落到P1/2(B*)內(nèi)下面給出直接使用Babai算法[29]找到格點(diǎn)As的概率估計(jì)：

LP最近平面算法,[LP11][28]中的優(yōu)化最近平面算法在每一次執(zhí)行尋找當(dāng)前距離目標(biāo)向量最近的超平面操作時(shí)，從原先的只選距離目標(biāo)向量最近的超平面改成：選擇di個(gè)超平面(i∈+)，如此將P1/2(B*)往每個(gè)方向上擴(kuò)大為原來(lái)的di倍，使得e落入P1/2(B*)的概率增大。同時(shí)，新算法要記錄下全部個(gè)候選值，并分別計(jì)算它們到目標(biāo)向量b的距離，取其中距離最小的作為其優(yōu)化最近平面算法輸出結(jié)果。如此在付出次對(duì)(B,b)的Babai算法的計(jì)算開(kāi)銷下，算法的成功率增大為

3.2 搜索型LWE問(wèn)題

3.2.1 BDD策略-原始攻擊

針對(duì)搜索型LWE問(wèn)題，BDD策略先是將搜索型LWE問(wèn)題歸約到某個(gè)q-ary格上的BDD問(wèn)題，再利用Kannan嵌入[7]將q-ary格上的BDD問(wèn)題歸約到最終構(gòu)造格上的uSVP進(jìn)行求解。根據(jù)LWE問(wèn)題中s的分布不同，最終構(gòu)造的格基的形式有所不同。

最早提出該策略的是文獻(xiàn)[28]，特別地，給定分布Ls,通過(guò)采樣獲得實(shí)例滿足：

其中，A2是由均勻采樣獲得，e來(lái)源于錯(cuò)誤分布, 另外階模q下可逆方陣。在文獻(xiàn)[28]中通過(guò)不斷地從分布Ls,中抽取生成新的實(shí)例直到這些實(shí)例形成可逆方陣A1，并直接丟掉其余實(shí)例。易知：

其格基矩陣M為

以上提到2種格攻擊一般稱為原始攻擊，其成功條件(08估計(jì)[10]見(jiàn)3.2.3節(jié)) 是相同的，即2種格基在求解標(biāo)準(zhǔn)型LWE 問(wèn)題本質(zhì)上沒(méi)有區(qū)別。

3.2.2 ISIS策略-對(duì)偶攻擊

針對(duì)秘密向量s很短的正規(guī)型LWE問(wèn)題，以及二進(jìn)制型LWE問(wèn)題，除了使用BDD策略的原始攻擊，[BG14][31]提出了一種更高效的求解策略：將Normal Form(Binary)型LWE問(wèn)題視為ISIS問(wèn)題進(jìn)行求解，充分利用了s也很短這一信息。一般將使用ISIS策略的[BG14]型攻擊稱為對(duì)偶攻擊[31]。歸約的思路可以概況如下：

Normal Form(Binary) LWE≤ISIS≤BDD≤u-SVP,

其中，第三個(gè)不等號(hào)處使用了Kannan嵌入。更詳細(xì)的過(guò)程如下：

給定服從分布Ls,選取的m個(gè)LWE實(shí)例考慮ISIS實(shí)例：

存在整系數(shù)線性組合u=(s|*|1)，使得uM=(s|e|1)是Λ(M)上短向量。

3.2.3 2種攻擊方式的比較

上述2種不同攻擊策略的區(qū)別在于：Bai等[31]的格基更有效地利用了s與e同分布時(shí)，s也是很短的這一信息，相較于原始攻擊中的格基[30],文獻(xiàn)[31]有更弱的攻擊成功條件。下面先給出求解u-SVP的理論條件再對(duì)2種攻擊進(jìn)行更詳細(xì)的比較。

原始攻擊的格基的gap為

而對(duì)偶攻擊的格基的gap為

此外，Bai等[31]的格基無(wú)需實(shí)例組成的n階方陣要在模q下求逆，因此對(duì)實(shí)例的數(shù)量沒(méi)有嚴(yán)格的要求。但原始攻擊中的格基因?yàn)樾枰獙?shí)例組成的n階方陣要在模q下可逆，因而只能用于求解實(shí)例個(gè)數(shù)m大于n的情況。

值得注意的是Bai等的格基也只能用于求解Normal Form LWE(s與e同分布)問(wèn)題，對(duì)s取自均勻分布的Standard LWE問(wèn)題無(wú)法直接使用。而原始攻擊的格基就不存在這個(gè)問(wèn)題，它們的格基對(duì)s取任意分布的LWE問(wèn)題都是適用的。值得注意的是，對(duì)于Standard LWE問(wèn)題，可以使用T變換[28]，在花費(fèi)不超過(guò)O(n2)的實(shí)例下，將其轉(zhuǎn)化為Normal Form LWE問(wèn)題。從而使用Bai等的格基去更高效地求解。2種不同的格基優(yōu)劣勢(shì)見(jiàn)表1。

表1 Primal攻擊中2種不同格基的優(yōu)劣勢(shì)

文獻(xiàn)[30]中有結(jié)論：對(duì)于普通形式的LWE(除Normal Form LWE以外)，Kannan嵌入和Dual嵌入的效果基本無(wú)差別。

該估計(jì)與BKZ類算法的實(shí)際實(shí)驗(yàn)結(jié)果更為貼切。目前，NIST第三輪中基于LWE困難假設(shè)方案的比特安全強(qiáng)度均采用這種由文獻(xiàn)[33]中提出的保守估計(jì)(采用最為保守Core-SVP模型，詳情見(jiàn)表2)[34-35]。該估計(jì)通過(guò)選擇試遍實(shí)例數(shù)m的可取值(對(duì)標(biāo)準(zhǔn)型LWE來(lái)說(shuō)m∈(0,nlogq)，對(duì)Normal Form和Binary 型LWE來(lái)說(shuō)m∈(0,2n))，求出當(dāng)前m下使得上述不等式成立的最小β值的方法，找到使得攻擊開(kāi)銷最小的(m,β)對(duì)，最后用Core-SVP模型估計(jì)出求解方案的安全參數(shù)設(shè)置下LWE問(wèn)題的計(jì)算開(kāi)銷作為方案的比特安全強(qiáng)度。

表2 SVP求解器復(fù)雜度估計(jì)模型

使用文獻(xiàn)[33]中的估計(jì)對(duì)上述2種攻擊策略與使用08估計(jì)[10]得到的結(jié)論一致。

3.2.4 對(duì)Binary型LWE問(wèn)題攻擊的加速技術(shù)

另外，針對(duì)Binary LWE問(wèn)題，其秘密向量s的每個(gè)分量都取自{0,1}或{-1,0,1}，使用全同態(tài)加密中的模轉(zhuǎn)換技術(shù)和文獻(xiàn)[31]中的Rescale技術(shù)，可以讓最終構(gòu)造格基的gap增大，降低攻擊算法的復(fù)雜度。此外，利用組合攻擊也可以一定程度上降低求解秘密向量分布稀疏的LWE問(wèn)題復(fù)雜度[36-38]。

(1)模轉(zhuǎn)換技術(shù)

模轉(zhuǎn)換是全同態(tài)加密中為加速模乘運(yùn)算速度提出的技術(shù)。因?yàn)楣潭ㄆ渌麉?shù)、縮小模數(shù)，將使得計(jì)算效率提升。但注意到模轉(zhuǎn)換技術(shù)雖然減少了模數(shù)，但也將引入一部分額外的噪聲。對(duì)于求解LWE問(wèn)題來(lái)說(shuō)，噪聲的增大會(huì)導(dǎo)致LWE問(wèn)題的求解越發(fā)困難。因此將大模數(shù)q換成小模數(shù)p的模轉(zhuǎn)換操作需要合適地取p的值。

其中，u∈,e′∈[-0.5,0.5],x,yp表示在模p的意義下對(duì)向量x和y求內(nèi)積。

如上文所述，當(dāng)模數(shù)p減小時(shí)，算法的時(shí)間復(fù)雜度會(huì)降低；但是當(dāng)p取得過(guò)小時(shí)，又會(huì)造成噪音規(guī)模的增加，導(dǎo)致解決這個(gè)實(shí)例的困難度增加，因此，p的取值需要平衡這兩者之間的矛盾。最優(yōu)的p值的選擇可以使得(p/q)·a-「(p/q)·a?,s≈|(p/q)·e|，即在模轉(zhuǎn)換后的錯(cuò)誤規(guī)模大致放縮為原來(lái)的p/q，據(jù)此，可以計(jì)算出p的最優(yōu)取值約等于

模轉(zhuǎn)換技術(shù)可用于原始攻擊和對(duì)偶攻擊中。

(2)Rescale技術(shù)

Rescale技術(shù)由Bai等[31]在2014年提出，這種技術(shù)可以被應(yīng)用在Dual嵌入中，并將其稱為BG嵌入。在BG嵌入中，嵌入格被修改為L(zhǎng)(M)={x∈νn×m+1|x·(A|Im|-b)T=0modq}形式，基且有(s|*|1)·M=(vs|e|1)。在普通的Dual嵌入情況下時(shí)， 當(dāng)v=1，由于s每個(gè)分量很小或很稀疏時(shí)，向量(s|e|1)的各個(gè)部分的模長(zhǎng)是不一樣長(zhǎng)的。要使才能將目標(biāo)向量的各個(gè)部分變成均衡的，即需要選擇合適的v值使得可以使得調(diào)整后的向量 (‖vs|e|1‖)就是L(M)中的一個(gè)最短向量，且利用格基約化算法找到它變得更加高效[31]。因?yàn)閷?shí)際實(shí)驗(yàn)表明格基約減算法更加傾向于輸出每個(gè)分量值都比較均衡的短向量[34]。以為例，有因此，令可以算出那么有

(3)組合攻擊

在秘密向量s取值稀疏的情況下, 如{0,1}或{-1,0,1}采用組合攻擊[36-39]，即給一個(gè)秘密s最多w

4 格基約減算法

經(jīng)過(guò)上述分析可知，無(wú)論是求解判定性LWE問(wèn)題還是求解搜索型LWE問(wèn)題，都是通過(guò)構(gòu)造某個(gè)格基將LWE問(wèn)題轉(zhuǎn)化為構(gòu)造格上的u-SVP問(wèn)題進(jìn)行求解，或是對(duì)構(gòu)造格的格基進(jìn)行約減得到質(zhì)量足夠“好”的格基，從而能夠成功解碼出目標(biāo)向量。所以高效的格基約減算法是求解LWE問(wèn)題的主要方法。作為求解近似SVP和近似CVP的近似算法，目前主要的格基約減算法有LLL、基于枚舉的BKZ類以及基于篩法的General Sieve Kernel(G6K),其中,基于近些年篩法發(fā)展最新結(jié)果的G6K是當(dāng)前最快的格基約減算法。在簡(jiǎn)單地回顧經(jīng)典的LLL和BKZ類之后，將著重介紹G6K算法。介紹格基約減算法之前，首先將BKZ類以及G6K算法所基于的SVP求解算法做一下梳理。

4.1 SVP求解算法

4.1.1 枚舉法

枚舉算法的優(yōu)勢(shì)是算法開(kāi)始后是確定性的，且只使用多項(xiàng)式大小的空間。其缺點(diǎn)就是時(shí)間復(fù)雜度是超指數(shù)的O(2nlog(n))。此外，多年來(lái)已經(jīng)開(kāi)發(fā)了一些優(yōu)化和啟發(fā)式方法，使得枚舉目前在實(shí)踐中對(duì)于較小的維度最具吸引力。枚舉是一種通過(guò)系統(tǒng)地枚舉空間中某個(gè)給定半徑的超球(通常是n維平行六面體或橢球體)內(nèi)所有格點(diǎn)來(lái)解決任意格上最短向量問(wèn)題(SVP)和最近向量問(wèn)題(CVP)的標(biāo)準(zhǔn)技術(shù)。人們對(duì)格枚舉技術(shù)的興趣主要是由于它們的低內(nèi)存需求(關(guān)于格的維數(shù)n是線性的)，以及在中等低維數(shù)上優(yōu)異的實(shí)際性能。枚舉算法的運(yùn)行時(shí)間在很大程度上取決于輸入格基的質(zhì)量。因此，使用格基約減算法對(duì)輸入格進(jìn)行適當(dāng)?shù)念A(yù)處理是枚舉法的重要組成部分。最早考慮執(zhí)行預(yù)處理后再做枚舉的是文獻(xiàn)[40-41]，其中，文獻(xiàn)[40]使用的是LLL算法作為預(yù)處理，經(jīng)過(guò)LLL算法處理后，再執(zhí)行枚舉求解出最短向量的開(kāi)銷是2O(n2)。而Kannan[41]提出了一種更加復(fù)雜的預(yù)處理方法，對(duì)枚舉算法進(jìn)行低維遞歸調(diào)用，將(總)漸近運(yùn)行時(shí)間減少到nO(n)。文獻(xiàn)[42]則給出了Kannan算法在最好情況下時(shí)間復(fù)雜度的最優(yōu)分析。文獻(xiàn)[42]表明Kannan算法求解SVP的時(shí)間為nO(n/(2e))。然而，由于其指數(shù)時(shí)間的預(yù)處理開(kāi)銷，對(duì)實(shí)際可以執(zhí)行枚舉算法的維數(shù)n來(lái)說(shuō)，Kannan算法并不比漸近復(fù)雜度更劣勢(shì)的方法(如文獻(xiàn)[40]基于多項(xiàng)式時(shí)間格基約減算法的變體)快。2015年，Micciancio等[43]引入了 Kannan算法的變體,該算法的漸進(jìn)時(shí)間是同Kannan算法一樣的nO(n)，但文獻(xiàn)[43]所需預(yù)處理開(kāi)銷更少，使得該算法在中低維的枚舉方法中有著很強(qiáng)的競(jìng)爭(zhēng)力。在實(shí)際使用時(shí)，枚舉算法的有效實(shí)現(xiàn)需要大量使用浮點(diǎn)運(yùn)算，但由于舍入誤差和精度問(wèn)題，浮點(diǎn)運(yùn)算可能相當(dāng)棘手。有關(guān)使用浮點(diǎn)運(yùn)算的SVP枚舉的詳細(xì)分析，請(qǐng)參閱文獻(xiàn)[44]。

2021年，文獻(xiàn)[45-48]將近幾年枚舉的新技術(shù)，如文獻(xiàn)[45-47]中放松裁剪枚舉算法條件的技術(shù)，以及文獻(xiàn)[48]中擴(kuò)展預(yù)處理技術(shù)相結(jié)合，提出了漸進(jìn)復(fù)雜度更低的枚舉算法，其漸進(jìn)復(fù)雜度為nO(n/(8))。此外，他們將這個(gè)新的枚舉算法應(yīng)用到BKZ(2.0)算法中，減少了基于篩法實(shí)現(xiàn)的BKZ算法[13]與基于枚舉實(shí)現(xiàn)的BKZ算法之間實(shí)際性能的差距[49]。

4.1.2 篩法

篩法是通過(guò)在固定半徑的球殼上堆積格點(diǎn)來(lái)求解最短向量問(wèn)題。2001年，Ajtai等[50]提出的隨機(jī)篩法被認(rèn)為是最早且最著名的指數(shù)空間復(fù)雜度算法之一，它的時(shí)間復(fù)雜度和空間復(fù)雜度均為2O(n)。其后，Regev[51]、Nguyen等[52]、Micciancio等[53]，先后給出了AKS篩法更準(zhǔn)確的時(shí)間和空間復(fù)雜度估計(jì)，分別為23.4n+o(n)和21.97n+o(n)。Micciancio等[53]提出了一種確定性的算法，ListSieve該算法將時(shí)間和空間復(fù)雜度分別改進(jìn)到了23.199n+o(n)和21.325n+o(n)，該方法結(jié)合生日攻擊可以在22.465n+o(n)的時(shí)間內(nèi)找到最短向量。2015年，Aggarwal等[54]基于離散高斯采樣提出了新的隨機(jī)算法，將時(shí)間復(fù)雜度進(jìn)一步改進(jìn)到了2n+o(n)，此外，在啟發(fā)式假設(shè)下，篩法的復(fù)雜度上界可以進(jìn)一步降低。2008年，Nguyer等[52]基于AKS篩法提出了第一個(gè)隨機(jī)啟發(fā)式篩法，分別達(dá)到了20.415n+o(n)和20.207 5n+o(n)的時(shí)間和空間復(fù)雜度，其他啟發(fā)式篩法的改進(jìn)工作還包括二重篩法和三重篩法[55-58]等，當(dāng)前已知最高效的經(jīng)典計(jì)算機(jī)模型下的篩法是由Anja等[59]提出的，該算法實(shí)現(xiàn)了時(shí)間和空間復(fù)雜度的平衡，2者均見(jiàn)文獻(xiàn)[59-60]。在量子計(jì)算模型下，Larhoven等[60]通過(guò)Grover算法將上述篩法的時(shí)間復(fù)雜度進(jìn)一步改進(jìn)為20.265n+o(n)[60]。Voroni細(xì)胞算法是由Daniele等[61]于2010年提出的一種新型確定性算法，該算法利用格點(diǎn)的Voronoi細(xì)胞結(jié)構(gòu)，將求解相關(guān)向量問(wèn)題的方法用于求解最近向量問(wèn)題的預(yù)處理，其時(shí)間和空間復(fù)雜度約為22n+o(n)和2n+o(n)。

4.2 對(duì)經(jīng)典格基約減算法的梳理

4.2.1 LLL算法

LLL算法是一個(gè)多項(xiàng)式時(shí)間算法[62], 可視為是在二維拉格朗日/高斯算法在高維空間上的擴(kuò)展。理論上,LLL算法的Hermite因子根可以達(dá)到δ0=(4/3)(n-1)/4n≈1.075,而實(shí)際運(yùn)行LLL算法的輸出結(jié)果要好過(guò)其理論結(jié)果，LLL算法的Hermite因子根實(shí)際可達(dá)1.021 9[10]。在小維數(shù)格上，LLL算法甚至能求出最短向量。

LLL算法的細(xì)節(jié)描述:

定義5 (LLL約減基) 一組基B={b1,b2,…,bn}∈n稱為L(zhǎng)(B)的δ-LLL既約基，如果以下條件成立：

1.?1≤i≤n,j

下面的定理說(shuō)明了，這樣的基是存在的并且能夠在多項(xiàng)式時(shí)間內(nèi)找到。

定理1任給格基B={b1,b2,…,bn}∈n，任意1/4

LLL算法的實(shí)現(xiàn)細(xì)節(jié)：

輸入：格基b1,b2,…,bn∈n及參數(shù)y；

輸出：L(B)的y-LLL約減基.

2. 循環(huán)for(i=2,2≤i≤n,i++)

3. 循環(huán)for(j=i-1,1≤j≤i-1,j--)

5.endfor

6.endfor

8.bi?bi+1

9. goto 1

10.endif

11. 輸出b1,b2,…,bn

接下來(lái)，給出y-LLL約減基的一些性質(zhì)，為了表述簡(jiǎn)單，令y=3/4，對(duì)于其他的1/4

性質(zhì)：令b1,b2,…,bn為格L∈n的一組LLL既約基，為其相應(yīng)的Gram-Schmidt正交化，則

3. 對(duì)任意t≤n個(gè)線性無(wú)關(guān)向量x1,x2,…,xn∈L，則對(duì)1≤j≤t,有

4.2.2 BKZ類算法

(1)BKZ算法

BKZ算法是由Schnorr等[9]應(yīng)用分塊約減的思想改進(jìn)LLL算法而提出的。衡量BKZ算法的關(guān)鍵參數(shù)是分塊大小的β，β越大，BKZ輸出約減基的質(zhì)量越好，輸出的最短向量也越短，但同時(shí)算法運(yùn)行時(shí)間也越長(zhǎng)。

BKZ算法的每一輪會(huì)依次在L[i:i+β]上運(yùn)行枚舉算法(其中，i∈{1,2,…,n-β}，當(dāng)i∈{n-β+1,…,n}時(shí)，則在L[i:n]上運(yùn)行枚舉算法)，并將枚舉出的最短向量嵌入格基B，然后用LLL算法去除線性相關(guān)性，從而逐漸提高格基質(zhì)量。當(dāng)某一輪運(yùn)行結(jié)束后，最短向量模長(zhǎng)與上一輪輸出的結(jié)果相比沒(méi)有改變，則BKZ算法終止，并輸出當(dāng)前的最短向量。下面給出BKZ算法輸出基的質(zhì)量和算法運(yùn)行時(shí)間的估計(jì)。

1)質(zhì)量估計(jì)

2)時(shí)間估計(jì)

(2)BKZ2.0算法

2011年，Chen等[14]對(duì)BKZ算法進(jìn)行了4點(diǎn)改進(jìn)，得到BKZ2.0算法[65]：

1)提前終止算法：原始BKZ算法的運(yùn)行終止條件是執(zhí)行完本輪約減得到的格基較之上一輪約減得到的格基沒(méi)有任何變化，則終止BKZ算法。但文獻(xiàn)[11]等實(shí)驗(yàn)表明，BKZ算法執(zhí)行一定的輪數(shù)后，繼續(xù)執(zhí)行BKZ算法對(duì)格基質(zhì)量的改善作用越來(lái)越少。但要達(dá)到格基不能作進(jìn)一步改善的條件，仍需執(zhí)行很多輪BKZ。因此，BKZ2.0將算法的終止條件改成格基的質(zhì)量無(wú)明顯改善時(shí)終止。

2)極度裁剪：如4.1.1小節(jié)中所描述那樣，枚舉通過(guò)搜索固定某個(gè)半徑內(nèi)的n維平行六面體或橢球體內(nèi)所有的格點(diǎn)來(lái)解決任意點(diǎn)陣上最短向量問(wèn)題。Gama等[68]通過(guò)重復(fù)多次：隨機(jī)地裁剪掉搜索空間中絕大部分格點(diǎn)，只枚舉剩下的少量格點(diǎn)的極度裁剪枚舉，獲得了總時(shí)間開(kāi)銷更少的枚舉算法。

3)強(qiáng)預(yù)處理：原始的BKZ算法在執(zhí)行前是使用LLL算法做格基的預(yù)處理。BKZ2.0算法采用比輸入分塊大小更小的BKZ算法做BKZ2.0算法執(zhí)行前的預(yù)處理。這樣雖然使得預(yù)處理的開(kāi)銷比原來(lái)大，但能獲得比LLL算法輸出基質(zhì)量更高的預(yù)處理結(jié)果，如此可有效降低調(diào)用枚舉算法的計(jì)算開(kāi)銷[37]。

4)優(yōu)化枚舉算法的搜索半徑：原始BKZ算法調(diào)用枚舉算法求解投影子格上的最短向量時(shí)枚舉空間的搜索半徑都是固定的。但實(shí)際上隨著枚舉的層數(shù)逐漸增加，目標(biāo)向量下一個(gè)坐標(biāo)的可能取值范圍是逐漸減少的。BKZ2.0對(duì)枚舉每一層的搜索半徑進(jìn)行了估計(jì)，并用優(yōu)化的估計(jì)半徑代替了原先固定的大半徑，減少了枚舉算法的計(jì)算開(kāi)銷[14]。

其中，2)～4)有3個(gè)改進(jìn)的目的都是減少BKZ在調(diào)用枚舉算法時(shí)的計(jì)算開(kāi)銷。

此外，基于BKZ2.0算法，2021年，Albrecht等將放松裁剪條件[45-47]以及擴(kuò)展預(yù)處理等技術(shù)[48]相結(jié)合提出了新的BKZ算法，減少了基于篩法實(shí)現(xiàn)的BKZ算法[13]與基于枚舉實(shí)現(xiàn)的BKZ算法之間實(shí)際性能的差距[49]。

(3)Progressive-BKZ算法

2016年，Aono等[45]對(duì)BKZ算法中分塊長(zhǎng)度β的取值方式進(jìn)行了更細(xì)致的分析，提出了漸近型BKZ(Progressive-BKZ,P-BKZ)算法。P-BKZ算法與BKZ，BKZ2.0最大的不同就是其分塊的大小不是固定的,而是隨著P-BKZ算法的執(zhí)行由一個(gè)小的初值逐漸增大。P-BKZ算法通過(guò)合適選取的分塊大小初值和遞增值，使得算法整體的時(shí)間復(fù)雜度最優(yōu)。與BKZ2.0相比，P-BKZ算法在解決最高160維的SVP挑戰(zhàn)(SVP challenge)[15]時(shí)比BKZ2.0最多可以快約50倍[45]。

(4)BKZ算法模擬器

最早的BKZ模擬器由Chen等[14]提出。此后Aono等觀察到BKZ約化基Gram-Schmidt范數(shù)曲線相對(duì)于GSA 曲線的“頭部凹陷”現(xiàn)象并提出了分析和利用它提升BKZ效率的方法，并作出一個(gè)新的模擬程序。2017年，Yu等[69]進(jìn)行了大量實(shí)驗(yàn)對(duì)BKZ的實(shí)際行為進(jìn)行了評(píng)估，對(duì)于BKZ約化基Gram-Schmidt正交化后范數(shù)的分布進(jìn)行了更為細(xì)致的研究，并且通過(guò)觀察結(jié)果更準(zhǔn)確地量化了“頭部凹陷”現(xiàn)象。2018年，Bai等[70]通過(guò)考慮隨機(jī)格中短向量的分布又提出了一個(gè)更為精確的BKZ模擬程序，很好地模擬并解釋了“頭部凹陷”現(xiàn)象，并利用該現(xiàn)象構(gòu)造了Pressed-BKZ算法。同時(shí)指出該現(xiàn)象隨著分塊大小的增大而不再明顯，在分塊大小約為200時(shí)，該現(xiàn)象幾乎完全消失。

(5)Slide-BKZ算法

(6)對(duì)BKZ類算法計(jì)算開(kāi)銷的估計(jì)

根據(jù)文獻(xiàn)[72]中的實(shí)驗(yàn)結(jié)果，一些研究者將時(shí)間成本估計(jì)式中的o(β)省略或者替換為常數(shù)16.4。另外，文獻(xiàn)[72]還對(duì)空間和時(shí)間綜合考慮，在空間復(fù)雜度最低的情況下，成本模型中的參數(shù)c=0.336 6，o(β)替換為常數(shù)12.31。在進(jìn)行安全性評(píng)估時(shí)，根據(jù)考慮的SVP oracle調(diào)用次數(shù)，可將其分為3種模型: Core-SVP模型[33]、β-SVP模型[73]和8m-SVP模型[36]。值得注意的是，文獻(xiàn)[13]的結(jié)論指出8m-SVP模型是一個(gè)過(guò)高的估計(jì)(不再保守)，但文獻(xiàn)[13]的結(jié)論仍未打破Core-SVP模型的下界，因此，使用Core-SVP模型進(jìn)行估計(jì)仍是保守的。

4.3 G6K算法

4.3.1 G6K算法的CPU實(shí)現(xiàn)

General Sieve Kernel(G6K) 是Albrecht等[13]于2019年提出的一種基于篩法的可以執(zhí)行各類格基約減策略的抽象狀態(tài)機(jī)。這個(gè)抽象的狀態(tài)機(jī)可以通過(guò)調(diào)整不同的約減策略去執(zhí)行目前已有的各種格基約減算法，如經(jīng)典的BKZ算法。但值得注意的是，經(jīng)典BKZ算法是基于枚舉算法作為其在約減過(guò)程中求投影子格上最短向量時(shí)的Oracle調(diào)用，而G6K是基于篩法執(zhí)行其格基約減策略的。同時(shí)，使用篩法的G6K不僅僅像經(jīng)典BKZ類那樣將枚舉算法作為一個(gè)黑盒調(diào)用，只輸出一個(gè)短向量，而是構(gòu)造了一個(gè)篩法的數(shù)據(jù)庫(kù)，存儲(chǔ)著篩法篩出的大量相當(dāng)短的向量。

G6K結(jié)合并擴(kuò)展了近年來(lái)篩法的最新優(yōu)化改進(jìn)成果，其中主要代表是Ducas[19]在2018年歐密上對(duì)子篩法的研究。提出對(duì)于求解n維格上SVP，對(duì)這個(gè)n維格的n—d維投影子格做篩法，而不是對(duì)n維完整格做篩法，并利用最近平面算法從投影子格篩出的候選短向量中提升出n維完整格上最短向量的策略。將求解n維格上SVP降低至求解n—d維投影子格上SVP，理論上d=O(n/logn)時(shí)，Ducas證明子篩法均可成功[19]。實(shí)際上自由維數(shù)d的取值可能比理論估計(jì)更大，需要根據(jù)實(shí)例具體實(shí)驗(yàn)才能準(zhǔn)確得到。此外，G6k中還利用的一項(xiàng)技術(shù)是Laarhoven等[74]在2018年P(guān)QC 上提出的漸進(jìn)篩。其主要思想與Progressive BKZ的想法類似，從小的投影子格開(kāi)始做篩法，然后逐漸增大所篩子格維數(shù)，利用投影子格上已篩出的短向量組成的數(shù)據(jù)庫(kù)加速加入新格基向量后做篩法的速度。下面給出這2個(gè)技術(shù)的詳細(xì)描述。

(1)Dimension for free[19]

Ducas 提出的Dimension for free(Dimforfree)技術(shù)。Dimforfree技術(shù)的主要思想是：對(duì)于要求解的n維格上最短向量問(wèn)題并不是像之前一樣對(duì)整個(gè)n維格直接進(jìn)行篩法求解，而是只需幾次調(diào)用在n—d維原格投影子格上的篩法，以及利用低維格上的最近平面算法，將投影子格上求解出的短向量提升到n維完整格上的最短向量的組合算法。如此，就將最耗時(shí)的篩法所篩格的維數(shù)從n維降至n—d維。其中，d=n/logn時(shí)，Ducas[19]證明該子篩法仍能夠成功，盡管Ducas這個(gè)改進(jìn)的提升只是亞指數(shù)的2n/logn，但在實(shí)際實(shí)驗(yàn)中有顯著的提升效果。需要指出的是，具體實(shí)現(xiàn)時(shí)，Ducas同樣沒(méi)有找到一個(gè)很好的對(duì)d的準(zhǔn)確估計(jì)，只能通過(guò)實(shí)際測(cè)試的方法從大的d值逐漸減少，直到d減少到能求出原問(wèn)題的解。

Ducas的具體做法是：d先選一個(gè)很大的值，如n/4，然后d每次減少1，直到子篩法最終找到最短向量(d減小到n/logn時(shí)，就達(dá)到理論上子篩法成功條件了)，取更大的d純粹為了更快求解。

對(duì)n維格的n—d維投影子格Ld做篩法:

Ducas利用Dimforfree技術(shù)構(gòu)造了一個(gè)能求出近似HKZ 約減基的子篩法+算法，最后，再用輸出的近似HKZ 約減基V代替當(dāng)前格L的格基向量，作為新的輸出格基B。具體做法就是利用LLL 算法對(duì)[V|B]進(jìn)行約減，并去除其中線性相關(guān)的部分。

(2)[LM18] 漸近篩法[74]

[LM18] 漸近篩法的基本思想是首先對(duì)輸入格基做格基約減的預(yù)處理。其次從某個(gè)維數(shù)小于完整格的維數(shù)子格開(kāi)始做篩法，篩出的結(jié)果中實(shí)際上已經(jīng)包含了很多短的格向量，通過(guò)這些信息，可以更快地找到完整格上近似最短向量。一個(gè)更清晰地解釋漸進(jìn)篩比經(jīng)典篩法更快的理由是：當(dāng)篩法輸入的格基約減程度越高(格基質(zhì)量越好)，那么在較低維數(shù)的子格中，篩法會(huì)找到更短的格向量并將其添加到列表L中，而列表中有更短的向量，意味著：擴(kuò)大子格維數(shù)后，重新抽樣得到的新的格向量可以更容易更快地被已經(jīng)在列表中的短向量所約減。由于在經(jīng)典的篩法(直接在高維格上執(zhí)行篩法)中需要花費(fèi)更長(zhǎng)的時(shí)間先找到(近似)較短的格向量。同時(shí)經(jīng)典的篩法不能像漸進(jìn)篩一樣，在這種加速約減中獲益(在每一個(gè)低維子格中篩出的更短向量都將有助于列表中向量的質(zhì)量，讓下一次抽樣出的新向量被更短的向量所約減)。[LM18][74]相信在很大程度上解釋了當(dāng)使用約減程度更高的格基作為漸近篩的輸入時(shí)，所帶來(lái)的計(jì)算效率上的有效提升。

漸進(jìn)篩相較于經(jīng)典篩法的優(yōu)勢(shì)在于：更少的迭代次數(shù)就能求出SVP的解，更少的內(nèi)存開(kāi)銷，預(yù)處理對(duì)其求出速度影響更為明顯，更容易預(yù)測(cè)篩法的行為。

介紹完G6K 算法中使用的主要改進(jìn)篩法的技術(shù)后，再對(duì)G6K 算法本身進(jìn)行描述。

(3)G6K 算法內(nèi)部狀態(tài)、指令和約減策略[13]

所有被G6K所考慮的向量都在投影子格L[l:r]中。更準(zhǔn)確地說(shuō)，w=B[l:r]·v∈d，其中，v∈n。用格點(diǎn)w在投影格基B[l:r]下的坐標(biāo)向量v來(lái)表示格點(diǎn)。這種表示轉(zhuǎn)換的開(kāi)銷為O(n2)。接下來(lái)定義3種對(duì)向量分量的擴(kuò)展或是縮減操作：

1)G6K內(nèi)部狀態(tài)表示

-格基B∈d×d在每次使用最近平面算法做提升操作有新的格向量嵌入時(shí)需要更新，同時(shí)，B的Gram-Schmidt正交基B°也要隨著更新。

-位置參數(shù)0≤k≤l≤r≤d。[l:r]表示篩法所篩投影子格所在格基的下標(biāo)范圍，[k:r]表示提升嵌入格向量時(shí)，嵌入格向量可嵌入的格基下標(biāo)范圍。定義n=r—l為所篩子格維數(shù)。

-用db表示對(duì)投影子格L[l:r]做篩法篩出的N個(gè)格向量組成的數(shù)據(jù)庫(kù)。

-候選嵌入向量ck,…,cl, 其中，ci∈L[i:r]或ci=⊥。

2)G6K基本指令

-InitB：初始化格基。對(duì)G6K狀態(tài)機(jī)進(jìn)行初始化，初始格基設(shè)置為B∈d×d。

-Resetk,l,r：重置格向量數(shù)據(jù)庫(kù)db。將格向量數(shù)據(jù)庫(kù)設(shè)置為空集，并設(shè)置參數(shù)(k,l,r)

-Sieve(S):對(duì)選中投影子格做篩法，并將篩出的短向量通過(guò)最近平面算法嵌入到合適位置。在執(zhí)行對(duì)L[l:r]的篩法過(guò)程中，將篩出的短向量嵌入到L[k:r]上的合適位置。如果嵌入能改善格基的質(zhì)量，則稱on-the-fly lifting。

-(ER,SL,EL)：右擴(kuò)展，左縮減，左擴(kuò)展。向右或向左增加或減少數(shù)據(jù)庫(kù)中每一個(gè)向量的分量。

-Insert(I)：根據(jù)評(píng)分函數(shù)選擇最優(yōu)的嵌入位置ci，其中，k≤i≤l。同時(shí)，每次嵌入需要更新格基。如果沒(méi)有合適的嵌入位置，則繼續(xù)運(yùn)行SL以確保所篩法能正常終止。

-ResizeN：將數(shù)據(jù)庫(kù)大小調(diào)整至N。當(dāng)需要縮減數(shù)據(jù)庫(kù)大小時(shí)，將數(shù)據(jù)庫(kù)中最長(zhǎng)的向量移除；當(dāng)增大數(shù)據(jù)庫(kù)大小時(shí)，則抽樣新的格向量加入到數(shù)據(jù)庫(kù)中。

3)G6K約減策略表示

作為可以執(zhí)行不同格基約減策略的抽象狀態(tài)機(jī)。首先將G6K的基本指令按要執(zhí)行約減的策略組合成稱為Pump的指令集合：

其中，0≤k≤k+β≤d，0≤f≤β，s∈{0,1}控制在Pump-down階段是否執(zhí)行篩法。Resetk,k+β,k+β表示對(duì)數(shù)據(jù)庫(kù)的重置，其中，k確定此次Pump中數(shù)據(jù)庫(kù)格向量可嵌入位置的下標(biāo)下界。Pump-up階段利用子篩法和漸進(jìn)篩的思想，每次迭代對(duì)數(shù)據(jù)庫(kù)中全體格向量執(zhí)行一次左擴(kuò)展(EL)操作：將數(shù)據(jù)庫(kù)中全體格向量利用Babai算法從L[i:r]提升到L[i—1:r]后(其中，i∈[l+1,r])，都要對(duì)整個(gè)數(shù)據(jù)庫(kù)執(zhí)行一次篩法(Sieve(S)操作)。經(jīng)過(guò)β-f次迭代以后，獲得存有大量短的格向量數(shù)據(jù)庫(kù)db，隨后進(jìn)入Pump-down階段。Pump-down階段中據(jù)評(píng)分函數(shù)[31,75]將L[l:r]格中篩出的短的格向量提升嵌入到L[k:r]中評(píng)分最高的位置，得到新格基。嵌入操作利用Dimforfree技術(shù)和嵌入評(píng)分函數(shù)，實(shí)現(xiàn)了對(duì)格基的質(zhì)量提升。

最后，G6K利用一系列Pump指令集合的組合，刻畫不同的格基約減策略：

WorkOutk,β,f,f+,s:Pumpk,β-f+,β,s,Pumpk,β-2f+,β,s,Pumpk,β-3f+,β,s,…,Pumpk,f,β,s,

其中，f+表示每次迭代Pump時(shí)，所篩投影子格維數(shù)的遞增量。整個(gè)G6K算法實(shí)現(xiàn)的整體框架可以用圖2表示。

圖2 G6K算法整體框架圖Fig.2 Overal frame diagram of G6K algorithm

圖2中的分組步驟是G6K所基于的啟發(fā)式篩法在執(zhí)行格向量約減前的一個(gè)分組操作。不同啟發(fā)式篩法的最主要區(qū)別就在于它們對(duì)向量的不同分組方法，從而導(dǎo)致它們的時(shí)間復(fù)雜度和找到相對(duì)接近向量對(duì)的性能不同。以經(jīng)典的BGJ篩法為例介紹分組過(guò)程：利用NNS技術(shù)[75]，首先將數(shù)據(jù)庫(kù)中眾多格向量用一個(gè)個(gè)超錐體分成多個(gè)不同的組，其中同一個(gè)組中的格向量與指示超錐體方向的中心向量夾角小于某個(gè)預(yù)設(shè)值。分組后考慮同一組中格向量對(duì)之間是否存在約減，而不是考慮整個(gè)數(shù)據(jù)庫(kù)中全部可能的向量對(duì)組合是否存在約減。如此可有效減少篩法的計(jì)算復(fù)雜度。詳情見(jiàn)BGJ篩[75]以及BDGL篩[59]。

G6K算法默認(rèn)執(zhí)行的格基約減策略是：首先將r設(shè)置為d(d是輸入格基的維數(shù))，l設(shè)置為d—n0，其中，n0表示首次Pump的投影子格維數(shù)上界(默認(rèn)取值是40)。Pump-up階段中每次Pump的初始子格維數(shù)為30，經(jīng)過(guò)Pump-up完成對(duì)L[l:r]投影子格的漸進(jìn)篩。隨后進(jìn)入Pump-down階段，根據(jù)評(píng)分函數(shù)將L[l:r]格中篩出的短向量嵌入到L[k:r]中的合適位置并更新格基。下一次Pump時(shí)，采用子篩法的思想，使用Lift先將整個(gè)數(shù)據(jù)庫(kù)中格向量提升到L[l-f+:r]中，即令l=l-f+，將下一次Pump所篩投影子格維數(shù)上界增大f+(f+默認(rèn)值是3)，再次迭代。直到某次Pump時(shí)，嵌入的格向量模長(zhǎng)小于預(yù)設(shè)的目標(biāo)向量模長(zhǎng)，就終止程序并返回最短格向量，或是當(dāng)前Pump的子格維數(shù)達(dá)到β-f也終止算法。

因此，通過(guò)調(diào)整k,β,f,f+,s可以構(gòu)造各種約減策略不同的格基約減算法。例如，經(jīng)典的BKZ算法的約減策略可以寫成：

NaiveTourβ:WorkOut0,β,WorkOut1,β+1,…WorkOutd-β,d,…,WorkOutd-1,d

[LM18][74]中滑動(dòng)窗口(Sliding-window)策略可以表示成：

SlidingWindowTourβ:

Reset0,0,0,(ER,S)β,(Il,S,ER,S)d-β,(Il,S)β.

此外，G6K在Pump的初始階段默認(rèn)采用Gauss篩法以確保初始時(shí)不遺漏太多格向量。隨著Pump的進(jìn)行，對(duì)維數(shù)大于40的投影子格，G6K默認(rèn)使用hk3篩法。隨著篩法技術(shù)的進(jìn)步，可以將更快或是空間復(fù)雜度更小的篩法替換掉G6K當(dāng)前所使用的篩法。

4.3.2 G6K的GPU實(shí)現(xiàn)

2021年，Ducas等[76]利用NVIDIA GPU Tensor核心的高效矩陣計(jì)算能力極大加速了G6K算法執(zhí)行篩法時(shí)對(duì)向量分組和向量約減的效率。同時(shí)，所引入的Dual-hash技術(shù)在G6K算法執(zhí)行EL操作時(shí)過(guò)濾掉了很多并不值得提升的向量，有效減少了提升操作的開(kāi)銷。

提升了此前只使用CPU實(shí)現(xiàn)的G6K算法的計(jì)算效率，同時(shí)極大地降低了能耗(對(duì)180維隨機(jī)格上SVP挑戰(zhàn)，GPU實(shí)現(xiàn)的能耗不到CPU實(shí)現(xiàn)能耗的4%)。他們?cè)贒armstadt的SVP挑戰(zhàn)中創(chuàng)下了求解180維隨機(jī)格上求最短向量的紀(jì)錄，此前最好的紀(jì)錄由CPU實(shí)現(xiàn)的G6K算法創(chuàng)下，只能求到155維。

5 總 結(jié)

本文整理并比較了目前求解LWE問(wèn)題的分析策略，并對(duì)目前主要的格基約減算法的思想和所使用的技術(shù)進(jìn)行了梳理。對(duì)于不同類型的LWE 問(wèn)題, 雖然分析策略有所不同，但大都可以用格基約減算法完成求解。對(duì)于現(xiàn)有的格基約減算法，仍有很多改進(jìn)的地方，例如，如何通過(guò)優(yōu)化底層篩法去降低G6K算法的GPU實(shí)現(xiàn)所需的內(nèi)存開(kāi)銷，利用G6K所定義的抽象狀態(tài)機(jī)找到約減效果更好的格基約減策略，等等。此外，如何更準(zhǔn)確地預(yù)測(cè)格基約減算法輸出基的質(zhì)量，從而能夠?qū)贚WE問(wèn)題的困難性構(gòu)造密碼方案的安全性更準(zhǔn)確地估計(jì)也是筆者下一步工作的重點(diǎn)。尤其是對(duì)諸如G6K等新的格基約減算法輸出基質(zhì)量的預(yù)測(cè)，目前尚無(wú)很好的估計(jì)，筆者將在未來(lái)對(duì)這一問(wèn)題做進(jìn)一步的研究。