格基規(guī)約算法研究進(jìn)展

周世祥，劉梁華

（1．山東理工大學(xué)理學(xué)院，山東淄博255091；2．山東淄博實(shí)驗(yàn)中學(xué)，山東淄博255091）

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

格出現(xiàn)在19世紀(jì)的數(shù)論和密碼研究中，很長(zhǎng)一段時(shí)間，格在密碼學(xué)中的應(yīng)用主要是負(fù)面的，常被用來(lái)破解各種密碼方案，可喜的是，過(guò)去10年中已出現(xiàn)過(guò)好幾個(gè)積極的應(yīng)用，人們已經(jīng)設(shè)計(jì)了一些基于格困難問(wèn)題的密碼系統(tǒng)．基于格密碼學(xué)的非凡特性是它們可證明安全（即平均上難于破解）．格問(wèn)題已被密碼學(xué)界建議為新的計(jì)算困難問(wèn)題的源泉，用于構(gòu)造可證明安全密碼函數(shù)．

設(shè)b1，…，bd是n維歐式空間Rn中線性無(wú)關(guān)的實(shí)向量，定義點(diǎn)集

為格，稱(chēng)b1，…，bd為格的一個(gè)基．因?yàn)閎1，…bd是線性無(wú)關(guān)的，任何格矢量x可用基線性組合表示，且表達(dá)的方式也應(yīng)該是唯一的（λ1，…，λd唯一）；反之，如果x在格中且能用上述實(shí)線性組合形式表示，則系數(shù)λ1，…，λd一定為整數(shù)．

每一個(gè)格矢量都可以唯一地表示為基矢量的整線性組合．用基表示格是有意義的，格基自身就可以用一個(gè)實(shí)系數(shù)矩陣表示，這樣一來(lái)人們可以很方便地利用計(jì)算機(jī)來(lái)表示某個(gè)格．

從代數(shù)的角度看，格是具有d個(gè)生成元的Abel群，被認(rèn)為是Rn的子群．格矢量在“加”的意義下形成群，如果a∈L，則－a∈L，如果a，b∈L，則a±b∈L，所以格是最普通的n維空間上的離散加子群．格的任何子群也是格．

格計(jì)算研究的中心問(wèn)題是Shortest Vector Problem（SVP）：給定一個(gè)格基B，找到一個(gè)非零格矢量Bx≠0，長(zhǎng)度達(dá)到最小值‖Bx‖＝λ1，這里長(zhǎng)度可被定義成關(guān)于任何范數(shù)，但歐幾里得l2范數(shù)是最常用的．

另一個(gè)問(wèn)題是Closest Vector Problem（CVP）．給定一個(gè)目標(biāo)矢量和格基，要求找到最靠近該矢量的格點(diǎn)．CVP問(wèn)題比SVP問(wèn)題稍難．精確的SVP是NP難的，實(shí)際中也不一定需要，所以有人提出了下面的近似SVP問(wèn)題．

給定一個(gè)秩為d的格L基B，一個(gè)近似因子γ≥1，找到非零矢量u∈L，使得‖u‖這個(gè)問(wèn)題稱(chēng)為近似SVP問(wèn)題，簡(jiǎn)記作apprSVP．目前，已證明對(duì)于近似因子γ＝的apprSVP問(wèn)題是NP難的．

沒(méi)有有效的算法找任意格中最短矢量，1981年van Emde Boas證明：確定一個(gè)給定的格元素是否是l∞最短的是NP完全問(wèn)題．Ajtai證明在隨機(jī)規(guī)約下，找歐幾里得范數(shù)下最短矢量問(wèn)題是NP難的，Micciancio證實(shí)在近似因子小于時(shí)SVP問(wèn)題也是NP難的．

下面給出一些與格基規(guī)約相關(guān)的概念．

對(duì)任何矢量集S?Rn，span（S）表示由S張成的線性空間，或者為Rn包含S的最小子空間．

設(shè)b1，…，bd∈Rn為格L的一個(gè)格基，則其Gram行列式，表示為△（b1，…，bd）是d×n階Gram矩陣

Gram行列式有一個(gè)非常重要的幾何解釋?zhuān)寒?dāng)b1，…，bd線性無(wú)關(guān)時(shí)，由矢量b1，…，bd所張成的平行多面體表示為

設(shè)Bn（0，r）＝｛x∈Rn：‖x‖＜r｝表示中心在原點(diǎn)，半徑為r的n維開(kāi)球，簡(jiǎn)記為B（0，r）．

對(duì)于子空間E?Rn，它的正交補(bǔ)表示為E⊥＝｛x∈Rn：〈x，y〉＝0，?y∈E｝．用：Rn→Rn表示向量到E⊥上的投影，則有，當(dāng)x∈E⊥時(shí)，πE（x）＝x，當(dāng)x∈E時(shí)（x）＝0．

設(shè)L?Rn是一個(gè)格，則L的秩定義為span（L）的維數(shù)，如果n＝d，則格稱(chēng)為滿秩的．

與Rn的線性子空間一樣，格的基也是不唯一的．但最大不同的是，并非所有最大線性無(wú)關(guān)矢量集就能形成一個(gè)基．

每一個(gè)格有無(wú)限多個(gè)格基．設(shè)b1，…，bd∈Rn為格L的一個(gè)格基，矩陣表示為B，任何d個(gè)格矢量c1，…，cd∈L，矩陣表示為C，若存在一個(gè)可逆矩陣U，使得，C＝BU，且｜U｜＝±1，則c1，…，cd也是格L的一個(gè)基．顯然滿足要求的矩陣U有無(wú)限多個(gè)．

