一， fully homomorphic encryption（FHE）
Craig Gentry是Stanford大學Dan Boneh的博士生，在他攻讀博士學位期間，他成功的提出了一個fully homomorphic encryption scheme，較為成功的解決了這一密碼學領域很重要的open problem。這一構造的基礎是一些關于Ideal Lattice的技術，從之後的進一步發展來看，這一數學結構也被用來解決multilinear map等問題，可以說是一個相當重要的貢獻。他在他的博士論文（http://crypto.stanford.edu/craig/）（A FULLY HOMOMORPHIC ENCRYPTION SCHEME 2009年）中更近一步較為詳細的介紹了他的這一工作。他的這一工作在短短的時間内引用已經超過了1000次！可見大家對其的重視。
我們先來看一下他phd thesis的Abstract：
這裡的最後一段已經高度抽象地表述了他的基本思路。那就是由于直接構造FHE實在太困難，我們先構造一個能力較為有限的（即同态的層次是較為受限的） SHE，什麼樣的有限呢？就是有這樣的性質，當我們居然在這種encryption scheme之上進行其對應的decryption function運算時，由于它的解密能力是有限的，不能直接解密得到最原始的明文層，但是可以使得加密的這些密文“較為接近”明文。然後一旦具有這種性質“boostrappable”的somewhat homomorphic encryption（SHE）被得到了，那麼我們就可以對其不斷的疊代，利用它的這種能力，不斷進行self-embedding（先按某一種function在基礎密文上進行運算，然後“适度解密”一下，然後再加密、再“适度解密”·······這樣進行下去，一個原先同态性很有限的SHE就可以建構出我們所需要的最終的FHE了！（很明顯的看到了某種一般的解題的模式了吧，如同使用數學歸納法來解決一個難題一樣，先考慮一種簡單的，然後想辦法
下面我們稍微細緻的進一步看一下他的想法。
一。确定我們的問題，求解的目标。到底啥是FHE？： one can arbitrarily compute on encrypted data { i.e., one can process encrypted data (query it, write into it, do anything to it that can be effciently expressed as a circuit) without the decryption key. As an application, they suggested private data banks.
二，基本架構包括一個基本的SHE以及一個Recrypt。SHE加密中加密後的密文還伴随着一個noise值，這一noise值在我們進行密文上的同态Add、Mult時也會相應的增加。如果要保證加密後的密文能夠被解密，我們必要要使得這最終密文所伴随的noise小于某一個門檻值N。顯然這樣的一種SHE隻能實作有限的（受門檻值限制）次的同态運算。
如果我們對某一密文可以進行一個Recrypt操作，即使得經該操作後，仍是相同原明文的密文，但是相應的noise确實<sqrt(N)的，這樣的話，我們就可以使得每一次的Add或Mult密文同态到的結果對應的noise仍小于N，這樣我們就可以不斷的利用這種方法得到FHE了。而本文中是如何實作這種Recrypt的限制noise功能的呢？主要就是使得構造出來的SHE具有基于decryption function的boostrapable能力（“ a somewhat homomorphic encryption scheme that has this self-referential property of being able to handle circuits that are deeper than its own decryption circuit --in which case we say the somewhat homomorphic encryption scheme is ’bootstrappable‘-- is enough to obtain the Recrypt algorithm, and thereby fully homomorphic encryption! ”）
而為什麼基本的基石技術采用Ideal Lattice呢，這是因為其的一些特點在此将很有用：First, the circuit complexity of the decryption algorithms in typical lattice based encryption schemes is very low, especially compared to schemes like RSA or ElGamal, which rely on exponentiation, an operation that we do not know how to parallelize well. Second, since ideal lattices correspond to ideals in polynomial rings, they inherit natural Add and Mult operations from the ring. 即ideal lattice的解密算法本身更為簡單。
an ideal lattice has many representations or “bases". Some bases are “good" and can be used as the secret key, while some are “bad" and can be used as the public key -- i.e., they are good enough to be used for encryption, but not decryption.
二，Multilinear Map
論文《Candidate Multilinear Maps from Ideal Lattices》（GGH13） by Sanjam Garg， Craig Gentry and Shai Halevi。
如何構造出Multilinear map是2001年以後，随着Dan Boneh等人通過構造出bilinear map解決了當時仍為open problem的Identity Based Encryption等問題之後自然而然的一個祈求。因為Bilinear map已經被用來解決了好多原先以為很難的問題，并且據bilinear map的基本技術工具--（主要是圓錐曲線上的）pairing 技術形成了一個較新的密碼學分支--Pairing Based Cryptography。同時人們發現如果可以進一步得到multilinear map将可以有更加廣闊的應用，可以作為工具解決更多的問題，比如FHE. 是以在FHE被Gentry解決後，可能他自然而然地反向想到可以使用這種基于Ideal Lattice的技術手段來建構出MLM。當然這一點隻是我個人針對論文發表順序推向出來的，這種重大的發現背後肯定也是這些大師十分非凡努力的結果。
下面我們具體來看GGH三人是如何天才般的加以構造的，從中我們可以看到與上述FHE構造相似的一些基本思路。
首先因為之前Dan Boneh等前輩已經證明了這一構造的一些impossibility ，明确的提出可能的構造可能是一種Unntural的方式才能實作。
他們看待multilinear map（MLM）的角度又是獨特的，首先從各個group Gi内，他們指出了加密的實質就像一種encoding。然後這種encoding是可以一層一層的進行的，達到k層時就達成了k MLM的目的。這就是通過同功能轉換為（GES）Graded Encoding Systems來近似的實作MLM！（這裡主要先闡述symmetric MLM的情況，下面有一部分會介紹如何通過簡單的extension将其轉化為asymmetric的情形）。
一，multinear map（MLM）的本質要實作的什麼？
然後這是基本的結構，這一密碼系統需要對其上的一些operation有複雜度（難度）上的要求。即Speci cally, a cryptographic multilinear map scheme consists of effcient procedures for instance-generation, element-encoding validation, group-operation and negation, and multilinear map, MMP = (InstGen; EncTest; add; neg;map).即這幾個操作時efficient的：基本上述系統的生成是容易的，如各種參數；在各個source group上的加密是容易的；某一特點source group内部的的同态addition與negation是容易的；實作我們所需要的那一次k-map的計算是容易的。
另一方面，這一系統需要最起碼有兩個hardness基本assumption：
這構成了其安全性的基礎。當然安全性的證明不是我們這個簡介的重點，下面我們仍是重點分析其構造思路。
要想了解GGH的構造，我們必須轉變我們看待MLM的角度，看到其本質，從encoding的角度重新了解它。這裡其實和抽象代數系統很像。完全可以将MLM看做是滿足上述那些要求的一個具體代數系統，而這裡我們通過了解其本質結構，将它抽象出來，然後具體化為另一個同态（或者同行？）的以encoding為基礎的具體系統。進而通過這種對應關系，我們實作原先MLM的功能（這一抽象的功能才是我們真正在乎的，就像在抽象代數中數學家的研究重點展現的一樣）。
這裡我們直接給出了GES的定義，當然如何按上述的說法轉換看問題的角度我自己也是經曆了一個多次反複思考的過程，還是值得仔細回看原文的。
相應的，一些操作也必須加以”模拟“：
當然，這是我們直接按照我們的轉換角度得到的一個對應方案，但實際上，正如我們在FHE中已經介紹的那樣，基于Ideal Lattice的encoding是noisy的，是以同樣的，在我們具體基于Ideal Lattice技術實作這一方案是必須要進行相應的一些實際調整。但這些與Hardness assumption的實際調整一下是技術性的細節，在此不再叙述。
而實際上Ideal Lattice（理想格）也是一個抽象的代數系統，在最低層的實作中我們是通過多項式ring來具體實作上述各種抽象操作的：
之後的一大 部分就是基于Ideal Lattice具體實作上述GES的介紹和相關安全性的證明。
這裡我們介紹下如何将它擴充到非對稱source group之上：
最後文章介紹了如何通過這一構造按之前Dan Boneh的基本方法實作N-parties的Diffie-Hellman Key Exchange。
》》》相關後續工作有：（1）《Practical Multilinear Maps over the Integers》使用了Integer Zp來取代相關的Ideal Lattice，當然這也不是簡單的（要不然Craig又何必一開始選擇Ideal Lattice呢）。整體結構基本一樣，隻不過在具體實作GES的各個内部procedure時是基于雖然效率相對較高但構造其實并不簡單多少的Zp modular arithmetic來進行的。這篇文章的一大貢獻是具體實作了使用這種方法來實作Diffie-Hellman Key Exchange的程式并公開源代碼，相對的實驗結果來看，時間效率還不錯為seconds級，但各種key的size雖然經過優化仍然相對較大。
（2）