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

1、整数上全同态加密方案分析一篇论文看完了，如果都看懂了的话，很多人觉得案例都是小菜 一碟，但是在我写这个案例的时候我发觉论文看懂了， 更需要案例或 者说实现来进一步深入或者夯实， 因为只有通过具体的实现步骤， 才 能发现有些在论文中的一些细节问题， 反过来更可以促进对论文的理 解。整数上全同态加密方案有两篇非常经典的论文，一篇是 Fully Homomorphic Encryption over the Integers 以下简称 DGHV方案， 还有 一篇 是 Gentry 写 的 Computing Arbitrary Functions of Encrypted Data 简称 CAFED

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

3、。还有一篇论文就是全同态的经典论文 Fully homomorphic encryption using ideal lattices，如果对 格不熟悉的话， 可以读这篇文章的前面三分之一， 因为有详细的全同 态的定义、层级全同态、允许电路、增强解密电路、 bootstrable 、 重加密原理， 以及如何通过递归实现全同态的， 尤其是递归实现全同 态的过程，在论文中还是值得反复理解的。剩下的当然还有 Gentry 的博士论文，也可以分阶段阅读。这篇文章就算是一个阅读笔记吧，分为两个部分，一个是实现过 程，另一个是方案的参数分析。一、方案实现过程1、 全同态加密方案至于什么是全同态等等形式化定

4、义我就不说了，请参阅论文。 全同态加密用一句话来说就是：可以对加密数据做任意功能的运 算，运算的结果解密后是相应于对明文做同样运算的结果。 有点穿越 的意思，从密文空间穿越到明文空间， 但是穿越的时候是要被蒙上眼 睛的。另外上面的那句话是不能说反的，例如：运算的结果加密后是 相应于对明文做同样运算结果的加密， 这样说是不对的， 因为加密不 是确定性的， 每次加密由于引入了随机数， 每次加密的结果都是不一 样的，同一条明文对应的是好几条密文。而解密是确定的。全同态具有这么好的性质，什么样的加密方案可以符合要求呢？ 往下看：Enc(m): m+2r+pqDec(c): (c mod p) mod

5、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 ，密文空间是整数集。 全同态加密方案中除了加密、解密还有一个非常重要

6、的算法就 是： 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，按如下公式进行加密

7、： Enc(m): m+2r+sum(S); 其中 sum(S)表示对 S 中的 xi 进行求和。由于 sum(S)是一些 0的加密密文之和，所以对解密并不影响，整 个解密过程不变。这个方案是安全的，就是我们所说的 DGHV方案。其安全性依赖 于一个困难问题“近似 GCD问题”。就是给你一些 xi ，你求不出 p 来 （由于整数上全同态研究热了，近似 GCD也成了研究的一个点） 。为了说明方便，我们还是采取 pq 为公钥的方案（尽管不安全， 但是不影响说明过程） 。所以加密和解密还是按照一开始的公式，现 在 pq为公钥， p 还是私钥， q 是公开参数。再重复一遍我们的加密解 密算法：Enc（

8、m）: m+2r+pqDec（c）: （c mod p） mod 2= （c p* c/p ） mod 2 = Lsb（c） XOR Lsb（ c/p ）另外在这里约定： 一个实数模 p 为：a modp = 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运算，所以结果就

9、是这个二进制数 的最低位。2、 可怕的噪音由于公钥 pq是公开的，所以知道密文 c 后可以减去公钥得到：c-pq= m+2r由于存在 r 的干扰，所以无法识别明文 m。我们就把 m+2r 称为噪音。 另外在解密时只有当 c mod p=m+2r p/2 时 , 再对它进行模 2运算才能正确解密：( m+2r)mod 2= m。如果噪音大于 p/2 时，c mod p 就不再等于 m+2r，解密就可能无 法正确恢复出明文。 所以噪音是影响解密的关键。 而噪音会在密文计 算中增长，下面来看看增长的势头：假设 c1= m1+2r1+pq1; c2= m2+2r2+pq2; 其中 c1是对密文 m1的

10、 加密， 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,

11、有：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, 解密错误，错误的

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

