阅读论文《Homomorphic Multiple Precision Multiplication for CKKS and Reduced Modulus Consumption》

推荐阅读：本文是原始的深度问答记录（Q&A）。如果您想阅读经过整理、结构更清晰的技术博客版本，请访问：深度解析：CKKS 同态加密中的多精度乘法优化 (HMPM)

这篇文章的后续思考：第二篇文章

前言

本文记录了与 Gemini 3 关于论文《Homomorphic Multiple Precision Multiplication for CKKS and Reduced Modulus Consumption》的深度对话。论文作者：Jung Hee Cheon, Wonhee Cho, Jaehyung Kim, 和 Damien Stehlé。

论文核心内容概述

核心痛点与目标

• 痛点：现有的 CKKS 方案在每次乘法（Rescaling）中会消耗大量的密文模数。当模数耗尽时，需要昂贵的自举（Bootstrapping）操作。
• 目标：通过一种新的乘法算法（$\text{Mult}^2$），在保持精度的同时，将模数消耗减少近一半。

核心技术创新

• 同态欧几里得除法 (Homomorphic Euclidean Division)：论文提出了一种将密文分解为”商”（高位部分）和”余数”（低位部分）的方法。
• 对表示法 (Pair Representation)：将一个标准 CKKS 密文 $ct$ 分解为一对密文 $(ct_{\text{high}}, ct_{\text{low}})$。
• $\text{Mult}^2$ 算法：针对分解后的密文对执行同态乘法。它包含三个修改后的步骤：
  • $\text{Tensor}^2$：类似于双精度乘法，但舍弃了影响最小的项（低位 $\times$ 低位），从而节省模数。
  • $\text{Relin}^2$：对分解后的部分进行重线性化。
  • $\text{RS}^2$：修改后的重缩放（Rescaling）操作。

扩展与应用

• Double-CKKS & Tuple-CKKS：将该方法扩展到 $t \ge 2$ 的情况（即 $\text{Mult}^t$），可以进一步降低模数消耗，实现同态多精度算术。
• 优势：
  • 增加同态容量：在相同的参数下，可以执行更多层的乘法。
  • 提高精度：可以使用较小的参数（如环维数 $N$）来实现高精度计算（例如 100-bit scaling factor）。
  • 效率提升：通过减半模数，可以减半环维数，从而减少密文大小和计算延迟。

实验结果

• 论文展示了在 $N=2^{15}$ 时，Double-CKKS 可以支持 18 层乘法，而标准 CKKS 仅支持 13 层。
• 在高精度场景下，$\text{Mult}^2$ 在计算速度、密文大小和密钥大小方面均优于标准方法。

第一部分：基础概念与动机

Q1: RNS-CKKS 与方案兼容性

问题：这个方案不是基于 RNS-CKKS 的吗？为什么说乘法比特数越大，模数消耗越多？Euclidean division 是什么？为什么密文的低位是在 $R^2$ 这个数域中？

回答：

1.1 这个方案是基于 RNS-CKKS 的

是的，这个方案完全兼容并且是基于 RNS-CKKS 实现的。

虽然在论文的理论部分（Section 1 到 4），为了公式推导的简洁性，作者通常使用一个大的整数模数 $Q$ 来描述（比如写成 $R_Q$），这在密码学论文中很常见，为了避免符号过于复杂。

但在实验部分（Section 6） 和 具体实现讨论（Section 4.2 Modulus consumption） 中，作者明确指出：

• 代码是基于 HEaaN 库 开发的（这是一个经典的 RNS-CKKS 库）。
• 实现依赖于 RNS arithmetic。
• 特别是对于新引入的模数 $q_{\text{div}}$，在 RNS 系统中，它通常被选为 RNS 质数基中的一个或多个质数的乘积。

所以，理论上讲它是通用的，但工程上它就是为了 RNS-CKKS 设计的优化。

1.2 为什么说”乘法比特数越大，模数消耗越多”？

这句话的逻辑链条如下：

1. 精度与缩放因子（Scaling Factor $\Delta$）的关系：在 CKKS 中，为了支持小数运算并保持精度，我们把消息 $m$ 放大 $\Delta$ 倍，变成整数形式存储。如果你想要处理更大比特数（即更高精度或更大数值范围）的乘数，你需要更大的缩放因子 $\Delta$ 来保证在噪声影响下依然能正确解码有效位。

2. 乘法带来的膨胀：当你计算两个密文相乘 $ct_1 \times ct_2$ 时，底层的消息变成了 $(m_1 \cdot \Delta) \times (m_2 \cdot \Delta) = m_1 m_2 \cdot \Delta^2$。此时缩放因子变成了 $\Delta^2$。

3. Rescaling（重缩放）消耗模数：为了让后续计算能继续进行，必须把缩放因子从 $\Delta^2$ 降回 $\Delta$。这是通过 Rescaling 操作完成的，本质上是把密文除以 $\Delta$。而在 CKKS 中，除以 $\Delta$ 是通过模数切换（Modulus Switching） 实现的：模数从 $Q$ 变成了 $Q/\Delta$。

结论：

• 乘数比特数大 $\rightarrow$ 需要更大的缩放因子 $\Delta$。
• $\Delta$ 越大 $\rightarrow$ 每次 Rescaling 消耗掉的模数（$\log \Delta$ bits）就越多。
• 因此，为了支持大数（高精度）乘法，传统的 CKKS 会迅速耗尽模数，导致能支持的电路深度变浅。这正是论文想要解决的痛点。

1.3 Euclidean division 是什么？

Euclidean division 就是我们在小学数学里学的带余除法（欧几里得除法）。

对于任意整数 $a$ (被除数) 和 $b$ (除数，且 $b \neq 0$)，存在唯一的整数 $q$ (商) 和 $r$ (余数)，满足： $a = b \cdot q + r$ 其中 $0 \le r < |b|$。

在论文中的应用：

论文把这个概念应用到了密文（或者说是多项式的系数）上。作者想把一个大密文 $ct$ 分解成两部分。选定一个除数 $2^k$（或者文中的 $q_{\text{div}}$），那么密文就可以表示为：

$ct = 2^k \cdot \hat{ct} + \check{ct}$

• $\hat{ct}$ 是商（对应高位，High part）。
• $\check{ct}$ 是余数（对应低位，Low part）。

这就像把数字 $12345$ 按照 $100$ 分解：$12345 = 100 \times 123 + 45$。$123$ 是高位，$45$ 是低位。论文正是利用这种分解，把一个大精度的乘法拆成了几个小精度的乘法来做。

1.4 关于 1.1 节截图中的两个问题

问题 A：为什么密文的低位 $\check{ct}$ 是在 $R^2$ 这个数域中（而不是 $R_Q^2$）？

这里 $R$ 指的是整数多项式环 $\mathbb{Z}[X]/(X^N+1)$。

• 原因： $\check{ct}$ 是 $ct$ 除以 $2^k$ 的余数。
• 根据欧几里得除法的定义，余数的系数绝对值一定小于除数的一半，即 $|\check{ct}| \le 2^k/2$。
• 文中假设模数 $Q$ 远大于 $2^k$ （$Q > 2^k$）。
• 结论： 因为 $\check{ct}$ 的系数非常小（远没有达到模数 $Q$ 的边界），它在模 $Q$ 的意义下和在整数 $\mathbb{Z}$ 的意义下是完全一样的，不会发生取模回绕（Wrap-around）。所以作者说它可以被视为直接在 $R^2$（整数域）中，这强调了它是精确的数值，没有模数噪声。

问题 B：为什么解密后的误差项满足 $\check{e} = 2^k \hat{e}$？

这是一个通过线性关系推导出来的结果，目的是为了保证总和不变。

1. 分解关系： 密文被分解为 $ct = 2^k \cdot \hat{ct} + \check{ct}$。
2. 解密即线性运算： 解密函数 $\text{Dec}(\cdot)$ 是线性的。所以： $m = \text{Dec}(ct) = 2^k \cdot \text{Dec}(\hat{ct}) + \text{Dec}(\check{ct})$
3. 定义误差：
   • 设理想的商是 $\hat{m}$，实际解密出的是 $\text{Dec}(\hat{ct}) = \hat{m} + \hat{e}$（$\hat{e}$ 是商的误差）。
   • 设理想的余数是 $\check{m}$，实际解密出的是 $\text{Dec}(\check{ct})$。
   • 我们知道原消息 $m = 2^k \hat{m} + \check{m}$。
