畢 蕾,路獻(xiàn)輝,3,王鯤鵬

1.中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100093

2.中國(guó)科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,北京 100049

3.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100878

1 引言

格密碼近年來(lái)廣受關(guān)注.由于量子計(jì)算機(jī)的迅速發(fā)展,一些經(jīng)典模型下的困難問(wèn)題在量子計(jì)算環(huán)境下變得可以被有效求解.如果大規(guī)模的量子計(jì)算得以實(shí)現(xiàn),現(xiàn)有的公鑰密碼安全將受到巨大的威脅和挑戰(zhàn).因此,許多國(guó)家的政府和研究機(jī)構(gòu)已逐步發(fā)起了在量子計(jì)算模型下安全的公鑰密碼算法,即后量子公鑰密碼的研發(fā)工作.格密碼由于在安全性、公私鑰尺寸、計(jì)算速度上的優(yōu)勢(shì),以及抵抗量子攻擊的能力,是其中最受矚目的類(lèi)型之一.2020年,NIST后量子密碼算法標(biāo)準(zhǔn)征集的第三輪7個(gè)方案中有5個(gè)是基于格構(gòu)造的,格密碼在未來(lái)有望替代RSA等現(xiàn)行公鑰密碼算法成為新一代的公鑰密碼標(biāo)準(zhǔn).

格理論最初在密碼學(xué)中是一種分析工具,曾被用于分析背包密碼體制、RSA密碼體制等[1,2].1996年,Ajtai[3]開(kāi)創(chuàng)性地給出了格中唯一最短向量問(wèn)題(unique shortest vector problem,uSVP)在worstcase下到小整數(shù)解(small integer solutions,SIS)問(wèn)題在average-case下的歸約證明,即這些困難問(wèn)題在最壞情況下的困難性可以歸約到一類(lèi)隨機(jī)格中問(wèn)題的困難性,因此基于格的密碼體制可以提供最壞情況下的可證明安全性.

1997年,Ajtai-Dwork[4]首次將其作為一種設(shè)計(jì)工具,構(gòu)造了第一個(gè)具有可證明安全的基于格的公鑰密碼體制AjtaiDwork,該方案的安全性基于格上唯一最短向量問(wèn)題(unique shortest vector problem,uSVP)的困難性.此外,初期的格密碼方案還有NTRU密碼體制[5]、GGH密碼體制[6]等.這一時(shí)期的格密碼方案由于存在密鑰尺寸過(guò)大或者缺乏嚴(yán)格的安全性證明等缺陷,無(wú)法滿足實(shí)際應(yīng)用的需求.

2005年,格密碼理論取得突破性進(jìn)展—Regev[7]提出了基于帶錯(cuò)誤的學(xué)習(xí)(learning with errors,LWE)問(wèn)題的公鑰加密算法,大幅度縮小了密文和密鑰尺寸,同時(shí)又將加密算法的安全性歸約到了格上最壞情況困難問(wèn)題的難解性—在量子歸約下,它至少與worst-case下的最短向量問(wèn)題(shortest vector problem,SVP)的變體一樣困難.此后,LWE問(wèn)題在格密碼方案的設(shè)計(jì)中得到了廣泛的應(yīng)用.研究者們基于LWE問(wèn)題提出了許多格密碼方案,如加密[8]、數(shù)字簽名[9]、密鑰交換[10]、全同態(tài)加密[11]等.

目前,大部分格密碼方案是基于帶錯(cuò)誤學(xué)習(xí)(learning with errors,LWE)問(wèn)題和NTRU假設(shè)構(gòu)造的,而LWE和NTRU都可以用SVP求解算法進(jìn)行求解,因此SVP求解問(wèn)題的算法對(duì)于分析這些格密碼方案的實(shí)際安全性至關(guān)重要.

1.1 最短向量問(wèn)題

求解SVP的常用算法是BKZ算法,在使用BKZ算法求解SVP時(shí),需要將SVP精確求解算法嵌入BKZ算法的每一個(gè)基本模塊作為子程序,最終輸出最短向量的近似解.使用BKZ算法進(jìn)行實(shí)際安全性分析,并將其中內(nèi)嵌的精確SVP求解算法的復(fù)雜度作為算法總的時(shí)間復(fù)雜度的評(píng)估方式稱(chēng)為coreSVP方法,這種方法是目前應(yīng)用最廣泛的格密碼具體安全性評(píng)估方法.

SVP精確求解算法主要有以下四類(lèi):枚舉(enumeration)[12]、篩法(sieving)[13]、基于voronoi的方法(voronoi-based approach)[14]和離散高斯抽樣(discrete Gaussian sampling)[15].其中可實(shí)用化的有枚舉和篩法.枚舉的時(shí)間和空間復(fù)雜度分別為2ω(n)和poly(n),而篩法的時(shí)間和空間復(fù)雜度均為2Θ(n),其中n是格的維度.相比于枚舉算法,篩法的時(shí)間復(fù)雜度更低,因此是目前實(shí)用化格密碼算法實(shí)際安全性評(píng)估中主要使用的SVP精確求解算法.

1.2 篩法求解SVP

篩法是在2001年由Ajtai-Kumar-Sivakumar[13]首次提出的,稱(chēng)為AKS篩法(AKS Sieve).AKS篩法求解SVP可分為三個(gè)步驟:首先生成指數(shù)級(jí)別的格向量,然后對(duì)這些向量進(jìn)行篩選,在每一輪篩選中,將這些向量按照一定的規(guī)則遍歷、約化,使得向量的長(zhǎng)度越來(lái)越短,最終得到一定數(shù)量的長(zhǎng)度為O(λ1(Λ))的格向量,最后將這些向量?jī)蓛上鄿p,即可得到格中最短向量s∈Λ∧||s||=λ1(Λ).按照這一思路構(gòu)造的篩法統(tǒng)稱(chēng)為AKS類(lèi)篩法.

除AKS類(lèi)篩法外,還有另一類(lèi)構(gòu)造思路不同的篩法,稱(chēng)為MV類(lèi)篩法.這類(lèi)篩法的初始列表是一個(gè)空列表,在算法過(guò)程中不斷抽取格向量并使用已經(jīng)在列表中的向量對(duì)其進(jìn)行約化,再約化后的向量添加至列表中,重復(fù)此過(guò)程直至找到格中最短向量.第一個(gè)MV類(lèi)篩法是由Micciancio-Voulgaris[16]提出的列表篩法(ListSieve).

AKS篩法和列表篩法都是理論算法,即它們的正確性和復(fù)雜度都有嚴(yán)格的理論證明,并不依賴(lài)任何啟發(fā)式假設(shè).但為了證明它們的正確性,算法中使用了一些隨機(jī)擾動(dòng)技術(shù),這種技術(shù)使算法本身效率很低,因此理論算法很難在實(shí)際中使用.基于這兩種理論算法,研究者們又提出了它們所對(duì)應(yīng)啟發(fā)式版本—NV篩法(NV Sieve)[17]和高斯篩法(Gauss Sieve)[16].啟發(fā)式算法去掉了擾動(dòng)技術(shù),并引入了一些啟發(fā)式假設(shè),使得算法丟失了對(duì)于正確性和復(fù)雜度的理論保障,但是在實(shí)際使用時(shí)更加高效.

據(jù)此,我們可將現(xiàn)有篩法按篩取的方式不同以及是否依賴(lài)啟發(fā)式假設(shè)分為四大類(lèi),如圖1所示1圖中數(shù)組(c t,c s)表示算法的時(shí)間復(fù)雜度和空間復(fù)雜度為和.下文中的復(fù)雜度表示中2cn亦指2cn+o(n).該圖中未標(biāo)識(shí)出減秩篩法,因?yàn)樵擃?lèi)算法著重于實(shí)際應(yīng)用,并未在復(fù)雜度層面對(duì)算法進(jìn)行優(yōu)化..近十年來(lái),研究者們對(duì)這四類(lèi)篩法中的基本算法進(jìn)行了各種改進(jìn)(如表1所示),主要目標(biāo)是優(yōu)化篩法中的遍歷過(guò)程.Pujol-Stehlé[18]指出利用生日悖論可降低AKS篩法和列表篩法最后一個(gè)步驟中需要的長(zhǎng)度為O(λ1(Λ))的向量的數(shù)目,從而降低算法的空間和時(shí)間復(fù)雜度.

表1 篩法技術(shù)分類(lèi)Table 1 Sieving algorithms classified by technique

圖1 篩法發(fā)展歷程Figure 1 process of sieving

