全同态加密算法深入解析

介绍

同态加密方案提供了一种惊人的能力——能够在不解密的情况下，对密文数据进行计算。这使您无需破坏敏感源数据，同时可以对数据进行处理。

其中最有影响的一个方案(也是最近一些标准化工作的主题)被称为Fan-Vercauteren (FV)方案(或称为Brakerski-Fan-Vercauteren方案)，我们将在这里深入地进行说明，同时你也可以尝试使用以下实现该方案的算法库：

这些加密方案看起来很复杂，也有一点神秘，但希望本文能让您清楚地了解它们的工作原理和驱动因素。

这篇文章的整体结构包括

·一点点数学介绍

·加密和解密是如何工作的

·同态加法和乘法

一些数学介绍

这些同态加密方案是基于Ring Learning with Errors问题。本质上，这些方案中的数据在加密时(密文)和未加密时(明文)都以多项式表示。

这些几乎是学校里每个人都学过的多项式。像

4x2 + 2x + 1

但有一些区别，第一个是系数都是整数，并且需要mod t。假设t = 24，这就像一个24小时的时钟，21加6得到3。多项式的所有系数都是这样处理的。

或者，我们可以将数字考虑在-11到12之间，这样我们就可以方便地求负数。注意，这只是一个方便系数——余数为-1和余数为23(除以24时)之间没有区别。

第二点，也是比较棘手的一点，在于这种使用余数的思想不仅适用于多项式的系数，也适用于多项式本身。

我们定义了一个特殊的多项式，称为多项式模，并且只考虑多项式乘以该多项式模后的余数。FV方案中该多项式模的具体形式为xd + 1，其中对于某些n，有d = 2n。为了说明这一点，我们取n = 4，因此多项式为x16 + 1。

因为我们考虑的是关于模x16 + 1之后的余数，所以我们只需要考虑幂从x0到x15的多项式。任何更高次的幂都会因乘以该多项式模而消去。这也可以被理解为，x16 ≡ −1(mod x16 + 1)，这意味着x16可以被-1替换，以将x的更高次幂归约到0到15的范围内。

所以我们考虑的多项式都是这种形式的

其中这16系数(即ai)中的每一个的范围都是从0到t − 1。我们可以用系数的环面来说明，如下所示：

在这个图中，每个循环表示多项式中x的幂次方前的系数的取值范围（包含24个可能值）。绿点代表系数取0时所处的位置。这为我们提供了一种很好的方法来可视化多项式，这在我们考虑加密和解密步骤如何工作时将会有所帮助。

FV加密方案涉及大量的多项式乘法。当我们把x的两个幂次方相乘，比如2x14和x4时，我们把它们的指数相加，得到2x18。有人可能会假设，求这个多项式关于多项式模的余数可能需要在x16处将指数旋转回0，得到2x2，就像上面所示的整数系数那样。如果多项式模是x16，情况就是这样。然而，我们的多项式模是x16 + 1 – 如上所述，额外的+1因子引入了一个符号变化，这有助于进一步干扰乘法的结果。

如上图所示，当2x14乘以x4后模x16 + 1时，取这个项(由上面的红点表示)，向前旋转环面4个幂，然后从0处调整系数的值，得到22x2(或−2x2，如果我们认为数字是从-12到11而不是从0到23时)。

这种形式的多项式具有非常丰富的结构和许多不错的特性。它们是分圆多项式的子集。使用其中一个作为多项式模并不是严格必需的，但是这样做会更加方便快速。

使用环上的多项式加密

我们已经介绍了FV加密方案中使用的环上的多项式的一些属性，现在我们可以讨论加密和解密的工作原理。首先，我们需要讨论如何生成私钥和公钥，然后讨论如何使用它们进行加密和解密。

私钥和公钥

加密采用明文，并使用从私钥派生的公钥将其转换为密文。从明文到密文的转换是通过一种只有在您知道私钥的情况下才容易可逆的方式完成的。

更具体地说，明文是环上的多项式，其具有多项式模xd + 1，其中d = 2n，以及系数模t。明文加密后为密文，其是由两个环上的、具有相同多项式模的多项式构成的，但系数模为q，通常q远大于t。