4. 代入等式： $2^k \hat{m} + \check{m} = 2^k (\hat{m} + \hat{e}) + \text{Dec}(\check{ct})$ $2^k \hat{m} + \check{m} = 2^k \hat{m} + 2^k \hat{e} + \text{Dec}(\check{ct})$ 消去 $2^k \hat{m}$，得： $\check{m} = 2^k \hat{e} + \text{Dec}(\check{ct})$ 移项得： $\text{Dec}(\check{ct}) = \check{m} - 2^k \hat{e}$
5. 对应定义： 作者把 $\text{Dec}(\check{ct})$ 写成了 $\check{m} - \check{e}$ 的形式。 对比上面推导出的式子：$\check{m} - \check{e} = \check{m} - 2^k \hat{e}$。 所以：$\check{e} = 2^k \hat{e}$。

直观理解： 如果你在计算“商”（高位）的时候多算了 $\hat{e}$，那么因为商是被乘了 $2^k$ 的，所以你实际上多算了 $2^k \cdot \hat{e}$。为了让总数保持不变（还是原来的 $m$），你的“余数”（低位）就必须相应地少算 $2^k \cdot \hat{e}$ 来把这个误差抵消掉。

这就是文中提到的 “weak form of Euclidean division”（弱形式欧几里得除法）：高位和低位各自解密出来可能不是完美的数学上的商和余数，因为它们互相包含了一个”互补”的误差项，但它们合起来依然能完美还原原始消息。

第二部分：Decompose 与模数消耗

Q2: Decompose 机制与实现细节

问题：

1. 为什么论文中通过 decompose 能够减少模数消耗？
2. “First, we need a way to homomorphically decompose a large bit-size plaintext into smaller pieces” 这个是什么意思？
3. 1.1中的”Note that relying on smaller precision arithmetic for fixed-point or floating-point arithmetic is a standard technique”，这是什么意思，为什么要提这句话？
4. 1.1中，Attempt 1 里明文属于 $R^Q$，为什么 Attempt 2 中密文却是 $2^k \cdot Q$？对于 CKKS 方案，明文和密文多项式系数有什么大小限制吗？
5. 1.1节最后的图中在说些什么？

回答：

2.1 为什么通过 Decompose（分解）能够减少模数消耗？

核心逻辑：将“大数的乘法”转化为“小数的乘法”，并舍弃微不足道的部分。

在标准 CKKS 中，模数消耗（Rescaling 消耗的比特数）直接取决于你的缩放因子（Scaling Factor $\Delta$）。

• 如果你要计算两个很高精度的数（比如需要 100-bit 精度），你的 $\Delta$ 必须很大（比如 $2^{100}$）。
• 做一次乘法后，噪声变大，你需要除以 $\Delta$（Rescale）。这意味着你一次就要消耗掉 100-bit 的模数链。模数很快就用光了。

Decompose 的做法： 它把一个大数 $m$ 拆成两半：高位 $m_1$ 和 低位 $m_0$，即 $m = m_1 \cdot 2^k + m_0$。 这里 $m_1$ 和 $m_0$ 的数值范围都变小了（比如原来是 100-bit，现在两个都是 50-bit）。

• 现在做乘法时，我们实际上是在做 $(A_1 2^k + A_0) \times (B_1 2^k + B_0)$。
• 展开后是：$A_1 B_1 2^{2k} + (A_1 B_0 + A_0 B_1) 2^k + A_0 B_0$。
• 关键点：方案中的 Mult2 算法会扔掉最后那一项 $A_0 B_0$（因为它是“低位乘低位”，对总精度的影响极小）。
• 这样一来，每个分量（$m_1, m_0$）只需要较小的缩放因子就能维持精度。
• 结果：每次操作消耗的模数取决于分块的大小（比如 50-bit），而不是整个大数的大小（100-bit）。模数消耗减半，意味着你可以做更多层乘法，或者用更小的参数实现同等精度。

2.2 “Homomorphically decompose a large bit-size plaintext into smaller pieces” 是什么意思？

这句话拆开来看：

1. Large bit-size plaintext：一个数值很大的明文（例如 $m=12345$）。
2. Smaller pieces：把它拆成两个较小的数，比如按 $100$ 拆分，拆成商 $123$ 和余数 $45$。
3. Homomorphically（同态地）：这是最难的地方。
   • 如果你有私钥，解密出 12345，算出 123 和 45，再加密回去，这很简单。
   • 但是”同态”意味着你手里只有密文 $Enc(12345)$，你没有私钥，却要通过计算生成两个新的密文 $Enc(123)$ 和 $Enc(45)$。

为什么这很难？ 因为“取余数”和“整除”是非线性运算，在同态加密（尤其是 CKKS 这种近似计算）中非常难以实现。这篇论文的创新点就在于提出了一种高效的（虽然是近似的）方法来在密文状态下完成这个拆分。

2.3 关于 1.1 中提到的”Standard technique for fixed-point…”

意思是：不要觉得”扔掉低位乘低位”这个操作很奇怪，这在经典计算机科学里是很常见的操作。

• Fixed-point arithmetic（定点数算术）： 当计算机硬件只支持 32 位乘法，但你需要 64 位精度时，程序员会把 64 位数拆成两个 32 位数来算。
• 在计算 $A \times B$ 时，如果不把所有交叉项都算出来，而是为了效率舍弃掉最小的那个尾数项，结果依然是足够精确的。
• 为什么要提这句话？ 作者是在为他们的算法设计做辩护（Justification）。他们在 Mult2 算法中为了省模数，故意扔掉了 $A_0 B_0$ 这一项。如果有审稿人质疑“这不会导致精度损失吗？”，作者就可以说：“会损失一点点，但这是浮点数/定点数计算领域的标准做法，完全在可接受范围内。”

2.4 Attempt 1 和 Attempt 2 的模数问题，以及系数限制

这里你观察得很细致！

Attempt 1 vs Attempt 2：

• Attempt 1 (Decompose then Encrypt): 这是在说“如果我们在明文阶段就拆好”。比如我有明文 $m$，我先算出 $m_{hi}, m_{lo}$，然后分别加密成 $ct_{hi}, ct_{lo}$。这里 $R_Q$ 指的是多项式环，意思是系数很大也没关系，反正还没加密。
• Attempt 2 (Encrypt then Decompose): 这是论文真正采用的方法。这里密文模数是 $2^k Q$。
  • 为什么是 $2^k Q$？ 为了方便做除法。
  • 作者想在密文上通过乘以 $1/2^k$ 来提取高位。在模 $q$ 的算术中，“除以 $2^k$”其实是乘逆元。但如果模数本身是 $2^k$ 的倍数，我们可以通过简单的系数截断或者**重缩放（Rescaling）**操作来模拟“移位”和“除法”的效果。把模数设为 $2^k Q$ 可以让高位部分（Quotient）很自然地落在一个模数为 $Q$ 的密文空间里（即 $2^k Q / 2^k = Q$）。

CKKS 的系数限制：

• 明文多项式： 系数通常受限于缩放因子 $\Delta$ 或 $Q$。在编码后，系数大约是 $m \cdot \Delta$ 的大小。
• 密文多项式： 是一对多项式 $(c_0, c_1)$，它们的系数是在 $[0, Q-1]$ 范围内的整数（模 $Q$）。

2.5 这个截图（1.1节最后）到底在说什么？

这段话是在解释论文提出的**“弱形式同态欧几里得除法”（Weak Homomorphic Euclidean Division）**的原理，以及为什么即便有误差，它也是可用的。

逻辑流：

1. 目标： 我们把密文 $ct$ 拆成了 $( \hat{ct}, \check{ct} )$，希望 $\hat{ct}$ 是商（高位），$\check{ct}$ 是余数（低位）。理想情况是：$m = 2^k \cdot \text{商} + \text{余数}$。
2. 现实问题： CKKS 解密是有噪声（Error）的。所以解密出来的商 $\text{Dec}(\hat{ct})$ 不一定等于完美的整数商 $\hat{m}$。
   • 设：$\text{Dec}(\hat{ct}) = \hat{m} + \hat{e}$ （$\hat{e}$ 是商的误差）。
3. 互补效应（核心）：
   • 由于总的消息 $m$ 必须守恒（$m = \text{Dec}(ct)$），即： $m \approx 2^k \cdot \text{Dec}(\hat{ct}) + \text{Dec}(\check{ct})$
   • 如果你解密出的商多了一个误差 $\hat{e}$，那么这一项被乘了 $2^k$，变成了 $2^k \hat{e}$。
   • 为了让等式成立，解密出的余数 $\text{Dec}(\check{ct})$ 就必须自动包含一个相反的误差来抵消它。
   • 所以余数的解密值变成了：$\check{m} - \check{e}$，其中 $\check{e} \approx 2^k \hat{e}$。