Wang-Liu-Tian-Bi[19]和Zhang-Pan-Hu[20]提出的層次篩法(Level Sieve)以NV篩法為起點(diǎn),將篩法的每一輪分為多個(gè)層次進(jìn)行,使得算法從遍歷所有向量變成先劃分大區(qū)域,再在大區(qū)域中進(jìn)行分別遍歷和約化,使得算法所需遍歷向量數(shù)目減少,時(shí)間復(fù)雜度降低.Bai-Laarhoven-Stehlé[21]提出的元組篩法(Tuple Sieve)以列表篩法為基礎(chǔ),在約化向量時(shí)每次約化多個(gè)向量而非僅僅兩個(gè),這使算法需要的初始格向量個(gè)數(shù)減少,從而降低了算法的空間復(fù)雜度.之后,Herold-Kirshanova[22]和Herold-Kirshanova-Laarhoven[23]對(duì)元組篩法中尋找短向量的過(guò)程給出了更快的算法.Mukhopadhyay[24]提出的線性篩法(Linear Sieve)將之前篩法用球形區(qū)域劃分空間的方式換為用超立方體,從而降低了搜索向量進(jìn)行約化得時(shí)間.另外,局部敏感哈希技術(shù)[25]、局部敏感過(guò)濾技術(shù)[26]以及量子Grover搜索算法[27]都被用來(lái)加速篩法中遍歷搜索的過(guò)程.從實(shí)際執(zhí)行效果層面,漸進(jìn)式篩法[9]、子篩法[28]和G6K[29]利用減秩技術(shù)對(duì)篩法的實(shí)際執(zhí)行效果進(jìn)行了優(yōu)化,其中G6K是目前分析密碼安全性的主要實(shí)際工具.

發(fā)展到現(xiàn)在,篩法理論算法的時(shí)間和空間復(fù)雜度已經(jīng)由最初的(25.9n,22.95n)(AKS篩法[13])降低到了(22.49n,22.49n)(線性篩法[24]). 啟發(fā)式算法中復(fù)雜度最低的經(jīng)典算法是Becker-Ducas-Gama-Laarhoven[26]提出的LD篩法,它的時(shí)間和空間復(fù)雜度為(20.292n,20.208n),復(fù)雜度最低的量子算法是Laarhoven[30]提出的量子篩法,它的時(shí)間和空間復(fù)雜度為(20.265n,20.208n).目前coreSVP方法分析格方案的具體安全性時(shí)的經(jīng)典和量子復(fù)雜度來(lái)源即為L(zhǎng)D篩法和量子篩法.本文主要描述篩法發(fā)展過(guò)程中的重要思想和關(guān)鍵技術(shù),總結(jié)目前存在的主要問(wèn)題,并展望將來(lái)的發(fā)展方向.

1.3 組織結(jié)構(gòu)

本文剩余的內(nèi)容安排如下.第2節(jié)介紹相關(guān)的基礎(chǔ)知識(shí).第3節(jié)和第4節(jié)介紹篩法的四個(gè)類(lèi)別,其中第3節(jié)介紹AKS篩法和NV篩法,第4節(jié)介紹列表篩法和高斯篩法.接下來(lái)的章節(jié)按照時(shí)間順序介紹各種改進(jìn)的方法.第5節(jié)介紹生日-AKS篩法和生日列表篩法.第6節(jié)介紹層次篩法.第7節(jié)介紹使用LSH/LSF技術(shù)的篩法.第8節(jié)介紹元組篩法.第9節(jié)介紹減秩篩法.第10節(jié)介紹量子加速篩法.第11節(jié)介紹線性篩法.第12節(jié)總結(jié)篩法當(dāng)前存在的主要問(wèn)題和未來(lái)的發(fā)展趨勢(shì).

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

2.1 符號(hào)

在本文中,符號(hào)Z和R表示整數(shù)集合和實(shí)數(shù)集合.標(biāo)準(zhǔn)漸進(jìn)函數(shù)O(·)、Ω(·)、Θ(·)、o(·)、ω(·)定義如下:f(n)=O(g(n))意為存在正整數(shù)c和n0,對(duì)于所有n≥n0有f(n)≤c·g(n);f(n)=Ω(g(n))意為存在正整數(shù)c和n0,對(duì)于所有n≥n0有g(shù)(n)≤c·f(n);f(n)=Θ(g(n))意為既有f(n)=O(g(n))又有f(n)=Ω(g(n));f(n)=o(g(n))意為對(duì)于任意正數(shù)c,存在n0使得對(duì)于所有n≥n0有f(n)≤c·g(n);f(n)=ω(g(n))意為對(duì)于任意正數(shù)c,存在n0使得對(duì)于所有n≥n0有f(n)≥c·g(n).符號(hào)poly(x)表示關(guān)于變量x的任意未指定多項(xiàng)式函數(shù).向量用小寫(xiě)黑體字母表示(例如x),矩陣用大寫(xiě)黑體字母表示(例如X).符號(hào)||·||表示向量的二范數(shù)?2,或稱(chēng)歐式范數(shù).符號(hào)dist(a,b)表示a和b之間的歐式距離.符號(hào)B n(x,r)表示一圓心為x,半徑為r的n維球,符號(hào)B n(r)=B n(0,r).

2.2 格和格上困難問(wèn)題

定義1(格)已知Rm中的n個(gè)線性無(wú)關(guān)的行向量b1,b2,···,b n(m≥n),這組向量的所有整系數(shù)線性組合的集合稱(chēng)為Λ,記為

其中線性無(wú)關(guān)的向量組b1,b2,···,b n(m≥n)稱(chēng)為格Λ的一組基,n為格的秩,m為格的維數(shù).當(dāng)m=n時(shí),稱(chēng)Λ為一個(gè)滿秩格.格Λ上的最短向量的范數(shù)記為λ1(Λ)=minv∈Λ{0}||v||.

定義2(最短向量問(wèn)題,shortest vector problem,SVP)給定格Λ,尋找一個(gè)格向量u∈Λ{0}使得||u||=λ1(Λ).

3 AKS篩法和NV篩法

篩法是Ajtai-Kumar-Sivakumar于2001年首次提出的,稱(chēng)為AKS篩法[13].其基本思想是首先生成一定數(shù)量的格向量,讓它們通過(guò)一系列越來(lái)越“細(xì)”的篩子,使得留下來(lái)的向量長(zhǎng)度越來(lái)越短,最終找到最短的那一個(gè).由于其龐大的空間開(kāi)銷(xiāo),算法一直未能實(shí)用化.直到2008年,Nguyen-Vidick基于AKS篩法提出了第一個(gè)篩法的啟發(fā)式算法NV篩法[17],可以應(yīng)用于維度小于50的格,篩法才開(kāi)始走向?qū)嵱没?下面分別介紹AKS篩法和NV篩法.

3.1 AKS篩法

AKS篩法算法可分成三個(gè)步驟.首先,從一個(gè)較大的范圍B n(2O(n)O(λ1(Λ)))中抽取2O(n)個(gè)格向量.然后,通過(guò)一系列“篩取”的過(guò)程,輸出一定數(shù)量的B n(O(λ1(Λ)))中的格向量.最后,將得到的B n(O(λ1(Λ)))中的格向量?jī)蓛上鄿p并輸出最短的那個(gè),即可以接近1的概率得到格中的最短向量.

“篩取”的過(guò)程是AKS篩法的核心,也是時(shí)間復(fù)雜度最高的部分.“篩取”的過(guò)程分多輪進(jìn)行,每一輪輸入集合L?Λ∩B n(R)中的向量,輸出盡可能多的Λ∩B n(γR)中的向量,其中γ∈(0,1)稱(chēng)為收縮系數(shù).具體地,在一輪篩法中,從輸入集合L中選擇一個(gè)子集C作為“中心”,集合C滿足如下兩個(gè)性質(zhì):第一,集合C中任意兩個(gè)向量之間的距離都大于γR,即對(duì)于任意的v1,v2∈C,有||v1?v2||>γR;第二,對(duì)于中心之外的每個(gè)向量w∈LC,都存在C中的一個(gè)向量v,使得||w?v||≤γR,即w?v∈Λ∩B n(γR).因此,LC?Λ∩B n(R)中的每個(gè)向量對(duì)應(yīng)一個(gè)Λ∩B n(γR)中的輸出向量.在每一輪篩取結(jié)束后,集合C中的向量將被丟棄.由于集合C中任意兩個(gè)向量之間的距離都大于γR,并且C?B n(R),這兩個(gè)條件保證了每一輪丟棄的向量的數(shù)目不會(huì)太多.

