参考文献：

Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]//International conference on the theory and application of cryptology and information security. Springer, Cham, 2017: 409-437.
全同态加密：BGV
全同态加密：BFV
CKKS explained series

文章目录

CKKS
- Canonical Embedding
- Gaussian Distributions
- SIMD
- LHE
- Rotate

CKKS

不论是 LSB 编码的 BGV，还是 MSB 编码的 BFV，它们的同态运算都是对 $\mathbb Z_t$ 上明文的精确计算，因为密文中的明文空间和噪声空间是分离的。例如，在 BGV 中是 $t e + m$ ，在 BFV 中是 $\delta m+e$ 。但是，这种精确计算是在同余意义下的，如果将明文视为实数，那么实际上同态运算时的噪声破坏了明文的 MSB $\lfloor m/t \rfloor$ ，仅保留了 LSB $m]_t$ ，如图：

全同态加密：CKKS

而 CKKS 关注近似计算，它使得在密文中的明文空间和噪声空间是不分离的，噪声位于明文空间的 LSB 位置。也就是说，在 CKKS 中是 $m + e$ ，同态运算破坏明文的 LSB，但不破坏其 MSB。这也是合理的，可以将噪声破坏 LSB 视为浮点运算的精度误差。类似 BGV 做模切换，来使得噪声规模不会指数级增长；CKKS 也要做重缩放（rescaling），使得消息规模不会随电路深度而指数级增长，同时移除了 LSB 上的部分浮点误差。如图：

全同态加密：CKKS

Canonical Embedding

符号：

$\Phi_M(x) \in \mathbb Z[x]$ ， $M$ 次单位根的分圆多项式，度数为 $\phi(M)$
$\mathbb Z[x]/(\Phi_M(x))$ ，数域 $\mathbb Q[x]/(\phi_M(x))$ 的子环（离散子群）
$R_q = R/qR$ ，商环 $\mathbb Z_q[x]/(\Phi_M(x))$
$\mathbb R[x]/(\Phi_M(x))$ ，分圆环（cyclotomic ring），其中元素 $a (x)$ 的系数构成向量 $\vec a = (a_0,\cdots,a_{N-1}) \in \mathbb R^N$
$\|a\| := \|\vec a\|_{\infty}$ ，环元素的无穷范数
$\|a\|_1 := \|\vec a\|_1$ ，环元素的L1 范数
$\mathbb Z_M^* := \{x \in \mathbb Z_M:gcd(x,M)=1\}$ ，乘法群
$\xi_M := exp(-2\pi i/M)$ ， $M$ 次本原单位根
规范嵌入（canonical embedding） $\sigma: S \to \mathbb C^N$ 定义为
$\sigma(a) := (a(\xi_M^j))_{j \in \mathbb Z_M^*}$
其中 $\in \mathbb Q[x]/(\phi_M(x)) \sub S$
$\|a\|_\infty^{can} := \|\sigma(a)\|_\infty$ ，规范嵌入范数（canonical embedding norm）
$CRT_M$ ， $M$ 次本原单位根 $\xi_M^j,\, j \in \mathbb Z_M^*$ 上的 Vandermonde 矩阵（可逆），使得 $CRT_M \cdot \vec a = (a(\xi_M^j))_{j \in \mathbb Z_M^*} = \sigma(a)$ （规范嵌入是线性变换）
$\|U=(u_{ij})\|_\infty := \max_{i} \sum_j |u_{ij}|$ ，矩阵的无穷范数
$c_M := \|CRT_M^{-1}\|_\infty$ ，环常数（ring constant），仅与 $M$ 有关

性质：

$\forall a,b \in S$ ，有 $\|a \cdot b\|_\infty^{can} \le \|a\|_\infty^{can} \cdot \|b\|_\infty^{can}$
$\forall a \in S$ ，有 $\|a\|_\infty^{can} \le \|a\|_1$
$\forall a \in S$ ，有 $\|a\|_\infty \le c_M \cdot \|a\|_\infty^{can}$

Gaussian Distributions

定义线性子空间：
$\mathbb H := \{ \vec z = (z_j)_{j \in \mathbb Z_M^*} \in \mathbb C^N:\, z_j = \bar z_{-j},\, \forall j \in \mathbb Z_M^* \}$

