CKKS EXPLAINED, PART 4: MULTIPLICATION AND RELINEARIZATION

Introduction

在之前的文章《解释CKKS，第3部分：加密和解密》中，我们看到了如何基于RLWE问题创建同态加密方案，并实现同态加法和密文-明文乘法。

尽管密文-明文乘法很容易实现，但密文-密文乘法要复杂得多，正如我们将看到的。事实上，我们需要处理许多事情，例如找到合适的操作，使得解密后我们得到两个密文的乘积，并管理密文的大小。

因此，本文将介绍密文-密文乘法和重线性化的概念，以减小结果密文的大小。

Recap of basic operations

为了了解在CKKS中如何进行密文-密文乘法，让我们回顾一下在之前的文章中所讨论的内容。

首先，请记住我们在多项式空间${\mathcal{R}}_q={\mathbb{Z}}_q[X]/(X^N+1)$上进行操作。我们选择一个作为秘密密钥的多项式$s$，然后可以安全地生成一个公钥$p=(b,a)=(-a\cdot s+e,a)$，其中$a$是在${\mathcal{R}}_q$上均匀采样的多项式，$e$是一个小的随机多项式。

然后，我们有加密操作$Encrypt(\mu ,p)=c=(c_0,c_1)=(\mu ,0)+p=(-a\cdot s+e+\mu ,a)\in {\mathcal{R}}_q^2$，用于对明文$\mu \in {\mathbb{Z}}_q[X]/(X^N+1)$使用公钥$p$进行加密。

为了使用秘密密钥解密密文$c$，我们进行以下操作：$Decrypt(c,s)=c_0+c_1\cdot s=\mu +e$。

然后，我们看到定义密文加法$CAdd(c,c^{\prime })$很容易，这样一旦我们对$CAdd$的输出进行解密，我们将近似得到两个底层明文的加法。

具体做法是将$CAdd$定义为：$CAdd(c,c^{\prime })=(c_0+c_0^{\prime },c_1+c_1^{\prime })=c+c^{\prime }=c_{add}$

实际上，如果我们对其应用解密操作，我们会得到：

$$\begin{array}{rl}\text{Decrypt}(c_{add},s)& =c_0+c_0^{\prime }+(c_1+c_1^{\prime })\cdot s\\ & =c_0+c_1\cdot s+c_0^{\prime }+c_1^{\prime }\cdot s\\ & =\text{Decrypt}(c,s)+\text{Decrypt}(c^{\prime },s)\\ & \approx \mu +{\mu }^{\prime }.\end{array}$$

在这里，我们可以看到密文的加法操作非常简单，我们只需要将两个密文相加，然后使用常规的解密操作对结果进行解密，以获得两个底层明文的加法。

当进行密文-密文乘法时，我们将看到乘法和解密操作都更加复杂。

Ciphertext-ciphertext multiplication

现在我们已经看到了，我们的目标是找到操作$\text{CMult}$和$\text{DecryptMult}$，使得对于两个密文$c$和$c^{\prime }$​，我们有：

$$\text{DecryptMult}(\text{CMult}(c,c^{\prime }),s)=\text{Decrypt}(c,s)\cdot \text{Decrypt}(c^{\prime },s)。$$

请记住，$\text{Decrypt}(c,s)=c_0+c_1\cdot s$。因此，如果我们展开上面的表达式，我们得到：

$$\begin{array}{rl}\text{Decrypt}(c,s)\cdot \text{Decrypt}(c^{\prime },s)& =(c_0+c_1\cdot s)\cdot (c_0^{\prime }+c_1^{\prime }\cdot s)\\ & =c_0\cdot c_0^{\prime }+(c_0\cdot c_1^{\prime }+c_0^{\prime }\cdot c_1)\cdot s+c_1\cdot c_1^{\prime }\cdot s^2\\ & =d_0+d_1\cdot s+d_2\cdot s^2.\end{array}$$