設(shè)M?L是L的子格，如果存在線性子空間E?Rn，使得M＝L∩E，則稱(chēng)M為L(zhǎng)的本原子群．容易證明M為本原子格的充要條件是M的每一個(gè)基都可以擴(kuò)展為L(zhǎng)的一個(gè)基．

類(lèi)似地，定義本原格矢量b1，…，bk∈Rn，k＜d，要求這組矢量能擴(kuò)充為L(zhǎng)的一個(gè)基b1，…，bd．

當(dāng)投影一個(gè)格到它的子空間上時(shí)，可以得到投影格．設(shè)L?Rn是一個(gè)秩為d的格，M?L是L的秩為r的本原子格，1≤r≤d，定義：＝為到span（M）的正交補(bǔ)空間上的投影，則πM（L）?Rn是一個(gè)秩為d－r的格．

設(shè)b1，…，bd∈Rn為格L的一個(gè)格基，b1，…，bi－1，i≤d是本原的，對(duì)于1≤i≤d，定義映射πi：＝πspan（｛b1，…，bi－1｝），則（L）是秩為d－i＋1的格，從而減少了格L的秩，在格基規(guī)約的許多迭代算法中就是反復(fù)運(yùn)用這個(gè)變換技巧來(lái)降低格的規(guī)模．

對(duì)任何秩為d的格L來(lái)說(shuō)逐次最小值λ1，…，λd也是它的基本不變量．

正如前面所講的SVP問(wèn)題，每一個(gè)格一定存在最短非零矢量（不是唯一的），Minkowski定義了最短非零矢量的長(zhǎng)度為格L的第一最小值λ1．然而，定義第二短矢量沒(méi)有意義，所以Minkowski在他的逐次最短矢量定義中限定為線性無(wú)關(guān)的格矢量．

定義1 ［逐次最小值（The successive minima）] 格L（b1，…，bd）的第i個(gè)逐次最小值λi，1≤i≤d定義為中心在原點(diǎn)，包含i個(gè)線性無(wú)關(guān)格矢量的最小球半徑λi（L）＝inf｛r：dim（span（L∩B（0，r）））≥i｝．

格作為離散子群，總存在矢量達(dá)到逐次最小值，即有線性無(wú)關(guān)的矢量x1，…，xd∈L使‖xi‖＝λi，（i＝1，…，d）．然而，一旦dim（L）≥4，這樣的矢量不一定形成一個(gè)格基．容易證明，任何兩個(gè)不同格點(diǎn)之間的最小距離也等于最短非零格矢量的長(zhǎng)度，λ1＝min｛‖x－y‖，xy∈L｝．

早在19世紀(jì)Korkine和Zolotarev研究二次型時(shí)發(fā)現(xiàn)當(dāng)格秩d≥5時(shí)，格L沒(méi)有基能同時(shí)到達(dá)所有逐次最小值．

我們可以證明格L最短矢量長(zhǎng)度λ1與它的體積vol（L）之間是齊次關(guān)系，因?yàn)槿绻胻L代替L，則λ1（tL）＝｜t｜λ1（L），vol（tL）＝．Hermite在研究二次型理論時(shí)，得出λ1（L）2／vol（L）2／d上邊界為Hermite常量γd，即λ1（L）≤．然而，找到精確的γd也不是容易的事情，目前人們僅僅知道1≤d≤8及d＝24時(shí)精確的γd值．Hermite自己證明了對(duì)于d≥2，γd≤其中，γ2＝利用鴿籠原理，Minkowski證明了定理1．

定理1 （Minkowski凸體定理）設(shè)L?Rn是一個(gè)n秩格，C?Rn是其可測(cè)凸集，關(guān)于原點(diǎn)對(duì)稱(chēng)，且測(cè)度嚴(yán)格大于2nvol（L），則C∩L至少包含一個(gè)非零矢量．

根據(jù)定理1我們做出下列推論．

推論1 設(shè)L?Rn是一個(gè)d秩格，vd＝為相應(yīng)的單位球體積，其中Gamma函數(shù)可以看做階乘函數(shù)在實(shí)數(shù)情況下的擴(kuò)展，則格L包含一個(gè)非零矢量x，使得λ1（L）≤‖x‖≤

重寫(xiě)表達(dá)式為λ1（L）2／vol（L）2／d≤4／所以γd≤4／，我們得出γd的線性邊界γd≤1．這個(gè)值可以幫助我們界定λ（L）的上邊界．1

接下來(lái)考查λ2的范圍，不幸的是對(duì)于λ2卻無(wú)法界定．下面由一個(gè)實(shí)例可說(shuō)明，設(shè)L是由矩陣生成的格，對(duì)于ε≤1，λ1（L）＝ε，λ2（L）＝1／ε，當(dāng)ε→0時(shí)，λ2可以任意大．盡管如此，Minkowski從幾何意義上整體界定了其他逐次最小值．

定理2 （Minkowski第二定理）設(shè)L?Rn是一個(gè)d秩格，則對(duì)1≤γ≤d，總有

對(duì)于基為b1，…，bd的格L總有Vol（L0）≤‖．當(dāng)基矢量相互正交時(shí)，結(jié)果取等號(hào)．

定義2 （正交虧損orthogonality defect）基為b1，…，bd的格L正交虧損定義為‖／vol（L）≥1，等號(hào)成立條件是格基為正交基．