4. 结论（Weak form）：
   • 虽然“余数部分”的误差 $\check{e}$ 很大（它是商误差的 $2^k$ 倍），看起来很吓人。
   • 但是，因为 $ct$ 拆分后的余数多项式 $\check{ct}$ 本身系数很小（这是由分解操作强制保证的），所以解密出来的结果在数学上依然成立。
   • 这就叫“弱”形式： 我们得到的不是完美的“商”和“余数”，而是一个“带了一点误差的商”和一个“带了巨大补偿误差的余数”。但妙就妙在，只要把它们重新组合起来，误差会互相抵消，还原出原始的 $m$。

简单总结截图的意思： “我们把密文拆了。虽然拆出来的‘商’和‘余数’各自都有点误差（尤其是余数的误差看起来很大），但因为解密公式是线性的，这些误差在重组时会正好抵消。所以这个拆分是安全的。”

第三部分：误差分析与精度控制

Q3: Decompose 的精度影响与误差抵消机制

问题：

1. Decompose后最终结果的精度有影响吗？
2. 对于解密密文的高位数据 $\hat{ct}$，将其解密得到 $\hat{m}+\hat{e}$，问题是，这个误差 $\hat{e}$ 是随机的，而且我只会得到一个解密结果，我并不能推测出高位解密后的误差 $\hat{e}$ 是多少，同样，对于解密密文的低位数据也是如此，那么我怎么可能确保高位和低位的解密误差抵消，从而保证结果正确？

回答：

这两个问题直击了该方案最反直觉的核心。别担心，你的困惑非常合理——通常我们在密码学里谈论”误差”时，默认它是随机且不可控的。但在这里，情况完全不同。

3.1 Decompose 后最终结果的精度有影响吗？

答案：有影响，但影响很小，且是可控的。

精度损失主要来自两个方面：

1. 舍弃了“低位 $\times$ 低位”项（算法设计层面的损失）：

   • 在 $\text{Mult}^2$ 算法中，为了节省模数，作者故意扔掉了 $\check{ct}_1 \times \check{ct}_2$ 这一项。
   • 想象你在算 $12.001 \times 13.001$。
     • $(12 + 0.001) \times (13 + 0.001) = 156 + 0.012 + 0.013 + \mathbf{0.000001}$。
   • 那个 $\mathbf{0.000001}$ 就是“低位 $\times$ 低位”。扔掉它对结果的影响非常微小（远小于 CKKS 本身自带的噪声）。这在数值计算中是标准的舍入操作。

2. 噪声放大的风险（数学层面的损失）：

   • 虽然我们下面会说误差能抵消，但因为“低位部分” $\check{ct}$ 实际上承载了放大了 $2^k$ 倍的误差（即 $\check{e}$），如果不加控制，经过多次乘法后，这个 $\check{e}$ 可能会增长得比正常 CKKS 快一点。
   • 解决办法： 论文提出定期进行 Recombine（重组） 操作。把 $( \hat{ct}, \check{ct} )$ 合并回一个普通密文 $ct$，让那些大的正负误差物理上抵消掉，然后再重新分解。这相当于“重置”了误差状态，保证了长期运行的精度。

结论： 只要参数选得好（比如适时重组），最终精度和标准 CKKS 几乎是一样的。

3.2 既然误差是随机的，我怎么能保证高位和低位的误差刚好抵消？

这是一个极其精彩的问题！你的直觉是：“高位解密出 $A + error1$，低位解密出 $B + error2$，这俩 error 都是随机的，凭什么加起来正好是 0？”

真相是：低位的误差 $\check{e}$ 根本不是随机的，它是被”强行制造”出来抵消高位误差的。

请看下面的推导，我会用一个**“切蛋糕”的例子**来打破这个迷思。

1. 数学上的”强制绑定” 并不是先算出高位，再独立算出低位。低位是根据高位算出来的。

论文中的分解过程（$\text{DCP}$）本质上执行了以下逻辑：

1. 计算商（高位）： $\hat{ct} = \text{Round}(ct / 2^k)$。
   • 这一步确实引入了随机误差，因为 $\text{Round}$ 会导致精度丢失。
2. 计算余数（低位）： $\check{ct} = ct - 2^k \cdot \hat{ct}$。
   • 注意！ 这里是严格的等式。余数被定义为“原数减去（除数乘以商）”。

2. 解密时的”魔法”

现在我们来解密（记解密函数为 $D(\cdot)$，它是一个线性函数，即 $D(A+B) = D(A)+D(B)$）。

我们把上面的等式两边同时解密： $D(\check{ct}) = D(ct - 2^k \cdot \hat{ct})$ $D(\check{ct}) = D(ct) - 2^k \cdot D(\hat{ct})$

移项得到： $D(ct) = 2^k \cdot D(\hat{ct}) + D(\check{ct})$

这说明什么？

• 不管 $D(\hat{ct})$（高位）错得有多离谱，哪怕它算错了一万八千里。
• $D(\check{ct})$（低位）都会自动包含一个“负的一万八千里”。
• 因为 $\check{ct}$ 在生成的时候，就是用总量减去高位得到的。剩下的就是低位，无论剩下的是什么。

3. 直观类比：切绳子

假设你有一根绳子，总长度是 100.5 米（这就好比原密文 $ct$）。

1. 你想把它切成两段，一段是整数部分（高位），一段是小数部分（低位）。
2. 你测量了一下，觉得整数部分应该是 50 米，于是你切了 50 米下来（这是 $\hat{ct}$）。
3. 那么剩下那段是多少？必然是 50.5 米（这是 $\check{ct}$）。
   • 当你把它们拼回去：$50 + 50.5 = 100.5$。结果正确。

现在，假设你“高位”切错了（产生了随机误差）：

1. 你手抖了，第一刀切成了 51 米（高位误差 $\hat{e} = +1$）。
2. 那么剩下那段绳子是多少？物理上必然变成了 49.5 米（低位自动变成了 $\check{e} = -1$）。
3. 当你解密（把两段绳子拼起来）时： $51 \text{ (高位)} + 49.5 \text{ (低位)} = 100.5$ 结果依然正确！

总结

你不需要推测误差是多少，也不需要手动去抵消它。

误差抵消是由代数结构保证的。因为 $\check{ct}$ 的定义就是 $ct - 2^k \hat{ct}$，所以当你把它们按 $2^k \hat{ct} + \check{ct}$ 加回去时，你只是把减去的东西又加了回来，结果必然还原回原始的 $ct$（以及原始的 $m$）。

所以，高位的误差是随机的，但低位的误差是”高位误差的镜像”，它们是互补的。

第四部分：Mult² 算法详解

Q4: Relinearization 和 Rescaling 的改进

问题：帮我详细解释 1.2 Multiplication of decomposed ciphertexts 中的 Relinearization and rescaling 部分，解释为什么要这么做。

回答：

这一部分确实比较绕，但如果抓住了**“高位误差放大”和”强制互补”**这两个核心逻辑，就很容易理解了。

为了实现分解密文的乘法，论文重新定义了 $\text{Relin}$（重线性化）和 $\text{RS}$（重缩放）。我们来看看为什么要改，以及怎么改的。

4.1 为什么不能直接用标准的 Relin 和 RS？（痛点：误差放大）

假设我们有两个分解好的部分 $(\hat{ct}, \check{ct})$，其中 $ct \approx 2^k \cdot \hat{ct} + \check{ct}$。

如果我们“天真”地对它们分别做标准操作：

• 对高位操作： $\hat{ct}_{new} = \text{Relin}(\hat{ct})$。
  • 问题来了： CKKS 的 Relin 操作会引入一个小的随机噪声 $e_{relin}$。
  • 所以 $\hat{ct}_{new} = \hat{ct}_{ideal} + e_{relin}$。
  • 但在最终恢复数据时，高位是要乘以 $2^k$ 的！
  • 这就导致最终误差变成了 $2^k \cdot e_{relin}$。
  • 后果： 本来 $e_{relin}$ 很小，但被放大了 $2^k$ 倍（比如放大 $2^{50}$ 倍），这个巨大的误差会瞬间摧毁整个计算结果的精度。

结论： 我们绝对不能允许在高位 $\hat{ct}$ 上直接引入“未被低位补偿”的独立误差。

4.2 Relin²：如何安全地重线性化？

