巴比特专栏 | 全同态加密是如何被解决的？

一篇论文看完了，如果都看懂了的话，很多人觉得案例都是小菜一碟，但是在我写这个案例的时候我发觉论文看懂了，更需要案例或者说实现来进一步深入或者夯实，因为只有通过具体的实现步骤，才能发现有些在论文中的一些细节问题，反过来更可以促进对论文的理解。

整数上全同态加密方案有两篇非常经典的论文，一篇是《Fully Homomorphic Encryption over the Integers》以下简称DGHV方案，还有一篇是Gentry写的《Computing Arbitrary Functions of Encrypted Data》简称 CAFED论文。入门者适合先阅读CAFED论文，这并不是说这篇论文简单，只是因为这篇文章的写法很通俗（严格意义上这篇文章并不是一篇真正的论文，是给杂志写的文章，有点科普性质），有一个很好的比喻的例子“Glovebox”贯穿于整个论文中，Gentry的文笔很好写的也很生动，对有些地方进行了背景解释，而这些解释恰好是DGHV论文中没有说的，当然一开始要想把CAFED论文彻底读懂也不是那么容易的。这个时候可以开始阅读DGHV这篇论文。这篇论文对于我来说是百读不厌，因为有些地方就算读了一百篇也不见得可以理解，而且这篇文章很适合深挖，有些很有趣的地方，例如噪声参数的设置等等。

还有一篇论文就是全同态的经典论文《Fully homomorphic encryption using ideal lattices》，如果对格不熟悉的话，可以读这篇文章的前面三分之一，因为有详细的全同态的定义、层级全同态、允许电路、增强解密电路、bootstrable、重加密原理，以及如何通过递归实现全同态的，尤其是递归实现全同态的过程，在论文中还是值得反复理解的。剩下的当然还有Gentry的博士论文，也可以分阶段阅读。

1、全同态加密方案

至于什么是全同态等等形式化定义我就不说了，请参阅论文。

全同态加密用一句话来说就是：可以对加密数据做任意功能的运算，运算的结果解密后是相应于对明文做同样运算的结果。有点穿越的意思，从密文空间穿越到明文空间，但是穿越的时候是要被蒙上眼睛的。另外上面的那句话是不能说反的，例如：运算的结果加密后是相应于对明文做同样运算结果的加密，这样说是不对的，因为加密不是确定性的，每次加密由于引入了随机数，每次加密的结果都是不一样的，同一条明文对应的是好几条密文。而解密是确定的。

全同态具有这么好的性质，什么样的加密方案可以符合要求呢？往下看：

Enc(m):   m+2r+pq

Dec(c):   (c mod p) mod 2=（c – p×「c/p」）mod 2 = Lsb(c) XOR Lsb(「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, 所以我们可以做一个集合{x _i ；x _i =2r _i +pq _i }，公钥pk就是这个集合{x _i }，加密时随机的从{x _i }中选取一个子集S，按如下公式进行加密：

Enc(m):   m+2r+sum(S); 其中sum(S)表示对S中的x _i 进行求和。

由于sum(S)是一些0的加密密文之和，所以对解密并不影响，整个解密过程不变。

这个方案是安全的，就是我们所说的DGHV方案。其安全性依赖于一个困难问题“近似GCD问题”。就是给你一些x _i ，你求不出p来（由于整数上全同态研究热了，近似GCD也成了研究的一个点）。

为了说明方便，我们还是采取pq为公钥的方案（尽管不安全，但是不影响说明过程）。所以加密和解密还是按照一开始的公式，现在pq为公钥，p还是私钥，q是公开参数。再重复一遍我们的加密解密算法：

Enc(m):   m+2r+pq

Dec(c):   (c mod p) mod 2=（c – p×「c/p」）mod 2 = Lsb(c) XOR Lsb(「c/p」)

另外在这里约定：一个实数模p为：a mod p = a -「a/p」*p, 「a」表示最近整数, 即有唯一整数在（a-1/2, a+1/2]中。所以a mod p的范围也就变成了（-p/2，p/2 ]（这个牢记）。这个和我们平时说的模p范围是不一样的，平时模p范围是[0, p-1]，那是因为模公式中取得是向下取整：a mod p = a –floor（a/p）*p。

Lsb 是最低有效位，因为是模 2 运算，所以结果就是这个二进制数的最低位 。

2、可怕的噪音

