什么是全同态加密？ | 巴比特

全同态加密属于密码学领域。由于全同态加密支持无需解密，就能够对密文进行任意计算，因此可以立竿见影的解决数据隐私安全问题，有很大的应用需求。例如，在云环境下，用户加密数据后存储在云端，由于数据加密使得云端无法获得数据的内容，从而保证了数据的隐私。此外，由于是全同态加密，云端可以对密文数据进行任意计算。总而言之，全同态加密不但通过加密保护了数据，而且没有丧失计算性。

这么好的性质到哪里找呀！？

全同态加密的概念早在1978年就提出，然后一找就是30多年过去了。当然这30多年也没闲着，30年间人们提出的方案随后就被证明是不安全的。

当然在这30年间，人们也退而求其次，能做一次加法和一次乘法的也可以，例如c1c2+c3c4，即一个二次多项式。这样的方案称为BGN方案。

当然再退而求其次，就是只能做加法，或者只能做乘法，这种方案称为单同态。例如，RSA就是乘法同态，Paillier就是加法同态。这些方案在有些地方大放异彩，尽管只能做一种同态计算。

直到2009年，Gentry，一个斯坦福大学的博士生，基于理想格提出一个全同态加密方案。Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009. 这篇论文是来自于他的博士论文：Craig Gentry. A Fully Homomorphic Encryption Scheme (Ph.D. thesis).

世界哗然。各大报纸头条，密码学界的突破（Breakthrough），计算机界的突破。英文中Breakthrough可不是随便用的。

最为凑巧的是，09年左右恰好是云计算概念火热的时候。而所有介绍全同态加密的文章开头都会来一句，全同态加密用在云计算中可以保护数据隐私安全。谁催化了谁，真的不知道。

Gentry的全同态加密方案是基于理想格构造的。理想格为何物？通俗的说就是一种困难问题，就像大整数难题一样。

说到这里，不得不说两句格密码。很多人只知道RSA,ECC，但是提起格密码一脸的茫然与恐惧，觉得格密码一定是一个很难理解的问题。事实上，恰好相反，所谓的格（Lattice）就是整系数基的线性组合构成的点，通俗地说就是一个空间中的一些离散有规律的点。既然是离散的点，那么点之间一定有距离，距离产生美，从而产生了一些困难问题，例如：最短向量问题(SVP)。

如果是一个二维平面，那么寻找在格上寻找最短向量问题是简单的，但是当维数变大的时候，例如200多维，寻找格上的最短向量问题就变的异常困难，称之为格上标准困难问题，是一个指数级的困难问题。你可以想象一下，当你在迷宫里时（现实世界是3维的），找出口还不算很困难，但是当在一个200多维的迷宫里时，困难程度立刻指数级上升。

最令人感兴趣的是，格上标准困难问题至今没有量子算法可以破解或者撼动它，因此格上标准困难问题被认为是抗量子的。

格上的加密方案最大特征：是一个含有噪音的方案。加密时往里添加噪音，主要是为了进一步提高安全性。然而恰好是这个噪音，导致加密的形式与解密形式比较简单。这种特性为构造全同态加密埋下了伏笔。