前言

借鉴致远的文章学习同态加密，本文主要记录同态加密中近似计算思想，参考文献为 Jung Hee Cheon，Andrey Kim，Miran Kim 和 Yongsoo Song 的《Homomorphic Encryption for Arithmetic of Approximate Numbers》。传统的同态加密方案依赖于解密时的模运算来消除噪声。CKKS方案则截然不同：作者将噪声当作近似计算中固有的、可接受的误差。其核心思路是，只要噪声幅度远小于明文，便不会破坏有效数字的精度。为实现这一点，方案在加密前引入缩放因子以抬升明文，从而压制噪声的相对大小；随后，在密文运算中通过重缩放技术持续截断累积的低位噪声；最终，在解密后移除缩放因子，即可得到高精度的近似结果。

---

---

一、核心思想

下面从参数设置和噪声累积两个角度分析现有方法的局限性。

1. 现有方法

1.1. 参数设置方面的局限性

学术界在处理加密数据上的实数或浮点数运算时，主要采用三类方法：

类别	细节	缺陷
比特编码	将有理数放大为整数后转为二进制，每个比特单独加密。	同态乘法会使比特长度增加，为恢复原始精度需执行右移操作以丢弃低位比特。然而，由于每个密文仅承载 1 比特信息，哪怕只是对单个数值执行一次舍入，都要对多个密文进行复杂交互，计算成本极高。
大整数缩放	将定点数乘上一个缩放因子得到大整数，再将其作为多项式系数或直接作为明文，在明文模数较大的环上加密。	由于同态乘法会进一步放大缩放因子，必须同态地执行右移，通常依赖复杂的比特提取电路。此外，为保证计算正确性，明文模数 $t$ 的比特长度必须随电路深度指数级增长，导致性能大幅下降。
大基表示	将定点数按基向量展开，各维度数字作为多项式系数。	此方法比比特编码更高效，但若要确保定点运算的精确性并避免进位错误，所需的明文模数 $t$ 仍需随电路深度呈指数级增长，从而限制了整体效率。

局限性：从上面的介绍可以看出，现有方法为追求精确计算，导致计算复杂度或参数尺寸变得无法接受。

1.2. 噪声累积方面的局限性

现有的同态方案可以分为两类：

类别	BGV - type	FV - type
核心思想	将明文放在最低有效位，并通过模运算消除噪声。	通过缩放因子（$q/t$）将明文提升到最高有效位，再通过缩放取整消除噪声 。
方法示意
密文与密钥的关系	$⟨c_i,sk⟩=m_i+t{e}_i+I_{i}q$	$⟨c_i,sk⟩=(q/t)\cdot m_i+e_i+I_{i}q$
解密算法	$[[⟨c_i,sk⟩{]}_q{]}_t$	$\lceil (t/q)\cdot [⟨c_i,sk⟩{]}_q\rfloor$
解密成功的情况	当 $|e_i|\ll q$ 时，$m_i+t{e}_i<q$ ，则 $[m_i+t{e}_i{]}_q=m_i+t{e}_i$，解密算法有 $$\begin{array}{rl}[[⟨c_i,sk⟩{]}_q{]}_t& =[[m_i+t{e}_i+I_{i}q{]}_q{]}_t\\ & =[m_i+t{e}_i{]}_t\\ & =m_i\end{array}$$	当 $|e_i|\ll q$ 时，$(q/t)\cdot m_i+e_i<q$ ，则 $[(q/t)\cdot m_i+e_i{]}_q=(q/t)\cdot m_i+e_i$，解密算法有 $$\begin{array}{rl}\lceil (t/q)\cdot [⟨c_i,sk⟩{]}_q\rfloor & =\lceil (t/q)\cdot [(q/t)\cdot m_i+e_i+I_{i}q{]}_q\rfloor \\ & =\lceil m_i+(t/q)\cdot e_i\rfloor \\ & =m_i\end{array}$$
解密失败的情况	当 $|e_i|\approx q$ 时，$m_i+t{e}_i>q$ ，则 $[m_i+t{e}_i{]}_q=m_i+t{e}_i-kq$，解密算法有 $$\begin{array}{rl}[[⟨c_i,sk⟩{]}_q{]}_t& =[[m_i+t{e}_i+I_{i}q{]}_q{]}_t\\ & =[m_i-kq+t{e}_i{]}_t\\ & =m_i-kq\end{array}$$	当 $|e_i|\approx q$ 时，$(q/t)\cdot m_i+e_i>q$ ，则 $[(q/t)\cdot m_i+e_i{]}_q=(q/t)\cdot m_i+e_i-kq$，解密算法有 $$\begin{array}{rl}\lceil (t/q)\cdot [⟨c_i,sk⟩{]}_q\rfloor & =\lceil (t/q)\cdot [(q/t)\cdot m_i+e_i+I_{i}q{]}_q\rfloor \\ & =\lceil m_i-kt+(t/q)\cdot e_i\rfloor \\ & =m_i-kt\end{array}$$

