格(Lattice)學習筆記之一:歷史與基本概念

買賣虛擬貨幣
Lattice的歷史Lattice(格)在很早以前就被各大數學家研究了一遍。代表人物有Lagrange,Gauss和Minkowski等等。最近的幾十年內,Lattice在密碼學、通訊、密碼分析上有了很大的應用價值,是非常火的一個領域。近代Lattice時間線:1982:LLL basis reduction theorem使用Lattice來做Cryptanalysis1996:Ajtai-Dwork
第一次把Lattice中Average-case與Worst-case的複雜度問題關聯起來提出了使用Lattice構造的One-way Function與CRHF(Collision Resistant Hash Function)2002:找到了Average-case/worst-case複雜度之間的關係,基於Lattice的協議變得更加高效2005:Regev提出了LWE,並且發現其量子抵抗性提出PKE,IBE,ABE,FHE等等的可能性Lattice是什麼

Lattice可以被想象成是一個空間中很多有規律分佈的、離散的點。

我們可以對此Lattice進行任意的線性變換(Linear Transformation)B,然後可以得到新的Lattice。

Lattice與Bases(格與基)

更好的描述一個格的方法是使用基向量。

同理可得,我們可以用線性代數中學到的基變更(Change of basis)給這個Lattice找到一組新的基C。

如果系統性的定義一下Lattice的話,那麼我們可以說Lattice是Rn這個空間中的一個離散的、具有加法運算的子群(A discrete additive subgroup)。

Lattice的基本屬性

同理可得,一個Lattice的Determinant也是一樣的——對應的基向量所組成的Parallelepiped的體積。

同理,我們換了一組基向量,也可以計算它的Determinant。

值得注意的是,無論我們怎麼更換基向量,Determinant的大小,即基向量組成的多面體的體積是相同的。給定任意的一組基向量,我們都可以有效的找到這個Lattice空間的Determinant。

Lattice的密度

我們可以用一個Lattice的Determinant來衡量這個格的點陣分佈的密度。

首先,我們把上一部分基向量組成的多面體的中心挪到原點上來。這樣,空間P仍然保持相同的體積。

隨後,我們可以把這個多面體複製多份,然後平移到每一個Lattice中的點上。這樣我們就會得到很多份P,並且這些多面體可以平分整個多維空間Rn。

此時,我們如果在這個空間中任意的畫一個球體(多維空間即超球體),然後可以數數看這個球體中覆蓋了多少Lattice裡的點。點的數量平均於球體的體積,就是這個格的密度了。

這個概念理解起來也非常簡單。我們的球體中有多少個Lattice的點,其實大概和球體的體積中有多少個det(L)的多面體,這兩個比例大致相同。

最短距離

距離函式(Distance Function)與覆蓋半徑(Covering Radius)

給定任意一個點t(這個點不需要在Lattice上),我們可以定義距離函式u(t,L)為這個點到附近的Lattice點的最短距離。

同理可得,我們也可以左右移動t的位置,然後就可以找到在這個Lattice中可以得到的最大的u。我們一般稱這個最大值叫覆蓋半徑(Covering Radius)。

為什麼稱這個最遠距離為覆蓋半徑呢,其實很簡單。我們可以假設在這個Lattice中,以每個格點為圓心畫很多歌圓。

如果逐漸把圓的半徑擴大的話, 那麼所有的圓就會逐漸開始覆蓋整個Rn空間。

直到所有的圓正好完美的覆蓋了所有的空間的時候,這個時候的半徑,就是我們之前得到的u了。這就是覆蓋半徑這一名字的由來。

Lattice的Smoothing

如果我們把上面的覆蓋圓的概念稍微轉換一下,假設我們不是在每個格點上疊加一個圓形,而是疊加一個圓形範圍內取值的隨機噪音,那麼當圓的半徑達到覆蓋半徑之後,這個Lattice本身就和背後的連續空間Rn合二為一了。

但是如果就只是在覆蓋半徑上的話,可以在圖上發現,噪音覆蓋的分佈非常的不平均,因為格點之間相互的位置的問題。這也就是說,疊加了噪音之後,最後得到在Rn上的取值分佈也不平均。

如果想讓取值分佈更加平均的話,我們就需要更多的Smooth(平滑化?)這個Lattice,即繼續擴大圓的半徑。理論上當半徑接近於無限大的時候,我們得到的分佈是最完美、最平均的。但是當圓無限大了之後,這個構造就沒有太多實際操作的意義了。

所以一般來說,我們都會給這個Smoothing的半徑一個最大上限。這個最大上限是由這個Lattice中距離最大的最短向量來決定的。因為當我們的半徑大於了這個最短向量之後,那麼這個圓就會覆蓋太多的點(因為最短距離決定了點到點之間的距離),然後這個構造就失去了意義。

Minkowski凸集定理(Convex body theorem)

對於Lattice,Minkowski給出了幾個比較有意思的定理。第一個定理是用於尋找一個格點周圍最近的其他格點的,即凸集定理。

在整數格Zn中非常好理解,因為以原點出發到所有下一個點這段距離構成的空間,恰好就是2n,所以說任何凸集(集合的表面不能有凹陷)只要體積大於2n,那就一定會溢位這段空間,進而覆蓋某個非0的格點。透過Pigeonhole Principle(鴿子洞原理)就可以很生動的理解了。

接下來,如果我們換成一個不規則的Lattice,即在原有的Zn上疊加線性變換,這個定理還是成立的。

Minkowski第二定理

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;