一， 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）