為了保證“篩取”結(jié)束后輸出的B n(O(λ1(Λ)))中的格向量是不同的,AKS篩法算法還引入了擾動(dòng)(perturbation)技術(shù).具體地,在算法的第一步中,首先從B n(ξλ1(Λ))中隨機(jī)抽取向量x,其中ξ>0.5是選定的擾動(dòng)系數(shù).為了能夠最終找到格中的最短向量,擾動(dòng)不能太大,一般會(huì)選擇ξλ1(Λ)=O(λ1(Λ)).對(duì)每個(gè)隨機(jī)抽取的向量x,可找到基本區(qū)域中的向量y,使得v=y?x是一個(gè)格向量.由于向量y在基本區(qū)域中,有||y||≤R0:=nmaxi||b i||.因此,||v||≤R0+ξλ1(Λ).在第二步的“篩取”過(guò)程中,給定許多對(duì)(v,y)?Λ×B n(R),其中||v?y||≤ξλ1(Λ),算法會(huì)輸出(v′,y′)?Λ×B n(γR+ξλ1(Λ)),并保持||v′?y′||=||v?y||≤ξλ1(Λ).在執(zhí)行線性多次“篩取”之后,即可以得到B n(O(ξλ1(Λ)/(1?γ)))中的格向量.當(dāng)選擇合適的γ和ξ之后,Ajtai-Kumar-Sivakumar證明,算法會(huì)以很高的概率輸出長(zhǎng)度O(λ1(Λ))的非零格向量.AKS篩法詳見(jiàn)算法1.

算法1 AKS篩法Input:Λ,γ,ξ,N Output:A shortest vector ofΛ 1 R0←n max i||b i||;2 L←Sampling(Λ,ξ,N,R0); ?算法2 3 R←R0;4 for j=1 to k do ?k表示算法3執(zhí)行的輪數(shù),由R,γ,ξ定義得到5 L←Sieving(L,R,γ); ?算法3 6 R←γR+ξλ1(Λ);7 end 8 find v0∈Λs.t.||v0||=min{||v?v′||where(v,y)∈L,(v′,y′)∈L,v?=v′};9 return v0.算法2 AKS篩法中的Sampling子算法Input:Λ,ξ,N,R0 Output:A set{(v i,y i,i∈[1,n])}?Λ×B n(R0)and y i?v i is uniformly distributed in B n(ξ)1 for i=1 to N do$←B n(ξλ1(Λ));3 v i←ApproxCVP(?x i,Λ); ?ApproxCVP指Babai’s rounding算法4 y i←v i+x i;5 end 6 return{(v i,y i,i∈[1,n])}.2 x i算法3 AKS篩法中的Sieving子算法Input:A set L={(v i,y i,i∈I)}?Λ×B n(R)and?i∈I,||y i?v i||≤ξλ1(Λ),R,γ Output:A set L′={(v′i,y′i,i∈I′)}?Λ×B n(γR+ξλ1(Λ))and?i∈I′,||y′i?v′i||≤ξλ1(Λ)1 C←?;2 for i∈I do 3 if?c∈C s.t.||y i?v c||≤γR then L′←L′∪{(v i?v c,y i?v c)}5 end 6 else 4 C←C∪{i}8 end 9 end 10 return L′.7

3.2 NV篩法

在AKS篩法中,為了使算法的輸出結(jié)果和復(fù)雜度有理論保障,算法引入了擾動(dòng)技術(shù).但這一技術(shù)在算法的實(shí)際執(zhí)行中的作用并不顯著.當(dāng)把擾動(dòng)去掉,而直接在格點(diǎn)上進(jìn)行操作時(shí),可以使算法的執(zhí)行更高效.基于這樣的想法,Nguyen-Vidick[17]提出了AKS篩法的啟發(fā)式版本——NV篩法.這樣得到的啟發(fā)式算法執(zhí)行效率高,但無(wú)法保證一定可以得到格中的最短向量,也無(wú)法直接給出復(fù)雜度的界的證明.

與AKS篩法相似,NV篩法也分成三個(gè)步驟(見(jiàn)算法4).首先,用Klein近似最近平面算法算法抽取N個(gè)格向量放入集合L中.然后進(jìn)行“篩取”,在每一輪的“篩取”過(guò)程中,長(zhǎng)度在γR以?xún)?nèi)的向量直接通過(guò)“篩取”進(jìn)入下一輪,而其他長(zhǎng)度大于γR的向量將按照與AKS篩法中相同的方法,通過(guò)選取“中心”集合C得到剩下的長(zhǎng)度在γR以?xún)?nèi)的向量.重復(fù)這一“篩取”的過(guò)程直到某一輪中所有通過(guò)“篩取”的向量都是零向量.最后,輸出最后一輪“篩取”之前所有向量中長(zhǎng)度最小的向量.

算法4 NV篩法Input:Λ,2/3<γ<1,N Output:A short non-zero vector ofΛ 1 L←?;2 for j=1 to N do 3 L←L∪v sampled by using Klein’s randomized nearest plane algorithm;4 end 5 remove all zero vectors from L;6 L0←L;7 repeat 8 L0←L;9 L←Sieving(L,γ); ?算法5 10 remove all zero vectors from L;11 until L=?;12 compute v0∈L0 s.t.||v0||=min{||v||,v∈L0};13 return v0.算法5 NV篩法中的Sieving子算法Input:A set L?Λ∩B n(R)and shrinking factor 2/3<γ<1 Output:A set L′?Λ∩B n(γR)1 Set R←max v∈L||v||;2 initialize L′←{}and C←{0};3 for each v∈L do 5 4 if||v||≤γR then L′←L′∪{v}6 end 7 else if?c∈C s.t.||v?c||≤γR then L′←L′∪{v?c}9 end 10 else 8 11 C←C∪{v}12 end 13 end 14 return L′.

NV篩法算法中最重要的參數(shù)是初始輸入向量的數(shù)目N和收縮系數(shù)γ.當(dāng)參數(shù)γ確定后,最終輸出的格向量的長(zhǎng)度只與算法執(zhí)行的輪數(shù)相關(guān),輪數(shù)越多則最終得到的格向量越短.而算法會(huì)在所有初始抽取的N個(gè)向量用完之后結(jié)束,因此算法輪數(shù)受限于每輪算法執(zhí)行時(shí)損失的向量數(shù)目.而算法執(zhí)行過(guò)程中向量損失的主要來(lái)源是被用于作為“中心”.因此衡量“中心”集合的規(guī)模|C|對(duì)于確定參數(shù)和分析復(fù)雜度至關(guān)重要.為了分析|C|,Nguyen-Vidick使用了如下假設(shè),并在低維度的實(shí)驗(yàn)中對(duì)其合理性進(jìn)行了驗(yàn)證.

假設(shè)1令C n(γ,R)={x∈Rn,γR≤||x||≤R},假設(shè)L∩C n(γ,R)中的向量是均勻分布的.

實(shí)驗(yàn)證明,NV篩法在維度小于50的格上可以正常使用.但由于空間復(fù)雜度過(guò)高,致使在格的維度超過(guò)50之后,就很難再將其實(shí)用化.

4 列表篩法和高斯篩法

2010年,Micciancio-Voulgaris[16]提出了一種新的篩法理論算法,稱(chēng)為列表篩法,并給出了對(duì)應(yīng)的啟發(fā)式版本,稱(chēng)為高斯篩法.與AKS篩法和NV篩法在一開(kāi)始就先生成大量格向量不同,列表篩法和高斯篩法從一個(gè)空列表L開(kāi)始,逐步抽取和約化得到更短的格向量加入列表,直到找到滿足條件的短向量.

4.1 列表篩法

列表篩法算法使用列表L儲(chǔ)存每一輪生成的格向量.每一輪算法隨機(jī)抽取一個(gè)格向量,用列表L中的向量對(duì)其進(jìn)行約化,使它盡可能地短,約化之后將其放進(jìn)列表L中,已經(jīng)在L中的向量不再改變或移除.當(dāng)約化得到的向量長(zhǎng)度小于等于μ(目標(biāo)短向量長(zhǎng)度),即可作為最終的結(jié)果輸出.詳見(jiàn)算法6.

算法6列表篩法Input:Λ,μ,N Output:v∈Λ∧||v||≤μor⊥1 Initialize a list L={0};2 for i=1 to N do 6 if?w∈L s.t.||v?w||<μthen 3 (v,p)←sampling(Λ,ξ,μ); ?算法7 4 (v,p)sieving((v,p),L); ?算法8 5 if v/∈L then 7 return v?w;8 end L←L∪{v};10 end 11 end 12 return⊥.9

算法7列表篩法中的Sampling子程序Input:Λ,ξ,μO(píng)utput:(v,p)∈Λ×R n 1 e$←B n(ξμ);2 p←e modΛ;3 v←p?e;4 return(v,p).

算法8列表篩法Sieving子程序Input:(v,p),L Output:reduced pair(v,p)1 while?w∈L s.t.||p?w||≤||p||do 2 (v,p)←(v?w,p?w)3 end 4 return(v,p).

