8BTCCI: 15986.54 +2.02% 8BTCVI: 11272.13 +0.85% 24H成交额: ¥3348.70亿 -12.83% 总市值: ¥20101.08亿 +2.85%
巴比特专栏 | 全同态加密是如何被解决的?

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

陈智罡 发布在 区块链 74678

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

整数上全同态加密方案有两篇非常经典的论文,一篇是《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, 所以我们可以做一个集合{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+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 <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的加密,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思想中一个最重要的特性:同态解密。

那么同态解密对于降低噪音又有什么关系呢?

当密文运算后,噪音会被迅速放大,如果我们对运算后的密文做一次同态解密,是不是相当于得到了一个新鲜密文呢,而新鲜密文的噪音是最小的,所以达到了降噪的目的。(事实上同态解密后得到的密文的噪音要比新鲜密文噪音稍微大一些。)这一手法称之为:重加密技术,它为我们提供了降低噪音的一个方法。

接下来你肯定会想到:每次密文运算前只要对密文进行重加密来降低噪音,然后再进行密文运算,那么噪音永远都在可控的范围内,运算结果的解密也就不会失败了。运算电路可以反复递归此过程,就可以达到无限次密文运算的目的了。然而降低噪音并不是最终目的,降低噪音是为了能够进行下一次运算,所以解密电路加上一个门电路(这个门电路可以是加法门电路或者乘法门电路等等基本电路)称之为“增强电路”。如图:

1

增强电路

由于重加密在每次执行前都需要一个公钥来加密私钥和密文,要进行多次重加密就需要一个公钥序列{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算法(即运算)是有效地,那么我们就称该方案是全同态的。可以用下式说明:

2

上式太重要了,我觉得只要把上面的式子牢记在心,那么全同态的概念就装在心里了。“紧凑的”在这里就不说了,论文里有解释,而且也很好理解。正确性当然是必须的。那么如何衡量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)< nd 得:

f ( x1, x2, …,xn ) < Bd nd < 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多项式

3

 

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

4

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

那么t个数应用这个技巧经过log3/2 t 次相加后得到两个数,输出位的次数为2log3/2 t = tlog3/2 2= t1.71

再看两个t位数相加:

5

 

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

 

结合起来有:乘两个t位数的次数最多为2t1.71t=2t2.71,而c· p-1里c的位数为log c,p-1要取log c 位的,又因为log c > log p (因为 p<c),所以c· 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 」)是对和先取整,然后再取最低有效位。如下所示:

6

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

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

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

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

6

 

最后得到:

7

则有:

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

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

e2n( )     e2n-1( )     e21( )

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了,依次下去:

8

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

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

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

 

7、实现步骤

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

9

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

10

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

1)   对输入的明文m进行加密Enc(m),得到密文(c,z),c是密文,z是向量<z1,z2,……>也称为扩展密文。

2)   对输入的密文进行重加密。输入的密文为(c,z)。在对密文运算之前每次都要对其重加密。因为明文空间是{0,1},所以加密一定是对密文按位来加密。重加密的过程就是解密的过程,但是对象是对加密的密文以及加密的私钥进行。所以有:c’=Enc(Lsb(c)),得到的c’是一个整数。原本对z的每一位也要进行加密的,但是有一个方法可以提高效率,就是对z不加密,认为z的每一位自己就是自己的加密。另外私钥是s=<s1,s2,……>是0和1的向量,对私钥的每一位的加密记为sk’=<Enc(s1),Enc(s2),……>=<s1’,s2’,……>,得到的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行的每一位,得到一个整数矩阵(矩阵中每一个元素都是整数):

11

 

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

12

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

文章标签: 密码学
评论(2)
登录 账号发表你的看法,还没有账号?立即免费 注册