格密码与同态加密学习总结

2024-04-09 21:30:41 阅读数 3885

一、格密码学

1.与传统密码学相比的优点

安全性：基于最糟糕情况困难安全性(Worst-case security)的可证明安全。

传统密码算法：基于平均情况困难安全性（Average-case security)的可证明安全。
- 例如，如果通过某整数的分解破解了某RSA实例，不意味着可以破解所有整数的分解问题，只意味着可以分解该RSA实例涉及的那些整数。换言之，并非任何基于整数分解的密码学实例都是安全的，因为只是在平均情况（Average-case)下整数分解是困难的，而非所有整数的分解都是困难的。
- 基于最糟糕困难安全性(Worst-case security)的可证明安全确保了：如果可以破解基于某个格上的困难问题所构建的密码学实例，就可以解决最糟糕情况下的该困难问题，换言之，如果在最糟糕情况下即使以小概率破解了该问题的一个实例，就能破解基于该问题的所有实例。
困难问题：基于格的困难问题。格的困难问题是一个新提出的困难问题，在计算机领域，它只有三四十年的历史，且目前尚不能被量子算法破解，格密码算法是目前后量子领域最受瞩目的算法。
计算：简单计算，效率高。计算开销很小，只需要加法就能实现密码学方案（乘法可以看作加法的累积）。
应用：可以构造传统密码学无法实现的复杂而强力的密码学应用，最具代表性的是全同态加密(fully homomorphic encryption, FHE)，传统密码学无法实现。

2.近年来格密码学的研究主线

SIS（小整数解问题）与LWE（容错学习问题）是近年来格密码学的两个核心问题，利用这两个问题可以构造高效的密码学方案。它们将格的内容抽象化，使得研究者不需要去考虑最糟糕情况困难性的安全性证明，只需要基于SIS与LWE这两个中间问题即可构造出安全的密码学方案。
另一主线是基于特定格代数结构（理想格，ideal lattices）构造高效的密码学方案，产生了Ring-LWE与Ring-SIS问题。基于这种满足特定性质的格代数结构可以在满足安全性的同时，大幅提升所构造方案的效率（密钥长度缩小到KB极，计算效率甚至可以接近哈希函数）。

3.格中困难问题

各问题归约关系如下：（图来自Daniele Micciancio教授）

各困难问题问题概述：

符号说明：

格基底为B，由此生成的格为 $\cal{L}$ 。
n维格 $\cal{L}$ ，定义 $\lambda_i(L),\, 1 \le i \le n$ 是第i最短向量的长度。 $\gamma$ 为长度前的近似因子。
给定格 $\cal{L}$ ，定义任一点t 到最近格点的距离函数为： $\mu(t,L)=\min\limits_{x \in L}\Vert t-x \Vert$ ，格的覆盖半径： $\mu(L) = \max\limits_{t \in span(L)} \mu(t,L)$

各困难问题内容如下：

$SVP$ 问题（Shortest Vector Problem）

搜索问题

给定一组基B，找到非零向量 $\boldsymbol{v}\in\cal{L}$ ，使得 $||\boldsymbol{v}||=\lambda_1(\cal{L})$ 。
判定问题

给定一组基B， $d>0$ ，区分出 $\lambda_1(\cal{L})\leq d$ ，还是 $\lambda_1(\cal{L}) > d$ 。
计算问题

给定一组基B，计算出 $\lambda_1(\cal{L})$ 。

${SVP}_{\gamma}$ 问题

搜索问题，即 ${SVP}_{\gamma}$

给定一组基B，找到非零向量 $\boldsymbol{v}\in\cal{L}$ ，使得 $||\boldsymbol{v}||\leq\gamma\cdot\lambda_1(\cal{L})$ 。
判定问题，即 $GapSVP_{\gamma}$

给定一组基B，和 $d>0$ ，区分出 $\lambda_1(\cal{L})\leq d$ ，还是 $\lambda_1(\cal{L}) >\gamma\cdot d$ 。
估算问题，即 ${EstSVP}_{\gamma}$