例如，多项式模为x4096 + 1，这意味着明文和密文中的多项式都有d = 4096个系数。明文多项式的系数需要模t = 290764801，密文多项式的系数需要模q = 9214347247561474048或更大。

为了便于说明，我们将使用较小的数字，但希望这些数字能够更好地说明方案的各个步骤中发生了什么。在第一部分中，为了更直观，我们将使用d = 16、t = 7和q = 874。注意，这些参数是不安全的!!

对于私钥或密钥，我们用s表示，它是我们随机生成的一个系数为-1、0或1的多项式。例如，

接下来，我们从密文空间中随机生成一个多项式(用于生成公钥)，其系数模为q，我们用a表示。

我们还定义了一个噪音多项式，它是“小”的，因为它是从离散高斯分布中取的一个小系数。这个多项式只在这里使用一次，然后丢弃。

然后将公钥定义为一对多项式，即pk = ([−as + e]q, a)，其中多项式都是模多项式模和系数模q的。

对于上面给出的示例，公钥的第一个多项式被构造为

其中第一个乘法取多项式a，它的系数mod q，然后乘以系数为-1 0或1的s。由于模上多项式模的多项式的乘法具有“旋转和反射”性质，有效地混合和打乱了a的所有系数，并进一步增加了小的噪音。多项式a有效地掩盖了公钥中的私钥。

通过从公钥中找到s的方式来破解加密方案，其主要涉及的计算为([−as + e]q, a)。唯一的因素是该方案中包含了噪音——如果e为零，则很容易从公钥中计算出s。当e足够大，但又不太大时，这是一个难题。

本文的示例中，私钥可以通过暴力攻击恢复——−尝试每个可能的s(只有3 ^ 16 = 43046721组合)，然后计算as + e来寻找出一个接近公钥的第一项的答案。对于真正的参数，这种暴力攻击的方法是完全不可行的。3 ^ 4096是一个很大的数字，但有更聪明的方法，然后定义给定的一组参数的安全性。

加密

加密过程看起来有点像公钥生成过程。

加密明文的过程是将一个系数模为t的多项式转换为一对系数模为q的多项式。本例中，我们将加密一个非常简单的多项式(称为消息) – m = 3 + 4x8 ≡ 3−3x8 – 只有两个不为零的系数。

加密还需要三个小的多项式。两个噪音多项式来自于相同的离散高斯分布(即和公钥中的噪音多项式的取法一样)，另一个多项式我们称之为u，它的系数为-1、0或1，就像私钥一样。

和

这些多项式只在加密过程中使用，然后丢弃。

密文是由两个多项式组成的，通过如下计算得到

请注意消息中的值是在mod t的范围内，而在我们的示例中，它们被缩放为q/t (即128)，使它们覆盖mod q的范围。这是消息**入到密文时的唯一更改。这些值通过添加到第一项来掩盖，第一项的值是在mod q的范围内，与随机的噪音没有区别。u的随机性改变了每次加密中使用的掩码，从而确保相同的明文在每次加密时产生不同的密文。

同态加法和乘法之所以有效，是因为消息在密文中以比例来表示。其他项用于掩盖消息，而且可以证明它们是有效的，只有在您知道私钥的情况下才能删除它们。

使用上面给出的多项式显式地计算密文的第一个元素

代入公钥，我们可以看到密文的第一个元素展开为ct0 =[e1 + eu – aus + qm / t]q。在这个表达式中，前两项是“小”的，与噪音成比例，后两项是“大”的。第一个大项有效地掩盖了第二个大项，即消息。

密文的第二个元素是这样计算的:

代入公钥，我们看到密文的第二个元素展开为ct1 = [au + e2]q。这说明了解密是如何工作的——如果我们知道s，就可以计算出ct1s = [aus + e2s]q，它可以用来消除密文的第一个元素中的非消息大项。

综上所述，密文可以用公钥、私钥、掩码、噪音和消息表示为

解密

如上所述，解密相对简单。首先，我们计算[ct0 + ct1s]q，它将从消息中完全移除掩码。这给我们一个多项式，它可以展开为[qm / t + e1 + eu + e2s]q -也就是说，缩放后的信息加上一些噪声。因此，只要噪声不太大，我们就可以恢复消息。

明确地，