13、下 面让我们分析一下症结所在。二、方案参数分析1、 Bootstappable ：一个生硬的思路 噪音阻碍了我们的目标，那么如何消除噪音这个敌人呢？一个直 观的方法就是对密文解密， 密文解密后噪音就没有了， 但是要解密必 须要知道私钥， 要想通过获得私钥来消除噪音是不现实的。 那么如果 对密钥加密来做可以么？让我们先看看 Evaluate 算法。在 Evaluate 算法中能够对密文执 行函数功能 f 的运算，其中 f 是属于 permitted founctions 集合的 任一 founction （这里稍微解释一下， permitted founctions 集合也称 permitted

14、 circuit ，例如有两个函数功能 f1 和 f2 ，运行 Evaluate（pk, f1, c1,c2,， cn）和 Evaluate（pk, f1, c1,c2,，cn） ，就是分别对密文执行 f1 运算和 f2 运算，如果 f1 运算的结果解 密后恰好是 f1对相应明文运算的结果（同态成立） ，那么 f1 就属于 permitted founctions 。而 f2 运算的结果解密后如果不等于 f2 对相 应明文运算的结果， 那么 f2 就不属于 permitted founctions 。）。 试 想如果 Dec 解密算法也在 permitted founctions 集合中，那么

15、 Evaluate 算法就可以执行 Dec 解密功能了。如果我们输入的是 s*（是 用 pk2对私钥 s 加密得到的密文），以及对运算密文 c*（是用 pk2对 c 再加密的密文，原密文 c 是用 pk1进行加密的 ） ，那么执行Evaluate（pk2, Dec, s*,c*）；所得结果为一个新的密文，该密文是明文在 pk2下加密的密文， 是不是有点像魔术， 就像原来一个人穿的是西装， 现在你没有看到这 个人换衣服的情况下， 魔术师只是施了一下魔法， 这个人立刻就换了 一身运动服，人还是原来那个人，只是包装变了。这也是 Gentry 思 想中一个最重要的特性：同态解密。那么同态解密对于降低噪

16、音又有什么关系呢？ 当密文运算后，噪音会被迅速放大，如果我们对运算后的密文 做一次同态解密， 是不是相当于得到了一个新鲜密文呢， 而新鲜密文 的噪音是最小的，所以达到了降噪的目的。 （事实上同态解密后得到 的密文的噪音要比新鲜密文噪音稍微大一些。 ）这一手法称之为：重 加密技术，它为我们提供了降低噪音的一个方法。接下来你肯定会想到：每次密文运算前只要对密文进行重加密来 降低噪音，然后再进行密文运算，那么噪音永远都在可控的范围内， 运算结果的解密也就不会失败了。 运算电路可以反复递归此过程， 就 可以达到无限次密文运算的目的了。然而降低噪音并不是最终目的， 降低噪音是为了能够进行下一次运算， 所

17、以解密电路加上一个门电路 （这个门电路可以是加法门电路或者乘法门电路等等基本电路） 称之 为“增强电路”。如图：由于重加密在每次执行前都需要一个公钥来加密私钥和密文，要 进行多次重加密就需要一个公钥序列 pk1,pk2, ,pki ，对应于公钥 序列也有一个加密私钥链 sk1*,sk2*, ,sk（i-1）* （其中 ski* 是用 pk（i+1） 加密 ski 得到的密文）。这个过程是如何进行的呢？运算电路的每一层都对应一对公钥与私钥。第一层对应的是 pk1 和 sk1 ，第二层对应的是 pk2和 sk2。例如 : 初始公钥为 pk1，对 应的私钥为 sk1，在电路第一层进行重加密时，将用第

18、二层电路的公 钥 pk2对 sk1进行加密得到 sk1* （公钥对于所有层都是公开的） ，以 及用 pk2对密文进行加密；然后输入解密电路，解密电路运行后将输 出一个密文，该密文是用 pk2对明文进行加密的结果。同理在电路第 二层进行重加密时，将用 pk3对该层密钥 sk2加密得到 sk2* ，, 以及 对来自第一层电路的输出密文进行加密； 然后输入解密电路， 解密电 路将输出一个密文，该密文是对明文用 pk3进行加密的结果。如此下 去。这种情况下公钥与私钥的数量与电路的深度成线性的依赖关系。 如果将被加密的私钥信息泄露， 不会影响密钥本身的安全的话， 这称 之 为 circular secu

