全同态加密释疑（四）：转折点：LWE上全同态加密的诞生

陈智罡

Gentry构造全同态加密方案的思想是非常“规则”的，是按照数学的思维来考虑问题的，就是围绕理想这一概念，因为只有这样才能产生密文的加法和乘法算。Gentry第一个全同态加密方案是基于理想格构造的。方案所选择的代数结构是理想格，是因为在格里解密操作比较简单，绝大多数都是矩阵向量乘或是内积，它们都属于NC1，具有低的解密电路复杂度，此外理想格像格一样具有加法结构，同时它还具有乘法结构的特性，可以说两全其美。

所有后面沿着Gentry的构造思路都是按照这个思想来的。直到LWE上的全同态加密方案的出现。

Gentry构造全同态加密方案的思想可以抽象概述为：首先在环R上构造一个线性纠错码C，“线性”意味着保证加法同态性，“纠错”意味着码字中存在错误，如果该错误在一定范围内就可以纠错。而且C是环上的一个理想，其基有两种表示，一种是“好”的表示，用来做密钥，可以对大的错误进行纠错（相当于解密），当错误超过上限后将无法纠错（即无法解密）。另外一种表示是“坏”的表示，用来做公钥，可以产生随机的码字，用于加密。由于线性纠错码C的线性特性决定了其具有加法同态特性，另外C是环上的一个理想，所以其乘法也具有同态特性，然而由于错误存在上限，因此仅对有限次的乘法计算保持其同态特性。该思想形成的方案就是部分（Somewhat）同态加密方案，由于密文计算中错误增长的原因，该方案只能对密文进行有限次的运算。最初的方案都可以用这种思想解释。

上述构造思想中的环结构保证了乘法计算，但是对于LWE（环LWE）上的加密方案由于没有环结构，所以无法提供密文向量的乘法，一度成为LWE（环LWE）上构造全同态加密的最大障碍。Brakerski在论文Bv11中引入了再线性化技术与维数模约减技术，成功的解决了在没有环结构的方案中进行密文乘积的问题。后来在BGV方案中经过改进形成了密钥交换技术和模交换技术。

在基于LWE（环LWE）的全同态加密方案中，密文乘积定义为两个密文c₁和c₂的张量c₁c₂，对应的密钥为ss。按照这种形式的乘法定义，一方面，密文乘积将导致密文维数的膨胀，只能进行常数次的密文乘法计算；另一方面，同样面临着噪音在乘法中急剧增长的问题。解决这些问题，一方面通过使用密钥交换技术，可以将密文的维数还原到原来的维数，因此可以进行下一次密文的乘积；另一方面使用模交换技术，可以将增长的噪音约减回原来的噪音大小上。因此，不需要启动就可以获得层次型全同态加密方案(可以执行任意多项式深度的电路)，所以不再需要稀疏子集和问题假设和循环安全假设，这是全同态加密思想上的一次飞跃，打破了原有的Gentry构造框架，效率上也得到了极大地提升。目前效率最高的环-LWE上的BGV方案使用的就是这种构造方法