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

1、整数上全同态加密方案分析一篇论文看完了，如果都看懂了的话，很多人觉得案例都是小菜 一碟，但是在我写这个案例的时候我发觉论文看懂了，更需要案例或 者说实现来进一步深入或者夯实，因为只有通过具体的实现步骤，才 能发现有些在论文中的一些细节问题，反过来更可以促进对论文的理 解。整数上全同态加密方案有两篇非常经典的论文，一篇是fully homomorphic encryption over the integers以下简称 dghv 方案， 还有篇是 gentry 写的computing arbitrary functions of encrypted data简称cafei）论文。入门者适合先阅读

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

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

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

5、xorlsb( rc/pj )上面这个加密方案显然是正确的，模p运算把pq消去，模2运算 把2r消去，最后剩下明文m o这个公式看上去很简单，但是却很耐 看，需要多看看。公式中的p是一个正的奇数，q是一个大的正整数(没有要求是 奇数，它比p要大的多)，p和q在密钥生成阶段确定，p看成是密 钥。而r是加密时随机选择的一个小的整数(可以为负数)。明文m e 0,1,是对“位”进行加密的，所得密文是整数。上面方案的明文空间是0,1,密文空间是整数集。全同态加密方案屮除了加密、解密还有一个非常重要的算法就 是：evaluate,它的作用就是对于给定的功能函数f以及密文 cl, c2, , ct等做运算

6、f (cl, c2, , ct) o在这里就是对密文做相应 的整数加、减、乘运算。以上方案可以看成是对称加密方案。下面来考虑公钥加密方案。其实把pq看成公钥就0k。由于q是公开的，所以如果把pq看成公 钥，私钥p立刻就被知道了 (p=pq/q)o怎么办呢？看上面加密算法 中，当对明文0进行加密时，密文为2r+pq,所以我们可以做一个集合 xi； xi=2ri+pqi,公钥pk就是这个集合xi,加密时随机的从xi 中选取一个子集s,按如下公式进行加密：enc (m) : m+2r+sum(s);其中sum(s)表示对s中的xi进行求和。由于sum(s)是一些0的加密密文之和，所以对解密并不影响，

7、整 个解密过程不变。这个方案是安全的，就是我们所说的dghv方案。其安全性依赖 于一个困难问题“近似gcd问题”。就是给你一些xi,你求不出p来 (由于整数上全同态研究热了，近似gcd也成了研究的一个点)。为了说明方便，我们还是采取pq为公钥的方案(尽管不安全， 但是不影响说明过程)。所以加密和解密还是按照一开始的公式，现 在pq为公钥，p还是私钥，q是公开参数。再重复一遍我们的加密解 密算法：enc (m):m+2r+pqdec (c) :(c mod p) mod 2= (c - p*c/p_|) mod 2 = lsb(c) xorlsb( rc/pj )另外在这里约定：一个实数模p为：

8、a mod p = a - ta/pj *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后可以减去公钥得到：cpq= m+2r由于存在r的干扰，所以无法识别明文叽我们就把m+21：、称为噪咅。另外在解密时只有当c mod p

9、=m+2rp/2时，再对它进行模2运算才 能正确解密：(m+2r) mod 2= mo如果噪咅大于p/2吋，c mod p就不再等于m+2r,解密就可能无 法正确恢复出明文。所以噪音是影响解密的关键。而噪音会在密文计 算中增长，下面来看看增长的势头：假设 cl二 ml+2rl+pql; c2- m2+2r2+pq2;其中 cl是对密文 ml的 加密，c2是对密文m2的加密。密文加和乘运算：cl+c2=(ml+m2)+2(rl+r2)+p(ql+q2)cl*c2=( ml+2rl)(m2+2r2)+p(pqlq2+mlq2+m2ql+2rlq2+2r2ql)(cl+c2) mod p二(ml+m

10、2)+2(rl+r2)cl*c2 mod p=( ml+2rl)(m2+2r2)由上可见：密文之和的噪音是各口密文的噪音之和；而密文乘积 的噪音是噪音之积。因此噪音的主要来源还是乘法运算，在乘法运算 中噪音被放大的很快。例如：设p=ll, q二5, ml=0, m2=l,然后分别随机选取rl二1和r2=- 4,有：cl二enc(ml)二ml+2tl+pq二0+2*(-1)+11*5二53;cl mod p 二-2,dec (cl)=0 c2=enc(m2)=m2+2r2+pq=1+2*1+11*5=58: c2 mod p= 3, dec(1)=1. 因为cl mod p和c2 mod p都是