给定一组基B ，输出在 $[{\lambda}_1(\cal{L}),\gamma \cdot \lambda_1(\cal{L})]$ 中的 $d$ 。

解决 $SVPγ$ 问题，其中 $\gamma=2^{(n-1)/2}$ ，可以使用LLL算法（一般在低维应用）。

${SIVP}_{\gamma}$ 问题（Shortest Independent Vectors Problem）

给定一组基B, 找到一组线性独立的向量 $\boldsymbol{v_{1},...,v_{n}}\in\cal{L}$ ，使得 $||\boldsymbol{v_{i}}||\leq\gamma\cdot{\lambda}_{i}(\cal{L})。$
困难性： $GapSVP_{\gamma}\leq {SIVP}_{\gamma}$ 。

$CVP$ 问题（Closest Vector Problem）

给定一组基B，点 $t$ ，找到一些格点 $\boldsymbol{v}\in\cal{L}$ ，使得 $||t-\boldsymbol{v}||=\mu(t,\cal{L})$ 。

${CVP}_{\gamma}$ 问题

给定一组基B，点 $t$ ，找到一些格点 $\boldsymbol{v}\in\cal{L}$ ，使得 $||t-\boldsymbol{v}||\leq\gamma\cdot \mu(t,\cal{L})$ 。

$BDD$ 问题（Bounded Distance Decoding）

搜索问题

给定一组基B，点 $t$ ， $d<{\lambda}_{1}/2$ ，使得 $\mu(t,\cal{L})\leq d$ ，找到唯一接近t的 $\boldsymbol{v}\in\cal{L}$ 。换句话来说，给定陪集 $t+\cal{L}\ni e$ ，使得 $||e||\leq d$ ，找到这个 $e$ 。

一种理解方式是对 $\cal{L}$ 中的每个格点，以 $d$ 为半径作球体，使得点 $t$ 和某一格点在一个球体内的格点即要找的 $\boldsymbol{v}\in\cal{L}$ 。或者理解为对 $t+\cal{L}$ 中的每个点，以原点 0 为球心， $d$ 为半径作球体，球体内包含的点即要找的 $e \in t+\cal{L}$ 。
判定问题：

给定一组基B，陪集 $t+\cal{L}$ ，和d，区分出 $\mu(0,t+\cal{L})\leq d$ ，还是 $\mu(0,t+\cal{L}) >\gamma \cdot d$ 。

一种理解方式是以原点 0 为球心，分别以 $d$ 为半径作球体和以 $\gamma \cdot d$ 为半径做球体，判断 $t+\cal{L}$ 的点是否能落在以 $d$ 为半径的球体之内，或判断 $t+\cal{L}$ 的点是否都在以 $\gamma \cdot d$ 为半径的球体之外。

$ADD$ 问题（Absolute Distance Decoding）

令 $d \ge \mu(\mathbf{L})$ ，即 $d$ 已经大于整个格的覆盖半径，此时CVP问题至少会有一个解，但所找到的解并不一定是距离t最近的格点。

注：密码学系统的安全性基于困难问题，但不能基于NP困难问题来构造格密码方案，因为格上的NP困难问题有很多限制条件，因此，格密码学系统基于的困难问题其近似因子 $\gamma$ 量级常在 $n$ 与 $n^2$ 之间

二、SIS问题与LWE问题

问题之间的关系:

各难题关系

1.SIS 问题

SIS: 小整数解问题 , Small Integer Solutions Problem

定义：

给定整数 $m,n,q$ ，随机选取矩阵 $A \in Z^{n \times m}_q$ 和界定参数 $β$ ，求解非零整数向量 $\boldsymbol{z}\in Z^m$ ，使得 $A z=0$ ，且 $||z|| \le \beta$ 。