格基規(guī)約的目標(biāo)是找到規(guī)約基，即由相當(dāng)短或幾乎正交的矢量組成的基．格基規(guī)約算法在計(jì)算機(jī)和數(shù)學(xué)的許多領(lǐng)域具有很高的價(jià)值［1]．

2 規(guī)約基的定義和性質(zhì)

1982年三位數(shù)學(xué)家倫斯特拉（A．k．Lenstra），倫斯特拉（H．W．Lenstra），洛伐茲（Jr．L．Lovász）發(fā)明了LLL算法．LLL算法被許多專(zhuān)家視為有關(guān)NP問(wèn)題的一大突破，因?yàn)樗?jiǎn)明性和廣泛的應(yīng)用，立即被認(rèn)為是20世紀(jì)最重要的算法成果之一．

線性代數(shù)的基本理論表明任何有限維歐氏空間都有一個(gè)標(biāo)準(zhǔn)正交基，即一個(gè)基由兩兩正交的單位矢量組成，自然要問(wèn)，格是否也有標(biāo)準(zhǔn)正交基，不幸的是，即使是對(duì)2維格，也可能沒(méi)有正交基．格基規(guī)約的目標(biāo)退而求其次，一個(gè)格總有一個(gè)基離正交不遠(yuǎn)，要精確定義何為離正交不遠(yuǎn)也是需要技巧的，迄今為止，僅僅可說(shuō)這樣一個(gè)基應(yīng)當(dāng)是由足夠短的格矢量組成，意味著幾何上這樣的矢量離相互正交不遠(yuǎn)．下面給出規(guī)約基的一些精確定義．

2．1 規(guī)約基定義

從數(shù)學(xué)的觀點(diǎn)看，規(guī)約的歷史回溯到由lagrage，Gauss，Hermite等提出的二次型規(guī)約理論、由Minkowski開(kāi)創(chuàng)的數(shù)的幾何、以及1981年Lenstra的在整數(shù)線性規(guī)劃上做出的令人贊美的工作．1982年Lovász受啟發(fā)提出著名的LLL算法．這些算法在數(shù)學(xué)和計(jì)算機(jī)科學(xué)許多領(lǐng)域有著豐富的應(yīng)用．

在規(guī)約理論中常用到克拉姆－施密特正交化GSO（Gram－Schmidt Orthogonalization）．GSO廣泛用于格基規(guī)約，關(guān)鍵在于它允許三角化基．設(shè)Rn是n維實(shí)矢量空間，有標(biāo)準(zhǔn)內(nèi)積〈x，y〉＝xty，一個(gè)矢量b∈Rn，有長(zhǎng)度‖b‖＝，一個(gè)線性無(wú)關(guān)的有序矢量集b1，…，bd∈Rn是維數(shù)dim（L）＝d的格L?Rn的一個(gè)基，通常用矩陣B＝［b1，…，bd] ∈Rn×d表示基，記L＝L（B）＝L（b1，…，bd），所有矢量為矩陣列向量形式．設(shè)qi表示bi正交于的b1，…，bi－1分量，q1＝b1．基b1，…，bd的正交化矢量為q1，…，qd∈Rn，且Gram－Schmidt系數(shù)為，1≤i，j≤d，對(duì)j＝1，…，d滿足

設(shè)有格基b1，…，bd∈Zn，基長(zhǎng)度上邊界為M，不用快速整數(shù)算術(shù)，可以在O（d5log2M）時(shí)間內(nèi)計(jì)算出GSO系數(shù)，即有理數(shù)μi，j，‖

基的幾何標(biāo)準(zhǔn)型Geometric normal form（GNF）．基B∈有唯一的分解B＝QR，其中，Q∈Rn×d有兩兩正交的長(zhǎng)度為1的列，且R＝∈Rd×d是對(duì)角元為正的上三角矩陣，即i＞j，＝0，r1，1，…，rd，d＞0，因此，

稱(chēng)R為基的幾何標(biāo)準(zhǔn)型（GNF），記GNF（B）＝R．通過(guò)二次型的研究，Hermite最早引進(jìn)了弱規(guī)約的概念．

定義3 ［Hermite大小規(guī)約] 格L的一個(gè)基b1，…，bd是大小規(guī)約的，如果它的GSO系數(shù)對(duì)所有的1≤j＜i≤d，滿足｜μ，｜≤．幾何上，這意味著b

iji

在b1，…，bi－1線性張空間上投影bi－qi是在平行多面體P＝｜xj｜≤1／2｝內(nèi)部，規(guī)約時(shí)我們總是試圖減少bi在b1，…，bi－1線性張空間上的分量．定義也意味著對(duì)所有的1≤i≤d：‖≤

Lagrange在研究二次型時(shí)提出了下列規(guī)約概念．

定義4 ［Lagrange規(guī)約] 設(shè)L?Rn是一個(gè)2秩格，基為b1，b2，如果‖b1‖≤‖b2‖，且〈b1，b2〉≤‖b1‖2／2，則基為L(zhǎng)agrange規(guī)約的．

定理3 設(shè)L?Rn是一個(gè)2秩格，基b1，b2是Lagrange規(guī)約的，則‖b1‖＝λ1（L），‖b2‖＝λ2（L）．

LLL規(guī)約提出就是受到Lagrange規(guī)約的啟發(fā)．