接下來(lái)分析列表L長(zhǎng)度的上界,從而得到時(shí)間與空間復(fù)雜度.算法終止前每一輪得到的約化后的向量與L中已有的向量均距離較遠(yuǎn)(至少為μ).根據(jù)這一性質(zhì),利用球填充(sphere packing)問(wèn)題的分析結(jié)果,可給出|L|的上界,據(jù)此可以得到算法的空間復(fù)雜度.算法的每一輪需要使用新抽取的向量與L中的所有向量進(jìn)行兩兩組合計(jì)算,因此算法時(shí)間復(fù)雜度的上界約為|L|2.

在上面的分析中存在一個(gè)問(wèn)題:算法的某些輪得到的向量可能已經(jīng)存在于L中,即發(fā)生了“碰撞”.當(dāng)遇到這種情況,算法既浪費(fèi)了時(shí)間,又沒(méi)有得到更短的向量.因此在分析算法的時(shí)間復(fù)雜度時(shí),需考慮這樣的事件發(fā)生的概率.為此,列表篩法和AKS篩法一樣,采用了“擾動(dòng)”技術(shù).在抽取格點(diǎn)v時(shí),實(shí)際抽取的是一對(duì)向量e,p,再計(jì)算v=p?e,其中e滿足||e||≤ξμ,這里ξ>0.5.這樣得到的向量,滿足v在B n(p,ξμ)中均勻分布,且B n(p,ξμ)中包含多于1個(gè)格向量的概率大于0.因此,當(dāng)B n(p,ξμ)中包含兩個(gè)距離小于等于μ的格向量時(shí),抽到其中一個(gè)向量?jī)纱蔚母怕屎屯瑫r(shí)抽到這兩個(gè)向量的概率相同.據(jù)此,可以得到發(fā)生碰撞的概率的上界.可以看出,當(dāng)ξ增大時(shí),|L|上升,但發(fā)生碰撞的概率降低,反之亦然.因此ξ的選擇對(duì)于算法最終的復(fù)雜度至關(guān)重要.

4.2 高斯篩法

高斯篩法是列表篩法的啟發(fā)式版本(詳見(jiàn)算法9),它與列表篩法的區(qū)別在于,在抽取了一個(gè)隨機(jī)的格向量v并對(duì)其進(jìn)行長(zhǎng)度上的約化時(shí),列表篩法只利用列表L中的向量對(duì)于v進(jìn)行約化,而高斯篩法還利用v對(duì)L中已存在的向量進(jìn)行約化.當(dāng)這個(gè)過(guò)程結(jié)束后,列表中的所有向量都是兩兩互相約化的,即

?w1,w2∈L:||w1±w2||≥max{||w1||,||w2||}.

算法9高斯篩法Input:Λ,μO(píng)utput:v∈Λ∧||v||≤μ1 Initialize a list L={0}and a stack S=?;2 repeat v←v?w;6 end 7 while?w∈L s.t.||w||>||v||∧||w?v||≤||w||do 3 Get a vector v from S(or sample a new one);4 while?w∈L s.t.||w||≤||v||∧||v?w||≤||v||do 5 8 L←L{w};S←S∪{w?v};10 end 11 if v has changed then 9 12 S←S∪{v}(unless v=0);13 end 14 else L←L∪{v};15 until v satisfying||v||≤μ;

除了約化方式的不同,高斯篩法還去掉了列表篩法中的擾動(dòng)技術(shù),因此高斯篩法的時(shí)間復(fù)雜度并沒(méi)有一個(gè)可以證明的上界,但可以估計(jì)時(shí)間復(fù)雜度大約為將列表中的向量?jī)蓛山M合檢查否可以互相進(jìn)行約化的時(shí)間,因此時(shí)間復(fù)雜度大約為列表長(zhǎng)度的平方級(jí)別,即O((4/3)n).

5 生日-AKS篩法和生日-列表篩法

2011年,Pujol-Stehlé[18]提出,利用生日悖論(birthday paradox)可降低篩法成功找到最短向量所需的向量總數(shù),因此可以降低算法的復(fù)雜度.Pujol-Stehlé對(duì)AKS篩法和列表篩法進(jìn)行了優(yōu)化,優(yōu)化得到的算法分別稱(chēng)為生日-AKS篩法(AKS Sieve-birthday)和生日-列表篩法(ListSieve-birthday).

由于使用生日悖論結(jié)論時(shí)需要集合中的向量是互相獨(dú)立同分布的,但AKS篩法的最后一個(gè)部分中的向量并不滿足這個(gè)條件,因此需要對(duì)算法進(jìn)行一些調(diào)整.可以證明這些調(diào)整帶來(lái)的開(kāi)銷(xiāo)很小,對(duì)于整體復(fù)雜度的下降沒(méi)有影響[32].

6 層次篩法

2011年,Wang-Liu-Tian-Bi提出了一種的新的啟發(fā)式算法—兩層篩法(Two-Level Sieve)[19],在這一新的框架下,之前的NV篩法可視作一層篩法(One-Level Sieve).之后在2013年,Zhang-Pan-Hu通過(guò)進(jìn)一步改進(jìn)兩層篩法的結(jié)構(gòu)對(duì)算法進(jìn)行優(yōu)化,提出了三層篩法(Three-Level Sieve)[20].通過(guò)使用多層篩的技術(shù),層次篩法以增加空間復(fù)雜度為代價(jià)降低了算法的時(shí)間復(fù)雜度.

6.1 兩層篩法

Wang-Liu-Tian-Bi提出,可以將原始的NV篩法看作一層篩法,那么兩層篩法即為利用“兩層篩”的技術(shù).具體地,算法的每一輪分為兩層:第一層首先將C n(γ2R)={x∈Rn:γ2R≤||x||≤R}中的格向量劃分進(jìn)不同的半徑為γ1R的大球中(γ1>1),所有大球需覆蓋C n(γ2R);第二層再將每個(gè)大球中的格向量劃分進(jìn)不同的小球中(詳見(jiàn)算法10).可以看出,對(duì)于每個(gè)格向量,一層篩的大球數(shù)目較少,二層篩時(shí)只需與已確定的大球內(nèi)部的小球中心點(diǎn)相比較即可,因此減少了比較時(shí)間,降低了時(shí)間復(fù)雜度.但同時(shí),由于需要存儲(chǔ)的向量數(shù)量變多,導(dǎo)致空間復(fù)雜度上升.

算法10兩層篩法Input:A set S?Λ∩B n(R)and shrinking factors√2/3<γ2<1<γ1<√2γ2 Output:A set S′?Λ∩B n(γ2 R)1 Set R←max v∈S||v||;2 Initialize S′←{}and C1←{0},C2←{0};3 for each v∈S do 4 if||v||≤γ2 R then S′←S′∪{v};6 end 7 else 5 8 if?c∈C1 s.t.||v?c||≤γ1 R then 9 if?c′∈C c2 s.t.||v?c′||≤γ2 R then 10 S′←S′∪{v?c′};11 end 12 else C c2←C c2∪{v};13 end 14 else 15 C1←C1∪{v};16 C2←C2∪{C v2={v}};17 end 18 end 19 end 20 Return S′.

6.2 三層篩法

三層篩法的思路和兩層篩法類(lèi)似,采用了“三層篩”的技術(shù),以增大空間復(fù)雜度為代價(jià),進(jìn)一步降低了算法的時(shí)間復(fù)雜度.

一個(gè)自然的問(wèn)題是,是否可以繼續(xù)增大層次的數(shù)目來(lái)降低算法的時(shí)間復(fù)雜度.對(duì)此,文獻(xiàn)[20]指出,這種想法是可行的,但由于這樣做的技術(shù)難度越來(lái)越高,而收益卻越來(lái)越低,所以沒(méi)有繼續(xù)的必要.之后,Laarhoven在詳細(xì)分析了兩種層次篩法的復(fù)雜度后,給出了k層篩法(k-Level Sieve)的算法框架和空間、時(shí)間復(fù)雜度的分析方式[30].

算法11三層篩法Input:A set S?Λ∩B n(R)and shrinking factors 0.88<γ3<1<γ2<γ1<√2γ3 Output:A set S′?Λ∩B n(γ3 R)1 Set R←max v∈S||v||;2 initialize S′←{}and C1←{0};3 for each v∈S do 4 if||v||≤γ3 R then S′←S′∪{v};6 end 7 else 5 8 if?c1∈C1 s.t.||v?c1||≤γ1 R then 9 if?c2∈C c12 s.t.||v?c2||≤γ2 R then 10 if?c3∈C c1,c23 s.t.||v?c3||≤γ3 R then 11 S′←S′∪{v?c3};12 end 13 else C c1,c23 ←C c1,c23 ∪{v};14 end 15 else C c12←C c12∪{v};16 end 17 else 18 C1←C1∪{v};19 end 20 end 21 end 22 return S′.

