CKKS EXPLAINED, PART 4 MULTIPLICATION AND RELINEARIZATION

# CKKS EXPLAINED, PART 4: MULTIPLICATION AND RELINEARIZATION

# Introduction

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

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

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

# Recap of basic operations

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

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

然后，我们有加密操作 $E n c r y p t (μ, p) = c = (c_{0}, c_{1}) = (μ, 0) + p = (- a \cdot s + e + μ, a) \in R_{q}^{2}$ ，用于对明文 $μ \in Z_{q} [X] / (X^{N} + 1)$ 使用公钥 $p$ 进行加密。

为了使用秘密密钥解密密文 $c$ ，我们进行以下操作： $D e c r y p t (c, s) = c_{0} + c_{1} \cdot s = μ + e$ 。

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

具体做法是将 $C A d d$ 定义为： $C A d d (c, c^{'}) = (c_{0} + c_{0}^{'}, c_{1} + c_{1}^{'}) = c + c^{'} = c_{a d d}$

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

\begin{aligned} Decrypt (c_{a d d}, s) & = c_{0} + c_{0}^{'} + (c_{1} + c_{1}^{'}) \cdot s \\ = c_{0} + c_{1} \cdot s + c_{0}^{'} + c_{1}^{'} \cdot s \\ = Decrypt (c, s) + Decrypt (c^{'}, s) \\ \approx μ + μ^{'} . \end{aligned}

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

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

# Ciphertext-ciphertext multiplication

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

DecryptMult (CMult (c, c^{'}), s) = Decrypt (c, s) \cdot Decrypt (c^{'}, s) 。

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

\begin{aligned} Decrypt (c, s) \cdot Decrypt (c^{'}, s) & = (c_{0} + c_{1} \cdot s) \cdot (c_{0}^{'} + c_{1}^{'} \cdot s) \\ = c_{0} \cdot c_{0}^{'} + (c_{0} \cdot c_{1}^{'} + c_{0}^{'} \cdot c_{1}) \cdot s + c_{1} \cdot c_{1}^{'} \cdot s^{2} \\ = d_{0} + d_{1} \cdot s + d_{2} \cdot s^{2} . \end{aligned}

其中 $d_{0} = c_{0} \cdot c_{0}^{'}$ ， $d_{1} = c_{0} \cdot c_{1}^{'} + c_{0}^{'} \cdot c_{1}$ ， $d_{2} = c_{1} \cdot c_{1}^{'}$ 。

有趣！如果我们思考一下，将 $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}$ 进行求值。

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

CMult (c, c^{'}) = c_{m u l t} = (d_{0}, d_{1}, d_{2}) = (c_{0} \cdot c_{0}^{'}, c_{0} \cdot c_{1}^{'} + c_{0}^{'} \cdot c_{1}, c_{1} \cdot c_{1}^{'})

DecryptMult (c_{m u l t}, s) = d_{0} + d_{1} \cdot s + d_{2} \cdot s^{2}

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

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

# Relinearization

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

那么问题是什么？问题在于我们需要第三个项，即用于多项式解密的 $d_{2}$ 项，即 $D e c r y p t M u l t (c m u l t, s) = d_{0} + d_{1} \cdot s + d_{2} \cdot s^{2}$ 。但是，如果我们能够找到一种方法，只使用一个一次多项式作为常规解密，就可以计算出 $d_{2} \cdot s^{2}$ ，会怎么样呢？在这种情况下，密文的大小将保持不变，它们只是一对项式！

这就是重线性化的核心：找到一对多项式 $(d_{0}^{'}, d_{1}^{'}) = R e l i n (c m u l t)$ ，使得：

\begin{aligned} Decrypt ((d_{0}^{'}, d_{1}^{'}), s) & = d_{0}^{'} + d_{1}^{'} \cdot s \\ = d_{0} + d_{1} \cdot s + d_{2} \cdot s^{2} \\ = Decrypt (c, s) \cdot Decrypt (c^{'}, s) . \end{aligned}

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

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

现在你可能想知道我们如何定义Relin才能获得这样的结果。思路很简单，我们知道我们需要一对多项式，使得 $d_{0}^{'} + d_{1}^{'} \cdot s = d_{0} + d_{1} \cdot s + d_{2} \cdot s^{2}$ 。想法是，我们将定义 $(d_{0}^{'}, d_{1}^{'}) = (d_{0}, d_{1}) + P$ ，其中 $P$ 表示一对多项式，使得 $D e c r y p t (P, s) = d_{2} \cdot s^{2}$ 。

这样，当我们对 $(d_{0}^{'}, d_{1}^{'})$ 进行解密电路评估时，我们得到：

\begin{aligned} Decrypt ((d_{0}^{'}, d_{1}^{'}), s) & = Decrypt ((d_{0}, d_{1}), s) + Decrypt (P, s) \\ = d_{0} + d_{1} \cdot s + d_{2} \cdot s^{2} . \end{aligned}

一个方法是提供一个评估密钥，用于计算 $P$ 。设 $e v k = (- a_{0} \cdot s + e_{0} + s^{2}, a_{0})$ ，其中 $e_{0}$ 是一个小的随机多项式， $a_{0}$ 是在 $R_{q}$ 上均匀采样的多项式。然后，如果我们应用 $D e c r y p t (e v k, s) = e_{0} + s^{2} \approx s^{2}$ 。很好！我们看到我们可以公开分享评估密钥给执行计算的一方，因为根据RLWE问题，很难提取出密钥，它可以用于找到平方项。

因此， $P$ 的一个可能的候选，即解密为 $d_{2} \cdot s^{2}$ 的密文，可以简单地定义为 $P = d_{2} \cdot e v k = (d_{2} \cdot (- a_{0} + e_{0} + s^{2}), d_{2} \cdot a_{0})$ 。确实，正如我们所见，我们有 $D e c r y p t (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}^{'}$ ，其中每个 $c_{1}$ 包含在 $R_{q}$ 上均匀采样的多项式 $a$ ，因此它要比我们通常处理的小错误多项式大得多。

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

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

Relin ((d_{0}, d_{1}, d_{2}), e v k) = (d_{0}, d_{1}) + ⌊ p^{- 1} . d_{2} . e v k ⌉

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

将它们相乘： $cmult = CMult (c, c^{'}) = (d_{0}, d_{1}, d_{2})$

进行重线性化： $crelin = Relin ((d_{0}, d_{1}, d_{2}), evk)$

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

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

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

编辑

上次更新: 2025/04/01, 01:48:12

← CKKS EXPLAINED, PART 3 ENCRYPTION AND DECRYPTION CKKS EXPLAINED, PART 5 RESCALING→