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

博文

Bra12方案分析

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

噪音问题:该方案的噪音增长形式有些特别,若密文的噪音上限是E,初始密文中的噪音上限为NBB取自错误高斯分布),则密文加法的噪音为2E + ,密文乘法的噪音近似为(nlog q)•E+()B,乘法噪音和前面的方案都不同,没有出现E2,这是因为在其密文乘法定义中(2/q)•(c1c2),其每一项都除以q,使得出现E2项的地方变成E2/q,由于该方案为了启动以及经典约减到最坏情况下的格上标准困难问题,q必须取得很大,例如q=,从而使E2/q成为了可以忽略的小数,乘法噪音主要取决于(nlog q)•E。所以对于深度为L的电路有Ei+1≈(nlog q)•EiEL(nlog q)LB。为了能够正确解密,噪音值要小于,所以有q ∕ B > (nlog q)L,这使得该方案的同态特性仅依赖于q ∕ B的比值,所以qB的值可以任意取(只要符合安全性需求),B就可以从任何分布中选取(只要符合LWE安全假设),而BGV方案的B必须从错误高斯分布中选取。

参数及性能:该方案的密钥是从中随机选取,没有像BGV方案取自于错误高斯分布。其原因是该方案模q取的比较大,所以相应的B不能取小(安全性需求),由于噪音依赖于密钥的范数,为了约减范数,密钥采用的是二进制位的形式(BitDecomp)。另外,该方案使用的是启动技术获得全同态加密。由于解密电路深度是O(log n+loglog q),所以只要q ∕ B > (nlog q)O(log n+ loglog q)即可。方案取q=,则电路计算复杂度是。每次加法或乘法后要进行密钥交换,而密钥交换是一个高维矩阵与高维向量的乘积,所以上述复杂度主要来自于密钥交换,又由于模q取大的值,所以产生了较高的复杂度。该方案由于是用启动方法获得全同态,所以电路中的每个门电路还要与解密电路相连,而解密电路的计算复杂度是),所以最终所需的计算复杂度就是

安全性:该方案将安全性从标准格上困难问题GapSVP经典归约到LWE上,所以取q=,则B=q ∕(nlog q)O(log n+ loglog q)= q nO(logn)。因此其近似因子为nO(log n)




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

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

0

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

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

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

GMT+8, 2024-11-28 08:41

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部