不限定 $\boldsymbol{z}$ 范围，即为平凡问题（高斯消元即可解决）。
可以构造抗碰撞哈希函数。
与格的关系:
- 非平凡解构成的集合形成了一个格；
- SIS问题等价为“找到该格中的一个短向量”；
- 如果可以解决SIS问题，就可以解决格的最糟糕困难问题，可以从任意格中找到短向量。

2.LWE问题

LWE: 容错学习问题, Learning with Errors Problem

定义：

给定均匀随机生成的矩阵 $A\in Z^{n\times m}_q$ ，向量 $s \in Z^m_q$ 和噪声值 $e\in Z^n_q$ 都服从错误分布 $\mathcal X$ ， $b_i={ A}_i s+e$ 。

搜索版本的 LWE 问题（Search LWE, SLWE）：给定多组 $(A_i,b_i)$ ，找到 $\boldsymbol s$ 。
判定版本的 LWE问题（Decision LWE, DLWE）：将 $b_i$ 和均匀随机生成的向量区分开。

困难性关系：

SLWE在最糟糕情况下的困难度不比解决GapSVP问题简单（该困难性的证明需要量子归约算法，用量子性质将高斯选取的值组合在一起）。
- SLWE困难性并未归约到SIVP，只是归约到GapSVP，但GapSVP也是困难问题，结论仍很有意义。
- 归约算法要求模数q非常大，需要与n成指数关系，而不是多项式关系。
SLWE困难度不比DLWE难，若前者是困难问题，则后者也为困难问题。
基于LWE密码学方案的构造需要DLWE困难。

与SIS问题对比：

密码学角度：
- SIS问题有计算假设，属于搜索性问题（类似整数分解问题），需要找到 $\boldsymbol{z}$ 满足已知等式。难以把SIS转为判定问题，因为必存在 $\boldsymbol{z}=0$ 满足条件，如果通过缩小维度转为判定问题，则SIS和LWE问题等价。
- LWE（一般指DLWE)属于判定性问题（类似二次剩余和DDH（判定Diffie-Hellman)问题）, 需要区分给定值满足一定条件还是完全均匀随机的。
解的角度：
- SIS可以有多个解；
- LWE只存在唯一解，这种唯一性是用来构造公钥密码和加密方案的基础。
归约角度
- LWE可以归约到SIS, 如果可以解决SIS，也可以平凡地解决LWE：
  
  假如拥有 $(A，b)$ 和SIS预言机，首先通过预言机得到满足 $A\boldsymbol{z}=0$ 的 $\boldsymbol{z}$ ，再将 $b$ 与 $\boldsymbol{z}$ 点乘，得到 $b\boldsymbol{z}=(As+e)\boldsymbol{z}=e\boldsymbol{z}$ 。
  - 如果 $b$ 是服从LWE分布的，则 $e$ 为短的错误向量，坐标很小且服从高斯分布，又因为 $\boldsymbol{z}$ 也很小，故 $b\boldsymbol{z}$ 点乘结果非常小。
  - 如果 $b$ 是均匀随机分布的，则 $b\boldsymbol{z}$ 很大，在空间均匀分布。因此我们可以根据 $b\boldsymbol{z}$ 的大小对 $b$ 的分布做出判别，从而解决LWE问题。
- 这意味着LWE问题不比SIS困难。
- 困难性关系SIS<=LWE还有待证明（但从某角度看应该是对的，如果可以使用量子计算机，则可方便地证明SIS和LWE等价）。
应用角度：
- SIS应用于Minicrypt : 单向函数、抗碰撞Hash函数、签名方案、ID方案等，但难以用于公钥加密。
- LWE开创Cryptomania世界：公钥加密（PKE)、不经意传输(OT)、全同态加密（FHE)等。
格的角度：
- 可以将SIS看作格问题，A定义了一个随机格（所有满足Az=0的z组成格点），SIS等价于要在该格中找短非零向量。
- LWE中，A类似格的基，指定了格点，b和某一个随机格点跟接近，e是两者的差。

LWE特性：