为了解决上述问题，作者设计了 $\text{Relin}^2$。它的核心思想是：先把高位”还原”到原来的量级，处理完再拆开。

步骤解析：

公式：$\text{Relin}^2(\hat{ct}, \check{ct}) := \text{DCP}_{2^k}(\text{Relin}(2^k \cdot \hat{ct})) + (0, \text{Relin}(\check{ct}))$

这里做了三件事：

1. 放大高位（$2^k \cdot \hat{ct}$）：作者没有直接处理 $\hat{ct}$，而是先把它乘上 $2^k$。这样它的量级就和原始密文一样了。

2. 在大量级上做 Relin：计算 $\text{Relin}(2^k \cdot \hat{ct})$。此时引入的噪声 $e$ 是加在 $2^k \cdot \hat{ct}$ 上的，也就是加在”总数”上的。这个噪声没有被额外放大。

3. 重新分解（DCP）：把处理完的结果再次通过 $\text{DCP}$ 拆成新的商和余数。妙处：这一步拆分会自动把刚才 Relin 引入的噪声分配到新的”低位”里去（就像我们之前讨论的”切绳子”原理）。

总结：$\text{Relin}^2$ 避免了直接在高位加噪声，而是把噪声加在整体上，再通过分解操作把噪声”挤”到低位去。

4.3 RS²：如何安全地重缩放？

$\text{RS}$（Rescaling）的作用是把密文除以缩放因子 $\Delta$ 并取整。这也是一个会引入舍入误差的操作。

公式解析： $\text{RS}^2(\hat{ct}, \check{ct}) := (\underbrace{\text{RS}(\hat{ct})}_{\text{新高位}}, \underbrace{\text{RS}(2^k \cdot \hat{ct} + \check{ct}) - 2^k \cdot \text{RS}(\hat{ct})}_{\text{新低位}})$

这简直就是我们上一轮讨论的**“切绳子/互补误差”**逻辑的直接应用！

让我们看看为什么要这么写（假设 $\text{RS}(x) \approx x / \Delta$）：

1. 新高位（New High）： 直接对高位做重缩放：$\text{NewHigh} = \text{RS}(\hat{ct})$。

   • 这一步肯定有舍入误差：$\text{NewHigh} = \frac{\hat{ct}}{\Delta} + \epsilon_{round}$。
   • 就像之前说的，这个 $\epsilon_{round}$ 如果不处理，会被放大 $2^k$ 倍。

2. 新低位（New Low）： 作者是怎么算低位的？ $\text{NewLow} = \text{RS}(\text{Total}) - 2^k \cdot \text{NewHigh}$ (注：公式里的 $2^k \cdot \hat{ct} + \check{ct}$ 就是重组后的 Total 密文)。

   • 这步操作的物理含义： $\text{NewLow} = \text{近似总数} - 2^k \cdot \text{近似高位}$
   • 因为 $\text{总数} \approx 2^k \cdot \text{高位} + \text{低位}$。
   • 如果 $\text{NewHigh}$ 包含了正向误差（切多了），那么在计算 $\text{NewLow}$ 时，因为减去了 $2^k \cdot \text{NewHigh}$，这个正向误差就被减掉了。
   • 结果： $\text{NewLow}$ 会自动变成一个包含“负向补偿误差”的值。

总结： $\text{RS}^2$ 的做法是：先算高位，然后用“总数”减去“高位占的部分”来强行定义低位。 这样就强迫低位吸收了高位 Rescaling 过程中产生的所有舍入误差，保证了 $2^k \cdot \text{新高位} + \text{新低位} \approx \text{RS}(\text{旧总数})$ 的恒等关系。

全文总结

为什么要这么麻烦地设计 $\text{Relin}^2$ 和 $\text{RS}^2$？

一句话解释：为了防止“高位”上的微小操作误差被系数 $2^k$ 放大成灾难。

所有这些操作的核心策略都是：

1. 不要独立修改高位。
2. 要么先还原成整体再修改（Relin²）。
3. 要么利用代数恒等式 Total - High = Low，强行让低位去背锅（RS²）。

Q5: Relin² 的输入和数据结构

问题：Relin² 的输入是什么？是上一步 tensor 后的结果？以及 $(0, \text{Relin}(\check{ct}))$ 这里的 0 是什么意思？

回答：

这两个问题问到了算法的数据结构和运算逻辑的细节，非常棒。

5.1 Relin² 的输入是什么？

简短回答： 是的，它的输入正是 Tensor²（上一步） 的输出结果。

详细解释：

我们需要回顾一下 CKKS 乘法的标准流程：Tensor $\rightarrow$ Relin $\rightarrow$ Rescale。

1. Tensor² 的输出（即 Relin² 的输入）： 在标准 CKKS 中，两个密文相乘（Tensor）后，密文会膨胀。原本密文是 2 个多项式 $(c_0, c_1)$，相乘后变成了 3 个多项式 $(d_0, d_1, d_2)$。这被称为“度为 2 的密文”（Degree-2 ciphertext），因为它包含密钥 $s$ 的二次项 $s^2$。

   在 $\text{Mult}^2$ 方案中，因为我们维护的是一对密文 $(\hat{ct}, \check{ct})$，所以 Tensor² 的输出是一对“膨胀”了的密文：

   • $\hat{ct}$：是一个包含 3 个多项式的密文（高位部分）。
   • $\check{ct}$：也是一个包含 3 个多项式的密文（低位部分）。

   Relin² 的任务就是把这两个“膨胀”的 3 元素密文，压缩回正常的 2 元素密文 $(c'_0, c'_1)$。

5.2 (0, Relin(č̌t)) 这里的 0 是什么意思？

简短回答：这里的 0 代表一个**“全零密文”（Zero Ciphertext），它是为了保持”密文对”格式**而存在的占位符。

详细逻辑：

公式如下： $\text{Relin}^2(\hat{ct}, \check{ct}) := \underbrace{\text{DCP}_{2^k}(\text{Relin}(2^k \cdot \hat{ct}))}_{\text{部分 A}} + \underbrace{(0, \text{Relin}(\check{ct}))}_{\text{部分 B}}$

请注意，整个系统的基本数据单元是 “密文对” (Pair)，即所有运算结果都必须长这样：(高位部分, 低位部分)。

我们来看看加号两边分别是什么：

• 部分 A（处理高位）： $\text{DCP}(\dots)$ 这个函数会将输入分解，输出一个对：$(A_{high}, A_{low})$。 这是把高位的 Relin 结果拆解后得到的商和余数。

• 部分 B（处理低位）： 我们在做 $\text{Relin}(\check{ct})$，这是对低位进行的压缩操作。 这个操作的结果理应只属于**“新的低位”，而不应该影响“新的高位”。 但是，为了能和“部分 A”进行向量加法，它必须也被写成一个对**的形式。

  所以作者构造了这样一个对：

  • 高位位置： 放一个 0（全零密文）。意思是我这一步操作对高位没有贡献。
  • 低位位置： 放 $\text{Relin}(\check{ct})$。

最终的加法过程（向量加法）：

总结：

那个 0 就像我们在做向量运算 $(x, y) + (0, z)$ 时的那个 0 一样，只是为了让维度对齐，确保 $\text{Relin}(\check{ct})$ 只被加到结果的低位分量上，而不污染高位分量。

Q6: Growth of the low part（低位膨胀问题）

问题：详细介绍 1.2 中的 Growth of the low part。

回答：

这一部分描述了 $\text{Mult}^2$ 算法面临的一个核心挑战，以及作者提出的解决方案。我们可以把它称为**“低位部分的膨胀问题”**。

6.1 现象：低位部分（Low Part）为什么会变大？

起初，当我们刚对一个密文进行分解（Decompose）时： $ct = 2^k \cdot \hat{ct} + \check{ct}$ 根据带余除法的定义，低位 $\check{ct}$ 是余数，所以它的系数绝对值很小，被严格限制在 $\le 2^k/2$。

但是，当我们开始对分解后的密文进行乘法运算（特别是 $\text{Tensor}^2$ 步骤）时，低位部分会迅速变大。

原因分析： 回顾一下乘法的交叉项逻辑。假设我们有两个数 $A$ 和 $B$： $A \approx 2^k \hat{A} + \check{A}$ $B \approx 2^k \hat{B} + \check{B}$

$\text{Mult}^2$ 试图计算 $A \times B$。根据 $\text{Tensor}^2$ 的定义，新的低位部分（在逻辑上）大致对应于交叉项： $\text{NewLow} \approx \hat{A} \cdot \check{B} + \hat{B} \cdot \check{A}$ (注：这里为了直观忽略了具体的缩放因子和 $2^k$ 的系数调整，只看量级)