其中$d_0=c_0\cdot c_0^{\prime }$，$d_1=c_0\cdot c_1^{\prime }+c_0^{\prime }\cdot c_1$，$d_2=c_1\cdot c_1^{\prime }$。

有趣！如果我们思考一下，将$\text{Decrypt}(c,s)=c_0+c_1\cdot s$视为在秘密密钥$s$上进行多项式求值，那么它可以被看作是一个一次多项式，形式为$c_0+c_1\cdot S$，其中$S$是多项式变量。

因此，如果我们将对两个密文乘积的解密操作视为在秘密密钥$s$上对二次多项式$d_0+d_1\cdot S+d_2\cdot S^2$进行求值。

因此，我们可以使用以下操作来进行密文-密文乘法：

$$\text{CMult}(c,c^{\prime })=c_{mult}=(d_0,d_1,d_2)=(c_0\cdot c_0^{\prime },c_0\cdot c_1^{\prime }+c_0^{\prime }\cdot c_1,c_1\cdot c_1^{\prime })$$$$\text{DecryptMult}(c_{mult},s)=d_0+d_1\cdot s+d_2\cdot s^2$$

使用这样的操作可能有效，但是存在一个问题：密文的大小增加了！实际上，虽然密文通常只包含几个项式，但在这里，我们的密文有3个项式。根据之前的推理，如果我们不采取任何措施，在正确解密下一个乘积时，我们将需要5个项式，然后是9个项式，以此类推。因此，密文的大小将呈指数级增长，并且如果我们采用这种方式来定义密文-密文乘法，它在实践中将无法使用。

我们需要找到一种方法，在每一步中进行乘法而不增加密文的大小。这就是重线性化的作用！

Relinearization

我们注意到，可以将密文之间的乘法定义为操作$CMult(c,c^{\prime })=(d_0,d_1,d_2)$。然而，问题在于现在输出是一个维度为3的密文，如果在每次计算后继续增加密文的大小，实际使用将变得不可行。

那么问题是什么？问题在于我们需要第三个项，即用于多项式解密的$d_2$项，即$DecryptMult(cmult,s)=d_0+d_1\cdot s+d_2\cdot s^2$。但是，如果我们能够找到一种方法，只使用一个一次多项式作为常规解密，就可以计算出$d_2\cdot s^2$，会怎么样呢？在这种情况下，密文的大小将保持不变，它们只是一对项式！

这就是重线性化的核心：找到一对多项式$(d_0^{\prime },d_1^{\prime })=Relin(cmult)$，使得：

$$\begin{array}{rl}\text{Decrypt}((d_0^{\prime },d_1^{\prime }),s)& =d_0^{\prime }+d_1^{\prime }\cdot s\\ & =d_0+d_1\cdot s+d_2\cdot s^2\\ & =\text{Decrypt}(c,s)\cdot \text{Decrypt}(c^{\prime },s).\end{array}$$

换句话说，重线性化允许我们拥有一对项式，而不是三对项式，一旦使用只需要秘密密钥而不需要其平方的常规解密电路解密它们，我们就能得到两个底层明文的乘积。

因此，如果我们在每个密文-密文乘法之后执行重线性化，我们将始终拥有相同大小的密文，并使用相同的解密电路！

现在你可能想知道我们如何定义Relin才能获得这样的结果。思路很简单，我们知道我们需要一对多项式，使得$d_0^{\prime }+d_1^{\prime }\cdot s=d_0+d_1\cdot s+d_2\cdot s^2$。想法是，我们将定义$(d_0^{\prime },d_1^{\prime })=(d_0,d_1)+P$，其中$P$表示一对多项式，使得$Decrypt(P,s)=d_2\cdot s^2$。

这样，当我们对$(d_0^{\prime },d_1^{\prime })$进行解密电路评估时，我们得到：

