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

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

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

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

1 預(yù)備知識

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

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

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

2 LWE問題的分析策略以及非基于格的求解算法

2.1 LWE問題的分析策略

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

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

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

2.2 非基于格的求解算法

2.2.1 組合算法

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

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

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

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

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

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

3 基于格的求解方法

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

3.1 判定性LWE問題

3.1.1 SIS策略

3.1.2 BDD策略

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

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

3.2 搜索型LWE問題

3.2.1 BDD策略-原始攻擊

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

最早提出該策略的是文獻[28]，特別地，給定分布Ls,通過采樣獲得實例滿足：

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

其格基矩陣M為

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

3.2.2 ISIS策略-對偶攻擊

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

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

其中，第三個不等號處使用了Kannan嵌入。更詳細的過程如下：

給定服從分布Ls,選取的m個LWE實例考慮ISIS實例：

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

3.2.3 2種攻擊方式的比較

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

原始攻擊的格基的gap為

而對偶攻擊的格基的gap為

此外，Bai等[31]的格基無需實例組成的n階方陣要在模q下求逆，因此對實例的數(shù)量沒有嚴格的要求。但原始攻擊中的格基因為需要實例組成的n階方陣要在模q下可逆，因而只能用于求解實例個數(shù)m大于n的情況。

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

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

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

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

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

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

3.2.4 對Binary型LWE問題攻擊的加速技術(shù)

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

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

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

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

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

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

(2)Rescale技術(shù)

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

(3)組合攻擊

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

4 格基約減算法

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

4.1 SVP求解算法

4.1.1 枚舉法

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

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

4.1.2 篩法

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

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

4.2.1 LLL算法

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

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

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

1.?1≤i≤n,j

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

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

LLL算法的實現(xiàn)細節(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

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

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

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

4.2.2 BKZ類算法

(1)BKZ算法

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

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

1)質(zhì)量估計

2)時間估計

(2)BKZ2.0算法

2011年，Chen等[14]對BKZ算法進行了4點改進，得到BKZ2.0算法[65]：

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

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

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

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

其中，2)～4)有3個改進的目的都是減少BKZ在調(diào)用枚舉算法時的計算開銷。

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

(3)Progressive-BKZ算法

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

(4)BKZ算法模擬器

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

(5)Slide-BKZ算法

(6)對BKZ類算法計算開銷的估計

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

4.3 G6K算法

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

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

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

(1)Dimension for free[19]

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

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

對n維格的n—d維投影子格Ld做篩法:

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

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

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

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

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

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

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

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

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

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

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

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

2)G6K基本指令

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

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

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

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

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

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

3)G6K約減策略表示

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

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

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

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

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

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

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

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

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

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

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

SlidingWindowTourβ:

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

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

4.3.2 G6K的GPU實現(xiàn)

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

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

5 總 結(jié)

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