也就是所有满足共轭约束的向量。可以验证，作为内积空间（inner product space） $\mathbb H \cong \mathbb R^N$ ，关于幺正矩阵（unitary basis matrix，酉矩阵）
$\begin{bmatrix} \frac{1}{\sqrt 2}I & \frac{i}{\sqrt 2}J\\ \frac{1}{\sqrt 2}J & \frac{-i}{\sqrt 2}I\\ \end{bmatrix} \in \mathbb C^{N \times N}$

其中 $\in C^{N/2 \times N/2}$ 是单位阵， $J$ 是其翻转矩阵（reversal matrix）
$\begin{bmatrix} 0 & \cdots & 0 & 1\\ 0 & \cdots & 1 & 0\\ & \vdots\\ 1 & \cdots & 0 & 0\\ \end{bmatrix} \in \mathbb C^{N/2 \times N/2}$

易知，共轭转置 $U^H = U^{-1}$ ，并且有： $\mathbb H = U \cdot \mathbb R^N$ ， $U^H \cdot \mathbb H = \mathbb R^N$

对于 $r > 0$ ，定义 Gaussian function 为 $\rho_r: \mathbb R^n \to (0,1]$ 为
$\rho_r(\vec z) = \exp\left(\frac{-\pi \|\vec z\|_2^2}{r^2}\right)$

对于 $\vec r = (r_1,\cdots,r_N) \in (\mathbb R^+)^N$ ， $\mathbb H$ 上的 elliptical Gaussian distribution $\Gamma_{\vec r}$ 定义为：根据 $\Gamma_{r_i}$ 独立采样 $z_i \in \mathbb R$ ，然后输出 $\cdot \vec z$

上述连续高斯分布同时诱导了环 $\mathbb R[x]/(\phi_M(x))$ 上的分布 $\Psi_{\vec r}$ ，它的采样输出为： $\vec e := CRT_M^{-1} \cdot U \cdot \vec z$ ，就是 $\in S$ 在基 $1,x,x^2,\cdots,x^{N-1}$ 上的组合系数。

为了获得离散高斯分布，执行圆整操作 $\chi := \lfloor \Psi_{\vec r}\rceil_{R^\vee}$ ，即把采样结果 $\in S$ 最近的环元素 $\in R^\vee$ 作为离散采样结果。其中 $R^\vee$ 是环 $R$ 的 dual fractional ideal（这啥？），我数学不好没看懂 (╥╯^╰╥)

SIMD

CKKS 使用 RLWE，类似 BGV 使用分圆多项式 $\phi_M(x)$ ，根据 CRT 可以将密文分成 $N$ 个的槽（slot），从而可以实现 SIMD。

基于 RLWE 的密码方案的明文空间可以被视作 $S$ 的子集，其中的元素是 $\|m\|_\infty^{can} \ll q$ 的那些 $m (x)$

令 $\xi_M$ 是一个复平面上的 $M$ 次本原单位根。分圆环 $\mathbb R[x]/(\Phi_M(x))$ ，对于 $\in S$ ，规范嵌入为 $\sigma(a) := (a(\xi_M^j))_{j \in \mathbb Z_M^*} \in \mathbb C^N$ 。

确切地说，由于 $\in S$ 是实系数多项式，因此 $a(\xi^{-j}) = a(\overline{\xi^j}) = \overline{a(\xi^j)}$ ，规范嵌入的像 $Im(\sigma) = \mathbb H \sub \mathbb C^N$ ，容易看出同构 $\mathbb H \cong S$

由于 $\mathbb H$ 中的元素满足共轭约束，因此令 $T$ 是 $\mathbb Z_M^*$ 的乘法子群，使得 $\mathbb Z_M^*/T = \{\pm 1\}$ ，那么考虑自然投影（natural projection） $\pi: \mathbb H \to \mathbb C^{N/2}$
$\pi((z_j)_{j \in \mathbb Z_M^*}) := (z_j)_{j \in T}$

那么关于映射 $\pi$ ，有同构 $\mathbb H \cong \mathbb C^{N/2}$

