|||
全同态加密释疑(四):转折点:LWE上全同态加密的诞生
陈智罡
Gentry构造全同态加密方案的思想是非常“规则”的,是按照数学的思维来考虑问题的,就是围绕理想这一概念,因为只有这样才能产生密文的加法和乘法算。Gentry第一个全同态加密方案是基于理想格构造的。方案所选择的代数结构是理想格,是因为在格里解密操作比较简单,绝大多数都是矩阵向量乘或是内积,它们都属于NC1,具有低的解密电路复杂度,此外理想格像格一样具有加法结构,同时它还具有乘法结构的特性,可以说两全其美。
所有后面沿着Gentry的构造思路都是按照这个思想来的。直到LWE上的全同态加密方案的出现。
Gentry构造全同态加密方案的思想可以抽象概述为:首先在环R上构造一个线性纠错码C,“线性”意味着保证加法同态性,“纠错”意味着码字中存在错误,如果该错误在一定范围内就可以纠错。而且C是环上的一个理想,其基有两种表示,一种是“好”的表示,用来做密钥,可以对大的错误进行纠错(相当于解密),当错误超过上限后将无法纠错(即无法解密)。另外一种表示是“坏”的表示,用来做公钥,可以产生随机的码字,用于加密。由于线性纠错码C的线性特性决定了其具有加法同态特性,另外C是环上的一个理想,所以其乘法也具有同态特性,然而由于错误存在上限,因此仅对有限次的乘法计算保持其同态特性。该思想形成的方案就是部分(Somewhat)同态加密方案,由于密文计算中错误增长的原因,该方案只能对密文进行有限次的运算。最初的方案都可以用这种思想解释。
上述构造思想中的环结构保证了乘法计算,但是对于LWE(环LWE)上的加密方案由于没有环结构,所以无法提供密文向量的乘法,一度成为LWE(环LWE)上构造全同态加密的最大障碍。Brakerski在论文Bv11中引入了再线性化技术与维数模约减技术,成功的解决了在没有环结构的方案中进行密文乘积的问题。后来在BGV方案中经过改进形成了密钥交换技术和模交换技术。
在基于LWE(环LWE)的全同态加密方案中,密文乘积定义为两个密文c1和c2的张量c1c2,对应的密钥为ss。按照这种形式的乘法定义,一方面,密文乘积将导致密文维数的膨胀,只能进行常数次的密文乘法计算;另一方面,同样面临着噪音在乘法中急剧增长的问题。解决这些问题,一方面通过使用密钥交换技术,可以将密文的维数还原到原来的维数,因此可以进行下一次密文的乘积;另一方面使用模交换技术,可以将增长的噪音约减回原来的噪音大小上。因此,不需要启动就可以获得层次型全同态加密方案(可以执行任意多项式深度的电路),所以不再需要稀疏子集和问题假设和循环安全假设,这是全同态加密思想上的一次飞跃,打破了原有的Gentry构造框架,效率上也得到了极大地提升。目前效率最高的环-LWE上的BGV方案使用的就是这种构造方法
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-19 14:43
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社