19、rity 。 如 果 全 同 态 的 加 密 方 案 是 circular security 的话，就不需要这么多公钥与私钥，所有电路层都共用一 个公钥与加密的私钥就可以了。 好处在于我们不需要为了确定密钥的 数量，而在运算前确定执行函数功能的电路深度，从而方便许多。要 证明前面的方案是 circular security 的还很困难，但是目前可以认 为不会带来攻击的。如果解密电路是在 Evaluate 所执行的 permitted functions 的 集合里，则称该加密方案是 Bootstrappable 。从上面的解决思路可 以看到没有特别绕弯子的地方， 就是碰到问题解决问题， 解决不

20、了的， 创造条件也要解决。 通过创造同态执行解密电路的条件， 从而降低噪 音以达到无限次对密文运算的目的。好了，到这里似乎全同态实现了（有种共产主义立马实现的感 觉）。然而还存在一个问题： Evaluate 电路能否能够运行解密电路呢？ 换句话说：解密电路是否在 Evaluate 所执行的 permitted functions 的集合里呢？可能有些人会说 : 一个算法调用另外一个算法， 有什么 执行不了的？这就要说说电路的复杂度。2、电路复杂度前面的方案中大家看到了是按“位”来加密的（即 m 0,1 ）， 加密后得到的是一个整数， 密文膨胀的很厉害， 那么为什么明文不取 整数来加密呢？例如取

21、明文 mZ。我想原因是这样的：每个研究全 同态的人们都想过了， 但是没有找到一个方案可以把明文按照整数来 加密。并不是说没有这种方案，估计只是现在还没有找到。又有人会问：为什么全同态方案要用电路来描述呢？ 首先我们来说说什么叫一个方案是全同态的？如果一个方案能够对 密文做任意功能的运算，而且运算结果所得密文是紧凑的，同时 Evaluate 算法（即运算）是有效地，那么我们就称该方案是全同态 的。可以用下式说明：上式太重要了，我觉得只要把上面的式子牢记在心，那么全同态 的概念就装在心里了。 “紧凑的”在这里就不说了，论文里有解释， 而且也很好理解。正确性当然是必须的。那么如何衡量 Evaluat

22、e 的 有效性呢？最直观的方法可以通过复杂度来衡量。显然 Evaluate 的 复杂度依赖于所运算的功能 f 。那么 f 的复杂度如何衡量呢？当然最 直接的方法是通过在图灵机上运算 f 的时间来衡量。但是功能函数 f 又是什么呢？我想应该是五花八门的功能， 如果想用功能去描述它恐 怕是一言难尽，但是如果用布尔电路的大小（ the size of boolean circuit, 即门电路的数量） 来衡量， 那么 f 就能够被拆解成一些简单 的布尔电路：例如“与”电路、 “或”电路、“非”电路。而这些电路 是可以组合成任意电路的， 也就是说可以表示任意功能的电路。 同样 我们也可以选择用 AND

23、电路和 XOR电路，因为这两个电路是具有完备 性质的，也就是说这两个电路的组合也可以表出任意功能的电路 （而 且用这两个电路来描述更加直观， 它们直接对应的算术运算就是乘法 和加法）。显然 AND电路和 XOR电路是属于 permitted functions 集 合里的（为什么？因为 AND电路是对应的是两个二进制位相乘， XOR 对应的是两个二进制位相加， 上述同态方案肯定能够正确执行这两个 运算，因为就是一次乘法或者一次加法，既然能够正确执行，所以它 们就属于 permitted functions 集合）。又由于 AND电路和 XOR电路 是完备的， 所以任意功能都可以用这两个电路组合

24、表出， 也就是说该 同态方案可以对密文做任意功能的运算， 这不就是传说中的全同态定 义么！任意功能的问题解决了，但是还缺一点：必须是正确的才行。你一阵对密文蹂躏后，如果结果解密后不是同样对明文蹂躏的结果， 你有什么感觉？那么上述同态方案能够保证计算的正确性么？上面我们已经看 到由于噪音的存在， 该方案只能做有限次的运算， 也就是说只能够对 permitted functions 集合里的功能函数保证是正确的，在此之外保 证不了，现在你知道 permitted functions 集合里有什么东西了吧。 那如何能够保证对密文做任意功能的运算还是正确的呢？前面说过 可以通过重加密技术降低噪音呀！