11、在(-p/2, p/2)范围内，所以解密 正确。cl和c2称之为新鲜密文，就是直接市明文生成的密文，在新鲜 密文屮噪音是在一定合理的范围内的。我们再来看看cl*c2:c*二cl*c2二53*58二3074; c* mod p二5, dec（c*）二 1 hml*ni2二0,解 密错误，错误的原因是噪音c* mod p= -6不在（-p/2, p/2）范围 内。看来对密文运算会造成噪音的增大，当噪音超出范围，解密就失 败，这意味着对密文运算不可能是无限次的（也就是evaluate运算 功能函数的电路深度是有限的，这在后面我们说到电路时会看到）。 到这里我们只得到了一个运算时噪音范围不能超过p/2

12、的同态方案 （somewhat同态方案），看来似乎用这个方案实现全同态是行不通 的。我们需要的是全同态方案即evaluate可以运行任意功能函数， 而不是某一类功能函数（这叫同态方案）。估计多少英雄好汉到了这 里就觉得没戏了，于是另寻他路，于是一个突破就擦肩而过。那么下 面让我们分析一下症结所在。二、方案参数分析1、 bootstappable： 一个生硬的思路噪咅阻碍了我们的冃标，那么如何消除噪咅这个敌人呢？ 一个直 观的方法就是对密文解密，密文解密后噪音就没有了，但是要解密必 须要知道私钥，要想通过获得私钥来消除噪音是不现实的。那么如果 对密钥加密來做可以么？让我们先看看evaluate算

13、法。在evaluate算法中能够对密文执 彳亍函数功能f的运算，其中f是属于permitted founctions集合的 任一 founction （这里稍微解释一下，permitted founctions 集合 也称permitted circuit,例如有两个函数功能fl和f2,运行 evaluate （pk, fl, cl, c2,cn）和 evaluate （pk, fl, cl, c2, cn）,就是分别对密文执行fl运算和f2运算，如果fl运算的结果解 密后恰好是门对和应明文运算的结果（同态成立），那么fl就属于 permitted founctionso而f2运算的结果解密后

14、如果不等于f2对相 应明文运算的结果，那么f2就不属于permitted founctions。）。 试 想如果dec解密算法也在permitted founctions集合中，那么 evaluate算法就可以执行dec解密功能了。如果我们输入的是s*（是 用pk2对私钥s加密得到的密文），以及对运算密文c* （是用pk2对c 再加密的密文，原密文c是用pkl进行加密的），那么执行evaluate （pk2, dec, s*,c*）；所得结果为一个新的密文，该密文是明文在pk2下加密的密文， 是不是有点像魔术，就像原来一个人穿的是西装，现在你没有看到这 个人换衣服的情况下，魔术师只是施了一下魔

15、法，这个人立刻就换了 一身运动服，人还是原来那个人，只是包装变了。这也是gentry思 想中一个最重要的特性：同态解密。那么同态解密对于降低噪音又有什么关系呢？当密文运算后，噪音会被迅速放大，如果我们对运算后的密文 做一次同态解密，是不是相当于得到了一个新鲜密文呢，而新鲜密文 的噪音是最小的，所以达到了降噪的目的。（事实上同态解密后得到 的密文的噪音要比新鲜密文噪音稍微大一些。）这一手法称之为：重 加密技术，它为我们提供了降低噪音的一个方法。接下來你肯定会想到：每次密文运算前只要对密文进行重加密來 降低噪音，然后再进行密文运算，那么噪音永远都在可控的范围内， 运算结果的解密也就不会失败了。运算

16、电路可以反复递归此过程，就 可以达到无限次密文运算的目的了。然而降低噪音并不是最终目的， 降低噪音是为了能够进行下一次运算，所以解密电路加上一个门电路 （这个门电路可以是加法门电路或者乘法门电路等等基本电路）称之 为“增强电路”。如图：由于重加密在每次执行前都需要一个公钥来加密私钥和密文，要 进行多次重加密就需要一个公钥序列pkl, pk2,pki,对应于公钥 序列也有一个加密私钥链ski*, sk2*,，sk（i-l）*（其中ski*是用 pk（i+l）加密ski得到的密文）。这个过程是如何进行的呢？运算电路的每一层都对应一对公钥与私钥。第一层对应的是pkl 和ski,第二层对应的是pk2和

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

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

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

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

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

