2018-10-06 13:30

全同态加密释疑(一):四个算法(2)

2.9万

Enc算法(加密)和我们平常意义的加密是一样的,但是在全同态加密的语境里,使用Enc算法加密的密文,一般称之为新鲜密文,即该密文是一个初始密文,没有和其他密文计算过。所以新鲜密文的噪音称之为初始噪音。这个相当重要。 Dec算法(解密)也和我们平常理解的一样,就是对密文的解密,但是这里解密算法不仅能对初始密文解密,还能够对计算后的密文解密。但是由于部分同态加密方案中密文存在噪音,例如在整数上的全同态加密方案里,密文乘积的噪音是噪音之积,密文加法的噪音是噪音之和。所以当密文计算到一定程度,其噪音将超过上限,所以对这样的密文解密将可能失败。全同态加密的关键就是对噪音的控制,使之能对任何密文解密。 最后一个算法:Evaluate算法(密文计算),这个算法是整个全同态加密四个算法中的核心。可以做个这样的比喻:前面三个算法是大楼的地基,后面这个Evaluate算法就是大楼。这个比喻在后面会体会到它的用意。密文的计算是在电路里进行的,电路是分层的,电路深度越深,层数越多,密文就能够进行更多次的计算。随便提一句,密文计算的次数等于电路深度的对数。什么是计算次数?例如c1*c2,就是进行了一次计算,c1*c2*c3就是进行了三次计算。在全同态加密中,我们一般用乘法次数来衡量计算次数,这是因为乘法的噪音比加法噪音增长的快很多。 Evaluate算法有三个输入,第一个输入是计算公钥Evk,就是我们在上次博文里讲到的。Evk可以没有。第二个输入是函数f,就是Evaluate算法所要执行的函数,可以是任意函数,因为全同态加密的目标就是对密文能够进行任意计算。当然这个函数也可以是“解密函数”,Gentry通过观察发现了一个秘密,等会我们说。第三个输入是密文,理论上可以有无穷多个密文,但是这是不可能的。 所以Evaluate算法就是将密文输入到函数f里进行计算。我们知道在全同态加密的方案里,密文都是含有噪音的,密文的计算会导致噪音的增长,如果把函数f表示成电路,那么Evaluate算法实际上只能够对有限深度L的电路进行计算,超过这个深度L的电路就不行了。所以我们把这样的方案称之为部分同态加密方案。由此可见Evaluate算法的重要性,全同态加密就靠它了。还记得刚才的比喻么?Evaluate算法相当于大楼,这个大楼的层数是有限的,而全同态加密的目标是无限高! 所以噪音问题导致了Evaluate算法不能够对任意电路(函数)进行计算。 而全同态加密追求的就是Evaluate算法能够对任意电路进行计算,怎么办?那只有控制噪音问题了。如何控制噪音呢?下回分解。

本文链接:https://www.8btc.com/article/282785
转载请注明文章出处

评论
登录 账号发表你的看法,还没有账号?立即免费 注册
下载
分享
收藏
阅读
评论
点赞
上一篇
下一篇