参考文献：

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)}$ 作为公钥发布，从而实现密文上各个槽里的明文信息的任意搬移。

近期文章

近期评论

分类

电脑基础 · 2023年3月31日

全同态加密：CKKS

文章目录

CKKS

Canonical Embedding

Gaussian Distributions

SIMD

LHE

Rotate

发表回复取消回复

电脑基础 · 2023年3月31日

文章目录

CKKS

Canonical Embedding

Gaussian Distributions

SIMD

LHE

Rotate

发表回复 取消回复

发表回复取消回复