7使用LSH/LSF技術(shù)的篩法

2015年,Laarhoven[25]提出使用局部敏感哈希(locality-sensitive hashing,LSH)技術(shù)對(duì)篩法中窮搜的部分進(jìn)行加速,并在高斯篩法上進(jìn)行了實(shí)現(xiàn),改進(jìn)后的算法稱(chēng)為哈希篩法(HashSieve).相比于高斯篩法,哈希篩法在保持空間復(fù)雜度不變的基礎(chǔ)上降低了時(shí)間復(fù)雜度.

LSH有許多不同的類(lèi)型,哈希篩法使用的是角(angular)LSH,在這之后,Laarhoven-Weger[33]以及Becker-Laarhoven[34]又分別提出了利用球(sphere)LSH和正軸體(cross-polytope)LSH加速的篩法球篩法(SphereSieve)和正軸體篩法(CPSieve).球篩法和正軸體篩法又進(jìn)一步降低了哈希篩法的時(shí)間復(fù)雜度.

2016年,Becker-Ducas-Gama-Laarhoven[26]提出使用一種與LSH類(lèi)似的、稱(chēng)為局部敏感過(guò)濾(locality-sensitive filters,LSF)的技術(shù)對(duì)篩法進(jìn)行加速,改進(jìn)后的算法稱(chēng)為L(zhǎng)D篩法(LDSieve).相比于使用LSH技術(shù)的三個(gè)算法,LD篩法的空間復(fù)雜度不變,時(shí)間復(fù)雜度更低.

7.1 LSH和LSF技術(shù)

LSH.LSH是用來(lái)解決最近鄰搜索(near(est)neighbor searching,NNS)問(wèn)題的一項(xiàng)技術(shù).正式地,最近鄰搜索問(wèn)題定義為:

定義3(最近鄰搜索問(wèn)題,near(est)neighbor searching,NNS)給定一列n維的向量L={w1,w2,···,w N},對(duì)于一個(gè)目標(biāo)向量v/∈L,找到一個(gè)w∈L使得它是L中離v最近的向量.

顯然,這個(gè)問(wèn)題可以通過(guò)遍歷列表L解決.但當(dāng)列表L規(guī)模較大時(shí),這樣做的時(shí)間復(fù)雜度很高.而使用LSH技術(shù)可以降低解決問(wèn)題的時(shí)間復(fù)雜度.正式地,LSH函數(shù)簇H有性質(zhì)如下:

定義4對(duì)任意v,w∈Rn,一簇函數(shù)H={h:Rn→N}對(duì)于測(cè)度D有如下性質(zhì):

(1)如果D(v,w)≤r1,那么Prh∈H[h(v)=h(w)]≥p1,

(2)如果D(v,w)≥r2,那么Prh∈H[h(v)=h(w)]≤p2,那么稱(chēng)H對(duì)于測(cè)度D是(r1,r2,p1,p2)-敏感的.

根據(jù)定義4,如果有p1?p2,那么可使用H以不可忽略的概率區(qū)分在測(cè)度D下與v距離至多r1和至少r2的向量.

具體地,使用LSH技術(shù)時(shí),首先從哈希簇H中隨機(jī)選擇t×k個(gè)哈希函數(shù).之后,構(gòu)造t個(gè)哈希表T1,T2,···,T t,每個(gè)表T i中使用由k個(gè)哈希函數(shù)組合得到的哈希函數(shù)組,表示為h i.對(duì)每個(gè)w∈L,計(jì)算它的t個(gè)哈希值h1(w),h2(w),···,h t(w),并根據(jù)每個(gè)哈希值h i(w)將w存放在哈希表T i中相應(yīng)的位置.那么,當(dāng)給定目標(biāo)向量v后,計(jì)算它的t個(gè)哈希值h i(v),將每個(gè)哈希表中與之發(fā)生碰撞的所有w∈L取出作為一個(gè)集合,這個(gè)集合即為離v較近的向量的集合.之后,再遍歷這個(gè)集合中尋找離v最近的向量即可.

考慮圖2中一個(gè)使用角LSH技術(shù)的實(shí)例:給定列表L={w1,w2,···,w10}和目標(biāo)向量v,要求找到L中距離v最近的向量.該實(shí)例中使用3個(gè)哈希表,每個(gè)表中使用k=2個(gè)超平面來(lái)劃分空間(即為選定的哈希函數(shù)),因此使用2k=4個(gè)哈希桶存放相應(yīng)哈希值的向量.可以看出,使用多個(gè)哈希表可以使得靠近目標(biāo)點(diǎn)的向量盡可能地不被遺漏.對(duì)于每個(gè)哈希表(即每種空間劃分的方式),首先對(duì)L中的向量計(jì)算哈希值(即落在平面中的哪個(gè)區(qū)域)并存放在相應(yīng)的哈希桶中.之后,計(jì)算v的3個(gè)哈希值,與每個(gè)哈希表相比對(duì),將與之哈希值相同的向量取出并存儲(chǔ),留待最后遍歷時(shí)使用.在該實(shí)例中,最終得到的與v距離較近的向量的集合為C={w6,w7,w8,w9,w10}.那么在尋找離v最近的向量時(shí),遍歷集合C即可.

圖2 局部敏感哈希實(shí)例Figure 2 Example of locality-sensitive hash

顯然,算法解決NNS問(wèn)題的效率取決于對(duì)哈希簇和參數(shù)k、t的選擇.

?哈希簇:根據(jù)選擇的哈希簇不同,目前在使用的LSH技術(shù)主要可分為:角(angular)LSH(或稱(chēng)超平面(hyperplane)LSH)、球(sphere)LSH、正軸體(cross-polytope)LSH.其中角LSH的理論分析較差但算法運(yùn)行非常高效,球LSH的理論非常完善但不具備實(shí)際操作性.而正軸體LSH則同時(shí)具備了以上兩個(gè)算法的優(yōu)點(diǎn):它既有充分的理論保障,在實(shí)踐中又比角LSH效果更好.

?參數(shù)k和t:當(dāng)選擇較大的k和t時(shí),可以將區(qū)分“近”和“遠(yuǎn)”的概率差放大(定義4中的p1?p2),這樣可以使篩選出的“較近”的元素的集合較小,最終的比較次數(shù)較少,但另一方面,這樣做會(huì)使得哈希表較長(zhǎng),需要的存儲(chǔ)空間較大.因此,需要選擇合適的參數(shù)k和t來(lái)平衡算法的時(shí)間和空間復(fù)雜度.

LSF.對(duì)于LSF技術(shù)來(lái)說(shuō),每個(gè)過(guò)濾函數(shù)的輸出是二元的,即通過(guò)或沒(méi)有通過(guò)這個(gè)過(guò)濾函數(shù).因此對(duì)于一個(gè)列表L,當(dāng)它經(jīng)過(guò)過(guò)濾函數(shù)f之后得到的集合L f?L中包含所有通過(guò)這個(gè)過(guò)濾函數(shù)的向量.L f中的向量在對(duì)應(yīng)的測(cè)度下距離較近.

當(dāng)利用這樣的過(guò)濾函數(shù)來(lái)解決NNS問(wèn)題時(shí),首先給定一個(gè)過(guò)濾函數(shù)的分布F,再抽取t×k個(gè)過(guò)濾函數(shù)f i,j∈F.將每k個(gè)進(jìn)行組合,構(gòu)造t個(gè)過(guò)濾函數(shù)組f i.對(duì)于w,通過(guò)過(guò)濾函數(shù)組f i意味著通過(guò)了其中的所有k個(gè)過(guò)濾函數(shù)f i,j,j=1,2,···,k.那么對(duì)于列表L,相應(yīng)地存在t個(gè)過(guò)濾輸出集合L1,L2,···,L t.最后,當(dāng)輸入一個(gè)目標(biāo)向量v時(shí),用t個(gè)過(guò)濾函數(shù)組對(duì)v進(jìn)行檢測(cè),對(duì)于那些v可以通過(guò)的過(guò)濾函數(shù)組f i,將它對(duì)應(yīng)的L i中的向量全部集合在一起,即為離v較近的向量的集合.再?gòu)倪@個(gè)集合中遍歷尋找離v最近的向量即可.

7.2 哈希篩法

哈希篩法是利用角(angular)LSH技術(shù)對(duì)高斯篩法進(jìn)行優(yōu)化得到的.具體地,角LSH技術(shù)是指在LSH中使用角距離(angular distance)來(lái)進(jìn)行距離的度量:對(duì)于向量v和w,它們的角距離定義為

在這樣的度量方式下,當(dāng)兩個(gè)向量的夾角小時(shí)即可認(rèn)為它們的距離較近,反之亦然.

