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

博文

DGHV方案分析

已有 12011 次阅读 2014-9-16 16:24 |个人分类:全同态|系统分类:科研笔记| style, 能力, 影响, 安全性

我们从噪音、参数及性能、安全性三个方面对DGHV方案进行分析。

噪音问题:噪音问题直接影响方案的同态计算能力。上述方案中,两个密文之和的噪音等于噪音之和,两个密文之积的噪音等于噪音之积,所以噪音的增长主要来自于乘法。假设DGHV方案中的初始密文噪音为xi,且|xi|<B,那么方案能对密文执行多少次同态计算呢?令f (x1,…, xt )是次数为d的初等对称多项式,则当 |f (x1,…, xt )| < p/2时方案能够正确执行该函数,显然有 |f (x1,…, xt )|< td • Bd,令td • Bd < p/2,则有d < (log p)∕(log tB)。而解密电路的运算次数主要取决于c·p-1,然而p-1是一个小数,为了保证c·p-1取整之后的精确度,p-1要取log c位。由于两个t位数的乘积次数最多为2t1.71t=2t2.71,所以c· p-1的运算次数至少为2(log p)2.71(具体解释参见[49,50]),显然大于方案所能执行的次数d,因此需要压缩解密电路。而压缩解密电路的目的是为了通过启动技术获得全同态加密方案。由于计算次数与深度是对数关系,所以DGHV方案的部分同态计算电路深度是logd,非常浅。

参数及性能:通过上述噪音分析可以看到,要想提高同态计算能力,可以增大模p的取值,但是为了抵抗各种格的攻击,要求log qi要远远大于log p2,所以提高p的值将会导致密文变得很大。一个比较合适的参数选择是:。部分同态方案中有个公钥,每个公钥xi的长度为,则整个公钥的长度达到了。在实践中为了抵抗格的攻击,每个公钥尺寸至少应该为223位,那么公钥大小就可达246位,对于实践应用来说太大了!。

根据上述参数选择,两个密文乘积的计算复杂度是O(),由于方案是利用启动技术,而启动的计算复杂度是,所以方案的门电路计算复杂度是O()。整数上的全同态加密方案最大优势就是易于理解。随后Coron 等人对DGHV方案进行了优化[29,30],公钥尺寸下降到

安全性:方案的安全性依赖于两个问题:一个是近似GCD问题,另一个是稀疏子集和问题。前者在部分同态加密方案中使用,后者是在压缩电路时使用。近似GCD问题已经有比较深入的研究[52]。目前稀疏子集和问题还没有被深入研究,在构造全同态加密方案中,只是假设该问题是安全的,这方面值得进一步深入研究。但是在第二代全同态加密方案中,已经无需使用该假设了。




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

上一篇:英国访学需要办理那些银行卡?
下一篇:BGV方案分析
收藏 IP: 39.189.5.*| 热度|

0

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

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

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

GMT+8, 2024-7-17 14:36

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部