局限性：从上述介绍可以看出，无论哪种方案，成功解密的前提都是$B\ll q$ 。然而，在同态乘法过程中，现有方案的噪声项均以指数速度累积并逐渐逼近模数 $q$ ，导致噪声项远大于明文值，在密文中主导最高有效位，从而解密失败。

2. 动机

现实世界中的数据往往伴随各种误差，例如测量过程中的观测误差、统计分析中的采样误差，以及计算机因有限精度表示而产生的舍入误差。因此，在实际计算中通常只保留原始数据的高位，并在此基础上进行近似运算。完成计算后，为了保持有效数字的位宽，会再次进行舍入，以去除不可靠的低位数据。类似的，CKKS方案将噪声视作近似计算中的固有误差，通过舍入操作消除最低有效位所包含的噪声，从而模拟浮点数的近似运算。

3. 思想

只要噪声 $e$ 足够小，解密结果 $m^{\prime }=m+e$ 就可以看作原始明文 $m$ 的一个高精度近似值，通过计算噪声上界可以评估近似精度。在同态计算过程中，要求 $m+e$ 的绝对值始终小于模数 $q$，不然解密时的模 $q$ 运算会约减 $m+e$ 的值。同时，为了防止密文维度随乘法深度增长，将同态计算的中间值除以一个预定义的基数，通过丢弃部分低位消息来降低噪声并控制明文比特规模。利用这一思想，CKKS 成功地将密文模数 $q$ 的大小从关于电路深度的指数级降为线性级别，同时在精度方面与明文的浮点数计算最多只有 1 比特差距。

---

二、核心方案

CKKS相当于一个插件，对现有算法进行两部分改装。

1. 编码与解码

1.1. 核心思想

相关基础知识见：分圆多项式

• Step1：选择明文空间
  为了将多个明文数值（一个向量）加密到单个密文中，现有方法选择有限特征环 $R_t={\mathbb{Z}}_t[X]/({\Phi }_M(X))$ 作为明文空间。根据中国剩余定理，环 $R_t$ 同构于多个有限域的乘积，因此环上的每个元素都包含 $M$ 个独立的槽位，对该元素的同态操作等同于对多个槽位进行并行计算。相比之下，本文使用特征为 0 的环 $R=\mathbb{Z}[X]/({\Phi }_M(X))$，利用等距环同构进行密文的并行同态运算。其中，${\Phi }_M(X)$ 是第 $M$ 个分圆多项式，阶数为 $N=\varphi ({\Phi }_M(x))$，则分圆多项式 ${\Phi }_M(X)$ 有 $N$ 个本原单位根 ${\zeta }_M^1,\cdots ,{\zeta }_M^N$，并且存在共轭关系：
  $${\zeta }_M^j=\overline{{\zeta }_M^{M-j}}$$

环的特征：使得乘法单位元相加得 0 的最小乘法次数，若不存在则环的特征为 0。例如，分圆多项式环的特征为0，而模 $t$ 下的分圆多项式环的特征为 $t$。

