整数上全同态加密方案分析

整数上全同态加密方案分析一篇论文看完了，如果都看懂了的话，很多人觉得案例都是小菜一碟，但是在我写这个案例的时候我发觉论文看懂了，更需要案例或者说实现来进一步深入或者夯实，因为只有通过具体的实现步骤，才能发现有些在论文中的一些细节问题，反过来更可以促进对论文的理解。整数上全同态加密方案有两篇非常经典的论文，一篇是《FullyHomomorphicEncryptionovertheIntegers》以下简称DGHV方案，还有一篇是Gentry写的《ComputingArbitraryFunctionsofEncryptedData》简称CAFED论文。入门者适合先阅读CAFED论文，这并不是说这篇论文简单，只是因为这篇文章的写法很通俗（严格意义上这篇文章并不是一篇真正的论文，是给杂志写的文章，有点科普性质），有一个很好的比喻的例子“Glovebox”贯穿于整个论文中，Gentry的文笔很好写的也很生动，对有些地方进行了背景解释，而这些解释恰好是DGHV论文中没有说的，当然一开始要想把CAFED论文彻底读懂也不是那么容易的。这个时候可以开始阅读DGHV这篇论文。这篇论文对于我来说是百读不厌，因为有些地方就算读了一百篇也不见得可以理解，而且这篇文章很适合深挖，有些很有趣的地方，例如噪声参数的设置等等。还有一篇论文就是全同态的经典论文《Fullyhomomorphicencryptionusingideallattices》，如果对格不熟悉的话，可以读这篇文章的前面三分之一，因为有详细的全同态的定义、层级全同态、允许电路、增强解密电路、bootstrable、重加密原理，以及如何通过递归实现全同态的，尤其是递归实现全同态的过程，在论文中还是值得反复理解的。剩下的当然还有Gentry的博士论文，也可以分阶段阅读。这篇文章就算是一个阅读笔记吧，分为两个部分，一个是实现过程，另一个是方案的参数分析。一、方案实现过程1、全同态加密方案至于什么是全同态等等形式化定义我就不说了，请参阅论文。全同态加密用一句话来说就是：可以对加密数据做任意功能的运算，运算的结果解密后是相应于对明文做同样运算的结果。有点穿越的意思，从密文空间穿越到明文空间，但是穿越的时候是要被蒙上眼睛的。另外上面的那句话是不能说反的，例如：运算的结果加密后是相应于对明文做同样运算结果的加密，这样说是不对的，因为加密不是确定性的，每次加密由于引入了随机数，每次加密的结果都是不一样的，同一条明文对应的是好几条密文。而解密是确定的。全同态具有这么好的性质，什么样的加密方案可以符合要求呢？往下看：Enc(m):m+2r+pqDec(c):(cmodp)mod2=（c–p*「c/p」）mod2=Lsb(c)XORLsb(「c/p」)上面这个加密方案显然是正确的，模p运算把pq消去，模2运算把2r消去，最后剩下明文m。这个公式看上去很简单，但是却很耐看，需要多看看。公式中的p是一个正的奇数，q是一个大的正整数（没有要求是奇数，它比p要大的多），p和q在密钥生成阶段确定，p看成是密钥。而r是加密时随机选择的一个小的整数（可以为负数）。明文m∈{0,1}，是对“位”进行加密的，所得密文是整数。上面方案的明文空间是{0,1}，密文空间是整数集。全同态加密方案中除了加密、解密还有一个非常重要的算法就是：Evaluate，它的作用就是对于给定的功能函数f以及密文c1,c2,…,ct等做运算f(c1,c2,…,ct)。在这里就是对密文做相应的整数加、减、乘运算。以上方案可以看成是对称加密方案。下面来考虑公钥加密方案。其实把pq看成公钥就OK。由于q是公开的，所以如果把pq看成公钥，私钥p立刻就被知道了（p=pq/q）。怎么办呢？看上面加密算法中，当对明文0进行加密时，密文为2r+pq,所以我们可以做一个集合{xi；xi=2ri+pqi}，公钥pk就是这个集合{xi}，加密时随机的从{xi}中选取一个子集S，按如下公式进行加密：Enc(m):m+2r+sum(S);其中sum(S)表示对S中的xi进行求和。由于sum(S)是一些0的加密密文之和，所以对解密并不影响，整个解密过程不变。这个方案是安全的，就是我们所说的DGHV方案。其安全性依赖于一个困难问题“近似GCD问题”。就是给你一些xi，你求不出p来（由于整数上全同态研究热了，近似GCD也成了研究的一个点）。为了说明方便，我们还是采取pq为公钥的方案（尽管不安全，但是不影响说明过程）。所以加密和解密还是按照一开始的公式，现在pq为公钥，p还是私钥，q是公开参数。再重复一遍我们的加密解密算法：Enc(m):m+2r+pqDec(c):(cmodp)mod2=（c–p*「c/p」）mod2=Lsb(c)XORLsb(「c/p」)另外在这里约定：一个实数模p为：amodp=a-「a/p」*p,「a」表示最近整数,即有唯一整数在（a-1/2,a+1/2]中。所以amodp的范围也就变成了（-p/2，p/2]（这个牢记）。这个和我们平时说的模p范围是不一样的，平时模p范围是[0,p-1]，那是因为模公式中取得是向下取整：amodp=a–floor（a/p）*p。Lsb是最低有效位，因为是模2运算，所以结果就是这个二进制数的最低位。2、可怕的噪音由于公钥pq是公开的，所以知道密文c后可以减去公钥得到：c-pq=m+2r由于存在r的干扰，所以无法识别明文m。我们就把m+2r称为噪音。另外在解密时只有当cmodp=m+2rp/2时,再对它进行模2运算才能正确解密：（m+2r）mod2=m。如果噪音大于p/2时，cmodp就不再等于m+2r，解密就可能无法正确恢复出明文。所以噪音是影响解密的关键。而噪音会在密文计算中增长，下面来看看增长的势头：假设c1=m1+2r1+pq1;c2=m2+2r2+pq2;其中c1是对密文m1的加密，c2是对密文m2的加密。密文加和乘运算：c1+c2=(m1+m2)+2(r1+r2)+p(q1+q2)c1*c2=(m1+2r1)(m2+2r2)+p(pq1q2+m1q2+m2q1+2r1q2+2r2q1)(c1+c2)modp=(m1+m2)+2(r1+r2)c1*c2modp=(m1+2r1)(m2+2r2)由上可见：密文之和的噪音是各自密文的噪音之和；而密文乘积的噪音是噪音之积。因此噪音的主要来源还是乘法运算，在乘法运算中噪音被放大的很快。例如：设p=11,q=5,m1=0,m2=1，然后分别随机选取r1=1和r2=-4,有：c1=Enc(m1)=m1+2r1+pq=0+2*(-1)+11*5=53;c1modp=-2,Dec(c1)=0.c2=Enc(m2)=m2+2r2+pq=1+2*1+11*5=58;c2modp=3,Dec(1)=1.因为c1modp和c2modp都是在（-p/2，p/2）范围内，所以解密正确。c1和c2称之为新鲜密文,就是直接由明文生成的密文，在新鲜密文中噪音是在一定合理的范围内的。我们再来看看c1*c2:c*=c1*c2=53*58=3074;c*modp=5,Dec(c*)=1≠m1*m2=0,解密错误，错误的原因是噪音c*modp=-6不在（-p/2，p/2）范围内。看来对密文运算会造成噪音的增大，当噪音超出范围，解密就失败，这意味着对密文运算不可能是无限次的（也就是Evaluate运算功能函数的电路深度是有限的，这在后面我们说到电路时会看到）。到这里我们只得到了一个运算时噪音范围不能超过p/2的同态方案（Somewhat同态方案），看来似乎用这个方案实现全同态是行不通的。我们需要的是全同态方案即Evaluate可以运行任意功能函数，而不是某一类功能函数（这叫同态方案）。估计多少英雄好汉到了这里就觉得没戏了，于是另寻他路，于是一个突破就擦肩而过。那么下面让我们分析一下症结所在。二、方案参数分析1、Bootstappable：一个生硬的思路噪音阻碍了我们的目标，那么如何消除噪音这个敌人呢？一个直观的方法就是对密文解密，密文解密后噪音就没有了，但是要解密必须要知道私钥，要想通过获得私钥来消除噪音是不现实的。那么如果对密钥加密来做可以么？让我们先看看Evaluate算法。在Evaluate算法中能够对密文执行函数功能f的运算，其中f是属于permittedfounctions集合的任一founction（这里稍微解释一下，permittedfounctions集合也称permittedcircuit，例如有两个函数功能f1和f2，运行Evaluate(pk,f1,c1,c2,…，cn)和Evaluate(pk,f1,c1,c2,…，cn)，就是分别对密文执行f1运算和f2运算，如果f1运算的结果解密后恰好是f1对相应明文运算的结果（同态成立），那么f1就属于permittedfounctions。而f2运算的结果解密后如果不等于f2对相应明文运算的结果，那么f2就不属于permittedfounctions。）。试想如果Dec解密算法也在permittedfounctions集合中，那么Evaluate算法就可以执行Dec解密功能了。如果我们输入的是s*（是用pk2对私钥s加密得到的密文），以及对运算密文c*（是用pk2对c再加密的密文，原密文c是用pk1进行加密的)，那么执行Evaluate(pk2,Dec,s*,c*)；所得结果为一个新的密文，该密文是明文在pk2下加密的密文，是不是有点像魔术，就像原来一个人穿的是西装，现在你没有看到这个人换衣服的情况下，魔术师只是施了一下魔法，这个人立刻就换了一身运动服，人还是原来那个人，只是包装变了。这也是Gentry思想中一个最重要的特性：同态解密。那么同态解密对于降低噪音又有什么关系呢？当密文运算后，噪音会被迅速放大，如果我们对运算后的密文做一次同态解密，是不是相当于得到了一个新鲜密文呢，而新鲜密文的噪音是最小的，所以达到了降噪的目的。（事实上同态解密后得到的密文的噪音要比新鲜密文噪音稍微大一些。）这一手法称之为：重加密技术，它为我们提供了降低噪音的一个方法。接下来你肯定会想到：每次密文运算前只要对密文进行重加密来降低噪音，然后再进行密文运算，那么噪音永远都在可控的范围内，运算结果的解密也就不会失败了。运算电路可以反复递归此过程，就可以达到无限次密文运算的目的了。然而降低噪音并不是最终目的，降低噪音是为了能够进行下一次运算，所以解密电路加上一个门电路（这个门电路可以是加法门电路或者乘法门电路等等基本电路）称之为“增强电路”。如图：由于重加密在每次执行前都需要一个公钥来加密私钥和密文，要进行多次重加密就需要一个公钥序列{pk1,pk2,…,pki}，对应于公钥序列也有一个加密私钥链{sk1*,sk2*,…,sk(i-1)*}（其中ski*是用pk(i+1)加密ski得到的密文）。这个过程是如何进行的呢？运算电路的每一层都对应一对公钥与私钥。第一层对应的是pk1和sk1，第二层对应的是pk2和sk2……。例如:初始公钥为pk1，对应的私钥为sk1，在电路第一层进行重加密时，将用第二层电路的公钥pk2对sk1进行加密得到sk1*（公钥对于所有层都是公开的），以及用pk2对密文进行加密；然后输入解密电路，解密电路运行后将输出一个密文，该密文是用pk2对明文进行加密的结果。同理在电路第二层进行重加密时，将用pk3对该层密钥sk2加密得到sk2*，,以及对来自第一层电路的输出密文进行加密；然后输入解密电路，解密电路将输出一个密文，该密文是对明文用pk3进行加密的结果。如此下去。这种情况下公钥与私钥的数量与电路的深度成线性的依赖关系。如果将被加密的私钥信息泄露，不会影响密钥本身的安全的话，这称之为circularsecurity。如果全同态的加密方案是circularsecurity的话，就不需要这么多公钥与私钥，所有电路层都共用一个公钥与加密的私钥就可以了。好处在于我们不需要为了确定密钥的数量，而在运算前确定执行函数功能的电路深度，从而方便许多。要证明前面的方