SEAL全同态加密库（七）

一.同态的乘法

全同态乘法的具体代码如下，下面会讲述其具体过程

 public void MultiplyInplace(Ciphertext encrypted1, Ciphertext encrypted2,
            MemoryPoolHandle pool = null)
        {
            Multiply(encrypted1, encrypted2, destination: encrypted1, pool: pool);
        }
 public void Multiply(Ciphertext encrypted1, Ciphertext encrypted2,
            Ciphertext destination, MemoryPoolHandle pool = null)
        {
            if (null == encrypted1)
                throw new ArgumentNullException(nameof(encrypted1));
            if (null == encrypted2)
                throw new ArgumentNullException(nameof(encrypted2));
            if (null == destination)
                throw new ArgumentNullException(nameof(destination));

            IntPtr poolPtr = pool?.NativePtr ?? IntPtr.Zero;
            NativeMethods.Evaluator_Multiply(NativePtr, encrypted1.NativePtr, encrypted2.NativePtr, destination.NativePtr, poolPtr);
        }

二.乘法的具体过程

同态乘法在程序上很简单，但是比加法复杂得多。如上所述，消息以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的幂次方的系数和噪音量，以便我们确信它们能够正确解密。