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

博文

BGV方案分析

已有 10349 次阅读 2014-9-16 16:26 |个人分类:全同态|系统分类:科研笔记

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

噪音问题:假设密文的噪音是E,对应的模是qj,则两个密文相加后噪音增长为2E,乘积后噪音增长近似为E2。然后进行密钥交换,噪音增长一个小的加法因子eswitch,噪音为E2+eswitch,再经过模交换噪音变为 (qj-1qj)( E2 + eswitch) + escale。上述的每一步都要保证噪音小于界限,从而密文可以正确解密。例如加法、乘法和密钥交换后,噪音要小于qj2,模交换后噪音要小于qj-12 。根据噪音的增长形势,可以设置各级模的大小以管理噪音。如果取qjqj-1E,则(qj-1qj)( E2 + eswitch) + escaleE,那么每次模交换后噪音被拉回到原来的大小。因此对于深度为L的电路,如果密文初始噪音是B(取自于错误高斯分布),则令最大的模qLBL+1,最小的模q0 > B(略大于B就可以),qjqj-1B,那么该方案就可以执行深度为L的电路。这比以往只能执行次数为d 的电路来说,是极大地提升。

参数及性能BGV方案的参数重点是设置阶梯模的大小,而模的大小与深度L和安全参数相关,同时还要满足上述的噪音条件约束,即每一次密文计算后,密文的噪音要小于其界限。阶梯模可以取为qj。另外使用模交换技术要求密钥必须是短的,所以密钥必须取自错误高斯分布[47],对于LWE问题也有同样的结果[53]。性能方面,整个电路计算复杂度为。密文的长度为。如果最后额外再进行一次维数约减,可以进一步约减密文的大小,最终密文的长度可以与Regev05方案的密文长度相同,但是不能再进行同态计算了。如果上述层次全同态加密方案,再使用启动技术即可获得“纯”的全同态方案,电路的计算复杂度为

安全性:其安全性建立在理想格上的最短向量(SVP)问题,该问题可以量子规约到R-LWE问题。近似因子为:  qL/B =




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

上一篇:DGHV方案分析
下一篇:Bra12方案分析
收藏 IP: 39.189.5.*| 热度|

0

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

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

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

GMT+8, 2024-4-24 18:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部