自己的沙场:全同态加密研究分享 http://blog.sciencenet.cn/u/chzg99 不要对我说生命中无聊的事,不要对我说失败是命运的事。

博文

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

已有 12945 次阅读 2013-11-3 20:07 |个人分类:全同态|系统分类:科研笔记| 密码学, 全同态加密

继续说全同态加密中的其他三个算法。


Enc算法(加密)和我们平常意义的加密是一样的,但是在全同态加密的语境里,使用Enc算法加密的密文,一般称之为新鲜密文,即该密文是一个初始密文,没有和其他密文计算过。所以新鲜密文的噪音称之为初始噪音。这个相当重要。

 

Dec算法(解密)也和我们平常理解的一样,就是对密文的解密,但是这里解密算法不仅能对初始密文解密,还能够对计算后的密文解密。但是由于部分同态加密方案中密文存在噪音,例如在整数上的全同态加密方案里,密文乘积的噪音是噪音之积,密文加法的噪音是噪音之和。所以当密文计算到一定程度,其噪音将超过上限,所以对这样的密文解密将可能失败。全同态加密的关键就是对噪音的控制,使之能对任何密文解密。

 

最后一个算法:Evaluate算法(密文计算),这个算法是整个全同态加密四个算法中的核心。可以做个这样的比喻:前面三个算法是大楼的地基,后面这个Evaluate算法就是大楼。这个比喻在后面会体会到它的用意。密文的计算是在电路里进行的,电路是分层的,电路深度越深,层数越多,密文就能够进行更多次的计算。随便提一句,密文计算的次数等于电路深度的对数。什么是计算次数?例如c1*c2,就是进行了一次计算,次数为2,c1*c2*c3就是进行了两次计算,次数为3。在全同态加密中,我们一般用乘法次数来衡量计算次数,这是因为乘法的噪音比加法噪音增长的快很多。

 

Evaluate算法有三个输入,第一个输入是计算公钥Evk,就是我们在上次博文里讲到的。Evk可以没有。第二个输入是函数f,就是Evaluate算法所要执行的函数,可以是任意函数,因为全同态加密的目标就是对密文能够进行任意计算。当然这个函数也可以是“解密函数”,Gentry通过观察发现了一个秘密,等会我们说。第三个输入是密文,理论上可以有无穷多个密文,但是这是不可能的。

 

所以Evaluate算法就是将密文输入到函数f里进行计算。我们知道在全同态加密的方案里,密文都是含有噪音的,密文的计算会导致噪音的增长,如果把函数f表示成电路,那么Evaluate算法实际上只能够对有限深度L的电路进行计算,超过这个深度L的电路就不行了。所以我们把这样的方案称之为部分同态加密方案。由此可见Evaluate算法的重要性,全同态加密就靠它了。还记得刚才的比喻么?Evaluate算法相当于大楼,这个大楼的层数是有限的,而全同态加密的目标是无限高!

 

所以噪音问题导致了Evaluate算法不能够对任意电路(函数)进行计算。

 

而全同态加密追求的就是Evaluate算法能够对任意电路进行计算,怎么办?那只有控制噪音问题了。如何控制噪音呢?下回分解。

 




https://blog.sciencenet.cn/blog-411071-738683.html

上一篇:全同态加密释疑(一):四个算法(1)
下一篇:全同态加密释疑(二):一个技术
收藏 IP: 134.219.227.*| 热度|

31 吴艳华 王梅娟 孙爽 刘才思 孔金英 胡明星 zhengchy huxianjun heyechengzhang Xmain woshizzm123 yangwwv SnowInRain logozy lilu2012 heyide amoebaz qianrenjian kongfu liuliqw xxhaitun ZhuziTang huquan2013 xiangliuming zhongguo393 ZBCDZBCD fairy1674 leijie0358 fanjiabing zznfighting lt2222

该博文允许注册用户评论 请点击登录 评论 (6 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-23 17:12

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部