定義5 ［Minkowski規(guī)約定義] 設(shè)格L的有序基B＝［b1，…，bd] ，如果對(duì)所有的1≤i≤d，在所有的按序排列的第i個(gè)格矢量中bi有最小的范數(shù)，使得［b1，…，bi] 可以擴(kuò)展成格L的一個(gè)基．

定義6 ［Minkowski規(guī)約等價(jià)定義［2]] 設(shè)格L的有序基B＝［b1，…，bd] ，如果對(duì)i∈［1，d] ，對(duì)任何整數(shù)x1，…，xd，使得xi，…，xd互素時(shí)，有‖x1b1＋…＋xdbd‖≥‖bi‖．

按上述定義，在低維時(shí)只需檢驗(yàn)一些條件子集．一般地，要確定給定的基是Minkowski規(guī)約的需要驗(yàn)證無(wú)數(shù)個(gè)條件．這種規(guī)約主要用在數(shù)的幾何理論上，因?yàn)椴磺宄欠裼卸囗?xiàng)式時(shí)間算法計(jì)算這樣的基，所以實(shí)際計(jì)算價(jià)值較?。?/p>

Korkine和Zolotarev進(jìn)一步加強(qiáng)了Hermite的大小規(guī)約，即Hermite－Korkin－Zolotarev－reduction，簡(jiǎn)稱(chēng)HKZ－reduced：

定義7 ［KZ（或HKZ）規(guī)約基遞歸定義［3]]

設(shè)格L的基B＝［b1，…，bd] ，［q1，…，qd] 為其Gram－schmidt正交化矢量，L（d－1）表示L到Rb1＝span（b1）的正交補(bǔ)上的投影，則KZ規(guī)約基滿足下列三個(gè)條件：

1）b1是格的最短非零矢量．

2）Gram－schmidt系數(shù)｜μ，｜≤≤i≤d．

i1

3）b2，…，bd到的投影，b2－μ2，1b1，…，bd－μd，1b1是格L（d－1）的KZ基．

定義8 ［KZ規(guī)約基非遞歸定義] 設(shè)格L的基B＝［b1，…，bd] ，L（d－1）表示L到Rb1＝span（b1）的正交補(bǔ)上的投影，則KZ規(guī)約基滿足下列三個(gè)條件：

1）對(duì)于1≤i≤d來(lái)說(shuō)，qi是格L（d－i＋1）的最短非零矢量．

2）Gram－schmidt系數(shù)

通過(guò)對(duì)任意二次型規(guī)約的研究，KZ及Minkowski考慮格基b1，…bd中b1是一個(gè)格最短非零矢量．Minkowski推廣這個(gè)特性到所有的子基上，即bi是子格bi，…，bd的最短非零格矢量．KZ進(jìn)一步推廣，要求子基bi，…，bd在線性空間上的正交投影也有這個(gè)特性成立．

定義9 ［分塊k規(guī)約基] 如果對(duì)i＝1，…，d－k＋1，bi，…，bi＋k－1在上的投影形成秩為k的KZ規(guī)約基，則稱(chēng)格基b1，…，bd為分塊k規(guī)約的．

注意到qi∈πi（L）且qi0，自然要求‖qi‖＝λ1（∏i（L）），特別地，條件‖qd‖＝也是必然滿足的．

這樣的k規(guī)約基是局部KZ規(guī)約的．對(duì)k＝2，概念上基本等價(jià)于LLL規(guī)約，對(duì)于d＝k＝2，與Gauss規(guī)約一致；對(duì)于d＝k，就是KZ規(guī)約．

對(duì)i＝0，…，m－2，如果對(duì)所有2k個(gè)分塊bik＋1，…，b（i＋2）k的投影是KZ規(guī)約的，稱(chēng)格基b1，…，bmk是2k規(guī)約的．

每個(gè)分塊2k規(guī)約基b1，…，bd包含一個(gè)近似因子為的最短格矢量．

為獲得多項(xiàng)式時(shí)間算法，schnorr［4]放松規(guī)約概念，提出準(zhǔn)k規(guī)約基和準(zhǔn)分塊2k規(guī)約基概念及算法．

2．2 KZ規(guī)約基和逐次最小值關(guān)系

設(shè)［b1，…，bn] 是格L的KZ規(guī)約基，λi（L），λi（L＊）分別表示L和其對(duì)偶格L＊的逐次最小值，Lagarias等1989年在文獻(xiàn)［3]中證明對(duì)所有的1≤i≤n總有，［4／（i＋3）] λi（L）2≤‖≤［（i＋，且≤［（i＋3）／4] ［（n－i＋4）／4，其中＝min｛γj：1≤j≤n｝，γj表示Hermite常量．

KZ規(guī)約基有兩個(gè)有趣的特性．第一，KZ規(guī)約基是逐次最小值的很好近似．

第二，HKZ規(guī)約基有局部特性．從它的遞歸定義中就能看出這一點(diǎn)，如果（b1，…，bd）是KZ規(guī)約的，則對(duì)所有的1≤i≤j≤是HKZ規(guī)約的．這樣通過(guò)研究低維KZ規(guī)約，可以遞歸得出任意維的特性．

3 規(guī)約算法目前的進(jìn)展

第一個(gè)SVP算法是Lagrange的規(guī)約算法，在二次時(shí)間內(nèi)解精確的二維SVP．對(duì)任意維格，有兩類(lèi)SVP算法．

3．1 精確算法