易检验性：检验s’是否为解只需计算所有LWE实例的 $b - <s’ , a >$ 是否都很小，如果是则s’=s, 即s’为解。
平移性：可用原向量s平移t后所得的s+t构造LWE有效实例，新实例为： $(a, b’)=(a, b+<t,a>)=(a,<s+t,a>+e)$ 。
随机自归约性：以上两点特性组成LWE的随机自归约性，敌手可以借此放大解决LWE的成功概率，例如利用平移特性重随机化秘密，每次就可以生成一个新的LWE问题实例。
多独立秘密值：可以将k个LWE实例中独立的秘密值 $b_i,...,b_t$ 重新组合为一个新LWE问题，判断它们都是LWE实例还是都是随机值。

三、RLWE问题

定义：

给定均匀随机生成的多项式 $a∈R_q$ ，与服从错误分布 χ的 $s∈R_q$ 和 $e∈R_q$ ，生成 $b_i=a_is+e_i$ 。

搜索版本的 RLWE 问题 (Search RLWE) 为：给定多组 ( $a_i,b_i$ )，找到 s；
判定版本的 RLWE 问题 (Decision RLWE) 为：将 $b_i$ 和均匀随机生成的向量区分开。

Vadim Lyubashevsky等给出了 R 中理想格上的近似 SVP (最坏情况下) 到 R-LWE 的搜索版本的量子归约 (quantum reduction)，其目标是从 (a,b=a⋅s+e) 中恢复秘密 $s∈R_q$ 。

RLWE 与 LWE 问题很类似，只不过在 RLWE 问题中，和 LWE 相比，直观地看所有元素要"小了很多"。因为 RLWE 中，每个部分都是一个多项式，而不是 LWE 问题中的矩阵。这极大地提高了方案的实际效率，也减小了通信开销。

类似的更灵活的问题还有 MLWE (Module Learning with Errors)。

四、全同态加密

1.第一代FHE

2009 年，Gentry基于理想格构造出了第一个全同态加密方案，摘取了“ 密码学圣杯”。Gentry 设计了一个构造全同态加密方案的 “蓝图”：

首先构造一个类同态加密( Somewhat Homomorphic Encryption, SHE)方案(这类方案能够同态计算一定深度的电路);
然后压缩解密电路(需要稀疏子集和假设)，使得它能够同态计算它本身的增强的解密电路，得到一个可以“自举”(Bootstrapping)的同态加密方案;
最后有序执行自举操作(需要循环安全假设)，得到一个可以同态计算任意电路的方案，即全同态加密。
同时，基于理想格上的 ICP 假设，并结合稀疏子集和与循环安全假设，他也开创性地构造了一个具体的方案。

2.第二代FHE：BGV、BFV

随着 Gentry 全同态加密方案的提出，人们开始尝试基于RLWE和NTRU相关问题构造全同态加密方案，并结合理想格的代数结构、快速运算等优良性质来进行方案的优化和实现，最终取得了成功，BGV、BFV等方案随之产生。

第二代FHE特性：

在整数向量上进行高效的SIMD计算（使用批处理）；
快速高精度整数算术；
快速向量的标量乘法；
Leveled design（通常不需使用bootstrapping）。

BFV 将基于LWE问题的 Brakerski 全同态方案移植到 RLWE 中。

BGV是在BV11b方案基础上改进的新的全同态加密方法，它极大地提高了性能，并基于较弱的假设建立了安全性。核心贡献是在不需要使用 Gentry 的 bootstrapping 情况下，建立一种新的方法来构造 Leveled 的全同态加密方案（能够评估任意多项式大小的电路）。该方案采用模数切换来控制噪声, 使得噪声始终维持在较小的水平, 从而可以进行较多次的乘法同态运算。

3.第三代FHE：GSW、FHEW、TFHE

2013 年，Gentry 等人基于LWE和“ 近似特征向量”技术，设计了一个无需计算密钥的全同态加密方案:GSW，标志着第三代全同态加密方案的诞生。他们进而还设计了基于身份和基于属性的全同态加密方案，掀起了全同态加密研究的新高潮。