22、出任意功能的电路（而 且用这两个电路来描述更加直观，它们直接对应的算术运算就是乘法 和加法）。显然and电路和xor电路是属于permitted functions集 合里的（为什么？因为and电路是对应的是两个二进制位和乘，xor 对应的是两个二进制位相加，上述同态方案肯立能够正确执行这两个 运算，因为就是一次乘法或者一次加法，既然能够正确执行，所以它 们就属于permitted functions集合）。又由于and电路和xor电路 是完备的，所以任意功能都可以用这两个电路组合表出，也就是说该 同态方案可以对密文做任意功能的运算，这不就是传说中的全同态定 义么！任意功能的问题解决了，但是还

23、缺一点：必须是正确的才行。你一阵对密文蹂蹒后，如果结果解密后不是同样对明文蹂蹒的结果， 你有什么感觉？那么上述同态方案能够保证计算的正确性么？上面我们已经看 到由于噪音的存在，该方案只能做有限次的运算，也就是说只能够对 permitted functions集合里的功能函数保证是止确的，在此之外保 证不了，现在你知道permitted functions集合里有什么东西了吧。 那如何能够保证对密文做任意功能的运算还是正确的呢？前血说过 可以通过重加密技术降低噪咅呀！具体如何做呢？很简单：给and电 路上接一个解密电路，给xor电路上也接一个解密电路，任何密文在 进入and电路或x0r电路之前，

24、先让它进入解密电路进行重加密，之 后从解密电路里出来的密文就是一个类似于新鲜密文的密文，噪音比 进来前降低了，然后再让这个新的密文进入and电路或xor电路，这 样我们就可以对密文正确的做任意功能的计算了 ！而接了解密电路的 and电路或xor电路就称为增强电路。总结一下：任意函数功能拿来，先用增强型and电路和增强型xor 电路表出，这样就可以对密文做任意功能的计算了，由于是增强型的, 我们不再害怕噪音的阻碍，可以无限运算下去。0k,全同态的蓝图终 于在纸上实现了。但是还有一个问题（问题真多，难怪人说科学是由问题产生的， 现在我才理解），解密电路是属于permitted functions集

25、合里的么？ 可能有人会说，方案中不是有解密电路么，evaluate应该可以运行 它吧。另外还有人说，按照上面方法把解密电路表示成增强电路不就 行了。别忘了，增强型电路是含有解密电路的，所以这样说等于由果 来推因了。and电路、xor电路、解密电路都可看成是“原电路”(这 个名字是我自己取的)，就是说它们是构成任意功能函数的基石， permitted functions集合里含有它们就完全够了。前面我们已经解释了 and电路和x0r电路属于permitted functions 集合的原因。唯一缺的就是没有证实解密电路也在permitted functions集合里。下面就来分析分析。1、解密电

26、路的深度上面有一个人说对了一半，其实我们可以把解密电路用and电路 和xor电路表出，计算一下电路的深度(电路的深度代表着运算的次 数)，然后再和permitted functions屮功能电路所允许的最大深度 做个比较，就知道解密电路是否属于permitted functions集合了。首先來分析permitted functions集合所允许的电路深度。由于 permitted functions集合里的任一功能函数f都可以用and电路和 xor电路表出，而and电路和xor电路可以看做对输入的二进制位做 乘法和加法，所以f电路的深度可以用输入位的对称多项式来衡量 (用多项式衡量是因为多项

27、式里恰好是变元的乘法和加法)，又由于 乘法是噪音的主要来源，所以可以用多项式中乘法次数来做电路深度 的主要衡量指标。有：c* = f ( cl, c2,，cn ) = f ( ml+2rl+pq, m2+2r2+pq,， mn+2rn+pq )=f ( ml+2rl, m2+2r2,，mn+2rn ) +p()密文 c*的噪音为：c* mod p = f ( ml+2rl, m2+2r2,，mn+2rn ), 要想c*解密正确必须有：f ( ml+2rl, m2+2r2, ，mn+2rn ) < p/2, 其中mi+2ri是密文ci的噪咅。不妨令mi+2ri = xi,且xi <