這些算法可證明找到一個(gè)最短矢量，但他們是開(kāi)銷(xiāo)很大，運(yùn)行時(shí)間至少是維數(shù)的指數(shù)次．本質(zhì)上，這些算法執(zhí)行一個(gè)窮舉搜索．精確算法可分成兩類(lèi)：

（1）多項(xiàng)式空間精確算法．這些算法基于列舉法，下面我們簡(jiǎn)要闡述列舉法的基本原理．列舉法與基的GSO關(guān)系密切，設(shè)（b1，…，bd）為格L基，相應(yīng)的GSO為（q1，…，qd），設(shè)u∈L是一個(gè)最短非零格矢量，M為一個(gè)設(shè)定的邊界值，比如設(shè)為M＝‖b1‖，此時(shí)有這樣就把u表示為GramSchmidt－正交化矢量的和，u的投影也容易表示為由于正交性故有‖u‖2≤M2，這些不等式限制了λd，…，λ1搜索范圍，可以找出所有長(zhǎng)度小于M的非零格矢量．最好的確定性的列舉算法是Kannan的算法［5]，具有超指數(shù)的最壞復(fù)雜度多項(xiàng)式時(shí)間運(yùn)算［6]．

Schnorr引入的“剪枝”（Pruning）技巧［7]，把列舉法和分塊規(guī)約結(jié)合起來(lái)，本質(zhì)上是在分塊KZ規(guī)約算法中利用列舉算法作為一個(gè)子過(guò)程，算法獲得一個(gè)很好的加速．

（2）指數(shù)空間精確算法．這些算法有更好的漸近運(yùn)行時(shí)間，但它們都需要指數(shù)空間2Θ（n）存貯．這類(lèi)算法的代表是Ajtai，Kumar，Sivakumar的隨機(jī)篩法（簡(jiǎn)記AKS）［8]，最壞情況下具有指數(shù)時(shí)間復(fù)雜度2O（n）．最近Micciancio等提出一個(gè)確定性算法［9]，能在多項(xiàng)式時(shí)間22n＋O（n）內(nèi)解CVP和SVP問(wèn)題．有趣的是有好幾個(gè)AKS的啟發(fā)式變形［10－12]，具有運(yùn)行時(shí)間2O（n）．

3．2 近似算法

這些算法比精確算法更快，但他們僅僅輸出一個(gè)短格矢量，不一定是最短的．算法一般輸出整個(gè)規(guī)約基，稱(chēng)之為格基規(guī)約算法，這類(lèi)算法最著名的當(dāng)屬Lenstra，Lenstra and Lovász開(kāi)發(fā)的LLL算法［13]，算法可在多項(xiàng)式時(shí)間內(nèi)解決近似因子為O（（2／）的SVP問(wèn)題，該算法可看作是Hermite不等式的算法版本．對(duì)LLL及其應(yīng)用的全面總結(jié)見(jiàn)LLL的25周年會(huì)議文集［1]，其中有兩章描述了對(duì)LLL算法的改進(jìn)．隨著LLL出現(xiàn)，研究主要集中在兩個(gè)方面：

（1）更快的LLL．獲得質(zhì)量類(lèi)似于或弱一些的LLL規(guī)約基，但用更少的運(yùn)行時(shí)間，技巧是通過(guò)分治策略，例如文獻(xiàn)［14] ．或通過(guò)浮點(diǎn)算法，當(dāng)用浮點(diǎn)數(shù)算術(shù)可以加快格基規(guī)約速度，但同時(shí)也會(huì)帶來(lái)浮點(diǎn)誤差，這些誤差會(huì)引起錯(cuò)誤的結(jié)果，甚至使得程序不能終止，因此，研究格基規(guī)約上的浮點(diǎn)運(yùn)算特性很有必要．第一個(gè)正確性得到證明的浮點(diǎn)LLL是由Schnorr于提出的［15]，最近，一個(gè)更有效的浮點(diǎn)LLL改進(jìn)由Nguyen和Stehlé提出的［7]．目前，最流行的版本是啟發(fā)式的浮點(diǎn)LLL．盡管常規(guī)方法有可證明的安全性，但有時(shí)啟發(fā)式的方法更有效．一個(gè)重要的啟發(fā)式方法是由Schnorr和Euchner于1994年提出的［7]，直到今天這個(gè)算法仍然是許多浮點(diǎn)LLL快速算法的基礎(chǔ)．有關(guān)浮點(diǎn)數(shù)的運(yùn)算請(qǐng)參考［16]．

（2）更強(qiáng)的LLL．用更多的運(yùn)行時(shí)間獲得比LLL更好的近似因子．分塊規(guī)約方法（定義9）是在LLL規(guī)約和HKZ規(guī)約之間取一個(gè)折中方案，當(dāng)分塊長(zhǎng)為d，參數(shù)δ＝1，分塊KZ規(guī)約等價(jià)于HKZ規(guī)約，當(dāng)分塊長(zhǎng)為2時(shí)，分塊KZ規(guī)約就是LLL規(guī)約．直覺(jué)地，LLL反復(fù)地用2維規(guī)約找到n維格的近似最短格矢量．用稍高維的精確規(guī)約子過(guò)程代替2維規(guī)約，分塊規(guī)約算法［4]獲得比LLL更好的近似因子．最好的多項(xiàng)式時(shí)間分塊規(guī)約算法［17]目前達(dá)到一個(gè)亞指數(shù)近似因子．這個(gè)算法是Mordell不等式的算法版本．文獻(xiàn)［7] 中也引進(jìn)了“深插入（deep insertion）”的技巧，當(dāng)Lovász條件不滿足時(shí)，用深插入方法代替原LLL算法中交換步驟，即不交換bk－1和bk，而是把bk插入某個(gè)位置i，其中1≤i≤k－1，為尋找i，因?yàn)椋絨i長(zhǎng)度相當(dāng)，i從1開(kāi)始，直到δqi＞（bk）（δ為參數(shù)）為止，這時(shí)基b1，…，bk，…，bd重排為b1，…，bi－1，bk，bi，…，bk－1，bk＋1，…，bd．對(duì)1d，等價(jià)于用下列條件代替Lovász條件這個(gè)改動(dòng)似乎改進(jìn)了規(guī)約基的質(zhì)量，盡管理論上也沒(méi)有得到可證明的最短矢量界，而且運(yùn)行時(shí)間也可能是亞指數(shù)的，但這個(gè)方法在實(shí)際中運(yùn)行良好．