第三代FHE特性：

能够快速比较；
支持任意布尔电路；
快速Bootstrapping（噪声刷新过程，减少因密文计算而产生的噪音，降低失败可能性）。

与非门是完备的, 可以通过不断地叠加与非门来实现相当复杂的函数运算, 并且仅用与非门可以实现任何一个布尔函数。但是每一次进行与非门运算, 都会导致新密文得噪声变得更大, 因此较多层的运算后, 噪声可能大得导致解密错误。因此必须评估究竟能进行多少次的运算, 以及在快要达到极限的时候使用Bootstrapping技术。

这里以GSW为代表分析，GSW方案根据解密算法的选区不同, 实际上有构造两套方案。

第一种是选择 $\mathsf{Dec}$ 作为解密算法, 该算法仅能解出 $\mu_i\in\{0,1\}$ , 因此整个同态运算中主要用与非门构建逻辑电路进行计算。
另一个解密算法 $\mathsf{MPDec}$ 可以解出 $\mu_i\in\mathbb Z_q$ , 这样就可以自然地使用加法与乘法进行运算。

GSW并不是一个标准假设下的全同态加密方案。 GSW如果要做到全同态加密, 需要用到Bootstrapping, 进而需要用到LWE加密方案的Circular Security假设(即用一对公私钥中的公钥来加密私钥相关信息的加密结果是安全的)。FHEW、TFHE是GSW密码系统的环变体。

4.浮点数FHE：CKKS

CKKS是2017年提出基于RLWE的同态加密方案。它支持浮点向量在密文空间的加减乘运算并保持同态，但是只支持有限次乘法的运算。这里对CKKS方案展开细致说明，具体操作如下：

1.编码

目的：将复数向量映射成为多项式.
初始：对于 $M > 4$ ，我们有 $N = ϕ ( M ) = M / 2$ 并且分圆多项式 $\Phi_M(X) = X^N + 1$ 。
映射：求一个整数系数的插值多项式 $m(X)$ （用牛顿插值、拉格朗日插值、快速傅里叶变换等都可以），使得 $m(\xi) \approx \Delta \times Message'_i$ 。即把 $X^n + 1 = 0$ 的复数根作为自变量丢到 m 里面去，使得输出的值是 $Message'$ 的对应分量。
系数放大：由于共轭性质，插值出来的 m 的系数都是实数。但是，CKKS最后要对整数进行操作，因此需要对多项式系数进行取整。但如果直接对 m 系数取整，误差会比较大。因此在这里引入放大因子 $\Delta$ ，将Message的数值放大，得到 $m = m · \Delta$ 之后再进行取整。这样可以尽可能保留小数的位数，提高加密的精度。
重缩放：引入了放大操作之后，多项式系数变大了很多。如果再做多次乘法，就不可避免地会出现溢出模数的情形。于是需要重缩放来避免这一问题。

CKKS的重缩放可以看作一种分层乘法机制，它引入了一个模数链 $Q = q_0 · p^L$ 。这里的 p是和 $\Delta$ 大小近似的素数， $L$ 称为乘法深度，近似为乘法最多可计算次数。刚加密的密文的模数为 $Q$ ，当密文相乘时， $\Delta$ 就会增加为原来的平方，此时对系数除以 $p$ （也相当于对模数除以 $p$ ）来抵消掉 $\Delta$ 的增加，从而确保密文数据中自始至终仅有一个 $\Delta$ 因子，但由于模数被除变小，乘法深度有一定的降低。
最终得到的m 即对消息编码的结果。

2.解码

与编码过程相反，将m代入 $\xi$ 即可，最后除以 $\Delta$ 。

3.加密

取私钥 $(1, s)$ ，公钥 $(b = -a·s + e, a)$ ，其中 s和 a 为向量，e为随机数（这里基于RLWE问题确保了破解私钥的困难性）
则密文 $(c_0, c_1) = r(b, a) + (m + e_1, e_2) = (rb + m + e_1, ra + e_2)$ ，其中r 为随机整数， $e_1, e_2$ 为随机多项式（也可以理解为向量）。