由于公钥pq是公开的，所以知道密文c后可以减去公钥得到：

c-pq= m+2r

由于存在r的干扰，所以无法识别明文m。我们就把m+2r称为噪音。另外在解密时只有当c mod p=m+2r

（m+2r）mod 2= m。

如果噪音大于p/2时，c mod p就不再等于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) mod p= (m1+m2)+2(r1+r2)

c1*c2 mod p=( 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;  c1 mod p= -2, Dec(c1)=0.

c2=Enc(m2)=m2+2r2+pq=1+2*1+11*5=58;  c2 mod p= 3, Dec(1)=1.

因为c1 mod p 和c2 mod p 都是在（-p/2，p/2）范围内，所以解密正确。c1和c2称之为新鲜密文,就是直接由明文生成的密文，在新鲜密文中噪音是在一定合理的范围内的。

我们再来看看c1*c2:

c*=c1*c2=53*58=3074; c* mod p=5, Dec(c*)=1≠m1*m2=0, 解密错误，错误的原因是噪音之积（c1 mod p）*（c2 mod p）= -6 不在（-p/2，p/2）范围内。

看来对密文运算会造成噪音的增大，当噪音超出范围，解密就失败，这意味着对密文运算不可能是无限次的（也就是Evaluate运算功能函数的电路深度是有限的，这在后面我们说到电路时会看到）。到这里我们只得到了一个运算时噪音范围不能超过p/2的同态方案（Somewhat 同态方案），看来似乎用这个方案实现全同态是行不通的。我们需要的是全同态方案即Evaluate可以运行任意功能函数，而不是某一类功能函数（这叫同态方案）。估计多少英雄好汉到了这里就觉得没戏了，于是另寻他路，于是一个突破就擦肩而过。那么下面让我们分析一下症结所在。

3、Bootstappable：一个生硬的思路

噪音阻碍了我们的目标，那么如何消除噪音这个敌人呢？一个直观的方法就是对密文解密，密文解密后噪音就没有了，但是要解密必须要知道私钥，要想通过获得私钥来消除噪音是不现实的。那么如果对密钥加密来做可以么？

让我们先看看Evaluate算法。在Evaluate算法中能够对密文执行函数功能f的运算，其中f是属于permitted functions 集合的任一function（这里稍微解释一下，permitted functions 集合也称permitted circuit，例如有两个函数功能f1和f2，运行Evaluate(pk, f1, c1,c2,…，cn)和Evaluate(pk, f1, c1,c2,…，cn)，就是分别对密文执行f1运算和f2运算，如果f1运算的结果解密后恰好是f1对相应明文运算的结果（同态成立），那么f1就属于permitted functions。而f2运算的结果解密后如果不等于f2对相应明文运算的结果，那么f2就不属于permitted functions。）。  试想如果Dec解密算法也在permitted functions 集合中，那么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进行加密的结果。如此下去。

这种情况下公钥与私钥的数量与电路的深度成线性的依赖关系。如果将被加密的私钥信息泄露，不会影响密钥本身的安全的话，这称之为circular security。如果全同态的加密方案是circular security的话，就不需要这么多公钥与私钥，所有电路层都共用一个公钥与加密的私钥就可以了。好处在于我们不需要为了确定密钥的数量，而在运算前确定执行函数功能的电路深度，从而方便许多。要证明前面的方案是circular security的还很困难，但是目前可以认为不会带来攻击的。

如果解密电路是在Evaluate所执行的permitted functions的集合里，则称该加密方案是Bootstrappable。从上面的解决思路可以看到没有特别绕弯子的地方，就是碰到问题解决问题，解决不了的，创造条件也要解决。通过创造同态执行解密电路的条件，从而降低噪音以达到无限次对密文运算的目的。

好了，到这里似乎全同态实现了（有种共产主义立马实现的感觉）。然而还存在一个问题：Evaluate电路能否能够运行解密电路呢？换句话说：解密电路是否在Evaluate所执行的permitted functions的集合里呢？ 可能有些人会说: 一个算法调用另外一个算法，有什么执行不了的？这就要说说电路的复杂度。

4、电路复杂度

前面的方案中大家看到了是按“位”来加密的（即m∈ {0,1}），加密后得到的是一个整数，密文膨胀的很厉害，那么为什么明文不取整数来加密呢？例如取明文m∈Z。我想原因是这样的：每个研究全同态的人们都想过了，但是没有找到一个方案可以把明文按照整数来加密。并不是说没有这种方案，估计只是现在还没有找到。

又有人会问：为什么全同态方案要用电路来描述呢？

首先我们来说说什么叫一个方案是全同态的？如果一个方案能够对密文做任意功能的运算，而且运算结果所得密文是紧凑的，同时Evaluate算法（即运算）是有效地，那么我们就称该方案是全同态的。可以用下式说明：

上式太重要了，我觉得只要把上面的式子牢记在心，那么全同态的概念就装在心里了。“紧凑的”在这里就不说了，论文里有解释，而且也很好理解。正确性当然是必须的。那么如何衡量Evaluate的有效性呢？最直观的方法可以通过复杂度来衡量。显然Evaluate的复杂度依赖于所运算的函数f。那么f的复杂度如何衡量呢？当然最直接的方法是通过在图灵机上运算f的时间来衡量。但是函数f又是什么呢？我想应该是五花八门的功能函数，如果想用功能去描述它恐怕是一言难尽，但是如果用布尔电路的大小（the size of boolean circuit,即门电路的数量）来衡量，那么f就能够被拆解成一些简单的布尔电路：例如“与”电路、“或”电路、“非”电路。而这些电路是可以组合成任意电路的，也就是说可以表示任意功能的电路。

同样我们也可以选择用AND电路和XOR电路，因为这两个电路是具有完备性质的，也就是说这两个电路的组合也可以表出任意功能的电路（而且用这两个电路来描述更加直观，它们直接对应的算术运算就是乘法和加法）。显然AND电路和XOR电路是属于permitted functions集合里的（为什么？因为AND电路是对应的是两个二进制位相乘，XOR对应的是两个二进制位相加，上述同态方案肯定能够正确执行这两个运算，因为就是一次乘法或者一次加法，既然能够正确执行，所以它们就属于permitted functions集合）。又由于AND电路和XOR电路是完备的，所以任意功能都可以用这两个电路组合表出，也就是说该同态方案可以对密文做任意功能的运算，这不就是传说中的全同态定义么！任意功能的问题解决了，但是还缺一点：必须是正确的才行。你对密文一阵蹂躏后，如果结果解密后不是同样对明文蹂躏的结果，你有什么感觉？

那么上述同态方案能够保证计算的正确性么？上面我们已经看到由于噪音的存在，该方案只能做有限次的运算，也就是说只能够对permitted functions集合里的功能函数保证是正确的，在此之外保证不了，现在你知道permitted functions集合里有什么东西了吧。那如何能够保证对密文做任意功能的运算还是正确的呢？前面说过可以通过重加密技术降低噪音呀！具体如何做呢？很简单：给AND电路上接一个解密电路，给XOR电路上也接一个解密电路，任何密文在进入AND电路或XOR电路之前，先让它进入解密电路进行重加密，之后从解密电路里出来的密文就是一个类似于新鲜密文的密文，噪音比进来前降低了，然后再让这个新的密文进入AND电路或XOR电路，这样我们就可以对密文正确的做任意功能的计算了！而接了解密电路的AND电路或XOR电路就称为增强电路。

总结一下：任意函数功能拿来，先用增强型AND电路和增强型XOR电路表示出来，这样就可以对密文做任意功能的计算了，由于是增强型的，我们不再害怕噪音的阻碍，可以无限运算下去。OK，全同态的蓝图终于在纸上实现了。

但是还有一个问题（问题真多，难怪人说科学是由问题产生的，现在我才理解），解密电路是属于permitted functions集合里的么？可能有人会说，方案中不是有解密电路么，Evaluate应该可以运行它吧。另外还有人说，按照上面方法把解密电路表示成增强电路不就行了。别忘了，增强型电路是含有解密电路的，所以这样说等于由果来推因了。AND电路、XOR电路、解密电路都可看成是“原电路”（这个名字是我自己取的），就是说它们是构成任意功能函数的基石，permitted functions集合里含有它们就完全够了。

前面我们已经解释了AND电路和XOR电路属于permitted functions集合的原因。唯一缺的就是没有证实解密电路也在permitted functions集合里。下面就来分析分析解密电路。

5、解密电路的深度

上面有一个人说对了一半，其实我们可以把解密电路用AND电路和XOR电路表示出来，计算一下电路的深度（电路的深度是运算次数的对数，例如深度是d，计算次数就是log d），然后再和permitted functions中功能电路所允许的最大深度做个比较，就知道解密电路是否属于permitted functions集合了。

首先来分析permitted functions集合所允许的电路深度。由于permitted functions集合里的任一功能函数f 都可以用AND电路和XOR电路表出，而AND电路和XOR电路可以看做对输入的二进制位做乘法和加法，所以f电路的深度可以用输入位的对称多项式来衡量（用多项式衡量是因为多项式里恰好是变元的乘法和加法）， 又由于乘法是噪音的主要来源，所以可以用多项式中乘法次数来做电路深度的主要衡量指标 。有：

c* = f ( c1, c2, …，cn ) = f ( m1+2r1+pq, m2+2r2+pq, …，mn+2rn+pq )

= f ( m1+2r1, m2+2r2, …，mn+2rn ) +p(……)

密文c*的噪音为：c* mod p = f ( m1+2r1, m2+2r2, …，mn+2rn ), 要想c*解密正确必须有：f ( m1+2r1, m2+2r2, …，mn+2rn )< p/2, 其中mi+2ri 是密文ci的噪音。不妨令mi+2ri = xi, 且xi < B, B是密文ci噪音的上界，则有：

f ( x1, x2, …，xn ) < p/2。

我们的目标是衡量f 的运算次数d，所以可以用初等对称多项式来表达f ，有：

f ( x1, x2, …，xn ) = x1x2…xd + x1x3…xd + ……；其中d<=n

f ( x1, x2, …，xn )的每一项就是从n个变元( x1, x2, …，xn )里选取d个变元，因此有C（n, d）个项（C表示组合运算），由C（n, d）< n ^d 得：

f ( x1, x2, …，xn ) < B ^d n ^d < p/2  => d < log p / log Bn , 也就是说f 最多运算次数为 log p / log Bn 。

下面再看看解密电路的运算次数：

Dec(c):   (c mod p) mod 2=（c – p·「c/p」）mod 2 = Lsb(c) XOR Lsb(「c/p」)

仔细端详解密电路的公式，发觉其复杂性主要来源是c/p，所以我们主要看c/p所需的运算次数。c/p=c·p ^-1 , p ^-1 是小数，为了保证c· p ^-1 取整之后的的精确度，p ^-1 要取log c 位的。例如 12345678× 0.111111 和 12345678×  0.11111111的结果取整后是不一样的。那么两个数相乘的次数如何衡量呢？有如下结论:

乘两个t位数相当于加t个数: 输出位是关于输入位的一个 2 次 多项式

加t个数可以应用“3-for-2 trick” :  3个数相加得到两个数相加，输出位是关于输入位的一个次数最多为2次的多项式

其中a1b1+a1c1+b1c1是进位，注意它从形式上还是一个对称多项式。

那么t个数应用这个技巧经过log _3/2 t 次相加后得到两个数，输出位的次数为2 ^{log 3/2 t} = t ^{log 3/2 2} = t ^1.71 。

再看两个t位数相加：

因此输出位的次数最多为t次，因为上面3位数相加次数最多为3次。

结合起来有：乘两个t位数的次数最多为2t ^1.71 t=2t ^2.71 ，而c· p ^-1 里c的位数为log c，p ^-1 要取log c 位的，又因为log c > log p (因为 p-1 的次数至少是2(log p) ^2.71 , 而前面说过f最多运算次数为 log p / log Bn，所以解密电路的深度要大于Evaluate所允许运行功能电路的深度，因此如果Evaluate运行解密电路的话，将会产生不正确的结果，我们就说Evaluate无法运行解密电路，换句话说解密电路不在permitted functions 集合里。

结论应该知道了吧，是一个坏消息。解密电路不在permitted functions 集合里，其后果就是：无法对密文进行任意功能的运算！与全同态失之交臂。

怎么办呢？古人云：兵来将挡，水来土掩。解密电路深了，把它变浅不就完了。说容易做起来有点难。我觉得有技巧的地方就在于压缩解密电路。

6、  压缩解密电路

如何把电路变浅呢？一个直观的方法就是替别人承担一些工作，这样原来的任务量就变小了。

还是先来仔细打量一下问题出在的地方：

c× p ^-1

这是一个乘积，要想把它变成一个较浅的运算电路，应该如何做呢？最直观的方法就是：把乘积变成和，也就是说把c·p ^-1 →∑zi。c是密文，我们不可能拿它开刀，唯一可以做处理的地方就是p ^-1 ，也就是说应该把p ^-1 转换成一个和的形式即： p ^-1

→∑yi，要知道p是私钥是不能公开的，所以可以把p隐藏在∑yi中，同时这种隐藏要不会泄露p才可行，所以要有一个陷门才可以，这个陷门就是Sparse Subset Sum Prob (SSSP)，就是给一串整数x1,x2,……，xn，存在一个{1,……，n}的子集S，使得∑si * xi=0 (其中i∈S)，让你求这个S是不可行的。这个问题据说是困难的，好像没有被well studied。有了这个陷门就可以构造出：

取y1,y2,…,yn ∈[0, 2)，存在一个稀疏子集S，使得∑si · yi ≈ 1/p mod 2 (i∈S)(因为是实数所以用近似等于1/p表示，是存在一个误差的，这个误差不影响取整后的结果)。令 zi←c· yi  mod 2，zi保留一定的精确度，从而有：∑si · zi ≈ c/p  mod 2。所以解密电路中的「c/p」可以替换成「∑si * zi 」。解密电路变成：

Lsb(c) XOR Lsb(「∑si·zi 」)。

这个变换后的方案，公钥除了原来的公钥pk之外还多加了一个向量{yi}。密文除了原来的c之外多出了一个向量{zi}。这个多出来的zi可以看做是提前拿出来计算以减轻解密电路负担的，这个方法叫预处理（post-process）。私钥由原来的sk变成了{si}。可以看到公钥变大，密文也变大，这个代价就是为了换得更浅的电路。那么电路变浅了吗？下面来分析一下：

主要分析一下∑si·zi的多项式次数，然后和我们前面分析的f所能执行的最大次数比较就OK。

假设zi的精确度为n位（我们考虑的都是二进制表示），整数位只考虑最低位，因为Lsb(「∑si·zi 」)是对和先取整，然后再取最低有效位。如下所示：

如果上述t个数应用“3-for-2 trick”相加，电路深度也不会满足要求。所以得另寻它法。

有个概念说一下：HammingWeight，海明重量通俗的说就是向量中“1”的个数，由于我们是二进制相加，所以上面 每一列相加的结果可以看成是该列的海明重量 。那么海明重量怎么求呢？有一个定理非常有用，就是：

对于任意一个二进制向量，其海明重量为W，并且其二进制表示为：wn,……w1w0的话，则wi可以表示为关于变元a1,a2,……，at的一个 次数是 2 ⁱ 多项式 。这个多项式很好求，就是对称多项式e ₂ ⁱ （a1,a2,……，at），有现成的算法。

好了我们可以对上面的那些列运用此定理。对最低列求海明重量，则海明重量的最低位是e ₂ ⁰ （a1,-n, a2,-n ……，at,-n）mod 2，它就是该列的和，这个海明重量的倒数第二位是e ₂ ¹ （a1,-n, a2,-n ……，at,-n）mod 2，就进位到倒数第二列记为Cn,-(n-1)，如此下去;

最后得到：

则有：

b=「∑si * zi 」= (b0 + b-1 ) mod 2  (因为是取整，所以只关心第0列，取整是要取最近的整数，所以和b-1有关，如果b-1是1则要进上去)

别忘了我们现在的任务：是要计算「∑si * zi 」的电路关于ai,j的多项式次数。开始时可以看成都是一次的：

a1,0 ·  a1,-1 …… a1,-(n-1)  a1,-n   deg=1 · deg=1…… deg=1 deg=1

a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n   deg=1 · deg=1…… deg=1 deg=1

a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n   deg=1 · deg=1…… deg=1 deg=1

……        …………

at,0  · at,-1 ……  at,-(n-1)  at,-n    deg=1 · deg=1…… deg=1 deg=1

然后计算完最后一列，有了向前面各列的进位后,变成如下形式：

e ₂ ⁿ ( )     e ₂ ^n-1 ( )     e ₂ ¹ ( )

deg=1 · deg=1…… deg=1 deg=1

deg=1 · deg=1…… deg=1 deg=1

deg=1 · deg=1…… deg=1 deg=1

……         ………………

deg=1 · deg=1…… deg=1 deg=1

每一列关于ai,j的次数都变了，例如倒数第二列次数为4了，依次下去：

因为最后的结果是(b0 + b-1 ) mod 2，所以我们只关心前面两列的次数（即第0列和第一列）。由于每列计算的结果都是e ₂ ⁰ (……)，它是关于输入项的一个次数为1次的对称多项式。对于第0列，由于其最高次数为2 ⁿ ，所以其结果e ₂ ⁰ (……)的最高次数为2 ⁿ 。对于第1列，由于其最高次数为2 ^n-1 ，所以其结果e ₂ ⁰ (……)的最高次数为2 ^n-1 。所以，计算「∑si * zi 」的电路关于ai,j的多项式次数为2 ⁿ （别忘了n是zi的精确度）。回忆一下我们原来说的f所能计算的最高多项式次数为：log p / log Bn （注意2 ⁿ 中的n和此式的n不是一个n）。如何比较呢，得把参数确定一下，按照DGHV方案中的参数，λ为安全参数，取||p|| ～λ ² , ||r||～λ，所以p～2 ^λ2 ，B～2 ^λ ，则log p / log Bn～λ。要想让Evaluate能够运行「∑si * zi 」电路，zi的精确度要取logλ才可以。现在你知道DGHV论文中zi精确度为什么要取那个数了吧。

到此为止我们知道了解密电路经过压缩，可以被Evaluate正确运算了，从而解密电路堂而皇之的进入permitted functions集合里了，所以该方案可以对密文做任意功能的运算了，知道这意味着什么吧，全同态实现了。七拐八歪的才修成正果，确实不容易。

接下来我们总结一下实现步骤，其实上面已经有了。

7、实现步骤

功能函数f里其实有两样基本东西就够了：AND增强型电路，XOR增强型电路，经过集成电路化后如下现状：

任意功能函数例如f1，都可以应用如上两个增强电路组合来表示，例如：

所以每次计算的基本步骤如下：

1)   对输入的明文m进行加密Enc(m),得到密文（c,z）,c是密文，z是向量也称为扩展密文。

2)   对输入的密文进行重加密。输入的密文为（c,z）。在对密文运算之前每次都要对其重加密。因为明文空间是{0,1}，所以加密一定是对密文按位来加密。重加密的过程就是解密的过程，但是对象是对加密的密文以及加密的私钥进行。所以有：c’=Enc(Lsb(c))，得到的c’是一个整数。原本对z的每一位也要进行加密的，但是有一个方法可以提高效率，就是对z不加密，认为z的每一位自己就是自己的加密。另外私钥是s=是0和1的向量，对私钥的每一位的加密记为sk’==，得到的si’也是整数。然后运行∑si·zi，运行它的算法如前面所说，把每一个zi的二进制表示写成矩阵的一行，这样就得到一个矩阵：

