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

博文

GSW13方案分析

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

噪音问题:该方案的噪音形式也很特别。如果密文C1C2的噪音是e1e2,则两个密文加法的噪音是e1+e2,密文乘积的噪音是m2e1+ C1e2,乘积噪音不仅依赖于原来的老的噪音,还依赖于密文C1。如果C1C2B-边界密文,即Ci中元素的值与ei中元素的值不超过B,则密文矩阵的乘积是(N+1)B2有界的,经过深度为L的乘法电路,噪音增长形式为,其电路计算深度为对数深度,而我们需要的是多项式深度。为了达到这个目的,每次密文计算后对结果密文进行Flatten操作,使得密文是“强B边界”的,即密文C中元素的值至多为1,错误e中的元素值至多为B,这样就可以执行深度为L的电路,其噪音至多为(N+1)LB,立刻就得到一个能够执行多项式深度的层次型全同态加密方案。要保证密文解密正确,只要(N+1)LB < q/8所以有8(N+1)L < q/B,这与Bra方案的噪音形式非常相像。

参数及性能:根据上面噪音分析有q/B > 8(N+1)L,由于q/B是安全归约的近似因子,所以q/B不能取为关于n的指数[54],则可以取q/B是关于n的亚指数。这是因为在该方案中不需要为了更多的同态计算而把B取得特别小,另外L是多项式,这样取q/B是关于n的亚指数就是合理的,所以q就可取为关于n的指数,例如q =。根据Peikert的经典归约理论[48],该方案可以经典归约到LWE问题。该方案消除了使用密钥交换技术,从而在电路计算中不需要一个高维矩阵与高维向量的乘积(其复杂度为)。但是密文计算不再是向量之间的计算,而是矩阵之间的加法或乘法,矩阵的维数是O(nlog q)。该方案对深度为L,且由与非门组成的电路计算复杂度为,其中n是维数,< 2.3727

安全性:根据上面参数选择,该方案将安全性从标准格上的标准困难困难问题GapSVP经典归约到LWE上。其近似因子为q/B = (poly(n))L




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

上一篇:Bra12方案分析
下一篇:在Mathtype中如何输入花体字母
收藏 IP: 39.189.5.*| 热度|

0

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

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

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

GMT+8, 2024-4-25 14:19

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部