Gama和Nguyen用NTL庫(kù)［18]實(shí)現(xiàn)三個(gè)不同算法：LLL算法，深插入的LLL算法，分塊KZ規(guī)約法，實(shí)驗(yàn)證實(shí)，后兩種算法得到規(guī)約基質(zhì)量比LLL要好，而且分塊值k越大，得到的規(guī)約基的質(zhì)量越高，但同時(shí)運(yùn)行時(shí)間也在增加．

可以看出，這兩大類(lèi)算法是互補(bǔ)的，所有的精確算法首先都用一個(gè)近似算法（如LLL）做預(yù)處理，而所有的分塊算法都要調(diào)用許多低維格的精確算法作為子過(guò)程．啟發(fā)式的方法在實(shí)際中被大量采用，它們的運(yùn)行時(shí)間提高很多，但理論上仍未得到證明．實(shí)際上，在高維時(shí)（n≥150），只有近似算法是實(shí)用的．

最后，人們以前普遍感覺(jué)格基規(guī)約算法的實(shí)際執(zhí)行效率比它們可證明的理論界更好．在上世紀(jì)80年代末，格問(wèn)題的計(jì)算復(fù)雜性吸引了人們的關(guān)注，主要因?yàn)锳jtai發(fā)現(xiàn)某種格近似問(wèn)題在最壞情況復(fù)雜度和平均情況下的復(fù)雜度之間聯(lián)系，吸引了理論密碼學(xué)和計(jì)算機(jī)復(fù)雜性領(lǐng)域?qū)＜业呐d趣．

眾所周知，密碼學(xué)需要平均意義上是困難的的問(wèn)題．當(dāng)一個(gè)密鑰被隨機(jī)選擇時(shí)，相應(yīng)的解密函數(shù)難于以很高概率被破解．格問(wèn)題的復(fù)雜性打開(kāi)了密碼設(shè)計(jì)之門(mén)．格規(guī)約在密碼分析上的成功使得人們相信存在象隨機(jī)Oracle預(yù)言器（證明密碼安全性的一種理想計(jì)算模型）一樣強(qiáng)的格基規(guī)約算法，但隨著Ajtai的最壞／平均情況復(fù)雜性格困難問(wèn)題的證明［19]，以及基于格的密碼系統(tǒng)NTRU的開(kāi)發(fā)［20]，人們對(duì)基于格的密碼的安全性有了更深的認(rèn)識(shí)．

4 規(guī)約算法性能分析

著名的LLL［13]及其變形在多項(xiàng)式時(shí)間內(nèi)計(jì)算一個(gè)近似因子為的格矢量．對(duì)于SVP問(wèn)題，kannan確定性算法［5]有一個(gè)超指數(shù)復(fù)雜度，需要2O（dlogd）次運(yùn)算（d指格的維數(shù)）．Ajtai的隨機(jī)算法［8]有一個(gè)指數(shù)復(fù)雜度2O（d）．

最好的解近似SVP問(wèn)題的多項(xiàng)式時(shí)間算法是分塊算法，在每一個(gè)小分塊上運(yùn)行精確的SVP算法，比如k是分塊大小，當(dāng)k比較小時(shí)，開(kāi)銷(xiāo)仍然是格的維數(shù)d的多項(xiàng)式，例如，kannan算法［5]，若選擇k＝log d／log log d，運(yùn)行時(shí)間2O（klogk）仍然是d的多項(xiàng)式．

Gama－Nguyen提出了一個(gè)很好的分塊算法［17]，在多項(xiàng)式次調(diào)用一個(gè)維數(shù)小于等于k的子過(guò)程SVP－Oracle后能解近似因子（（1＋ε的近似SVP問(wèn)題．

如果取分塊大小k＝log d，用AKS算法［8] 作為一個(gè)SVP子過(guò)程，獲得一個(gè)隨機(jī)多項(xiàng)式時(shí)間算法，解近似因子為，即亞指數(shù)因子的格問(wèn)題．

繼Lovász之后，kannan提出了一個(gè)求KZ規(guī)約基的算法，Kannan的算法［21]返回一個(gè)最短格矢量，但需要指數(shù)運(yùn)行時(shí)間．

通過(guò)運(yùn)用Kannan算法到長(zhǎng)為2k的分塊的格基中，Schnorr［15]改進(jìn)了LLL的近似因子為（k／3）n／k，具有時(shí)間復(fù)雜度為O（n3kk＋O（k）A）（其中A為O（n2）比特長(zhǎng)的整數(shù)進(jìn)行算術(shù)運(yùn)算所需的比特運(yùn)算的數(shù)量）．