a1,0 ·  a1,-1 …… a1,-(n-1)  a1,-n

a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n

a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n

……        …………

at,0  · at,-1 ……  at,-(n-1)  at,-n

然后用si’乘以上面矩阵第i行的每一位，得到一个整数矩阵(矩阵中每一个元素都是整数)：

然后对最后一列（最低位）求海明码，根据前面所述定理，海明码的最低位是e ₂ ⁰ （b1,-n, b2,-n ……，bt,-n），其余各位e ₂ ¹ （b1,-(n-1), b2,-(n-1) ……，bt,-(n-1)），……，都作为进位进到前面相应的位。依次计算下去，第1列的结果是b-1 = e ₂ ⁰ （b1,-1, b2,-1 ……，bt,-1，……），第0列的结果是b0 = e ₂ ⁰ （b1,0, b2,0 ……，bt,0，……）

3)   计算b= (b0 + b-1 ) ，b就是对应的Lsb(「∑si* zi 」)密文运算的结果。

4)   根据上面已经得到的c’=Enc(Lsb(c))，最终对密文c的重加密结果为：

c* = c’+ b

知道此c*和c有什么关系么？c*是c的“重生”，噪音比原来降低了。

5)   然后将c*输入门电路。门电路一般都是二元的，需要两个输入，另外一个输入也用同样的方法计算得到

6)   进行门电路运算，例如加或乘，输出得到的结果。接下来有两种情况：第一种：此结果为最终结果，那么再进行重加密一次后，将密文返还给用户，用户解密后得到正确的运算结果。第二种：此结果不是最终结果，那么继续输入到下一级电路，依然是要先进行重加密。