為了更加方便的舉例子，我們這裡介紹一個最簡單的格系統——整數格（Integer Lattice）。
現在，如果我們再給這一個線性空間系統加上一個約束：所有的線性組合係數都必須是整數（Integer），那會和之前有什麼不同呢？
因為圖片上看上去是網格狀的，我們把這樣的一個離散的基向量生成空間集合，稱之為整數格（Integer Lattice）。
在這裡，為了方便理解，我們舉的例子僅僅是一個2維的格空間，但是其實我們可以擴充套件構造任意維度的格空間，唯一隻需要把基向量的維度增加就好了。
實際上，如果我們需要把整數格設計成方便密碼學應用的系統的話，那麼我們一定需要很高的維度，才能確保問題的困難度。這個我們後續再詳細描述。
整數格（Integer Lattice）的構造
瞭解了整數格是什麼之後，我們不禁會想：這玩意有什麼大不了的？不就是一個離散的線性生成集合嘛。但恰巧因為這個系統是離散的，並且只允許整數出現，我們會發現有很多有趣的問題。
這個很難的問題，就是格密碼學的開端了。基於CVP問題，我們可以從而衍生出一個新的難題：Learning With Error（LWE）問題。
PS：格密碼學中還有另一個難題叫SVP問題（Shortest Vector Problem），和CVP不同但也是NP-hard的問題。我們在這裡就不多解釋了。
Learning With Error（LWE）問題
讀到這裡，想必大家應該對整數格已經有了一個大致的理解，並且也知道了整數格中的一個難問題：CVP問題。現在我們一起來看看，如何從CVP問題出發，衍生到我們的主角LWE問題上。為了更加方便理解LWE，我們不妨先來回顧一下中學數學～
我們在初中或者高中的數學課上應該都學過如何求解線性方程組（solve system of equations）。一般來說，我們會給到一組多元一次方程：
有噪音的高斯消除問題（Gaussian Elimination with Noise）
當我們學會如何求解線性方程組之後，我們發現這其實並不是什麼難的問題，只需要不停地在行與行之間相互使用高斯消除，就可以得到未知數的解。畢竟這也是中學的時候學的數學題，難不到哪裡去。
現在，我們把這個高斯消除問題變化一下，給它增加一些難度：增加噪音。
假如這個問題變成，如果已知一個矩陣A，並且我們還知道一個向量:
這樣說來，如果CVP是一個複雜度很高（NP-hard） 的問題的話，那麼相對應的，LWE問題也是一個 複雜度很高（NP-hard ）的問題了。
大家應該對LWE是什麼有概念了吧？接下來，我們來看LWE的正式定義！
搜尋LWE問題（Search LWE Problem）的正式定義
首先，我們需要熟悉一下，LWE問題裡面需要用到的一些關鍵概念：
引數詳細說明
是不是乍一看一堆符號有些難以理解？莫慌，讓我們來逐一看看這個定義到底是什麼意思。
從搜尋LWE（Search LWE）到決策LWE（Decisional LWE）
Diffie-Hellman公鑰交換中的離散對數問題（Dlog Problem）
看到這裡，對密碼學熟悉的朋友們可能會對一個問題的多種版本（如搜尋、決策）等等並不陌生。沒錯，在我們學習Diffie-Hellman公鑰交換問題的時候，我們也使用了相同的問題轉換。如果不瞭解的朋友也不用著急，容我解釋一波。
然而，如果我們比較DDH和CDH問題的難度的時候，我們會發現，CDH問題其實比DDH問題難的多。具體的原因我們上期其實也稍微有所講到——因為配對（Pairing）這一特殊屬性的存在。
DLWE與DDH的困難度比較
為什麼我們要長篇大論的扯DDH問題呢？這是因為，瞭解了SLWE/DLWE與CDH/DDH這兩對密碼學中被認為困難的問題之後，我們可以來比較他們的困難度分佈到底是怎麼樣的。
DDH假設其實非常的不完美，甚至於令人頭疼。因為Pairing這個後門的存在，這直接給DDH問題設定了一個驚人的困難度下限——在Pairing存在的組中，DDH問題太簡單了。所以我們在挑選群的時候，一定要精心挑選。DDH的大哥CDH卻不一樣，因為沒有任何高效率的演算法可以破解離散對數，所以在任何迴圈群中的複雜度都較為平均。這樣一來，CDH就算再困難，對於DDH的困難度分佈也沒有太多實質性的幫助。我們往往需要使用平均困難度來定義DDH問題的困難度（因為下限太低了）。這在密碼學中是一件非常膈應人的事情，就像是我送給你一輛車，但是告訴你這個車，有一定的可能性會一開就自動散架一樣。
相比起來，LWE問題就完美許多。因為沒有任何像Pairing一樣的後門的存在，所以DLWE問題其實和SLWE的困難度是相同的。因為不管是解決DLWE還是SLWE，我們都會被卡在如何還原未知向量這一步上面。像這一類就算問題形式被轉換，但是複雜度保證大致相同的問題，在密碼學中是不可多得的寶貝。對於DLWE問題的困難度，我們可以很優雅的使用最壞困難度（Worst Case Performance）來定義。
這一段其實多少都是密碼學界大家的情懷，有一個乾淨的定義比搞一堆亂七八糟的假設來的舒服多了。這也就是為什麼格密碼學那麼的吸引人的原因。 不過，這些關於困難度/複雜度的小情緒，對於我們理解全同態加密是無關緊要的。大家可以當作茶餘飯後的趣聞，隨便看看。
DLWE的實戰應用：格密碼學與Regev加密演算法
如果你成功的啃完了前面的乾貨，看到了這裡，那麼恭喜你，現在你已經掌握了LWE與格密碼學的基礎了！
現在，當我們學會了這麼多知識之後，我們可以結合一下之前學習的內容，融會貫通一下， 來看看如何使用LWE問題來構建一個格密碼學中常見的公鑰加密系統——Regev加密演算法。
Regev加密是一個叫Regev的大佬在2005年發明出來的，是一個非常類似於ElGamal型別的公鑰加密系統，基於了DLWE的假設。我們來看看它的具體定義吧：
Regev加密的正確性
Regev加密演算法的正確性（Correctness）其實挺好理解的，我們可以把解密部分所做的計算展開：
如果對Regev做的事情還是一頭霧水的話，不妨我們來看一下Regev當年論文中給到的一張圖。因為我們在一個有限素數域中，所以所有的數字連起來是一個環狀結構，這也對應了圖上的環。當我們需要加密一個bit的時候，我們就把這個bit的值對映到這個環上來——0代表環的一頭（即0），1代表環的另一頭（即q/2）。我們疊加的噪音就等於是把這個對映的點往上或者往下位移了一部分，這樣只要噪音的大小不過分（低於q/4），我們就可以透過看這個值到底在環的哪一側來判斷這個bit的具體取值了。
看到這裡，想必有些朋友可能會突然恍然大悟——Regev加密中的這個噪音，和我們上一期提到的有限級數全同態加密的噪音概念非常相似！的確，全同態加密體系的實現，和我們這裡提到的把一個bit對映到環上並且疊加噪音的場景非常相似。一旦疊加的噪音超過了臨界值（q/4），我們就無法判斷這個bit到底原來是1還是0了，我們也就無法還原這段密文了。具體的內容留個懸念，我們下期繼續討論～
Regev加密的安全性
剛才屬性的話題討論到一半，我們打了個岔。最後我們回來繼續學習一下，Regev加密系統的安全性（Security）。
為了證明Regev加密體系是語義安全的，我們需要使用密碼學中的一種常見的證明工具：混合論證法（Hybrid Argument）。混合論證其實並不是什麼黑科技，而是我們把要證明的問題劃分成若干小步，然後逐步證明罷了。
首先，我們來看一下，假如一個第三方偷看到了Regev加密系統的加密密文的所有訊息，那麼他的世界觀是這樣的：
未完待續：構建有限級數全同態演算法
最後，我們來回顧一下這一期的內容～
首先，我們一起看到了整數格（Integer Lattice）的定義，然後基於整數格瞭解了NP-hard的最短向量問題（ CVP）。隨後，我們重新回顧了高中時期學習的求解線性方程組問題，並且統一歸納為高斯消除問題。隨後，我們給高斯消除問題本身加入了一個隨機的誤差噪音，從而構成了我們的主角，誤差還原（LWE）問題。
瞭解了LWE是什麼之後，我們又詳細學習了LWE問題的正式定義，以及其中的等引數。接著我們把搜尋LWE（SLWE）轉換為決策LWE（DLWE）問題，然後探討了SLWE/DLWE的假設為什麼比CDH/DDH更好。最後，我們結合了所有學習的知識，一起構建了格密碼學中很經典的Regev加密演算法，透過LWE的困難假設對密文（一個bit）進行加密。
如果你讀到這裡，並且成功的理解了所有的內容的話，那麼其實你已經掌握了全同態加密80%的精髓了！ 接下來，我們需要做的只是把這些部分像搭積木一樣搭起來，就可以構成我們想要的全同態加密系統了。
由於篇幅原因，我們這一期就寫到這裡。下一期，我們使用這期學到的知識，一起來構建一個有限級數全同態加密體系。