• Step2：将明文解码为消息
  通过如下流程可以将整数多项式环上的明文解码为复数向量空间上的原始消息：
  
  现有一个明文 $m(x)={\sum }_{j=0}^{N-1}{m}_j\cdot x^j\in R$ ，在系数表示法下是一个 $N$ 维向量 $[m_0,\cdots ,m_{N-1}]$ ，对其进行典范嵌入 $\sigma :R\to \mathbb{H}$ 有
  $$\sigma (m(x))=[m({\zeta }_M^1),\cdots ,m({\zeta }_M^{N-1})]$$ 映射后的结果 $\sigma (m(x))$ 可以看作将本原单位根 ${\zeta }_M$ 输入 $m(x)$ 得到的点值表示，是空间 H = { z = ( z j ) j ∈ Z M ∗ ∣ z j = z − j ‾ } ⊆ C N \mathbb{H}=\{z=(z_j)_{j\in \Z^*_M}|z_j=\overline{z_{-j}} \} \subseteq \mathbb{C}^{N} H={z=(zj​)j∈ZM∗​​∣zj​=z−j​​}⊆CN 下的一个 $N$ 维复数向量。根据共轭复数的运算法则，我们知道
  $$m({\zeta }_M^j)=m\left(\overline{{\zeta }_M^{M-j}}\right)=\overline{m({\zeta }_M^{M-j})}$$ 因此，复数向量 $\sigma (m(x))$ 中有一半的元素可以通过共轭运算得到，我们可以进一步利用映射 $\pi :\mathbb{H}\to {\mathbb{C}}^{N/2}$ 将其长度压缩为 $N/2$ ，即
  $$z=\pi (\sigma (m(x)))$$

• Step3：将消息编码为明文
  编码过程与解码过程互逆：
  
  对复数向量 $z$ 进行逆映射 ${\pi }^{-1}$ 时，可能产生无限精度的小数值，但我们希望将其映射回整数多项式环上，因此需要取整操作。最简单的取整方法就是将每个复数的实部和虚部都四舍五入到最近的整数，即将复数舍入到最近的高斯整数。因此，选择高斯整数环 $\mathbb{Z}[i]$ 作为典范映射的空间。此外，为了减小取整操作带来的截断误差，引入缩放因子 $\Delta \ge 1$，将部分小数值扩大为整数，以保留对应的精度。对应的，在解码阶段需要除去 $\Delta$ 。

高斯整数：形如 $a+bi$ 的复数，其中 $a,b\in \mathbb{Z}$ 。

1.2. 核心设计

算法	细节
编码算法	令 $\Delta$ 为缩放因子，则通过以下步骤将 $N/2$ 维的复数向量 $z=[z_i{]}_{i\in T}$ 编码为明文 $m(x)$ ： $$m(x)={\sigma }^{-1}(\lfloor \Delta \cdot {\pi }^{-1}(z){\rceil }_{\sigma (R)})\in R$$
解码算法	令 $\Delta$ 为缩放因子，则通过以下步骤将明文 $m(x)$ 解码为 $N/2$ 维的复数向量 $z=[z_i{]}_{i\in T}$ ： $$z=\pi (\sigma ({\Delta }^{-1}\cdot m(x)))$$ 其中，对于 $z$ 的第 $j\in T$ 维是 $z_j={\Delta }^{-1}\cdot m({\zeta }_M^j)$ 。

2. 重缩放

2.1. 核心思想

在没有舍入的情况下，两个 $k$ 比特的数相乘，结果会变为 $2k$ 比特，例如二进制乘法 $11\times 11=1001$ 。经过 $L$ 次乘法后，运算结果有 $2^L\cdot k$ 比特。为了容纳这种指数级别的噪声增长，明文模数也要设置为指数级别位数。针对这一问题，文章提出了重缩放算法，通过对密文除以一个预定义基数，实现明文和噪声幅度的缩减，在控制明文比特位数的同时舍去了小噪声。

2.2. 核心设计

算法	细节
重缩放算法	为了将第 $l$ 层的密文 $c\in R_{q_l}^k$ 缩减到第 $l^{\prime }<l$ 层，进行如下操作 $$c^{\prime }=\lfloor \frac{q_{l^{\prime }}}{q_l}\cdot c\rceil \in R_{q_{l^{\prime }}}^k$$

假设重缩放操作引入的阶段误差为 $\tau =\frac{q_{l^{\prime }}}{q_l}\cdot c-c^{\prime }$ ，则重缩放后密文有：
$$\begin{array}{rl}⟨c^{\prime },sk⟩& =⟨\frac{q_{l^{\prime }}}{q_l}\cdot c-\tau ,sk⟩\\ & =\frac{q_{l^{\prime }}}{q_l}\cdot ⟨c,sk⟩-⟨\tau ,sk⟩\\ & =\frac{q_{l^{\prime }}}{q_l}\cdot (m+e)-⟨\tau ,sk⟩\\ & =\frac{q_{l^{\prime }}}{q_l}\cdot m+(\frac{q_{l^{\prime }}}{q_l}\cdot e-⟨\tau ,sk⟩)\end{array}$$ 可以看出，重缩放同时减小了明文与噪声的幅度。

