全同态加密算法深入解析-3

加密

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

加密明文的过程是将一个系数模为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方案)的工作原理。