• $\hat{A}$ 和 $\hat{B}$ 是“商”，代表了数值的主要部分，数值很大。
• $\check{A}$ 和 $\check{B}$ 是“余数”，起初很小。
• 相乘结果： 一个“大数”乘以一个“小数”，结果会比原来的“小数”大得多。

结论： 经过一次乘法后，新的低位部分不再是简单的“余数”了，它混合了高位的信息，导致其数值量级显著增长。如果连续做多次乘法，这个膨胀会呈指数级累积。

6.2 危害：变大有什么问题？

如果低位部分 $\check{ct}$ 长得太大，会引发两个严重后果：

1. 精度雪崩（主要原因）：还记得 $\text{Mult}^2$ 为了省模数，在 Tensor 步骤中直接丢弃了 $\check{ct}_1 \otimes \check{ct}_2$ 这一项吗？

   • 起初：因为 $\check{ct}$ 很小，所以”小 $\times$ 小”微不足道，丢了也就丢了，误差很小。
   • 膨胀后：如果 $\check{ct}$ 变得很大，那么 $\check{ct}_1 \otimes \check{ct}_2$ 就变成了一个巨大的误差项。这时候再把它扔掉，就会导致计算结果严重偏离正确值。

2. 可能溢出：如果 $\check{ct}$ 的系数增长到超过了模数（虽然我们在 $R^2$ 中讨论，但实际实现还是有物理限制的），或者超过了为了保证”弱欧几里得除法”成立的界限，整个数学假设就会崩塌。

6.3 解决方案：重组与再分解 (Recombine and Decompose)

为了解决这个问题，作者提出了一种类似“定期重置”的策略。

策略名称： Recombine and Decompose (RCB $\circ$ DCP)

操作步骤： 当发现低位膨胀到一定程度（或者在进行了固定次数的乘法后），执行以下操作：

1. Recombine (RCB)： 把高位和低位拼回去，变成一个普通的单密文。 $ct_{temp} = 2^k \cdot \hat{ct} + \check{ct}$ 在这个加法过程中，低位中积累的那些“大数值”会被加到高位上去（进位），或者与高位的数值合并。

2. Decompose (DCP)： 立即对这个 $ct_{temp}$ 再次执行分解操作。 $ct_{new\_pair} = \text{DCP}(ct_{temp})$

效果：

• 新的低位 $\check{ct}_{new}$ 是通过强制取余得到的。
• 强制归零： 无论之前膨胀得由多大，经过这一步，新的低位系数又被强行压回了 $\le 2^k/2$ 的范围内。
• 误差重置： 之前累积的可能导致丢弃误差变大的因素被消除了。

4. 实验结论（来自 Figure 1）

论文在 1.2 节末尾和实验部分提到了一个具体的数据（参考 Figure 1）：

• 对于特定的参数（$N=2^{15}$），低位膨胀是显而易见的。
• 如果不处理，误差会指数级上升。
• 最佳实践： 作者发现，在连续执行 6 次 $\text{Mult}^2$ 乘法后，执行一次“重组与再分解”是性价比最高的。既避免了频繁操作带来的计算开销，又控制住了误差的增长。

总结

• 问题：乘法会让”低位”不再是单纯的”余数”，而是包含了高位的交叉项，导致数值越来越大。
• 后果：低位变大 $\rightarrow$ 丢弃项变大 $\rightarrow$ 精度丢失。
• 解决：也就是”洗牌”——定期把牌收回来（Recombine）重新发一次（Decompose），强行把低位压回初始的小状态。

第五部分：参数优化与模数分配

Q7: 不对称分解的效率分析

问题：之前有提到，将密文维度从 100bits，分解为高位低位各 50bits，可以节省一半模数，那如果分解的大小不一致呢？比如高位 60bits，低位 40bits 这种情况下是怎样的？

回答：

这是一个非常敏锐的问题！这涉及到优化理论中的**“均值不等式”**原理在密码学参数选择中的应用。

简短的回答是：不对称分解（如 60/40）会导致效率降低。50/50 分解是数学上的最优解（即模数消耗最小）。

为了解释为什么，我们需要回到该方案中控制精度和模数消耗的核心公式。

7.1 核心公式回顾

在 $\text{Mult}^2$ 方案中，我们要维持的总精度（Scaling Factor $\Delta$）大约等于“分解因子”乘以“消耗掉的模数”： $\Delta \approx q_{\text{div}} \times q_{\ell}$

1. $q_{\text{div}}$ ($= 2^k$)：决定了**低位部分（Low Part）**的大小。
   • 如果你选 $k=40$，低位就是 40 bits。
   • 如果你选 $k=60$，低位就是 60 bits。
2. $q_{\ell}$：是我们在做 Rescaling 时扔掉的模数（也就是我们要消耗的成本）。

制约条件（瓶颈）： 论文在误差分析（Theorem 4.8 和 4.9）中指出，为了保证计算结果正确，扔掉的模数 $q_{\ell}$ 必须足够大，至少要比低位部分的平方稍大一点，否则低位的误差项 $\frac{\text{Low}^2}{q_{\ell}}$ 会爆炸。 简单来说，必须满足： $q_{\ell} \gtrsim q_{\text{div}} \quad (\text{或者说 } \log q_{\ell} \ge k)$ (注：严格来说误差项是 Low $\times$ Low / $q_{\ell}$，如果要让这一项变小， $q_{\ell}$ 的比特数最好不小于 Low 的比特数)

7.2 场景分析：目标总精度 100 bits

我们现在的目标是 $\log \Delta = 100$。这意味着 $\log q_{\text{div}} + \log q_{\ell} \approx 100$。

我们来看看不同切分方式的代价：

1. 对称分解（50 / 50）—— 最优解

• 低位大小 ($k$)： 50 bits。
• 模数消耗 ($q_{\ell}$)： 为了凑齐 100 bits，且满足 $q_{\ell} \ge k$，我们选 $q_{\ell} = 50$ bits。
• 检查误差： $50 \ge 50$，误差被压制住了，没问题。
• 最终代价： 消耗 50 bits 模数。

2. 不对称：低位小，高位大（40 / 60）

即 $k=40$（低位 40 bits），剩下的高位承载 60 bits 的数值。

• 低位大小 ($k$)： 40 bits。
• 模数消耗 ($q_{\ell}$)： 必须满足两个条件：
  1. 总和 100：$40 + \log q_{\ell} = 100 \implies \log q_{\ell} = 60$。
  2. 压制误差：$60 \ge 40$。
• 检查误差： 满足条件。
• 最终代价： 消耗 60 bits 模数。
  • 亏了！ 本来只需要消耗 50 的，现在消耗了 60。因为虽然你的低位变小了，但为了维持总精度，你不得不把那个 $q_{\ell}$ 设得很大来补足剩下的精度。

3. 不对称：低位大，高位小（60 / 40）

即 $k=60$（低位 60 bits），剩下的高位承载 40 bits 的数值。

• 低位大小 ($k$)： 60 bits。
• 模数消耗 ($q_{\ell}$)： 必须满足两个条件：
  1. 总和 100：$60 + \log q_{\ell} = 100 \implies \log q_{\ell} = 40$。
  2. 压制误差（关键）： 论文要求 $q_{\ell}$ 至少要能包住低位。但这里 $40 < 60$！
     • 如果只用 40 bits 的模数去压制 60 bits 的低位噪声，误差项 $\approx 2^{120}/2^{40} = 2^{80}$。这会直接摧毁精度。
  • 强制修正： 为了不让误差爆炸，你被迫必须让 $q_{\ell}$ 至少也有 60 bits（甚至更大）。
• 最终结果：
  • 如果强行选 $q_{\ell}=40$，精度全毁，方案不可用。
  • 如果为了可用选 $q_{\ell}=60$，那么总精度变成 $60+60=120$ bits（超出了需求），且消耗了 60 bits 模数。
  • 又亏了！

总结

这就好比你要围一个 面积为 100 的矩形（面积代表总精度 $\Delta$），而模数消耗是矩形的较长边（因为 $q_{\ell}$ 必须既补足精度，又要盖过 $q_{\text{div}}$，取两者的最大值）。

• 正方形（50 $\times$ 50）： 边长为 50。这是让边长（模数消耗）最小的方案。
• 长方形（40 $\times$ 60）： 边长变成了 60。模数消耗变大了。