在这里您可以看到，除了明文的两个非零系数(x8和x0)之外，所有的系数都小于q/t = 128。如果我们把这个多项式缩放回mod t范围内的值，那么我们就得到

四舍五入这些系数可以恢复我们的消息m = 3 − 3x8。

我们通过将系数四舍五入，来舍入到最接近的整数后得到我们的信息:

把它们放在一起，我们通过如下计算来解密密文

⌊⌉表示舍入到最接近的整数(四舍五入)。

如果系数中噪音太大，那么它们最终会更接近一个与正确整数不同的整数，然后解密会(悄无声息地)失败并产生错误的结果。在上面的示例中，**的噪音为13 / 128，所以仍然有一些空间允许产生更多的噪音，并且能够正确解密。噪音的含量可以通过将q / t的比值变大或变小来调节。

同态操作

人们对这类密码体制如此感兴趣的一个主要原因是，它们允许同态加法和乘法(来自希腊语homo – same和morphe – shape)。这意味着您可以在数字仍然加密的情况下进行加法和乘法运算，而不必先解密它们。这是一个令人惊叹的功能，有望在数据保护和安全方面构建一个新的黄金标准。

同态加法

最简单的情况是两个加密数字的加法。假设我们已经用相同的公钥加密了两个多项式m1和m2：

注意，我们需要使用两个不同的、小的多项式u1和u2，以及4个小的噪音多项式e1…e4。

如果我们仅仅是将密文中的元素相加，就会得到一个新的密文

由于消息仅存在于具有缩放的密文中，所以加法的结果与m1 + m2加密的形式相同，只是增加了新的噪音：

近似解密(舍入之前)将是

这意味着只要新的噪音不是太大，消息m1 + m2将正确解密。噪音有三种类型:

我们担心的是，当这些项变得足够大，以至于噪音多项式中的一个系数大于q/(2t)时，解密就会失败，因为解密过程结束时的四舍五入操作会四舍五入到错误的数字。

如果我们只考虑第一项，那么我们就把来自离散高斯分布的多项式中的系数相加。这意味着，在某些情况下，我们会把一个负系数加到一个正系数上，结果会更接近于零。在其他情况下，系数会有相同的符号，所以结果会更大。我们可以做很多的同态加法，看看噪音是如何随着加法的数量增加而增加的，这是很有指导意义的。系数的分布如下图所示，其中我们添加了1、5和30个噪音多项式(随机地进行了数百次试验)。

当我们添加了30个噪音多项式时，某些系数有可能会大于64，即超过了q/t的一半，所以解密不会产生正确的结果。

另外两项表示不同的情况——第二项是一个噪音多项式乘以一些“小的多项式”(系数为-1、0或1)的总和。这种乘**产生更大的噪音。一个噪音多项式和一个小的多项式的乘积的系数大约将是随机正负号的噪音多项式系数的2/3rds的总和。这意味着这个噪音与多项式的**次的平方根√n一致。

对这一项绘制与上面相同的分布可以看出，它比第一项大得多，而且即使对于我们示例中的参数，也存在错误解密的危险，即使只是添加了几个参数。

第三项是类似的——一组噪音多项式之和，乘以一个“小的多项式”。它的噪音分布是这样的:

结合起来，我们可以画出这三项的**系数的增长，作为已经发生的加法数量的函数。这是一个须状图，给出了这些**值的可变性。(注意噪音的均值接近于零，这是**系数的幅值分布。)

这表明，对于我们所选择的参数，由两个以上加法产生的密文，解码错误的概率很高，而且两次加法失败的概率也很高。这是因为有时**错误大于64，当q/t = 128时，会导致不正确的解密，就像这里一样。为了给这样的操作提供更多的空间，我们需要使用更大的q/t比值，这可以应对通常由所执行的操作数量引入的噪音量。

不幸的是，由密文的同态乘法引入的噪音量又要大得多。

同态乘法

同态乘法在程序上很简单，但是比加法复杂得多。如上所述，消息以qm1/t的比例出现在密文的第一个元素中。因此，将两个密文的第一个元素相乘，再乘以t/q，就会得到一个带有qm1m2/t的项——如果我们仍然能够除去掩码项，这个项就可以恢复。