25、具体如何做呢？很简单： 给 AND电 路上接一个解密电路， 给 XOR电路上也接一个解密电路， 任何密文在 进入 AND电路或 XOR电路之前， 先让它进入解密电路进行重加密， 之 后从解密电路里出来的密文就是一个类似于新鲜密文的密文， 噪音比 进来前降低了， 然后再让这个新的密文进入 AND电路或 XOR电路，这 样我们就可以对密文正确的做任意功能的计算了！ 而接了解密电路的 AND电路或 XOR电路就称为增强电路。总结一下：任意函数功能拿来， 先用增强型 AND电路和增强型 XOR 电路表出，这样就可以对密文做任意功能的计算了， 由于是增强型的， 我们不再害怕噪音的阻碍，可以无限运算下去。

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

27、解释了 AND电路和 XOR电路属于 permitted functions 集合的原因。唯一缺的就是没有证实解密电路也在 permitted functions 集合里。下面就来分析分析。1、解密电路的深度 上面有一个人说对了一半，其实我们可以把解密电路用 AND电路 和 XOR电路表出， 计算一下电路的深度 (电路的深度代表着运算的次 数)，然后再和 permitted functions 中功能电路所允许的最大深度 做个比较，就知道解密电路是否属于 permitted functions 集合了。首先来分析 permitted functions 集合所允许的电路深度。由于 permit

28、ted 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* modp

29、= 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=nf ( x1, x2,，xn ) 的每一项就是从 n 个变元 ( x1, x2, ，x

30、n )里选取 d 个变元，因此有 C(n, d)个项( C表示组合运算)，由 C( n, d ) n d 得：f ( x1, x2,，xn ) B d nd d log p ( 因 为 pc) ，所以 c* p -1 的次数至少是 2(log p) 2.71 , 而前面说过 f 最多 运算次数为 log p / log Bn ，所以解密电路的深度要大于 Evaluate 所允许运行功能电路的深度， 因此如果 Evaluate 运行解密电路的话， 将会产生不正确的结果，我们就说 Evaluate 无法运行解密电路，换 句话说解密电路不在 permitted functions 集合里。结论应该知

31、道了吧，是一个坏消息。解密电路不在 permitted functions 集合里，其后果就是：无法对密文进行任意功能的运算！ 与全同态失之交臂。怎么办呢？古人云：兵来将挡，水来土掩。解密电路深了，把它 变浅不就完了。 说容易做起来有点难。 我觉得有技巧的地方就在于压 缩解密电路。2、压缩解密电路如何把电路变浅呢？一个直观的方法就是替别人承担一些工作，这样原来的任务量就变小了。还是先来仔细打量一下问题出在的地方：c* p -1 这是一个乘积，要想把它变成一个较浅的运算电路，应该如何做 呢？最直观的方法就是： 把乘积变成和，也就是说把 c* p-1 zi 。 c* 是密文，我们不可能拿它开刀，唯

32、一可以做处理的地方就是p-1，也就是说应该把 p-1 转换成一个和的形式即： p-1 yi ，要知道 p是私钥是不能公开的， 所以可以把 p 隐藏在 yi 中，同时这种隐藏 要不会泄露 p 才可行，所以要有一个陷门才可以，这个陷门就是 Sparse Subset SumP rob (SSSP)，就是给一串整数 x1,x2, ， xn， 存在一个1, ， n的子集 S，使得 si * xi=0 ( 其中 i S)，让 你求这个 S 是不可行的。这个问题据说是困难的，好像没有被 well studied 。有了这个陷门就可以构造出：取 y1,y2, ,yn 0, 2) ，存在一个稀疏子集 S，使得

33、 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 可以看做是提前拿出来计算以减轻解密电路负担的，这个方法 叫预处理( pos

34、t-process )。私钥由原来的 sk 变成了 si 。可以看到 公钥变大，密文也变大，这个代价就是为了换得更浅的电路。那么电 路变浅了吗？下面来分析一下：主要分析一下 si * zi 的多项式次数，然后和我们前面分析的f 所能执行的最大次数比较就 OK。假设 zi 的精确度为 n 位(我们考虑的都是二进制表示) ，整数位 只考虑最低位，因为 Lsb( si * zi )是对和先取整再取最低有 效位。如下所示：a1,0 a1,-1 a1,-(n-1) a1,-n s1*z1a2,0 a2,-1 a2,-(n-1) a2,-ns2*z2a3,0 a3,-1 a3,-(n-1) a3,-nat