4.解密

计算 $c_0 + c_1 s$ 即可，其结果约等于m 。过程如下：
$c_0 + c_1s = rb + m + e_1 + ra·s + e_2s = m + e_1 + e_2s + er$

5.运算

加法：明文向量按元素相加，密文向量对应位相加。
明文乘密文：
- 实质： $m \times (c_1+ c_2s) = mc_1 + mc_2s$ ;
- 操作：将明文 $m$ 和密文中的 $c_1, c_2$ 逐个做多项式乘法，得到的 $(c_1m, c_2m)$ 即为新密文。
密文乘密文：实质计算

$(c_{11}+ c_{12}s) \times (c_{21}+ c_{22}s) = c_{11}c_{21} + (c_{21}c_{12}+c_{11}c_{22})s + c_{12}c_{22}s^2$

6.重现性化

原因：乘法会不可避免地导致乘积多项式的次数增加，从而需要更多空间存储，我们希望进行在密文空间中做乘法之后密文向量对应的多项式次数保持不变，即 $(c_0 +c_1s) * (c_2 + c_3s) = (d_0 + d_1s)$ ，没有s的平方项。
设计：
- 启用一个重线性化秘钥 $evk = (b', a') = (-a'·s + e' + bs^2, a')$ 。我们将示例 $c_0c_2 + (c_0c_3 + c_1c_2)s + c_1c_3s^2$ 记为： $d_0 + d_1s + d_2 s^2$ ，其中 $d_0, d_1, d_2$ 都可由密文乘积计算得出。
输出的密文结果为 $(c'_1, c'_2) = (d_0, d_1) + p^{-1}·d_2·evk$ ，其中 $p$ 为重缩放中的模数因子。
理由：

$P^{-1}d_2(b', a')·(1, s) = P^{-1}·d_2·b' + P^{-1}·d_2·a' ·s = d_2s^2 + P^{-1}d_2e' \approx d_2s^2$

五、同态加密的工程实现

当前已经有非常多的成熟同态加密库，主要包括cuFHE、FHEW、FV-NFLib、HEAAN、HElib、PALISADE、SEAL、TFHE 和 Lattigo等。各有其优势，一些库及其支持的同态加密算法如下图所示：

SEAL实现

这里以BFV算法为例进行SEAL库的同态加密实现说明，CKKS算法的实现过程与之类似，因此只对两者不同处做出说明，不再对CKKS的实现展开介绍。

1.参数的取值与作用

poly_modulus_degree：环的分母项（分圆多项式） $x^n + 1$ 中n的值。明文多项式或密文多项式中最高次数为n-1。BFV方案中n必须为2的幂，通常取值为 $2^{10}$ 到 $2^{15}$ 。n取值越大则RLWE加密方案越安全，但对应的密文也越大，各种计算操作也更慢。
coeff_modulus: 密文多项式系数的模, 决定密文噪音预算（noise budget）的重要参数, 值越大，噪声预算越大，加密计算能力越强，但其上限由poly_modulus_degree决定。但该值越大则RLWE加密方案越不安全。
plain_modulus：取值任意，这里取了2的模数。它决定了明文数据的规模以及乘法计算所消耗的噪声预算。因此，可以尽量取小值来保证效率。

一个新加密的密文的噪声预算为： $log_2(\frac{coeff\_modulus}{plain\_modulus})\ bits$

一次同态乘法所消耗的噪声预算为： $log_2(plain\_moduls)\ +\ 其他次要项$

plaintext modulus为BFV独有，CKKS无法设置。

2.编码操作（Encode)

BFV的加密过程是将明文多项式转化为密文多项式，而不是直接对整数或浮点数进行加密操作。因此，需要编码操作将整数或浮点数转化为明文多项式，以便进行随后的加密操作。BFV目前主要有三种编码方式：IntegerEncoder、FractionalEncoder和BatchEncoder。

