同态加密

同态加密是指这样一种加密函数，对明文进行环上的加法和乘法运算再加密，与加密后对密文进行相应的运算，结果是等价的。

全同态加密是指同时满足加同态和乘同态性质，可以进行任意多次加和乘运算的加密函数。用数学公式来表达，即Dec(f(En(m1)，En(m2)，…，En(mk)))=f(m1，m2，…，mk)，或写成：f(En(m1)，En(m2)，…，En(mk))=En(f(m1，m2，…，mk))，如果f是任意函数，称为全同态加密。

加法同态，如果存在有效算法⊕，E(x+y)=E(x)⊕E(y)或者 x+y=D(E(x)⊕E(y))成立，并且不泄漏 x 和 y。

乘法同态，如果存在有效算法 ，E(x×y)=E(x) E(y)或者 xy=D(E(x) E(y))成立，并且不泄漏 x 和 y。

 

加密就是将消息或原始信息，用数学方法打乱，然后将其保存或传递给另一方，后者将使用另一种数学方法对信息进行解密并读取它。理想情况下，加密可以增加数据的安全性，因为只有我们授权的人可以读取消息。信息在解密之前都是很难辨认的，一旦加密后，则只有给定密钥才可以解密。虽然不同形式的加密已存在几个世纪，但它仍然是有效果的：加密的数据一定比不加密的数据安全得多，哪怕是在防火墙和杀毒软件之后也一样。加密是保护您的数据避免第三方窥探的方法，就像你的网上购物车里，填满了商品。

 

Gentry发现了一个方法：Boostrapping，该方法我把它称之为：同态解密。（他为什么可以构造全同态加密方案呢）

这个方法的作用是约减噪音。因为格上加密法案是噪音方案，即在密文中含有噪音，所以每次密文计算后，噪音都会增加，尤其是密文乘法导致噪音增长的非常快。即使你构造了一个具有同态性的加密方案，由于噪音增长，导致无法获得同态性。因此，约减密文计算后的噪音变得异常关键。当然在此之前应该构造一个具有同态性的方案

 

Gentry是在格上首先构造一个具有同态性的加密方案，该方案能够做加法，也能够做乘法，但是只能做有限次的乘法。为什么呢？因为噪音的增长。噪音增长太快，使得无法继续密文计算。这样的方案称为：有限同态加密方案（Somewhat HE）。

 

如果想做更多的计算，怎么办呢？约减噪音，我想连小孩都会的有的常规想法。路线并不新颖，不知道是否让你失望了。关键是怎么约减？

Gentry观察到一个现象：如果解密的时候，输入的不是密文，而是对密文加密后的密文，同样，不是解密密钥，而是加密后的密钥，解密会输出什么东西呢？

答案：一个新的密文，该新密文依然是对原明文的加密。最重要的是新密文的噪音总是恒定的。

说到这里，你反应过来了么。这意味着每次密文计算后，如果使用同态解密操作，将会输出一个噪音恒定的新密文，这个新密文可以继续计算，计算后再同态解密，再计算，周而复始，无穷尽也，所谓任意计算实现了。

 

把密文再加密，密钥再加密后，输入到解密函数中，输出新的密文，这个方法就是Boostrapping技术，即：同态解密

 

Gentry构造的加密方案中，解密电路的深度太深，导致无法同态解密。为此，Gentry又发明出一个方法：压缩电路，将解密电路的复杂度降低，使得可以同态执行解密电路。你说复杂不复杂。

随后人们遵循Gentry 的思想提出了整数上的，小主理想上的，而且还进行了实现。但是依然很复杂。

然而，2012年有一个人Brakerski将全同态加密推上了顶峰，使之变的简单了，而且将全同态加密构件建在LWE问题之上。

LWE问题是一个格上的平均性困难问题，可以被归约到格上标准困难问题。也是抗量子的。目前主流的格上加密方案都是构建在LWE之上。

由于使用Boostrapping实现任意计算代价太高，而且现实中并不太需要任意计算，所以退而求其次，如果能够执行多项式深度的同态计算，也是能够满足大多数需求的。所以随后的LWE上的全同态加密不使用Boostrapping技术约减噪音，而是使用其它噪音约减技术，使得能够进行多项式深度的密文计算，代价大大降低了。

总之，目前只有在格上建立的全同态加密方案是安全的。建立的方法就是首先建立一个有限同态加密方案(SWHE)，然后使用噪音约减技术，使之成为一个能够执行多项式深度同态计算的方案，称之为层次型全同态加密。

全同态加密的效率也是飞速提高，目前执行一次乘法在毫秒级，密文与明文之比约为10^2。微软去年初在人工神经网络上执行密文计算，效果是令人满意的。

全同态加密目前处在工程化研究阶段，相信全同态加密很快就会进入实践。

基于理想格提出一个全同态加密方案

理想格为何物？通俗的说就是一种困难问题，就像大整数难题一样。

所谓的格（Lattice）就是整系数基的线性组合构成的点，通俗地说就是一个空间中的一些离散有规律的点。既然是离散的点，那么点之间一定有距离，距离产生美，从而产生了一些困难问题，例如：最短向量问题(SVP)。

 

 

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

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

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