為了使用角LSH來(lái)優(yōu)化高斯篩法,需要對(duì)高斯篩法中的約化條件做一些相應(yīng)的調(diào)整.高斯篩法中的約化條件可寫(xiě)作:

用u2約化u1:如果||u1±u2||<||u1||,那么u1←u1±u2.

根據(jù)這樣的約化方法,可以使得得到的列表L中的向量都是兩兩約化的,即對(duì)于?w1,w2∈L均滿足||w1±w2||≥max{||w1||,||w2||}.從這個(gè)條件可以得到?w1,w2∈L均滿足夾角至少為π/3.據(jù)此可以得到一個(gè)弱化版的約化條件:

用u2約化u1:如果θ(u1,u2)<π/3并且||u1||≥||u2||,那么u1←u1±u2.

為了分析約化的過(guò)程和算法的復(fù)雜度,需作如下假設(shè):

假設(shè)2隨機(jī)抽取的向量v,w之間的夾角θ(v,w)和從Rn中的單位球面上隨機(jī)抽取的兩個(gè)向量v′,w′之間的夾角θ(v′,w′)服從相同的分布.

在高維空間中,已知隨機(jī)抽取的兩個(gè)向量之間的夾角以較大的概率等于π/2.因此在假設(shè)2成立時(shí),有?w1,w2∈L,θ(w1,w2)以很大的概率接近π/2.另一方面,由弱化的約化條件可知,當(dāng)兩個(gè)向量可以用其中一個(gè)對(duì)另一個(gè)進(jìn)行約化時(shí),意味著它們之間的夾角是小于π/3的,而約化之后的夾角一定是大于π/3的,為了簡(jiǎn)化分析,假設(shè)約化之后的向量之間的夾角均為π/2.

利用這些信息,即可定義角LSH所需的函數(shù)簇:

直觀地,每個(gè)a可定義一個(gè)如圖2實(shí)例中的虛線(超平面).而對(duì)于v,w,Pr[h(v)?=h(w)]可利用它們之間的角度進(jìn)行計(jì)算:

算法12哈希篩法Input:Λ,μO(píng)utput:v∈Λ∧||v||≤μ1 Initialize a list L={0}and a stack S=?;2 initialize t hash tables T i;3 sample k·t random hash vectors a i,j;4 repeat 5 Get a vector v from S(or sample a new one);6 obtain the set of candidates C=∪ti=1 T i[h i(v)];7 while?w∈C s.t.||w||≤||v||∧||v?w||≤||v||do v←v?w;9 end 10 while?w∈C s.t.||w||>||v||∧||w?v||≤||w||do 8 11 L←L{w};12 T i←T i{w}for all t hash tables;13 S←S∪{w?v};14 end 15 if v has changed then 16 S←S∪{v}(unless v=0);17 end 18 else 19 L←L∪{v};20 T i[h i(v)]←T i[h i(v)]∪{v}for all t hash tables;21 end 22 until v satisfying||v||≤μ;

7.3 球篩法

算法13球篩法Input:A set S?Λ∩B n(R)and shrinking factor 2/3<γ<1 Output:A set S′?Λ∩B n(γR)1 initialize S′←{}and C←{0};2 initialize t empty hash tables T i;3 sample k·t random spherical hash functions h i,j∈H;4 for each v∈S do 5 if||v||≤γR then S′←S′∪{v};7 end 8 else 6 9 obtain the set of candidates C=∪ti=1 T i[h i(±v)];10 for each w∈C do 11 if||v?w||≤γR then 12 S′←S′∪{v?w};13 continue the outermost loop;14 end 15 end 16 T i[h i(v)]←T i[h i(v)]∪{v}for all i∈[t];17 end 18 end 19 return S′.

7.4 正軸體篩法

正軸體篩法是利用正軸體(cross-polytope)LSH技術(shù)對(duì)高斯篩法進(jìn)行優(yōu)化得到的啟發(fā)式算法[34].正軸體是一類(lèi)任意維均存在的凸多胞體(如圖3是一個(gè)三維正軸體),由標(biāo)準(zhǔn)基向量{e i∈Rn}作為頂點(diǎn)定義而成.根據(jù)正軸體定義的哈希函數(shù)可寫(xiě)作

圖3 三維正軸體Figure 3 3-orthoplex

其中符號(hào)與絕對(duì)值最大的分量的符號(hào)一致.例如對(duì)于v=(3,?5)有h(v)=?2.

但這樣只定義了一個(gè)哈希函數(shù),因此我們需要引入一個(gè)隨機(jī)變換,使得它能夠成為一個(gè)函數(shù)簇.令分布A輸出矩陣A=(a i,j)∈Rn×n,其中對(duì)于任意的i,j有a i,j～N(0,1),即一個(gè)標(biāo)準(zhǔn)正態(tài)分布.這樣即可定義哈希函數(shù)簇

H={h A:h A(x)=h A(A x),A～A}.

之后,將這個(gè)哈希函數(shù)簇在GaussSieve上應(yīng)用即可得到新的算法CPSieve(見(jiàn)算法14).

算法14正軸體篩法Input:Λ,μO(píng)utput:v∈Λ∧||v||≤μ1 initialize a list L={0}and a stack S=?;2 sample t×k random Gaussian matrices A i,j;3 define h i,j(x)=h(A i,j x)and h i(x)=(h i,1(x),h i,2(x),···,h i,k(x))initialize t hash tables T i;4 sample k·t random hash vectors a i,j;5 repeat 9 6 get a vector v from S(or sample a new one);7 obtain the set of candidates C=∪ti=1 T i[h i(v)]∪∪ti=1 T i[h i(?v)];8 while?w∈C s.t.||w||≤||v||∧||v?w||≤||v||do v←v?w;10 end 11 while?w∈C s.t.||w||>||v||∧||w?v||≤||w||do 12 L←L{w};13 T i←T i{w}for all t hash tables;14 S←S∪{w?v};15 end 16 if v has changed then 17 S←S∪{v}(unless v=0);18 end 19 else 20 L←L∪{v};21 T i[h i(v)]←T i[h i(v)]∪{v}for all t hash tables;22 end 23 until v satisfying||v||≤μ;

7.5 LD篩法

8 元組篩法

2016年,Bai-Laarhoven-Stehlé指出,現(xiàn)有篩法都只考慮了兩個(gè)向量之間的相互約化,而實(shí)際上可以每次約化多個(gè)向量[21].根據(jù)這樣的思想,他們提出了基于列表篩法的新的啟發(fā)式篩法——元組篩法(Tuple Sieve),或稱(chēng)k-篩法(k-Seive),其中常數(shù)k表示每次約化時(shí)考慮的向量個(gè)數(shù).相比于之前的篩法,元組篩法以增加時(shí)間復(fù)雜度為代價(jià),降低了算法的空間復(fù)雜度,在一定程度上緩解了篩法由于空間復(fù)雜度過(guò)大而不能應(yīng)用于實(shí)際的問(wèn)題.之后,Herold-Kirshanova[22]和Herold-Kirshanova-Laarhoven[23]進(jìn)一步將尋找約化后的短向量的過(guò)程看作一個(gè)k-列表問(wèn)題(k-list problem),并給出了更快的算法.

8.1 BLS-元組篩法

BLS-元組篩法的每次約化中考慮k個(gè)向量.首先考慮k=2的情況,這時(shí)的算法稱(chēng)為雙篩法(DoubleSieve).算法的每一輪將一組B n(R)內(nèi)的向量通過(guò)兩兩約化得到一組B n(γR)內(nèi)的向量(見(jiàn)算法15).具體地,在每輪中,算法首先將范數(shù)小于γR的向量從列表L中去掉、直接進(jìn)入下一輪,使得列表L中只包含了范數(shù)在(γR,R)范圍內(nèi)的向量.然后,對(duì)列表L中的每一對(duì)向量w,v,如果||v±w||≤γR,則將v±w加入到下一輪的列表中.

下面分析雙篩法的時(shí)間與空間復(fù)雜度.由于算法在約化時(shí)所考慮的向量v,w∈L都在(γR,R)范圍內(nèi),如果γ≈1時(shí),那么||v||≈||w||≈R.此時(shí),事件||v?w||<γR等價(jià)于w∈B(R)∩B(v,γR).為了計(jì)算該事件發(fā)生的概率,需要做如下假設(shè):

假設(shè)3在雙篩法(算法15)中,假設(shè)對(duì)于?v∈L,v/||v||可看作是從單位球面上的均勻分布中抽取的獨(dú)立同分布的向量.