2.3. 算法对比

重缩放算法与模切换算法很像，下面对比这两个操作：

算法	重缩放	模切换
图示
算法前的密文	$$⟨c,sk⟩=m+e\mathrm{mod}{q}_l$$	$$⟨c,sk⟩=m+e\mathrm{mod}{q}_l$$
算法后的密文	$$⟨c^{\prime },sk⟩=\frac{q_{l^{\prime }}}{q_l}\cdot m+e^{\prime }\mathrm{mod}{q}_{l^{\prime }}$$	$$⟨c,sk⟩=m+e^{\prime }\mathrm{mod}{q}_{l^{\prime }}$$
差距	重缩放后，模数减小，明文幅度减小，并且位于最低有效位的噪声也被舍去	模切换后，模数减小，明文幅度不变，噪声减小

3. 槽置换

相关基础知识见：数域
CKKS 方案将多个明文打包到一个密文进行批处理，但是后续计算可能需要置换明文槽的位置。为此，利用伽罗瓦自同构实现。对于明文槽的置换流程如下：

• Step1：为了将槽位 $i$ 中的明文移至槽位 $j$ ，首先计算 $$k=j^{-1}\cdot i\mathrm{mod}M$$
• Step2：使用伽罗瓦同构对明文 $m(x)$ 进行映射 $\varphi$ ，如下 $$m^{\prime }(x)=\varphi (m(x))=m(x^k)=[({\zeta }_M^1{)}^k,\cdots ,({\zeta }_M^N{)}^k]=[{\zeta }_M^k,\cdots ,{\zeta }_M^{N\cdot k}]$$

同理，可以对密文槽进行置换，则置换后的密文 $\varphi (c)$ 对应的明文是 $\varphi (m)$ ，私钥是 $\varphi (sk)$ 。这里需要注意的是，置换后密文私钥发生改变，但是整个同态计算都需要在统一的私钥 $sk$ 下计算。因此，需要提前生成切换密钥，用于将 $\varphi (sk)$ 切换为 $sk$ 。

---

二、方案实现

CKKS算法可以用于改进现有的基于环 $R$ 的算法，下面以 BGV 方案为例，讲解其 CKKS 版本。

1. 方案描述

相关基础知识见：离散高斯分布

