格的歷史

公鑰密碼學(xué)的安全性都建立在數(shù)學(xué)問(wèn)題的困難性上，但量子計(jì)算的不斷發(fā)展，意味著從理論上，基于大整數(shù)分解的RSA方案、基于離散對(duì)數(shù)問(wèn)題的Diffie-Hellman等方案都不再安全。而格密碼學(xué)將成為候選抗量子計(jì)算攻擊的密碼學(xué)方案。因此，未來(lái)對(duì)于格密碼學(xué)的研究勢(shì)必會(huì)越來(lái)越深入。

研究格的代表人物有 Lagrange，Gauss 和 Minkowski 等等。最近的幾十年內(nèi)，Lattice 在密碼學(xué)、通訊、密碼分析上有了很大的應(yīng)用價(jià)值，是非常火的一個(gè)領(lǐng)域。

近代 Lattice 時(shí)間線：

• 1982：LLL basis reduction theorem 使用 Lattice 進(jìn)行 Cryptanalysis
• 1996：Ajtai-Dwork 第一次把 Lattice 中 Average-case 與 Worst-case 的復(fù)雜度問(wèn)題關(guān)聯(lián)起來(lái)；提出了使用 Lattice 構(gòu)造的 One-way Function 與 CRHF （Collision Resistant Hash Function）
• 2002：找到了 Average-case/worst-case 復(fù)雜度之間的關(guān)系，基于 Lattice的協(xié)議變得更加高效
• 2005：Regev 提出了 LWE，并且發(fā)現(xiàn)其量子抵抗性；提出 PKE，IBE，ABE，FHE 等等的可能性

格的定義

在數(shù)學(xué)中有兩個(gè)完全不同的對(duì)象都稱(chēng)為格。Lattice的本質(zhì)就是高維空間中幾何學(xué)和代數(shù)學(xué)的組合。我們現(xiàn)在說(shuō)的格是定義為向量空間的離散子空間Rⁿ。

格是 m 維歐式空間 R^m的n（m>=n）個(gè)線性無(wú)關(guān)向量 b_i(1<=i<=n)的所有整系數(shù)的線性組合，即
這里 B 就是 n 個(gè)向量的集合，我們稱(chēng)

• 這 n 個(gè)向量是格 L 的一組基。
• 格 L 的秩為 n
• 格 L 的位數(shù)為 m

如果 m=n，那么我們稱(chēng)這個(gè)格式滿秩的。

格的基本屬性

在一個(gè)線性空間里面，一個(gè)空間的 Determinant （行列式）代表了這個(gè)空間所有的基向量所組成的幾何體的體積。在二維空間里，兩個(gè)基向量組成的平行四邊形的面積就是這個(gè)空間的 Determinant。

同理可得，一個(gè) Lattice 的 Determinant 也是一樣的——對(duì)應(yīng)的基向量所組成的 Parallelepiped 的體積。

得注意的是，無(wú)論我們?cè)趺锤鼡Q基向量，Determinant 的大小，即基向量組成的多面體的體積是相同的。給定任意的一組基向量，我們都可以有效的找到這個(gè) Lattice 空間的 Determinant。

我們可以用一個(gè) Lattice 的 Determinant 來(lái)衡量這個(gè)格的點(diǎn)陣分布的密度。

首先，我們把上一部分基向量組成的多面體的中心挪到原點(diǎn)上來(lái)。這樣，空間仍然保持相同的體積。

隨后，我們可以把這個(gè)多面體復(fù)制多份，然后平移到每一個(gè) Lattice 中的點(diǎn)上。這樣我們就會(huì)得到很多份，并且這些多面體可以平分整個(gè)多維空間。

此時(shí)，我們?nèi)绻谶@個(gè)空間中任意的畫(huà)一個(gè)球體（多維空間即超球體），然后可以數(shù)數(shù)看這個(gè)球體中覆蓋了多少 Lattice 里的點(diǎn)。點(diǎn)的數(shù)量平均于球體的體積，就是這個(gè)格的密度了。

這個(gè)概念理解起來(lái)也非常簡(jiǎn)單。我們的球體中有多少個(gè) Lattice 的點(diǎn)，其實(shí)大概和球體的體積中有多少個(gè)的多面體，這兩個(gè)比例大致相同。

格上的基本問(wèn)題

與格相關(guān)的基本計(jì)算性難題有:在格中尋找最短的非零向量和在格中尋找與指定非格向量最為接近的向量。

最短向量問(wèn)題(SVP): 在格L中尋找一個(gè)最短的非零向量,即尋找一個(gè)非零向量v∈L,使它的歐幾里得范數(shù)||v||最小。

最近向量問(wèn)題(CVP): 給定一個(gè)不在格L中的向量w∈R^m,尋找一個(gè)向量v∈L,使它最接近w,即尋找一個(gè)向量v∈L,使歐幾里得范數(shù) ||w一v||最小。

要注意的是,在格中可能存在不止一個(gè)最短的非零向量。例如，在Z²中，(0,土1)和(士1,0)這四個(gè)向量都是SVP的解。這就是為什么在問(wèn)題的描述中指出“尋找一個(gè)向量"而不是說(shuō)“尋找這個(gè)向量”。這種情形同樣適用于CVP。

對(duì)SVP進(jìn)行求解可以用于攻破多種密碼系統(tǒng)，隨著格的維度n的增加，在計(jì)算上也越來(lái)越難解。一般來(lái)說(shuō),CVP被認(rèn)為是NP難問(wèn)題，SVP在特定的“隨機(jī)歸約假設(shè)”下也被認(rèn)為是NP難問(wèn)題。在實(shí)際應(yīng)用中,一般認(rèn)為CVP比SVP"稍微難一點(diǎn)”,因?yàn)镃VP經(jīng)常可以被歸約成稍微高一點(diǎn)維度的SVP。例如，一個(gè)用于解背包密碼系統(tǒng)的(n+1)維的SVP可以很容易地轉(zhuǎn)換成n維的CVP。

在理論和應(yīng)用中，還有一些很重要的SVP和CVP的變形形式。

最短基問(wèn)題(SBP)： 尋找格的一個(gè)基v₁，v₂，···，v_n，使它在某些情況下最短。例如，使下式最小：

近似最短向量問(wèn)題(apprSVP)： 給定格 L，找到格 L 中的非零向量 v 使得對(duì)于格中的任意其它非零向量 u，||v||<=γ||u||

近似最近向量問(wèn)題(apprCVP)： 和apprSVP類(lèi)似,只不過(guò)要找的是對(duì)CVP的近似解，而不是對(duì)SVP的近似解

總結(jié)

以上是生活随笔為你收集整理的lattice学习笔记（一）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。