k=3時(shí)的算法稱(chēng)為三篩法(TripleSieve,算法16),它與k=2時(shí)的區(qū)別在于每次約化時(shí)使用3個(gè)向量,即v±w±x.因此,此時(shí)在球覆蓋時(shí)不只考慮單個(gè)的向量,而也會(huì)考慮兩個(gè)向量的和或差也是否也可以覆蓋一部分球面.例如,如果有||v?w?x||≤γR,那說(shuō)明x∈B(R)∩B(v?w,γR).直觀上,這也解釋了為了什么k=3的情況下覆蓋整個(gè)球面所需的向量個(gè)數(shù)比k=2時(shí)更少.與雙篩法類(lèi)似,在三篩法的分析中也需要做與假設(shè)3類(lèi)似的假設(shè):

假設(shè)4在三篩法(算法16)中,假設(shè)對(duì)于?v∈L,v/||v||可看作是單位球面上均勻隨機(jī)抽取的的獨(dú)立同分布向量,且?v?=w∈L,v±w中范數(shù)最小的向量可看作一個(gè)隨機(jī)向量.

算法15雙篩法Input:L?B n(R),γ,R Output:L′?B n(γR)1 L′←{};2 for each v∈L do 3 if||v||≤γR then 4 L′←L′∪{v};L←L{v};6 end 7 end 8 for each v,w∈L do 5 9 if||v±w||≤γR then 10 L′←L′∪{v±w};11 end 12 end 13 return L′

算法16三篩法Input:L?B n(R),γ,R Output:L′?B n(γR)1 L′←{};2 for each v∈L do 4 L′←L′∪{v};3 if||v||≤γR then L←L{v};6 end 7 end 8 for each v,w,x∈L do 5 9 if||v±w±x||≤γR then 10 L′←L′∪{v±w±x};11 end 12 end 13 return L′

對(duì)于更大的k,Bai-Laarhoven-Stehlé指出,算法的時(shí)間和空間復(fù)雜度可以歸納為k n(1+o(1))和k n/k(1+o(1)).當(dāng)k趨近于n時(shí),算法的時(shí)間和空間復(fù)雜度分別趨近于n n+o(n)和n1+o(1).因此,參數(shù)k平衡了算法時(shí)間復(fù)雜度和空間復(fù)雜度,逐漸增大k的過(guò)程即可視為用時(shí)間換空間的過(guò)程.

8.2 HK-元組篩法

2017年,Herold-Kirshanova[22]繼續(xù)發(fā)展了元組篩法.他們指出,當(dāng)把利用篩法求解SVP的每一輪看作k列表問(wèn)題之后,Bai-Laarhoven-Stehlé[21]只是對(duì)所有的可能解進(jìn)行了遍歷去尋找滿足條件的那些,而實(shí)際上這個(gè)過(guò)程可以進(jìn)一步進(jìn)行優(yōu)化.具體地,一個(gè)近似k列表問(wèn)題可以歸約到滿足一定性質(zhì)的結(jié)構(gòu)問(wèn)題上,而這樣的結(jié)構(gòu)問(wèn)題可以被更快速地解決.因此,可以利用解決這個(gè)結(jié)構(gòu)問(wèn)題的算法來(lái)對(duì)現(xiàn)有的元組篩法加速.更進(jìn)一步地,這樣的結(jié)構(gòu)問(wèn)題還可以與LSH技術(shù)相結(jié)合,得到一個(gè)擴(kuò)展版的結(jié)構(gòu)問(wèn)題,Herold-Kirshanova也同樣給出了解決這個(gè)問(wèn)題的算法,并把它們一起用在了加速元組篩法上.

下面首先給出近似k-列表問(wèn)題,結(jié)構(gòu)以及結(jié)構(gòu)問(wèn)題的定義,然后分析近似k列表問(wèn)題的解與結(jié)構(gòu)問(wèn)題的解的關(guān)系,最后給出解決結(jié)構(gòu)問(wèn)題的算法(算法17).

定義6(結(jié)構(gòu),configuration)對(duì)于k個(gè)向量x1,x2,···,x k∈S n?1,其中S n?1表示單位球面,結(jié)構(gòu)C=Conf(x1,x2,···,x k)定義為這k個(gè)向量的Gram矩陣,即C i,j=〈x i,x j〉,i,j∈[k].

定義7(結(jié)構(gòu)問(wèn)題,configuration problem)輸入k個(gè)指數(shù)量級(jí)的列表L1,L2,···,L k,其中的元素取自S n.對(duì)于一個(gè)給定的目標(biāo)結(jié)構(gòu)C和?>0,輸出k元組(x1,x2,···,x k)∈L1×L2×···×L k,使其對(duì)于所有的i,j∈[k]均滿足|〈x i,x j〉?C i,j|≤?.

根據(jù)定義可知,若選擇目標(biāo)結(jié)構(gòu)C滿足∑i,j C i,j≤t2,那么C對(duì)應(yīng)的結(jié)構(gòu)問(wèn)題的解(x1,x2,···,x k)滿足〈x i,x j〉≈C i,j,?i,j,因此||∑i x i||2≈∑i,j C i,j≤t2,即(x1,x2,···,x k)也是以t為目標(biāo)的近似k-列表問(wèn)題的解.因此,任意一個(gè)滿足∑i,j C i,j≤t2的結(jié)構(gòu)C對(duì)應(yīng)的結(jié)構(gòu)問(wèn)題的解都包含在以t為目標(biāo)的近似k-列表問(wèn)題的解當(dāng)中.但反過(guò)來(lái),后者所有的解可能需要多個(gè)不同的結(jié)構(gòu)問(wèn)題的解才能完全覆蓋.

篩法的每一輪要求輸入列表和輸出列表的規(guī)?；疽粯?因此需要找到盡可能多的近似k-列表問(wèn)題的解.為了求解盡可能少的結(jié)構(gòu)問(wèn)題同時(shí)得到盡可能多的近似k-列表問(wèn)題解,Herold-Kirshanova選擇只求解包含最多解的結(jié)構(gòu)問(wèn)題.具體地,結(jié)構(gòu)問(wèn)題可較容易地確定輸出解的數(shù)目和目標(biāo)結(jié)構(gòu)C之間的關(guān)系:給定|L|k個(gè)可能的元組作為輸入,目標(biāo)是輸出|L|個(gè)元組,它們滿足方程|L|k·det(C)n/2=|L|.根據(jù)上述方程,選擇det(C)最大的C可使結(jié)果達(dá)到最優(yōu),即在輸入數(shù)目固定的情況下最大化輸出列表規(guī)模.