由于 $\mathbb Z[x]/(\phi(x))$ ，因此它有一组 $\mathbb Z-$ 基 $\{1,x,\cdots,x^{N-1}\}$ ，这利用规范嵌入 $\sigma(\cdot)$ 可以得到一个秩 $N$ 的理想格（ideal lattice） $\sigma(R)$ ，基为 $\{\sigma(1),\sigma(x),\cdots,\sigma(x^{N-1})\}$

现在，我们已经有了 $\to \mathbb H$ 的同构 $\sigma$ ，以及 $\mathbb H \to \mathbb C^{N/2}$ 的同构 $\pi$ ，那么就有同构映射
$\pi \circ \sigma: (S,\, \|\cdot\|_\infty^{can}) \to \mathbb (C^{N/2},\, \|\cdot\|_\infty)$

由于 $\sub S$ 是子环，因此 $\sigma(R) \sub \mathbb H$ 是离散子群，从而 $\pi(\sigma(R)) \sub \mathbb C^{N/2}$ 是有限精度的浮点数向量集合。如图：

全同态加密：CKKS

所以，任给一个复向量 $\vec z \in \mathbb C^{N/2}$ ，它的原像 $\pi^{-1}(\vec z)$ 不一定落在格 $\sigma(R)$ 上，需要就近圆整 $\lfloor \pi^{-1}(\vec z) \rceil_{\sigma(R)}$ ，得到最接近的格点，这就导致了圆整误差。为了提高浮点数精度，可以设置一个 scaling factor $\Delta \ge 1$ ，先 $\vec z' = \Delta \cdot \vec z$ ，然后 $\pi^{-1}(\sigma^{-1}(\vec z')) \in R$ 得到对应的明文。

全同态加密：CKKS

CKKS 的编码、解码算法为：

全同态加密：CKKS

LHE

CKKS 使用了：BGV 的密钥切换技术、模切换技术、打包技术，BFV 的重线性化技术。抽象的来说，CKKS 方案如下（注意 Enc 算法）：

全同态加密：CKKS

CKKS 使用模切换过程，来移除密文中明文信息的被噪声淹没的 LSB 部分，叫做重缩放（rescaling）。固定 base $p > 0$ 和模数 $q_0 > 0$ （都不必是素数）。对于深度为 $L$ 的电路，设置梯子为 $q_l = q^l \cdot q_0$ ，第 $l$ 层的密文属于 $R_{q_l}^2$

全同态加密：CKKS

同态运算时，密文中的消息和噪声的规模都会增长。为了方便管理密文，还要在 $c$ 上附加上一些标签：层级 $\le l \le L$ ，消息上界 $\in \mathbb R$ ，噪声上界 $\in \mathbb R$

全同态加密：CKKS