算法	细节
参数设置	安全参数： $\lambda$ 缩放因子： $p>0$ 模数： $q_0$ 模数链： $q_{l\in (0,L]}=p^l\cdot q_0$ ，从第 $L$ 层开始使用 分圆多项式次数： $M=M(\lambda ,q_L)$ 噪声方差： ${\sigma }^2$ 整数： $P=P(\lambda ,q_L)$ 和 $h=h(\lambda ,q_L)$
密钥生成	私钥：首先从 { − 1 , 0 , 1 } N \{-1,0,1\}^N {−1,0,1}N 中采样 $N$ 维多项式 $s$ ，则私钥为 $$sk=(1,s)$$ 在采样 $s$ 时要保证恰好有 $h$ 个非零系数，这样私钥较为稀疏且范数较小，有利于控制噪声增长，并且稀疏张量的运算更快。 公钥：随机采样多项式 $a\in R_{q_L}$ 和噪声多项式 $e$ ，其中噪声多项式的每一项独立取自方差为 ${\sigma }^2$ 的离散高斯分布，则 公钥 $pk=(a,b)$ 满足 $$b=-as+e\mathrm{mod}{q}_L$$ 评估密钥：随机采样多项式 $a^{\prime }\in R_{P\cdot q_L}$ 和噪声多项式 $e^{\prime }$ ，其中噪声多项式的每一项独立取自方差为 ${\sigma }^2$ 的离散高斯分布，则 评估密钥 $evk=(a^{\prime },b^{\prime })$ 满足 $$b=-a^{\prime }s+e^{\prime }+P{s}^2\mathrm{mod}(P\cdot q_L)$$
编码算法	令 $\Delta$ 为缩放因子，将高斯整数环 $\mathbb{Z}[i{]}^{N/2}$ 中的一个 $N/2$ 维复数向量 $z=[z_i{]}_{i\in T}$ 编码为明文 $m(x)$ ： $$m(x)={\sigma }^{-1}(\lfloor \Delta \cdot {\pi }^{-1}(z){\rceil }_{\sigma (R)})$$ 注意，加密前先编码。
解码算法	令 $\Delta$ 为缩放因子，将明文 $m(x)\in R$ 解码为高斯整数环 $\mathbb{Z}[i{]}^{N/2}$ 中的复数向量 $z=[z_i{]}_{i\in T}$ ： $$z=\pi (\sigma ({\Delta }^{-1}\cdot m(x)))$$ 其中，对于 $z$ 的第 $j\in T$ 维是 $z_j={\Delta }^{-1}\cdot m({\zeta }_M^j)$ 。注意，解密后要解码。
加密算法	随机采样随机多项式 $v$ ，和噪声向量 $e_0,e_1$ ，则明文 $m$ 被加密为：$$c=v\cdot pk+(m+e_0,e_1)\mathrm{mod}{q}_L$$ 其中，噪声多项式的每一项独立取自方差为 ${\sigma }^2$ 的离散高斯分布。同时，为确保 IND-CPA 安全性，即同一个明文加密两次会产生两个看起来不相关的密文，在采样随机多项式 $v$ 时引入随机性，以概率 $\rho /2$ 取 +1，以概率 $\rho /2$ 取 -1，以概率 $1-\rho$ 取 0，此时 $v$ 的汉明重量是一个围绕 $\rho N$ 的随机变量。本文设置 $\rho =0.5$ 。
解密算法	对于第 $l$ 层密文 $c=(a,b)$ 有 $$m=a\cdot s+b\mathrm{mod}{q}_l$$
同态加法	对于密文 $c_1,c_2\in R_{q_l}^2$ 有 $$c_{add}=c_1+c_2\mathrm{mod}{q}_l$$ 特别的，如果两个密文不在同一层，需要先用换模算法将高层密文降到低层。
同态乘法	对于密文 $c_1=(a_1,b_1),c_2=(a_2,b_2)\in R_{q_l}^2$ ，计算 $(d_0,d_1,d_2)=(b_1{b}_2,a_1{b}_2+a_2{b}_1,a_1{a}_2)(\mathrm{mod}{q}_l)$ ，则 $$c_{mult}=(d_0+d_1)+\lfloor P^{-1}\cdot d_2\cdot evk\rceil \mathrm{mod}{q}_l$$
重缩放算法	对于第 $l$ 层密文 $c\in R_{q_l}^2$ 有 $$c^{\prime }=\lfloor \frac{q_{l^{\prime }}}{q_l}\cdot c\rceil \mathrm{mod}{q}_{l^{\prime }}$$

2. 噪声分析

2.1. 绝对误差

• 编码与加密：刚加密完的密文噪声上界为 $B_{clean}=8\sqrt{2}\sigma N+6\sigma \sqrt{N}+16\sigma \sqrt{hN}$，当缩放因子为 $\Delta >N+2B_{clean}$ 时可成功解密。
• 重缩放： $B_{scale}=\sqrt{N/3}\cdot (3+8\sqrt{h})$ 。
• 同态乘法：$B_{mult}=P^{-1}\cdot q_l\cdot 8\sigma N/\sqrt{3}+B_{scale}$

2.2. 相对误差

此外，我们还要分析相对误差：

• 相对误差：噪声幅度上界 $B$ 和明文幅度上界 $v$ 的比值 $\beta =B/v$。相对误差越小，信噪比越大，有效位越多。相反，相对误差每增加一倍 $\beta \to 2\beta$，损失 1 比特精度。
• 同态加法的相对误差：相对误差分别为 ${\beta }_1,{\beta }_2$ 的两个密文相加，其结果的相对误差为
  β a d d = B 1 + B 2 v 1 + v 2 ≤ max ⁡ { β 1 , β 2 } \beta_{add}=\frac{B_1+B_2}{v_1+v_2}\leq \max\{\beta_1,\beta_2\} βadd​=v1​+v2​B1​+B2​​≤max{β1​,β2​}