35、,0 at,-1 at,-(n-1) at,-n sn*zn如果上述 t 个数应用“ 3-for-2 trick ”相加，电路深度也不会 满足要求。所以得另寻它法。有个概念说一下： HammingWeigh，t 海明重量通俗的说就是向量 中“1”的个数，由于我们是二进制相加，所以上面每一列相加的结 果可以看成是该列的海明重量。 那么海明重量怎么求呢？有一个定理非常有用，就是：对于任意一个二进制向量 ，其海明重量为 W， 并且其二进制表示为 ;wn, w1w0的话，则 wi 可以表示为关于变元 a1,a2, ，at 的一个次数是 2i 多项式。 这个多项式很好求， 就是对 称多项式 e2i (a

36、1,a2, ，at )，有现成的算法。好了我们可以对上面的那些列运用此定理。对最低列求海明重 量，则海明重量的最低位是 e20 (a1,-n, a2,-n ， at,-n )mod2 ， 它 就是 该列 的和， 这个 海明 重量的 倒数 第二 位 是 e21 ( a1,-n, a2,-n ， at,-n ) mod 2，就进位到倒数第二列记为 Cn,-(n-1) ， 如此下去 ;进位Cn,0 Cn,-1 Cn,-(n-1) 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

37、at,-1 at,-(n-1) at,-nb-n最后得到：C-1,0Cn-1,0Cn-1,-1Cn,0Cn,-1Cn,-(n-1)a1,0 a1,-1 a1,-(n-1)a1,-na2,0 a2,-1 a2,-(n-1)a2,-na3,0 a3,-1 a3,-(n-1)a3,-nat,0 at,-1 at,-(n-1) at,-n b0 b-1 b-(n-1) b-n则有：b= si * zi = (b0 + b-1 ) mod 2 (关心第 0列，取整是要取最近的整数，所以和 则要进上去 )别忘了我们现在的任务是要计算 si 的多项式次数。开始时可以看成都是一次的：因为是取整，所以只b-1

38、有关，如果 b-1 是1zi 的电路关于 ai,j deg=1 a1,0 a1,-1 a1,-(n-1) a1,-n deg=1 deg=1 deg=1a2,0 a2,-1 a2,-(n-1) a2,-n deg=1 deg=1 deg=1 deg=1a3,0 a3,-1 a3,-(n-1) a3,-n deg=1 deg=1 deg=1 deg=1at,0 at,-1 at,-(n-1) at,-n deg=1 deg=1 deg=1 deg=1然后计算完最后一列，有了向前面各列的进位后 , 如下：n n-1 2e2n( ) e 2n-1( ) e22( )deg=1 deg=1 deg=1

39、 deg=1deg=1 deg=1 deg=1 deg=1deg=1 deg=1 deg=1 deg=1deg=1 deg=1 deg=1 deg=1每一列关于 ai,j 的次数都变了，例如倒数第二列次数为 4了，依 次下去：e21( )e2n-1( )n-2e2n-2( ) e2n( )n-1e 2 ( ) e21( )deg=1 deg=1 deg=1 deg=1deg=1 deg=1 deg=1 deg=1deg=1 deg=1 deg=1 deg=1deg=1 deg=1 deg=1 deg=1因为最后的结果是 （b0 + b-1 ） mod 2 ，所以我们只关心前面两 列的次数（即第

40、 0列和第一列），显然最高次数为 2n ，所以计算 si * zi 的电路关于 ai,j 的多项式次数为 2n（别忘了 n 是 zi 的精 确度）。回忆一下我们原来说的 f 所能计算的最高多项式次数为： log p / log Bn （2n中的 n 和此式的 n 不是一个 n）。如何比较呢，得把 参数确定一下，按照 DGHV方案中的参数， 为安全参数，取|p| 2, |r| ，所以 p 22，B 2，则 log p / log Bn 。要 想让 Evaluate 能够运行 si * zi 电路， zi 的精确度要取 log 才可以。现在你知道 DGHV论文中 zi 精确度为什么要取那个数了吧。到此为止我们知道了解密电路经过压缩，可以被 Evaluate 正确 运算了，从而解密电路堂而皇之的进入 permitted functions 集合里 了，所以该方案可以对密文做任意功能的运算了， 知道这意味着什么吧，全同态实现了。七拐八歪的才修成正果，确实不容易接下来我们总结一下实现步骤，其实上面已经有了。3、实现步骤功能函数 f 里其实有两样基本东西就够了： AND增强型电路， XOR 增强型电路，经过集成电路化后如下现状：任意功能函数例如 f1 ，都可以应用如上两个增强电路组