3.重线性化操作（Relinearization）

BFV密文的size是其所含的多项式的个数。初始时密文由2个多项式组成，其size为2。但是，每次乘法操作后，结果密文的size变为M + N - 1，其中M和N分别为参与乘法操作的密文的size。虽然size变大后密文还能正常解密，但会带来两个负面影响：

乘法和加法的计算开销变大。每次密文乘法需要进行O(M * N)次多项式乘法，而密文加法则需要O(M + N)次多项式加法。
每次乘法操作所消耗的noise budget也变大。

重线性化可以让密文的size重新回到最小值2，因此对性能有较大好处。

Relinearization操作本身也有计算开销和noise budget消耗，并且与分解位数（decomposition bit count)参数（记为w）相关，具体关系如下：

w取值为1到60之间的整数。总体来说，若w取值小，计算速度较慢，但每次操作noise budget消耗很少；反之，若w取值大，计算速度较快，但每次操作noise budget消耗很大。
虽然w可能取值较大，但该w在每一组加密参数取值下都对应一个noise budget阈值。
- 当ciphertext的noise budget在该阈值之上时，每次relinearization操作会消耗较多的noise budget；
- 一旦ciphertext的noise budget减小到低过该阈值，再进行relinearizaiton时noise budget的消耗会下降到很小。

4.旋转操作（Rotation）

在BatchEncoding(编码方式的一种）下，每个密文可看作内含一个2*(n/2)的矩阵。而旋转操作Rotation就是将矩阵内的元素按行或列循环移位。

与Relinearization操作一样，Rotation的计算也基于分解位数（Decomposition Bit Count）参数w，w在1到60之间取值越大则计算越快，但消耗的noise budget也越多。
同样的，在某个w和一组加密参数下存在对应的noise budget阈值，当密文的noise budget大于阈值时，每次选择会导致noise budget消耗很多，但一旦下降到低于该阈值，再进行Rotation操作时noise budge的消耗会下降到很小。

5.模转换操作（Modulus switching）

BFV密文多项式系数的模coeff_modulus是一组素数的乘积。在初始化一组加密参数时，SEAL会自动生成一个参数链，链上的每个节点都是由初始参数推算出的一组新的加密参数，并且，每个节点与前一个节点的参数相比只是在coeff_modulus上减少了一个素数，其它的几乎完全一样。链上最后一组参数的index为0，且满足参数的有效性：coeff_modulus大于plain_modulus的值。
初始创建的参数组中coeff_modulus是最大的，每次Modulus switching都会减少coeff_modulus，从而可能带来noise budget降低。Modulus switching有如下益处：

密文大小与coeff_modulus线性正相关，如果确定密文不需再参与计算后，可以将其coeff_modulus降到最低值，以降低存储和传输的开销。
密文在经过计算后其内部的noise budget已经降低，此时如果适当降低coeff_modulus，有可能不会对noise budget产生影响。
有些情况下即使减小coeff_modulus会降低noise budget，但这种操作可以有效降低随后的计算开销（加快计算速度），并减小密文的大小，仍是一种利大于弊的操作。

6.CKKS与BFV的主要区别

参数上，CKKS没有plain_modulus。其主要参数的设置（poly_modulus_degree和coeff_modulus）与BFV方案的设置类似。CKKS的明文多项式系数以coeff_modulus为模，与BFV不同。
操作上，CKKS设计了重缩放Rescaling操作：
- Rescaling操作是CKKS区别于BFV的重要操作。Rescaling与Modulus switching类似，相同之处在于也是从coeff_modulus中除去一个素数因子。
- 不同之处在于，它同时产生的效果是将当前的scale因子也除以该素数因子。BFV处理浮点数时最大的问题是密文中的scale因子会累积膨胀越来越大而无法计算，而CKKS通过Rescaling降低密文的scale因子，有效解决了处理浮点数时的scale问题。