LLL算法是眾多規(guī)約算法的基礎(chǔ)，為了更好地洞察LLL算法的基本思想，我們著重從基B的幾何標(biāo)準(zhǔn)型GNF：R＝［ri，j] ∈Rn×n來(lái)描述標(biāo)準(zhǔn)的LLL規(guī)約：格基B＝QR∈Rn×n是大小規(guī)約的，如果對(duì)所有的j＞i，｜ri，j｜／＋ε（常忽略ε）．

對(duì)δ∈（η2，1] ，η＝＋ε，如果B是大小規(guī)約的，且滿足條件：

定理4 對(duì)α＝1／（δ－η2），格L的一個(gè)LLL規(guī)約基B∈Rn×n滿足：

（1）‖b1‖2≤

格基B＝QB是HKZ規(guī)約（或HKZ基）定義：如果B是大小約簡(jiǎn)的，且GNF標(biāo)準(zhǔn)型：R＝［ri，j] ∈Rn×n的每個(gè)對(duì)角元系數(shù)ri，i在所有GLn（Z）（GLn（Z）＝｛T∈Zn×n｜det（T）＝±1｝）變換下是最小的，該變換保持b1，…，bi－1不變．

設(shè)基b1，…，bn∈Zn，維數(shù)n＝k·m，QR分解為［b1，…，bn] ＝QR，R∈Rn×n．分基矩陣為m個(gè)片段Bl＝［bk（l－1）＋1，…，bkl] ，l＝1，…，m．兩個(gè)相連的片段的局部規(guī)約用2k×2k子矩陣Rl：＝［rkl＋i，kl＋j] ，－k＜i，j＜k∈R2k×2k來(lái)表示，其中R2k×2k是R子矩陣，對(duì)應(yīng)于兩個(gè)相繼的片段Bl－1，Bl．局部規(guī)約用Bl的表達(dá)，通過(guò)計(jì)算系數(shù)ukl＋i，kl＋j和得到．我們?cè)谀硞€(gè)Rl的局部坐標(biāo)上做LLL交換和大小規(guī)約．

在所有的局部LLL規(guī)約完成后做額外的全局變換．k－分片規(guī)約基目的是最小化這些全局開(kāi)銷(xiāo)．用D（l）＝…‖表示分片Bl的局部Gramian行列式．我們有Dkl＝D（1）…D（l）．

定義10［14]稱(chēng)有序基b1，…，bn∈Zn，n＝k·m為δ∈［1／4，1] 的k－分片規(guī)約基．如果是大小約簡(jiǎn)的且對(duì)α＝1／（δ－1／4）滿足：δ‖≤＋‖，imod k；

定理5 設(shè)b1，…，bn是一個(gè)有參數(shù)δ的k－分片規(guī)約基，則對(duì)i＝1，…，n：

其中λ1≤…≤λn是格的逐次最小值．

k－分片規(guī)約算法通過(guò)在兩個(gè)相鄰的分片［Bl－1，Bl] ＝［bk（l－1）＋1，…，bkl＋k] 上迭代地做局部LLL子過(guò)程：Loc－LLL（l）．Loc－LLL（l）子程序計(jì)算分片［Bl－1，Bl] 的正交化和大小約簡(jiǎn)．兩個(gè)相連基矢量的LLL交換及局部大小規(guī)約僅僅需要O（k2）算術(shù)步，比起全局坐標(biāo)上的LLL交換的開(kāi)銷(xiāo)O（n2）要少多了．

Koy［14]的原－對(duì)偶基（Primal－dual）方法減少運(yùn)行時(shí)間到n3kk／2＋O（k）A且仍能達(dá)到一個(gè)近似因子≤（k／6）k／n．Koy的primal－dual規(guī)約減少Dl＝如下．最大化RlTl的GNF中的rkl，kl，最小化Rl＋1Tl＋1的GNF中的rkl＋1，kl＋1，其中Tl，Tl＋1∈GLk（Z），如果能減少rkl，kl和Dl就交換bkl，bkl＋1．該算法是分塊2k算法變形，被廣泛應(yīng)用在實(shí)際中，雖然未被證明是多項(xiàng)式時(shí)間的．

Schnorr層次規(guī)約法（Hierarchy lattice basis reduction）．1987年Schnorr提出了多項(xiàng)式時(shí)間的層次規(guī)約算法［4]．?dāng)U展了LLL和KZ規(guī)約的技術(shù)，改進(jìn)了Kannan的KZ規(guī)約算法．設(shè)任意秩為n的格基b1，…，bn∈Rm，該算法作用在O（nlog‖B‖）比特的整數(shù)上，能夠在O（n2）（＋n2）log‖B‖時(shí)間內(nèi)找到一個(gè)非零格矢量b，且‖b‖2≤（6k2）k／nλ（L）2，其中k為相應(yīng)的KZ規(guī)約法中基分組長(zhǎng)，‖B‖為輸入基的最大歐幾里得范數(shù)．

2001年Ajtai等發(fā)現(xiàn)了一個(gè)隨機(jī)算法AKS［8]，該算法用了篩法的原理，比kannan的確定性算法具有更好的漸近復(fù)雜度．AKS算法以很高的概率在2O（n）時(shí)間內(nèi)找到一個(gè)最短格矢量．