所以，均分（Symmetric Decomposition） 是让模数消耗降到最低（$1/2 \log \Delta$）的唯一数学极值点。任何偏离均分的操作，都会导致你需要消耗更多的模数来达到同样的精度，或者在同等模数下得到更差的精度。

Q8: 模数消耗的平方关系疑问

问题：你不是说”扔掉的模数 $q_\ell$ 必须足够大，至少要比低位部分的平方稍大一点”，为什么示例比较的时候却没有平方？

回答：

这是一个非常非常棒的质疑！你发现了我在上一条回答中为了简化直觉而表述不够严谨的地方。

让我根据论文的数学推导，为你精确地纠正这个概念。

结论先行：

你是对的，直觉上”低位平方”应该是 $2^{2k}$。但是，在 $\text{Mult}^2$ 的算法结构中，有一个关键步骤（Tensor 后的隐式除法）抵消掉了一个 $2^k$。所以，最终的数学约束变成了**“线性关系”**，而不是”平方关系”。即：模数 $q_{\ell}$ 的比特数 $\ge$ 低位部分 $q_{\text{div}}$ 的比特数。

8.1 为什么”平方”变成了”线性”？（数学推导）

让我们打开论文 第 8 页 “Modulus consumption” 这一小节，作者在这里给出了精确的推导。

步骤 A：噪声源头确实是“平方”

在做 $\text{Tensor}^2$ 时，我们扔掉的项是 $\check{ct}_1 \otimes \check{ct}_2$。

• 设低位大小为 $Q_{\text{low}} \approx 2^k$。
• 那么扔掉的这一项的大小确实是 $\approx (2^k)^2 = 2^{2k}$。

步骤 B：算法自带的“除法效应”

请注意 $\text{Mult}^2$ 的逻辑是模拟 $(A \times B) / 2^k$ 的效果（因为我们提取的是商）。 根据 Lemma 4.2，$\text{Tensor}^2$ 的结果实际上被除以了 $q_{\text{div}}$（即 $2^k$）。

• 这一步把噪声从 $2^{2k}$ 缩小到了： $\frac{2^{2k}}{2^k} = 2^k$

步骤 C：Rescaling 的除法

最后，我们执行 $\text{RS}^2$（重缩放），这会把结果再除以模数 $q_{\ell}$。

• 最终残留的噪声大小是： $\text{Final Error} \approx \frac{2^k}{q_{\ell}}$

步骤 D：约束条件

为了让这个最终误差很小（比如小于 1，或者小于某个常数），分母必须大于分子： $q_{\ell} \ge 2^k$ 两边取对数（Bit-size）： $\log q_{\ell} \ge k$

这就是为什么我在比较时是直接比较比特数（50 vs 50），而不是比较平方。

2. 重新审视 60/40 的例子

现在用这个精确的数学关系，我们再看一遍为什么“均分”最优。

假设目标总缩放因子 $\Delta = q_{\text{div}} \cdot q_{\ell}$，我们需要 $\log \Delta = 100$。

方案 1：均分（50 / 50）

• 低位 $k = 50$。
• 根据约束 $\log q_{\ell} \ge k$，我们需要 $\log q_{\ell} \ge 50$。
• 为了凑齐 100 总量，我们正好取 $\log q_{\ell} = 50$。
• 结果： 完美匹配，模数消耗 50 bits。

方案 2：低位大（60 / 40）—— 你的疑问点

• 低位 $k = 60$（这意味着噪声源头 $2^{2k}$ 是 120 bits，被抵消一次后剩 60 bits）。
• 剩下的空间留给模数：$100 - 60 = 40$ bits。即 $\log q_{\ell} = 40$。
• 检查约束： $\text{Error} \approx \frac{2^60}{2^40} = 2^{20}$ 误差是 $2^{20}$（约 100 万）！ 这对于小数运算来说是巨大的精度灾难。
• 结论： 这个配置虽然凑够了 100 bits 总量，但因为模数压不住噪声，方案不可用。

方案 3：低位小（40 / 60）

• 低位 $k = 40$。
• 为了凑 100 总量，模数 $\log q_{\ell} = 60$。
• 检查约束： $60 \ge 40$。满足！而且 $2^{40}/2^{60} = 2^{-20}$，精度非常高。
• 代价： 虽然精度很高，但你消耗了 60 bits 的模数。
• 结论： 方案可用，但比 50 bits 方案更贵（模数消耗更大）。

总结

我在之前的回答中说“至少要比低位部分的平方稍大一点”，这是口语表达上的失误，容易产生歧义。更准确的说法是：

“模数 $q_{\ell}$ 必须足够大，以抵消掉‘低位平方项’在经过算法内部除法后残留的影响。”

而这个“残留的影响”，在比特数上，正好就等于低位的比特数。

所以：

• 低位 50 bits $\rightarrow$ 模数至少要 50 bits。
• 这就是 50/50 分割成为最优解的数学原因（Sum 为定值，求 Max(Item) 的最小值）。

Q9: Tensor² 中的除法效应

问题：你提到的”请注意 Mult² 的逻辑是模拟 $(A×B)/2^k$ 的效果（因为我们提取的是商）。根据 Lemma 4.2，Tensor² 的结果实际上被除以了 $q_{\text{div}}$（即 $2^k$）。“这不会对结果产生什么影响吗？

回答：

这是一个非常敏锐的直觉！通常我们在数学上把结果除以 $2^k$，数值不就变了吗？

但在这里，答案是：这不仅不会对结果产生负面影响，反而是为了维持计算正确性所”必须”的步骤。

原因在于 CKKS 的缩放因子（Scaling Factor）机制。

我用最通俗的逻辑给你拆解一下：

9.1 CKKS 的标准流程：必须”除掉”一部分

在 CKKS 中，我们不是直接计算 $1.2 \times 3.4$，而是计算放大后的整数。 假设缩放因子 $\Delta$（比如 $2^{40}$）。

• 数 A 变成了 $A \cdot \Delta$。
• 数 B 变成了 $B \cdot \Delta$。

做乘法时发生了什么？ $(A \cdot \Delta) \times (B \cdot \Delta) = (A \cdot B) \cdot \Delta^2$

注意到了吗？结果的缩放因子变成了 $\Delta^2$（即 $2^{80}$）。 如果不处理，下次再乘就会变成 $\Delta^4$，数值瞬间溢出。 所以，CKKS 算法强制要求：做完乘法后，必须把结果除以 $\Delta$，让它变回 $\Delta$ 的规模。

• 标准 CKKS 的做法： 也就是 Rescaling 步骤，直接除以一个模数 $Q \approx \Delta$。 $\frac{(A \cdot B) \cdot \Delta^2}{Q} \approx (A \cdot B) \cdot \Delta$

2. $\text{Mult}^2$ 的流程：分两步“除”

在 $\text{Mult}^2$ 方案中，作者把这个“必须除掉的 $\Delta$”拆成了两部分来实现。 设定：$\Delta \approx q_{\text{div}} \times q_{\ell}$ （例如：$\Delta = 2^{100}$，拆成 $q_{\text{div}}=2^{50}$ 和 $q_{\ell}=2^{50}$）。

第一步：$\text{Tensor}^2$（隐式除法） 正如你引用的 Lemma 4.2，这一步让结果被除以了 $q_{\text{div}}$。 此时结果的缩放规模从 $\Delta^2$ 变成了： $\frac{\Delta^2}{q_{\text{div}}}$

第二步：$\text{RS}^2$（显式除法） 这是算法最后的重缩放步骤，会再除以模数 $q_{\ell}$。 此时结果的缩放规模变成了： $\frac{\Delta^2}{q_{\text{div}} \cdot q_{\ell}}$

最终效果： 因为我们预先设计好了 $q_{\text{div}} \cdot q_{\ell} \approx \Delta$，所以： $\text{最终规模} \approx \frac{\Delta^2}{\Delta} = \Delta$

3. 为什么 Lemma 4.2 会造成除法效果？

为了让你更放心，我们简单看一下 Lemma 4.2 为什么会产生“除以 $q_{\text{div}}$”的效果。

逻辑如下：

1. 我们的分解是 $ct \approx q_{\text{div}} \cdot \hat{ct}$（忽略低位）。
2. 做乘法时，我们计算的是 $\text{Tensor}^2 \approx \hat{ct}_1 \times \hat{ct}_2$。
   • 这里 $\hat{ct}_1$ 其实是 $\frac{ct_1}{q_{\text{div}}}$。
   • 这里 $\hat{ct}_2$ 其实是 $\frac{ct_2}{q_{\text{div}}}$。