$$\begin{array}{rl}\text{Decrypt}((d_0^{\prime },d_1^{\prime }),s)& =\text{Decrypt}((d_0,d_1),s)+\text{Decrypt}(P,s)\\ & =d_0+d_1\cdot s+d_2\cdot s^2.\end{array}$$

一个方法是提供一个评估密钥，用于计算$P$。设$evk=(-a_0\cdot s+e_0+s^2,a_0)$，其中$e_0$是一个小的随机多项式，$a_0$是在${\mathcal{R}}_q$上均匀采样的多项式。然后，如果我们应用$Decrypt(evk,s)=e_0+s^2\approx s^2$。很好！我们看到我们可以公开分享评估密钥给执行计算的一方，因为根据RLWE问题，很难提取出密钥，它可以用于找到平方项。

因此，$P$的一个可能的候选，即解密为$d_2\cdot s^2$的密文，可以简单地定义为$P=d_2\cdot evk=(d_2\cdot (-a_0+e_0+s^2),d_2\cdot a_0)$。确实，正如我们所见，我们有$Decrypt(P,s)=d_2\cdot s^2+d_2\cdot e_0$。那么我们可以像通常一样做，将$d_2\cdot s^2+d_2\cdot e_0$近似为$d_2\cdot s^2$吗？

不幸的是在实践中，我们无法直接处理该问题，因为$d_2\cdot e_0$项远大于我们通常处理的噪声。如果您之前有注意到，我们允许对结果进行近似，是因为错误多项式很小，例如一系列小的多项式之和，这样不会对结果产生太大的影响。但是，这里的问题是$d_2$会很大，因为$d_2=c_1\cdot c_1^{\prime }$，其中每个$c_1$ 包含在${\mathcal{R}}_q$上均匀采样的多项式$a$，因此它要比我们通常处理的小错误多项式大得多。

那么在实践中我们如何解决这个问题呢？方法是对评估密钥（evaluation key）进行一些修改，定义为$\text{evk}=(-a_0\cdot s+e_0+p\cdot s^2,a_0)\mathrm{mod}(p\cdot q)$，其中$p$是一个大整数，$a_0$是从${\mathcal{R}}_{p\cdot q}$上均匀采样的值。这里的思想是我们将通过除以$p$来减小与$d_2$相乘引入的噪声，因此最终我们有： $P=\lfloor p^{-1}.d_2.evk\rceil (\mathrm{mod}q)$，这意味着我们将除以$p$并将结果四舍五入为最接近的整数，并使用模$q$进行处理（而不是$p\cdot q$）。

好了，最终我们终于有了候选解决方案！对于重线性化（relinearization）的定义，我们需要一个评估密钥（可以公开使用而不会带来风险），定义为：

$$\mathtt{Relin}((d_0,d_1,d_2),evk)=(d_0,d_1)+\lfloor p^{-1}.d_2.evk\rceil$$

所以，如果我们有两个密文$c$和$c^{\prime }$，并且我们想要将它们相乘（可能多次），然后解密结果，工作流程如下：

将它们相乘：$\text{cmult}=\text{CMult}(c,c^{\prime })=(d_0,d_1,d_2)$

进行重线性化：$\text{crelin}=\text{Relin}((d_0,d_1,d_2),\text{evk})$

解密输出：${\mu }_{\text{mult}}=\text{Decrypt}(\text{crelin},s)\approx \mu \cdot {\mu }^{\prime }$

我在这里给出了整体的思路，但如果您对细节感兴趣，我建议阅读论文《Somewhat Practical Fully Homomorphic Encryption》中的解释。

现在，我们知道了如何将两个密文相乘并保持它们的大小不变。太棒了！虽然您可能认为这已经结束了，但在实现同态加密方案之前，我们还需要进行最后一步：重新缩放（rescaling）。在下一篇文章中，我们将了解什么是重新缩放以及如何进行操作，然后再着手编写我们自己的代码！