文獻(xiàn)［22] 提出一種更快的LLL類(lèi)算法：SLLL算法，用基的分片方式進(jìn)行，通過(guò)迭代子分片進(jìn)行LLL規(guī)約，子分片運(yùn)行O（n3logn）算術(shù)步，最后得到的逐次最小值和原LLL幾乎相同．

對(duì)維數(shù)為n的整格，給定基長(zhǎng)度為2O（n），對(duì)δ＞0，SLLL規(guī)約運(yùn)行在O（n5＋ε）比特的整數(shù)上，而原LLL運(yùn)行在O（n7＋ε）比特整數(shù)上，Schnorr在1988年改進(jìn)的LLL和Storjohann在1996年實(shí)現(xiàn)的LLL需要運(yùn)行在O（n6＋ε）比特整數(shù)上．

文獻(xiàn)［23] 利用Grover量子搜索算法QSR，能達(dá)到近似因子（k／6）n／2k，有預(yù)期的運(yùn)行時(shí)間O（n3（k／6）k／8A＋n4A），這大約是Schnorr隨機(jī)抽樣規(guī)約算法的平方根．量子計(jì)算的使用將不僅影響基于整數(shù)分解或離散對(duì)數(shù)問(wèn)題的密碼安全性，而且也影響基于格密碼系統(tǒng)的密碼安全性，如果目前量子計(jì)算機(jī)可利用，建議NTRU安全參數(shù)需要增加為503－1277．最后給出一個(gè)表格進(jìn)行總結(jié)．

表1 幾種規(guī)約算法的漸近資源界和近似因子

［1] Nguyen P，Vallée B．The LLL algorithm：survey and applications［M] ．New York：Springer－Verlag Inc，2010．

［2] Nguyen P，StehléD．Low－dimensional lattice basis reduction revisited（Extended Abstract）［J] ．Lecture Notes in Computer Science，2004，3076：338－357，．

［3] Lagarias J，Lenstra H，Schnorr C．Korkin－Zolotarev bases and successive minima of a lattice and its reciprocal lattice［J] ．Combinatorica，Springer，1990，10：333－348．

［4] Schnorr C．A hierarchy of polynomial time lattice basis reduction algorithms［J] ．Theoretical computer science，Elsevier，1987，53（2－3）：201－224．

［5] Kannan R．Improved algorithms for integer programming and related lattice problems［C] ／／Proceedings of the fifteenth annual ACM symposium on Theory of computing，1983：193－206．

［6] Hanrot G，StehléD．Improved analysis of Kannan’s shortest lattice vector algorithm［C] ／／Advances in Cryptology－CRYPTO 2007，Springer，2007：170－186．

［7] Schnorr C，Euchner M．Lattice basis reduction：improved practical algorithms and solving subset sum problems［J] ．Mathematical programming，Springer，1994，66（1）：181－199．

［8] Ajtai M，Kumar R，Sivakumar D．A sieve algorithm for the shortest lattice vector problem［C] ／／Proceedings of the thirtythird annual ACM symposium on Theory of computing，2001：601－610．

［9] Micciancio D，Voulgaris P．A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations［C] ／／Proceedings of the 42nd ACM symposium on Theory of computing，2010：351－358．

［10] Nguyen P，Vidick T．Sieve algorithms for the shortest vector problem are practical［J] ．J．of Mathematical Cryptology，Citeseer，2008，2（2）：181－207．

［11] Micciancio D，Voulgaris P．Faster exponential time algorithms for the shortest vector problem［C] ／／Proceedings of the Twenty－First Annual ACM－SIAM Symposium on Discrete Algorithms，2010：1 468－1 480．

［12] Wang X，Liu M．Improved Nguyen－Vidick heuristic sieve algorithm for shortest vector problem［C] ／／Proceedings of the 6th ACM Symposium on Information，Computer and Communications Security，2011：1－9．

［13] Lenstra A，Lenstra H，Lovász L．Factoring polynomials with rational coefficients［J] ．Mathematische Annalen，Springer，1982，261（4）：515－534．

［14] Koy H，Schnorr C．Segment LLL－reduction of lattice bases［M] ．Cryptography and lattices，Springer，2001：67－80．

［15] Schnorr C．A more efficient algorithm for lattice basis reduction［J] ．Journal of Algorithms，Elsevier，1988，9（1）：47－62．

［16] StehléD．Floating－point LLL：theoretical and practical aspects［M] ．The LLL Algorithm，Springer，2010：179－213．

［17] Gama N，Nguyen P．Finding short lattice vectors within mordell＇s inequality［C] ．Proceedings of the 40th annual ACM symposium on Theory of computing，2008：207－216．

［18] Shoup V．Number Theory C＋＋Library（NTL）version 5．4．1［CP／OL] ．（2011－08－11）［2011－10－31] http：／／www．shoup．net／ntl／．

［19] Ajtai M．Generating hard instances of lattice problems（extended abstract）［C] ／／Proceedings of the twenty－eighth annual ACM symposium on Theory of computing，1996：99－108．

［20] Hoffstein J，Pipher J．NTRU：A ring－based public key cryptosystem［M] ．Algorithmic number theory，Springer，1998：267．

［21] Kannan R．Minkowski＇s convex body theorem and integer programming［M] ．Mathematics of operations research，JSTOR，1987：415－440．

［22] Schnorr C．Fast LLL－type lattice reduction［J] ．Information and Computation，Elsevier，2006，204（1）：1－25．

［23] Ludwig C．A faster lattice reduction method using quantum search［M] ．Algorithms and Computation，Springer，2003：199－208．