3. 所以乘出来的结果 $\approx \frac{ct_1}{q_{\text{div}}} \times \frac{ct_2}{q_{\text{div}}} = \frac{ct_1 \cdot ct_2}{q_{\text{div}}^2}$。
4. 但是！$\text{Mult}^2$ 的输出格式是“商和余数”。根据重建公式 $Result = q_{\text{div}} \cdot \text{High} + \text{Low}$，这个结果会被乘回一个 $q_{\text{div}}$。
5. 综合算一下： $\left( \frac{ct_1 \cdot ct_2}{q_{\text{div}}^2} \right) \times q_{\text{div}} = \frac{ct_1 \cdot ct_2}{q_{\text{div}}}$

总结

你担心的“结果被除了 $2^k$”是真实发生的，但这不是误差，而是功能。

• 标准 CKKS：一次性除以 $Q$。
• $\text{Mult}^2$：先由 $\text{Tensor}^2$ 隐式除以 $q_{\text{div}}$，再由 $\text{RS}^2$ 显式除以 $q_{\ell}$。

这两者殊途同归，最终都把乘法产生的 $\Delta^2$ 缩放回了 $\Delta$，保证了后续计算可以继续进行。

Q10: RS² 中模数消耗减少的本质

问题：原来如此，是因为 RS² 中需要显示除法步骤中除以的模数变小了，因此才导致模数消耗更少？

回答：

完全正确！你已经抓住了这篇论文最本质的”省钱之道”。

简单来说：我们把原本需要”付费”完成的除法，拆成了一半”付费”和一半”免费”来做。

我来给你算一笔账，你立刻就明白了：

10.1 任务目标：把数字缩小 $\Delta$ 倍

假设为了维持精度，我们需要总的缩放因子 $\Delta = 2^{100}$。 也就是说，做完乘法后，我们需要把数据缩小 $2^{100}$ 倍。

2. 标准 CKKS 的做法（全额付费）

在标准 CKKS 中，缩小数据唯一的方法就是 Rescaling（重缩放）。

• 操作： 物理上把密文除以一个模数 $Q$。
• 代价： 这个 $Q$ 必须等于 $2^{100}$。
• 后果： 你的模数链（Modulus Chain）一下子就被“吃掉”了 100 bits。
• 消费单： 100 bits 模数。

3. $\text{Mult}^2$ 的做法（AA制，但有一半人逃单了）

作者把 $\Delta = 2^{100}$ 拆成了两部分：$q_{\text{div}} = 2^{50}$ 和 $q_{\ell} = 2^{50}$。

• 步骤 1：$\text{Tensor}^2$（“免费”的除法）

  • 如我们刚才讨论的 Lemma 4.2，通过代数结构的重组，这一步在数学上让数据缩小了 $q_{\text{div}} = 2^{50}$ 倍。
  • 关键点： 这一步是靠“把高位系数移位”实现的，并没有消耗掉密文模数链上的任何一个质数。
  • 消费单： 0 bits 模数（这是纯粹的数学变换）。

• 步骤 2：$\text{RS}^2$（“付费”的除法）

  • 这一步是真正的 Rescaling，需要物理除以模数 $q_{\ell}$。
  • 因为只需要再缩小 $2^{50}$ 倍就够了，所以我们只需要消耗一个 $50$ bits 的模数 $q_{\ell}$。
  • 消费单： 50 bits 模数。

4. 最终对比

总结：

正是因为 $\text{RS}^2$ 这一步只需要处理剩余的那一半缩放（$q_{\ell}$），所以它消耗的模数比标准做法小得多。而另一半缩放（$q_{\text{div}}$）被算法的结构设计给”白嫖”了。这就是这篇论文降低模数消耗的秘密武器。

Q11: 为什么不能白嫖 100%？

问题：那为啥不直接白嫖 100%?

回答：

这是一个非常符合经济学原理的提问：既然有免费午餐，为什么不全吃免费的？

答案非常残酷：因为”免费”的那部分（$q_{\text{div}}$），副作用太大，必须用”付费”的那部分（$q_{\ell}$）来治病。

如果想白嫖 100%，你会直接死在噪声爆炸上。

我来给你演示一下，如果你尝试”白嫖 100%“会发生什么灾难。

11.1 贪心实验：试图白嫖 100%

假设目标总缩放因子 $\Delta = 2^{100}$。 你想让“免费的” $q_{\text{div}} = 2^{100}$，让“付费的” $q_{\ell} = 1$（即不消耗模数）。

后果推演：

1. 分解阶段（Decompose）： 你把密文分解为 $ct = 2^{100} \cdot \hat{ct} + \check{ct}$。

   • 因为 $q_{\text{div}} = 2^{100}$，根据定义，你的低位部分（余数） $\check{ct}$ 的大小可以达到 $2^{100}$。
   • 注意： 这个“低位”现在是个庞然大物，它本身就包含了巨大的数值。

2. 乘法阶段（Tensor）： 我们在做乘法时，扔掉了一项 $\check{ct}_1 \times \check{ct}_2$（低位 $\times$ 低位）。

   • 因为 $\check{ct}$ 大小是 $2^{100}$，所以这一项的大小约为 $2^{100} \times 2^{100} = 2^{200}$。
   • 虽然 Lemma 4.2 的机制帮我们除了一次 $q_{\text{div}}$（$2^{100}$），但剩下的噪声依然高达： $\frac{2^{200}}{2^{100}} = 2^{100}$
   • 现状： 你的计算结果里混入了一个大小为 $2^{100}$ 的随机噪声。

3. 重缩放阶段（Rescale）： 这是原本用来消除噪声的步骤。 公式是：除以 $q_{\ell}$。 但因为你太贪心，设了 $q_{\ell} = 1$（为了不消耗模数）。

   • 结果： $2^{100} \div 1 = 2^{100}$。
   • 最终误差： $2^{100}$。

结局： 你的真实数据可能只有几十 bit，但误差高达 100 bit。有效信号完全被噪声淹没了，解密出来全是乱码。

2. 原理解析：为什么必须 50/50？

这里的核心制衡关系是：$q_{\text{div}}$ 制造噪声，而 $q_{\ell}$ 消除噪声。

• 制造噪声： $q_{\text{div}}$ 越大，分解出来的“余数”（低位）就越大，乘法产生的“垃圾项”就越大。垃圾项的大小与 $q_{\text{div}}$ 成正比。
• 消除噪声： $q_{\text{div}}$ 只能负责“隐式”消除一部分，剩下的必须靠物理除法 $q_{\ell}$ 来压下去。

数学上的硬性约束（来自 Theorem 4.8）： 为了让最终误差 $\le 1$（或者可控），必须满足： $\frac{\text{产生的噪声}}{\text{消除的能力}} \approx \frac{q_{\text{div}}}{q_{\ell}} \le 1$ 也就是说： $q_{\ell} \ge q_{\text{div}}$ （翻译：你花的钱，必须盖得住你制造的麻烦。）

寻找最优解：

• 我们要求 $q_{\text{div}} \cdot q_{\ell} = \Delta$（定值，比如 $2^{100}$）。
• 又有约束 $q_{\ell} \ge q_{\text{div}}$。
• 为了让 $q_{\ell}$（花费）最小，我们只能取边界值：$q_{\ell} = q_{\text{div}}$。

这就是为什么 $2^{50}$ vs $2^{50}$ 是极限。

总结：

• $q_{\text{div}}$（免费） 是**“藏污纳垢”**的地方：它越大，藏的噪声（低位）就越大。
• $q_{\ell}$（付费） 是**“清洁工”**：它负责把藏不住的噪声清理掉。
• 如果你让污垢（$q_{\text{div}}$）无限大，却不雇佣清洁工（$q_{\ell}$），房子就炸了。
• 50% 的模数节省，已经是数学上允许的”白嫖”极限了。

第六部分：实验结果与相关工作

Q12: 1.5节和1.6节详解

问题：详细解释说明一下 1.5 节和 1.6 节。

回答：

这两个章节分别负责展示成果（1.5 节）和对比同行（1.6 节）。

简单来说：

• 1.5 节是用数据告诉你：这个方法不仅能算得更深（支持更多层乘法），还能在处理高精度任务时大幅降低硬件压力。
• 1.6 节是学术防御：说明这个方法和以前那些”看起来有点像”的方法有什么本质区别，为什么我们更好。

我为你详细拆解如下：

12.1 第 1.5 节：Concrete examples（具体实例与实验结果）