28、b, b 是密文ci噪音的上界，则有：f ( xl, x2,，xn ) < p/2o我们的目标是衡量f的运算次数d,所以可以用初等对称多项式 来表达f ,有：f ( xl, x2,，xn )二 xlx2xd + xlx3xd + ；其中cl<=nf ( xl, x2,，xn )的每一项就是从n个变元(xl, x2,， xn)里选取d个变元，因此有c (n, d)个项(c表示组合运算)，由 c (n, d) < nd 得:f ( xl, x2,，xn ) bd nd < p/2 二> d log p / log bn , 也就是说f最多运算次数为log p / lo

29、g bn o一卜面再看看解密电路的运算次数：dec (c) :(c mod p) mod 2二(c - p*c/p_|) mod 2 二 lsb(c) xorlsb( rc/pj )仔细端详解密电路的公式，发觉其复杂性主要来源是c/p,所以 我们主要看c/p所需的运算次数。c/p二c*pt, l是小数，为了保证 c* l取整之后的的精确度，pj要取log c位的。例如12345678 * 0. 111111和12345678 * 0. 11111111的结果取整后是不一样的。那 么两个数相乘的次数如何衡量呢？有如下结论：乘两个t位数和当于加t个数：输出位是关于输入位的一个2次多项式a3a2al

30、b3b2bla3bla2blalbla3b2 a2b2alb2a3b3 a2b3 alb3加t个数可以应用“3-for-2 trick” ：3个数相加得到两个数相加，输出位是关于输入位的一个次数最多为2次的多项式a3a2alb3b2blc3c2cla3+b3+c3a.2+b2+c2al+bl+cla3b3+a3c3+b3c3a2b2+a2c2+b2c2 albl+alcl+blcl次 二次那么t个数应用这个技巧经过10g：,2t次相加后得到两个数，输 出位的次数为2窗处=1103/2 2= t1.71o再看两个t位数相加：进位：a2b2+a2albl+b2alblalbla3a2alb3b2b

31、la.3+b3+a2b2+a2albl+b2albl a2+b2+albl al+bl三次输出位的次数最多为t次，因为上面3位数相加次数最多为3次。结合起来有：乘两个t位数的次数最多为2tl7!t=2t2'71,而c* p1 里c的位数为log c, p 1要取log c位的，又因为log c > log p (因 为p<c),所以c* q的次数至少是2 (log p)2-71 ,而前面说过f最多 运算次数为log p / log bn,所以解密电路的深度要大于evaluate 所允许运行功能电路的深度，因此如果evaluate运行解密电路的话, 将会产生不正确的结果，我们

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

33、呢？最直观的方法就是：把乘积变成和，也就是说把c*ptszio c*是密文，我们不可能拿它开刀，唯一可以做处理的地方就是l， 也就是说应该把l转换成一个和的形式即：plzyi,要知道 p是私钥是不能公开的，所以可以把p隐藏在工yi中，同时这种隐藏 要不会泄露p才可行，所以要有一个陷门才可以，这个陷门就是 sparse subset sum prob (sssp),就是给一串整数 xl, x2, xn,存在一个1,n的了集s,使得工si * xi二0 (其中igs),让 你求这个s是不可行的。这个问题据说是困难的，好像没有被well studiedo有了这个陷门就可以构造出：取yl, y2, ,

34、 yn e 0, 2),存在一个稀疏子集s,使得工si*yi "1/p mod 2 (ies)(因为是实数所以用近似等于1/p表示，是存在 一个误差的，这个误差不影响取整后的结果)。令zi一c*yi mod 2, zi保留一定的精确度，从而有：ssi * zi c/p mod 2。所以解 密电路中的c/p可以替换成工si * zi jo解密电路变成：lsb(c) xor lsb(工si * zi)。这个变换后的方案，公钥除了原来的公钥pk之外还多加了一个 向量yi °密文除了原来的c之外多出了一个向量zi。这个多出来 的zi可以看做是提前拿出来计算以减轻解密电路负担的，这个

