CKKS的Bootstrapping

前情提要

假设一个明文多项式为（已乘缩放因子），密文，则解密步骤为：

其中为噪声多项式，，为分层模数链。
同态乘法：假设密文，，同态乘法过程为：

验证密文值：

无法直接解密，需要对重线性化，在此不提。重点是解密后的噪音项，每次乘法后，多次乘法后，当时解密失败。

---

CKKS Regular Bootstrapping

---

Step 1: ModRaise（模数提升）

将密文从 提升到 （， 是辅助模数）：

此时：

作用：为 CoeffsToSlots 和 SlotsToCoeffs 提升乘法深度、ModDown 泰勒近似需要大模数空间

---

Step 2: Coefficients-to-Slots (CoeffsToSlots)

对于多项式 ，系数值和槽位值（明文向量值）的关系为（快速傅里叶变换FFT）：

其中为 Vandermonde 矩阵：

分段优化（CtoS_piece = 3）：将 分解为 3 个稀疏矩阵乘法，每个需要 次旋转而非 ：

过程：

---

Step 3: ModDown（模约化近似）

ModDown对每个槽位同态近似执行 （用泰勒/切比雪夫逼近），把值折回到低模数范围，相对 scale 的误差显著缩小，是“降噪”的核心数学步骤。由于，互素，令，则，，且，故有：

重点是需要同态计算 ，但 是非多项式函数，无法直接同态计算。模运算可以表示为：

可以直接用拟合，之后泰勒展开：

---

Step 4: Slots-to-Coefficients (SlotsToCoeffs)

实际上这是CoeffsToSlots的逆变换，过程：

将槽位域密文转回系数域：

其中：

复杂度与 CoeffsToSlots 对称，约 2 层深度。输出为密文 在模数 下加密 ，噪声 （由泰勒精度决定）。

---

完整流程总结

总深度消耗： 层（理论），实际我实验的输出显示消耗 层（优化后）。