算法17 k-list for the configuration problem Input:L1,L2,···,L k,C,? Output:List L of k-tuples(x1,x2,···,x k s.t.|〈x i,x j〉?C i,j|≤?for all i,j 1 L←{};2 for all x1∈L1 do 3 for all j=2,3,···k do j ←FILTER(x1,L j,C(1,j),?); ?算法18 5 end 6 for all x2∈L(1)2 do 4 L(1)7 L(2)j ←FILTER(x2,L(1)j,C(2,j),?); ?算法18 8···9 for all x k∈L(k?1)k do 10 L←L∪{(x1,x2,···,x k)};11 end 12 end 13 end 14 return L.算法18 FILTER Input:x,L,c,? Output:L′1 L′←{};2 for all x′∈L do 3 if|〈x,x′〉|≤γR then 4 L′←L′∪{x};5 end 6 end 7 return L′.

8.3 HKL-元組篩法

2018年,Herold-Kirshanova-Laarhoven[23]提出可以將近似k列表問(wèn)題約化到的結(jié)構(gòu)問(wèn)題略做調(diào)整以使得問(wèn)題能夠被更加快速地解決,并且可以結(jié)合LSF技術(shù)來(lái)對(duì)算法整體進(jìn)行加速.

具體地,文獻(xiàn)[22]選擇使用det(C)最大的C對(duì)應(yīng)的結(jié)構(gòu)問(wèn)題,以最大化每一輪輸出元組的數(shù)目.而Herold-Kirshanova-Laarhoven指出某些結(jié)構(gòu)C雖然det(C)不是最大的,但它們可以使輸出元組的搜索更加快速.為了保持對(duì)于輸出元組數(shù)目的要求,就需要增加輸入列表的大小.對(duì)此,Herold-Kirshanova-Laarhoven給出了對(duì)應(yīng)的關(guān)系和分析,并給出了如何找到最優(yōu)的C來(lái)平衡算法的時(shí)間和空間.

9 減秩篩法

減秩(rank reduction)技術(shù)是一種格上常用的解決困難問(wèn)題的技術(shù),當(dāng)求解n維格上的困難問(wèn)題時(shí),可以首先解決一個(gè)n?k維的子格上的問(wèn)題,利用求解得到的結(jié)果再來(lái)解決原問(wèn)題.

2018年,Laarhoven-Mariano[9]提出了利用減秩技術(shù)的漸進(jìn)式篩法(Progressive Lattice Sieving).具體地,對(duì)于一個(gè)n維格上的SVP,首先在一個(gè)低維度的子格上進(jìn)行篩法,然后逐漸向其中添加其余維度上的基向量,并在此過(guò)程中繼續(xù)篩的過(guò)程,直到所有的基向量都添加完畢并找到了完整格上的最短向量為止.減秩技術(shù)幾乎可以與所有篩法相結(jié)合使用,Laarhoven-Mariano提出的漸進(jìn)式篩法主要考慮了與高斯篩法和哈希篩法這兩種效率較高的篩法進(jìn)行結(jié)合,結(jié)果顯示利用這種方法,可將篩法提速20-40倍.除此之外,由于漸進(jìn)式篩法的大部分算法過(guò)程是在子格中進(jìn)行,因此算法的空間復(fù)雜度更低.

同年,Ducas[28]提出了子篩法(SubSieve),也可以看作是使用了減秩技術(shù).Ducas證明只需要在少于n?k維的格上調(diào)用數(shù)次篩法,即可解決原格上的SVP,其中k=Θ(n/logn).子篩法對(duì)于算法總體的時(shí)間、空間復(fù)雜度的優(yōu)化是亞指數(shù)級(jí)別的,但在實(shí)際執(zhí)行中比其他篩法在70-80維的實(shí)驗(yàn)中快10倍.

2019年,基于這兩種利用了減秩技術(shù)的篩法,Albrecht-Ducas-Herold等人[29]提出了一種開(kāi)源的抽象的狀態(tài)機(jī)——G6K(General Sieve Kernel),是目前分析密碼安全性的主要實(shí)際工具.利用這個(gè)狀態(tài)機(jī)可以實(shí)際地解決格上的SVP.具體地,Albrecht-Ducas-Herold等人利用G6K解決了Darmstadt SVP挑戰(zhàn)2https://www.latticechallenge.org/svp-challenge.中的151維SVP,時(shí)間比之前的記錄快了400倍.之后,在2021年,Ducas-Stevens-Woerden又利用G6K解決了180維的SVP挑戰(zhàn),是目前Darmstadt SVP挑戰(zhàn)的最高紀(jì)錄.

10 量子加速篩法

10.1 量子篩法

文獻(xiàn)[30,35]給出了一些啟發(fā)式篩法在利用Grover算法加速后的時(shí)間、空間復(fù)雜度(見(jiàn)表2),其中效果最好的是基于LDSieve的量子篩法(Quantum Sieve).

表2 部分啟發(fā)式篩法的在量子算法加速下的空間、時(shí)間復(fù)雜度Table 2 Space&time complexity of some heuristic sieving algorithms sped up by using quantum algorithm

10.2 量子元組篩法

2019年,Kirshanova-M?rtensson-Postlethwaite-Roy Moulik[31]提出了元組篩法的量子加速版本.具體地,在解決元組篩法中所引入的結(jié)構(gòu)問(wèn)題(見(jiàn)第8.2節(jié))時(shí),需要對(duì)許多元組進(jìn)行遍歷并判斷它們是否滿足給定的目標(biāo),這一遍歷過(guò)程可以使用量子Grover搜索算法進(jìn)行加速.另外,經(jīng)典的元組篩法在解決結(jié)構(gòu)問(wèn)題時(shí)使用了LSH/LSF技術(shù)進(jìn)行加速,而Grover搜索算法也可與這兩項(xiàng)技術(shù)結(jié)合使用.這是因?yàn)樵谑褂眠@兩項(xiàng)技術(shù)尋找合適的元組時(shí),是將所有元組按照一定的結(jié)構(gòu)進(jìn)行分類(lèi),之后再選擇其中的一些類(lèi)進(jìn)行搜索而非全部遍歷,這一過(guò)程也可利用量子Grover搜索算法進(jìn)行加速.

11 線性篩法

2019年,Mukhopadhyay[24]基于AKS篩法的框架,提出了一個(gè)新的可證明的篩法.新篩法的時(shí)間復(fù)雜度與空間復(fù)雜度是線性關(guān)系(之前是平方關(guān)系),因此算法命名為線性篩法(Linear Sieve).

AKS Sieve中的一個(gè)關(guān)鍵步驟就是對(duì)于一個(gè)在B n(R)抽取得到的向量y,找到離它最近的中心向量c.這個(gè)問(wèn)題可以看作一個(gè)NNS問(wèn)題(見(jiàn)第7節(jié)),可利用LSH和LSF技術(shù)解決,但這兩項(xiàng)技術(shù)的使用都依賴(lài)于一些啟發(fā)式假設(shè),因此不能用于優(yōu)化可證明的篩法.AKS Sieve的解決方式是在B n(R)中構(gòu)造很多半徑為γR的小球,將空間劃分為一些小區(qū)域,之后對(duì)每個(gè)向量y,在由所有的球心組成的中心集合中尋找是否存在一個(gè)球心c使得||y?c||≤γR.如果不存在這樣的球心,就將這個(gè)y對(duì)應(yīng)的格點(diǎn)v加入中心集合成為一個(gè)新的球心.

這樣做降低了算法的時(shí)間復(fù)雜度,但同時(shí)也增加了算法的空間復(fù)雜度.這是因?yàn)锳KS Sieve中的每個(gè)中心點(diǎn)之間的距離都是大于γR的,而當(dāng)用超立方體劃分時(shí)會(huì)有一些中心之間的距離是小于γR的,因此中心的數(shù)目會(huì)比之前更多.但可以證明即使是這樣,算法的時(shí)間復(fù)雜度依然比AKS Sieve低.

12 結(jié)論

自Ajtai-Kumar-Sivakumar于2001年提出第一個(gè)篩法以來(lái),研究者們對(duì)篩法進(jìn)行了大量深入的研究,不僅提出了不同的算法框架,而且通過(guò)借鑒其他領(lǐng)域相關(guān)問(wèn)題的技術(shù),提出了許多不同的改進(jìn)方法,降低了算法的復(fù)雜度.本文對(duì)目前主要的篩法進(jìn)行了分類(lèi),并梳理了它們之間的關(guān)系和發(fā)展脈絡(luò).

盡管篩法在過(guò)去二十多年取得了許多進(jìn)展,但目前的篩法仍然存在空間復(fù)雜度過(guò)高、理論與實(shí)際效果相差較大[36]等缺點(diǎn).在實(shí)際應(yīng)用中,篩法只能在低維度的格上進(jìn)行實(shí)驗(yàn),距離高維度、大規(guī)模使用仍然存在一定的差距.由于篩法對(duì)于格密碼方案的實(shí)際安全性分析至關(guān)重要,解決篩法在高維格上的應(yīng)用問(wèn)題,可以極大地推進(jìn)格密碼分析領(lǐng)域的發(fā)展.因此,對(duì)于篩法的進(jìn)一步研究無(wú)論是從理論角度還是從實(shí)用角度都具有十分重要的價(jià)值和意義.

基于目前的研究現(xiàn)狀,未來(lái)我們還可以在以下幾個(gè)方面對(duì)篩法進(jìn)行更加深入的研究:

?深化量子加速:目前利用量子算法對(duì)于篩法加速還停留在簡(jiǎn)單地替代篩法中窮搜的階段,如何更加充分和深入利用量子算法對(duì)篩法進(jìn)行加速尚不可知,這是我們?cè)诹孔雍Y法領(lǐng)域需要考慮的問(wèn)題.

?混合算法:混合算法的框架在格困難問(wèn)題的求解中是一種常見(jiàn)的思路,而目前大多數(shù)篩法都是單獨(dú)使用,如何與其他算法相結(jié)合是未來(lái)一個(gè)重要的研究方向.例如,2019年Guo-Johansson-M?rtensson-Wagner[37]提出將篩法與BKW算法相結(jié)合用來(lái)解決LWE問(wèn)題. 2020年Doulgerakis-Laarhoven-Weger[38]提出將篩法作為一個(gè)子程序、與枚舉以及切片等技術(shù)相結(jié)合的算法,該算法比直接使用篩法有更低的時(shí)間和空間復(fù)雜度.

?借鑒其他領(lǐng)域的技術(shù):在目前對(duì)于篩法的改進(jìn)中,借鑒其他領(lǐng)域的技術(shù)是一個(gè)重要的工具(例如局部敏感哈希技術(shù)),如何利用更多不同領(lǐng)域的想法和技術(shù)對(duì)篩法進(jìn)行優(yōu)化,是未來(lái)需要繼續(xù)考慮的問(wèn)題.例如,2019年Laarhoven[39]指出了人工智能領(lǐng)域中演化算法(evolutionary algorithm)的部分技術(shù)與篩法領(lǐng)域中近年來(lái)所發(fā)展技術(shù)的相似性,并進(jìn)一步利用演化算法中其他的技術(shù)對(duì)篩法進(jìn)行改進(jìn).