另外，同态运算之前，需要参与运算的两个密文 $(c,l,v,B),\, (c',l',v',B')$ 的 level 保证一致。假设 $l^{'} < l$ ，那么需要将 $c$ 降级到 $l^{'}$ 级的 $R_{q_{l'}}$ 上：

如果使用 RS 过程， $\mapsto RS(c)$ ，那么消息从 $m$ 变化为 $\frac{q_{l'}}{q_l}m$
而直接简单模约简， $\mapsto c \mod q_{l'}$ ，这不会改变消息 $m$

全同态加密：CKKS

如果选取 $M = 2^{k+1}$ ，那么 $\phi_M(x) = x^N+1$ ，其中 $N = 2^k$ ，环 $\mathbb Z[x]/(x^N+1)$ 有良好的性质：

此时 $R^\vee = N^{-1} \cdot R$ ，从而噪声 $\in R^\vee$ 可以转化为 $\cdot e' \in R$ ，它的各个系数是相互独立的离散高斯采样。
圆整运算可以高效计算，因为 $CRT_M$ 是正交阵，因此 $\lfloor a(x) \rceil_{\sigma(R)} = \sum_i \lfloor a_i\rceil_\mathbb Z \cdot x^i$ （多项式圆整就是各项系数分别圆整）

CKKS 使用了多种分布（我不知道为何需要这么多。为了效率？为了安全性？）：

$DG(\sigma^2)$ ：实数 $\sigma>0$ ，采样 $\mathbb Z^N$ 上向量，各分量是方差为 $\sigma^2$ 的 $\mathbb Z$ 上独立的离散高斯采样
$H W T (h)$ ：正整数 $h$ ，采样 $\{0,\pm 1\}^N$ 上向量（signed binary vectors），汉明重量为 $h$
$ZO(\rho)$ ：实数 $\le \rho \le 1$ ，采样 $\{0,\pm 1\}^N$ 上向量，它的各个分量以 $\rho/2$ 的概率为 $1, - 1$ ，以 $1-\rho$ 的概率为 $0$

CKKS 方案如下：

全同态加密：CKKS

我们说一个密文 $\in R_{q_l}^2,l,v,B)$ 是 $\in S$ 的有效密文（valid encryption），如果 $\|m\|_\infty^{can} \le v$ 且 $c,sk> = m+2 \mod q_l$ ，其中 $\in S$ 满足 $\|e\|_\infty^{can} \le B$ 。可以证明：

全同态加密：CKKS

为了达到 $\lambda-$ 比特的安全性，需要使得 $\ge \frac{\lambda+110}{7.2} \log(P \cdot q_L)$ 。由于 $q_L$ 是梯子中最大的模数，因此让 $P$ 接近于 $q_L$ 即可。对于 $\lambda = 80$ ，文章中设置 $\sigma = 3.2$ ， $h = 64$ 。

下图展示了安全性和计算效率之间的 tradeoff：为了提高安全性，这需要提升分圆多项式的次数 $N$ ，即使我们不需要太多的（ $N /2$ 个）明文槽。

全同态加密：CKKS

Rotate

根据数论知识，域扩张 $\mathbb Q(\xi_M)/\mathbb Q$ 的 Galois 群 $Gal(\mathbb Q(\xi_M)/\mathbb Q)$ 是个同构于 $\mathbb Z_M^*$ 的乘法群，其中的元素是自同构映射：
$\kappa_k: m(x) \mapsto m(x^k),\, \forall gcd(k,M)=1$

一个明文多项式为 $\in R \sub \mathbb Q(\xi_M)$ ，解码后对应的明文向量是 $\vec z = \pi(\sigma(m(x))) \in \mathbb C^{N/2}$ 。对于任意的 $\in T \sub \mathbb Z_M^*$ ，令 $j^{-1} \cdot i \mod M$ ，那么计算 $\kappa_k(m)$ ，满足
$z_j' = m'(\xi_M^j) = \kappa(m(\xi_M^j)) = m(\xi_M^{jk}) = m(\xi_M^{i}) = z_i$

也就是说，自同构映射 $\kappa_k$ 可以实现把明文信息从槽 $i$ 搬移到槽 $j$

定义向量 $c_i)_I$ 上的自同构映射为： $\kappa_k((c_i)_I) := (\kappa_k(c_i))_I$ ，可以验证，如果 $\in R_{q_l}^2$ 是明文 $\in R$ 在私钥 $(1, s)$ 下的有效密文，那么 $\kappa_k(c) \in R_{q_l}^2$ 是明文 $\kappa_k(m) \in R$ 在私钥 $(1,\kappa_k(s))$ 下的有效密文。

类似 BGV 的 Pack / Unpack 技术，将密文的密钥切换变换 $\tau_{(1,s) \to (1,\kappa_k(s))}$ 和 $\tau_{(1,\kappa_k(s)) \to (1,s)}$ 作为公钥发布，从而实现密文上各个槽里的明文信息的任意搬移。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

全同态加密：CKKS

文章目录

CKKS

Canonical Embedding

Gaussian Distributions

SIMD

LHE

Rotate

评论(0)

提示：请文明发言取消回复

作者信息

最近更新

2024年中考修辞手法复习：夸张

2024年中考修辞手法复习：借代

2024年中考修辞手法复习：排比

2024年中考修辞手法复习：反复

2024年中考修辞手法复习：对偶

电脑学习网官网是哪一个详细介绍

卸载软件之后电脑黑屏了怎么办？

怎么刷新电脑的dns缓存

全同态加密：CKKS

文章目录

CKKS

Canonical Embedding

Gaussian Distributions

SIMD

LHE

Rotate

评论(0)

提示：请文明发言 取消回复

相关文章

作者信息

最近更新

提示：请文明发言取消回复