35、方法 叫预处理(post-process )o私钥由原来的sk变成了 si。可以看到 公钥变大，密文也变大，这个代价就是为了换得更浅的电路。那么电 路变浅了吗？下面來分析一下：主耍分析一下工si * zi的多项式次数，然后和我们前面分析的 f所能执行的最大次数比较就oko假设zi的精确度为n位(我们考虑的都是二进制表示)，整数位 只考虑最低位，因为lsb( resi * zij )是对和先取整再取最低有 效位。如下所示：al, 0 al, -1 al,- (nl) al, _n sl*zla2, 0a2, -1a2, - (n-1)a2, -ns2*z2a3, 0a3, -1a3,(n 1)a

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

37、 (al,a2, at),有现成的算法。好了我们可以对上面的那些列运用此定理。对最低列求海明重量,则海明重量的最低位是e2° (al, -n, a2, -n ,at, -n) mod 2,它就是该列的和，这个海明重量的倒数第二位是e? (al,-n,a2, -n, at, -n) mod 2,就进位到倒数第二列记为cn, -(nl),如此下去；cn, 0cn, -1cn, (n 1)进位al, 0 al, 1 al, (n 1)al, -na2, 0a2, 1 a2, (n 1)a2, - na3, 0a3, 1 a3, (n 1)a3, nat, 0 at, 1 at, (n 1)

38、at, nbn最后得到:cn-1,0cn-1,-1cn, 0cn, -1cn, - (nt)al, 0 al,-l ， al, (n 1)al, -na2, 0 a2, 1 a2, (n 1)a2, -na3, 0 a3, 1 a3, (n 1)a3, nat, 0at, 1 at, (n 1)at, 一bo b-1 b-(nt)b-n则有：b二r zsi * zi二(bo + b-1 ) mod 2 (因为是取整，所以只 关心第0列，取整是要取最近的整数，所以和b-1有关，如果b-1是1 则要进上去)别忘了我们现在的任务是要计算工si*zi的电路关于ai,j 的多项式次数。开始时可以看成都是

39、一次的：al, 0 al, -1al, -(nl) al, -ndeg=l deg=ldeg=l deg=la2, 0a2,-l a2, (n 1)a2, -ndeg-l deg-1deg=ldeg=la3, 0a3, 1 a3, (n 1)a3, -ndeg二1 deg=ldeg 二 1deg=lat, 0 at, 1 at, (n 1)at, -ndeg_l deg_ldeg=l deg=l然后计算完最后一列，有了向前而各列的进位后,如下:e2n()er1 ()e22()deg=l deg=l deg=l deg=ldeg 二 1 deg_l deg_l deg_ldeg=l deg_l

40、deg=l degldeg=l deg二1 deg二1 deg二1每一列关于ai,j的次数都变了，例如倒数第二列次数为4了，依次下去：e2*()e；"()e厂2()e2n()er1 ()e2'()deg=l deg二deg=ldeg 二 1deg=l deg= deg=ldeg=ldeg=l deg= 1deg二1deg=ldeg 二 1 deg二1deg=ldeg=l因为最后的结果是（bo + b-1 ） mod 2,所以我们只关心前面两 列的次数（即第0列和第一列），显然最高次数为y ,所以计算工 si * zi的电路关于ai, j的多项式次数为2”（别忘了 n是zi的精

41、 确度）。冋忆一下我们原来说的f所能计算的最高多项式次数为：log p / log bn （2“中的n和此式的n不是一个n）。如何比较呢，得把 参数确定一下，按照dgiiv方案中的参数，入为安全参数，取| |p| | 入；| | r i i入，所以p2匕b2',则log p / log bn入。要 想让evaluate能够运行ysi * zi电路，zi的精确度要取log 入才可以。现在你知道dghv论文中zi精确度为什么要取那个数了吧。到此为止我们知道了解密电路经过压缩，可以被evaluate正确 运算了,从而解密电路堂而皇之的进入permitted functions集合里 了，所以该方案可以对密文做任意功能的运算了，知道这意味着什么 吧，全同态实现了。七拐八歪的才修成正果，确实不容易。接下来我们总结一下实现步骤，其实上面已经有了。3、实现步骤功能函数f里其实有两样基本东西就够了： and增强型电路，xor 增强型屯路，经过集成屯路化后如下现状：任意功能函数例如fl,都可以应用如上两个增强电路组合来表 示，例如：所以每次计算的基本步骤如下：1) 对输入的明