因此，要理解同态乘法的机制，关键在于了解如何从密文的乘积中去掉掩码项。要做到这一点，我们的想法是把密文看作是私钥s的幂次方的一个简单多项式。这是这篇文章中使用多项式的第三种不同的方法，所以它有点令人困惑，但是它是理解同态乘法如何工作的关键。

我们可以写出解密过程的第一部分，使密文的每个元素都是s的多项式的系数:

请记住，ct和s本身就是多项式，所以这个方程是一个多项式乘以一个多项式(s0)加上一个多项式乘以另一个多项式，然后所有这些都取多项式模xd + 1和系数模q。

现在，我们在上面看到解密产生了一个与掩码项au无关的量。

好了，现在考虑两个密文a和b，它们被定义为两个消息m1和m2的加密，它们可以被解密:

其中n1和n2表示密文中的噪声。

如果我们取它们的乘积，我们有:

右边的表达式与计算a和b所用的掩码无关，所以左边也必须与它们无关。

如果我们把左边展开成s的形式(为了方便起见，再乘以t/q)就得到了

其中

这样做意味着我们可以计算出一个新的密文的组成部分，它比原来的密文多一个元素，并且可以正确地使用密钥s的幂次方进行解密。

解密的形式展开如下:

这只是增加了另一项即多项式乘以多项式的平方。有很多簿记要做，但它只是学校级代数(直到模数部分!)这是解密步骤的概括，它允许我们解密同态乘法的结果。

要了解这一切是如何显式地工作的，请考虑a和b在加密过程中的展开式

如果我们展开乘法的定义，同时对结果进行部分解密(即解密到除以q/t和整数之前)，那么得到的表达式就很复杂。但是，由于每个密文的组件都是在解密过程中被构造成能够删除掩码项(aui)的，所以这个展开的结果完全不依赖于来自公钥的掩码项!!!得到的表达式如下：

这里有很多项，但是现在我们已经去掉了掩码，问题是，噪音(除了第一个)与q/(2t)的“噪音预算”相比有多大?

为了感受这一点，我们模拟了大量加密的随机信息的乘法，d = 16，t = 7，q = 7168 = 1024×t。各类型噪音的系数大小分布如下图所示。请注意，总的噪音需要大于q/(2t) = 512才能导致解密错误。在这些项中，涉及噪音多项式的项、消息和私钥e22m1 + e12m2s是**的贡献者。

上图显示，对于这些参数，**的贡献来自于包含噪音多项式乘以消息多项式和私钥的项。这种噪音的**系数约为300。这里有两项，其他的项更小。把所有的噪音合并成一个，就得到了乘法结果的总噪音。这些系数的分布如下图所示：

这表明没有足够的预算来安全地进行单次乘法，然后解密这些参数的正确结果(无论如何都是不安全的!)——大约1/4000的系数将具有大于512的噪音，导致约1%的解密错误率。

因此，如果我们将它们视为s的多项式，则可以进行密文的乘法，从而在解密时抵消它们自己的掩码项。将它们相乘，并分别跟踪s的幂次方的系数和噪音量，以便我们确信它们能够正确解密。

Relinearisation和其他话题

上面概述的乘法策略允许我们进行多次乘法，但代价是每次乘法都将密文的大小增加一个多项式。密文在大小上增长可能是一个问题。事实证明，有一些方法可以将密文的大小还原为两个多项式，但代价是增加噪音。这就是所谓的Relinearisation（再线性化），因为你要去掉s多项式中的二次项和更高的项。

另一项使这种加密方案切实可行的重要技术是将多个消息打包到一个明文中，通过并行化提高吞吐量。

结论

粗略地说，加密是将消息隐藏在一个环上的多项式中，并添加一些噪音。每个密文都包含足够的信息，可以在给定私钥的情况下除去自己的掩码。因为嵌入只涉及到消息的缩放，所以仍然可以对它们执行加法和乘法，并使用一些巧妙的结构来在之后移除掩码。该方案的安全性来自于在不知道私钥的情况下，在噪声存在的情况下很难去除掩码。这个问题的难度导致了一些**的安全性能，例如没有已知的量子算法来攻击这些系统。

如果您已经了解了这些，我们希望您现在能够更好地理解基于Ring Learning with Errors问题的同态加密方案(或者至少是这些方案中的FV方案)的工作原理。