这一节通过两个具体的应用场景，展示了 $\text{Mult}^2$（即 Double-CKKS）的威力。

场景 A：增加同态容量（Increased homomorphic capacity）

• 目标： 在硬件参数不变（环维数 $N=2^{15}$，安全性 128-bit）的情况下，看谁能跑更深的电路（做更多次连续乘法）。
• 对比：
  • 标准 CKKS： 只能跑 13 层乘法。
  • Double-CKKS： 可以跑 18 层乘法。
• 原理： 因为 Double-CKKS 每一层消耗的模数几乎减半（50 bits vs 100 bits），所以原本的“存款”（总模数预算）可以支撑更多次的“消费”。

场景 B：提高精度与效率（Increased precision）—— 这是最亮眼的部分

• 目标：我们想做 100-bit 高精度的计算（Scaling Factor $\Delta \approx 2^{100}$），且乘法深度为 8。
• 标准 CKKS 的困境：
  • 每次乘法要消耗 100 bits 模数。8 层就要消耗 $800+$ bits。
  • 连锁反应：模数 $Q$ 这么大（>1000 bits），为了保证安全性，环维数 $N$ 必须很大，只能选 $N=2^{16}$。
  • 后果：计算慢，密文极其巨大。
• Double-CKKS 的破局：
  • 我们把 100 bits 拆成 $50+50$。每次只消耗 50 bits 模数。
  • 总模数需求大幅降低（只需 $\approx 680$ bits）。
  • 连锁反应：因为模数小了，安全性更容易满足，我们就可以用更小的环维数 $N=2^{15}$（减半了！）。
• 降维打击的数据对比（Table 3）：
  • 计算速度（Latency）：从 270ms 降到 179ms（快了约 1.5 倍）。
  • 密文大小（Ciphertext Size）：从 14.8MB 降到 5.08MB（只有原来的 1/3）。
  • 密钥大小（Switching Key）：从 74MB 降到 30.6MB（大幅节省内存）。

总结 1.5：这个技术不仅仅是”省模数”，它通过省模数允许我们使用更小的 $N$，从而实现了速度、存储、通信的全方位优化。

12.2 第 1.6 节：Related works（相关工作对比）

这里作者主要对比了两个容易混淆或相关的技术路线。

1. Gadget Decomposition（小工具分解）

这是以前在 GSW 方案或 CKKS 的 Key Switching 中常用的技术。

• 原理： 把一个大数拆成几个小数（比如按位拆），为了减少 Key Switching 过程中的噪声增长。
• 缺点： 它会显著增加密钥的大小（Key Size），通常会增加 $dnum$ 倍（比如几倍到几十倍）。而且它会拖慢 Key Switching 的速度。
• 本文的区别： 本文的分解是针对乘法（Multiplication）的，而不是 Key Switching。而且，如 1.5 节所示，本文的方法实际上减小了密钥大小（因为 $N$ 变小了），而不是增加。

2. Module-CKKS / Module-LWE（基于模的 CKKS）

这是一个强有力的竞争对手。Module-CKKS 也是通过把密文变成向量（比如 3 个元素 $(c_0, c_1, c_2)$）来尝试降低维度。

• 对比 Rank-2 Module-CKKS vs. Double-CKKS：
  • 结构： Module-CKKS 用 3 个元素，Double-CKKS 用 4 个元素（一对密文，每对 2 个）。看起来 Module-CKKS 更紧凑？
  • 模数： 但是！ Module-CKKS 依然消耗全额模数（比如 100 bits）。而 Double-CKKS 消耗半额模数（50 bits）。
  • 总比特量： 综合算下来（元素个数 $\times$ 模数大小），Double-CKKS 的总比特量比 Rank-2 Module-CKKS 小 33%。
  • 计算量： Double-CKKS 只需要 2 次 Relin，而 Module-CKKS 需要 3 次。
• 结论： 当需要高精度（$t \ge 2$）时，Double-CKKS 在空间和时间上都优于 Module-CKKS。

总结 1.6：

作者在说：“别误会，我们不是以前那种会让密钥变大的 Gadget 分解，也不是那种虽然维数小但模数依然很大的 Module-CKKS。我们是真·减半模数，综合性能最优。“

第七部分：CKKS 底层原理深入

Q13: 2.1节中的多个技术细节

问题：

1. “The modulus Q is typically a product of RNS integers and, for the sake of efficiency, arithmetic modulo Q is performed in the RNS form whenever possible.” 似乎揭示了有些步骤是不能使用 RNS 表示的？
2. 为什么规范嵌入中要选 $5^i$？是为了方便进行旋转操作？如果是这样的话，其背后的数学原理是什么？为什么非得是 5？
3. 脚注中：“To minimize the numerical errors, it is useful to consider a different scaling factor for each multiplication level of the circuit to be homomorphically evaluated; for the sake of simplicity, we do not consider this optimization” 这是什么意思？实际代码实现中有考虑吗？
4. 解密中，在不同的层级解密结果的精度是不一样的？层级越深，精度越低？
5. 关于：“We assume that h is set so that the condition holds every time we use RS in this work.” 在 rescale 中，汉明权重 h 不是显然小于 $Q_\ell / q$ 吗？为啥要强调一下？
6. 这段话是啥意思？freshly generated ciphertexts、BDec bound 是啥，干啥用的？

回答：

这几个问题依然非常硬核，涉及到同态加密底层数学原理和论文的严谨性表述。我逐条为你解析：

13.1 关于 “arithmetic modulo Q is performed in the RNS form whenever possible”

是的，这意味着某些步骤不能（或很难）直接在 RNS 下进行。

• RNS 的强项： 加法、乘法。因为 $x+y \pmod M$ 和 $x \cdot y \pmod M$ 在 RNS 系统中就是对每个小质数 $q_i$ 分别做加法和乘法，完全并行，效率极高。
• RNS 的弱项： 除法、取整、模数切换（Modulus Switching）、比较大小、位分解。
  • 在 RNS 表示下（比如 $x$ 表示为 $(x \pmod 3, x \pmod 5)$），你很难直接知道 $x$ 到底有多大，也很难直接计算 $x/2$ 或者 $x \pmod {2^k}$。
• CKKS 的痛点：
  • Rescaling（重缩放）： 本质是 $c \mapsto \lfloor c/q \rfloor$。这是除法和取整。
  • 本论文的 Decompose： 需要计算 $c = 2^k \cdot \hat{c} + \check{c}$。这涉及到“除以 $2^k$”和“取余”。
• 怎么办？ 在这些步骤中，通常需要使用复杂的 RNS 扩展算法（如 Bajard-Eynard-Hasan-Zucca 算法或 HPS 算法），在不完全恢复大整数的情况下近似计算除法；或者在极少数情况下，不得不通过 CRT（中国剩余定理）暂时把数据恢复成大整数（或多项式形式），处理完后再转回 RNS。
• 论文语境： 这句话是在给自己留余地。虽然大部分时间都在 RNS 里跑，但到了 Rescaling 或 Decompose 这种非线性操作时，必须使用特殊的算法来处理，不能简单地 component-wise 进行。

2. 为什么规范嵌入（Canonical Embedding）中要选 $5^j$？为什么是 5？

是为了旋转（Rotation/Galois Automorphism），背后的数学原理是分圆域的伽罗瓦群结构。

• 背景： 我们工作的环是 $\mathcal{R} = \mathbb{Z}[X]/(X^N+1)$，其中 $N$ 是 2 的幂（比如 $2^{15}$）。
• 伽罗瓦群： 这个多项式对应的分圆域的伽罗瓦群同构于模 $2N$ 的乘法群 $(\mathbb{Z}/2N\mathbb{Z})^\times$。
• 生成元： 对于 $N$ 为 2 的幂的情况，这个群的结构是 $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/(N/2)\mathbb{Z})$。它有两个生成元：
  1. -1：对应复共轭（Complex Conjugation）。
  2. 5：对应槽（Slot）的循环置换。
• 为什么是 5？
  • 数学上，对于 $N \ge 8$，$5$ 在模 $2N$ 下的阶（Order）是 $N/4$。
  • 这意味着 $5^0, 5^1, 5^2, \dots$ 可以遍历大部分的指数，从而实现对密文槽（Slots）的遍历和置换。
  • 如果我们选 3，它在模 $2N$ 下的行为可能无法生成原本的子群，或者阶数不对。
  • 结论： 选 5 是因为在 $2N$ 为 2 的幂次时，5 是乘法群中指数为 1 的那个子群的标准生成元。它能保证把加密在向量里的数据“转”到任何你想要的位置。