||
从噪音、参数及性能、安全性三个方面对BGV方案进行分析。
噪音问题:假设密文的噪音是E,对应的模是qj,则两个密文相加后噪音增长为2E,乘积后噪音增长近似为E2。然后进行密钥交换,噪音增长一个小的加法因子eswitch,噪音为E2+eswitch,再经过模交换噪音变为 (qj-1∕qj)•( E2 + eswitch) + escale。上述的每一步都要保证噪音小于界限,从而密文可以正确解密。例如加法、乘法和密钥交换后,噪音要小于qj∕2,模交换后噪音要小于qj-1∕2 。根据噪音的增长形势,可以设置各级模的大小以管理噪音。如果取qj∕qj-1≈E,则(qj-1∕qj)•( E2 + eswitch) + escale≈E,那么每次模交换后噪音被拉回到原来的大小。因此对于深度为L的电路,如果密文初始噪音是B(取自于错误高斯分布),则令最大的模qL≈BL+1,最小的模q0 > B(略大于B就可以),qj≈qj-1•B,那么该方案就可以执行深度为L的电路。这比以往只能执行次数为d 的电路来说,是极大地提升。
参数及性能:BGV方案的参数重点是设置阶梯模的大小,而模的大小与深度L和安全参数相关,同时还要满足上述的噪音条件约束,即每一次密文计算后,密文的噪音要小于其界限。阶梯模可以取为qj≈
。另外使用模交换技术要求密钥必须是短的,所以密钥必须取自错误高斯分布[47],对于LWE问题也有同样的结果[53]。性能方面,整个电路计算复杂度为
。密文的长度为
。如果最后额外再进行一次维数约减,可以进一步约减密文的大小,最终密文的长度可以与Regev05方案的密文长度相同,但是不能再进行同态计算了。如果上述层次全同态加密方案,再使用启动技术即可获得“纯”的全同态方案,电路的计算复杂度为
。
安全性:其安全性建立在理想格上的最短向量(SVP)问题,该问题可以量子规约到R-LWE问题。近似因子为: qL/B =。
1/1 | 闂傚倷娴囬鏍礈濮橆儵锝夊箳濡ゅ﹥鏅i梺璺ㄥ櫐閹凤拷:8 | 婵犵妲呴崑鎾跺緤妤e啯鍋嬮柣妯款嚙杩濋梺璺ㄥ櫐閹凤拷 | 婵犵數鍋為崹鍫曞箰閹间焦鏅濋柨婵嗘川閸楁岸鎮楀☉娅辨粍绂嶅⿰鍫熺叆闁绘洖鍊圭€氾拷 | 婵犵數鍋為崹鍫曞箰閹间緡鏁勯柛鏇ㄥ幘閸楁岸鎮楀☉娅辨粍绂嶅⿰鍫熺叆闁绘洖鍊圭€氾拷 | 闂傚倷绀侀幖顐︽偋濠婂牆纾诲┑鐘叉搐杩濋梺璺ㄥ櫐閹凤拷 | 闂備浇宕垫慨鎾箹椤愶附鍋柛銉亹瑜版帗鏅搁柨鐕傛嫹 |
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2025-3-18 20:50
Powered by ScienceNet.cn
Copyright © 2007-2025 中国科学报社