• 同态乘法的相对误差：相对误差分别为 ${\beta }_1,{\beta }_2$ 的两个密文相乘，其结果的相对误差为
  $${\beta }_{mult}={\beta }_1+{\beta }_2+{\beta }_1{\beta }_2+\frac{B_{mult}+p^{l-l^{\prime }}\cdot B_{scale}}{v_1{v}_2}$$ 其中，如果明文幅度 $v_1,v_2$ 足够大，最后一项趋近于 0 。

---

三、方案应用

下面讲解使用 CKKS 实现常见电路的同态计算。
😀懒得打字了，就只记录个大概

1. 线性函数

函数	密态计算	密文变化	层数变化	明文幅度变化	噪声幅度变化
$f(x)=x+a$	$c_a=c+(a,0)\mathrm{mod}{q}_l$	$c\to c_a$	$l\to l$	$v\to v+\Vert a{\Vert }_{\infty }^{can}$	$B\to B$
$f(x)=a\cdot x$	$c_m=a\cdot c\mathrm{mod}{q}_l$	$c\to c_m$	$l\to l$	$v\to \Vert a{\Vert }_{\infty }^{can}\cdot v$	$B\to \Vert a{\Vert }_{\infty }^{can}\cdot B$
$f(x)=x^d$	见算法1，解密计算得到的密文有 $m^d/p^{d-1}$	$c\to c^{\prime }$	$l\to l-\lceil \log d\rceil$	$p\to p$	$B\to {\beta }_d\cdot p$，其中 ${\beta }_d\le d\cdot {\beta }_0+(d-1)\cdot {\beta }_{\ast }$
$f(x)={\sum }_{i=0}^d{a}_i{x}^i$	结合前三个函数	$c\to c^{\prime }$	$l\to l-\lceil \log d\rceil$	$p\to M_f$，其中 $M_f=p\cdot {\sum }_{i=0}^d\Vert a_i{\Vert }_{\infty }^{can}$	${\beta }_0\cdot p\to {\beta }_d\cdot M_f$，其中 ${\beta }_d\le d\cdot {\beta }_0+(d-1)\cdot {\beta }_{\ast }$

算法1如下，其中 RS 表示重缩放算法，Mult表示同态乘法：

2. 非线性函数

非线性函数可以用泰勒级数近似为 $$f(x)=T_d(x)+R_d(x)$$ 其中 $T_d(x)$ 为 $d$ 阶泰勒多项式，如下：
$$T_d(x)=\sum _{i=0}^d\frac{f^{(j)}(0)}{j!}\cdot x^j$$ 而 $R_d(x)=f(x)-T_d(x)$ 为截断误差，或者说是余项。变换后，泰勒多项式 $T_d(x)$ 可通过上面线性函数介绍的方法进行计算，并且为了保证计算结果的精度，需要乘以一个缩放因子 $p^u$ ，最终得到的密文解密后为 $p^{u+1}\cdot f(m/d)$ ，误差来自三方面：同态计算累积的评估误差、编码和重缩放引入的舍入误差、泰勒级数近似引入的截断误差。下面介绍两个常用的非线性函数的同态计算：

函数	密态计算	密文变化	层数变化	明文幅度变化	噪声幅度变化
$f(x)=e^x$	根据线性函数的方法进行计算 $$T_d(x)=\sum _{j=0}^d\frac{1}{j!}\cdot x^j$$解密计算得到的密文有 $p^{u+1}\cdot t_d(m/p)$	$c\to c^{\prime }$	$l\to l-\lceil \log d\rceil$	$p\to p^{u+1}$	${\beta }_0\cdot p\to B^{\prime }$，其中 $$B^{\prime }=dp+p^{u+1}\cdot (e{\beta }_0+{\beta }_{\ast }+\frac{e}{(d+1)!})$$
$f(x)=x^{-1}$	见算法2，解密计算得到的密文有 $$p\cdot \prod _{i=0}^{r-1}(1+(\frac{p-m}{p}{)}^{2^i})$$	$c\to v_r$	$l\to l-r$	$p/2\to 2p$	${\beta }_0\cdot p/2\to \beta \cdot 2p$，其中 $\beta \le {\beta }_0+r{\beta }_{\ast }$

算法2如下，其中 $\hat{m}=p-m$：

3. 傅里叶变换

😕彻底不想打字了，以后用到了再填坑吧