全同态加密：CKKS(全同态加密代码)

推荐整理分享全同态加密：CKKS(全同态加密代码)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:全同态加密与同态加密区别,全同态加密与同态加密区别,全同态加密 原理,全同态加密 原理,全同态加密应用场景,全同态加密与同态加密区别,全同态加密技术研究现状,全同态加密算法,内容如对您有帮助，希望把文章链接给更多的朋友！

参考文献：

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

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

符号：

ΦM(x)∈Z[x]\Phi_M(x) \in \mathbb Z[x]ΦM​(x)∈Z[x]，MMM 次单位根的分圆多项式，度数为 N=ϕ(M)N = \phi(M)N=ϕ(M)

R:=Z[x]/(ΦM(x))R := \mathbb Z[x]/(\Phi_M(x))R:=Z[x]/(ΦM​(x))，数域 Q[x]/(ϕM(x))\mathbb Q[x]/(\phi_M(x))Q[x]/(ϕM​(x)) 的子环（离散子群）

Rq=R/qRR_q = R/qRRq​=R/qR，商环 Zq[x]/(ΦM(x))\mathbb Z_q[x]/(\Phi_M(x))Zq​[x]/(ΦM​(x))

S:=R[x]/(ΦM(x))S := \mathbb R[x]/(\Phi_M(x))S:=R[x]/(ΦM​(x))，分圆环（cyclotomic ring），其中元素 a(x)a(x)a(x) 的系数构成向量 a⃗=(a,⋯ ,aN−1)∈RN\vec a = (a_0,\cdots,a_{N-1}) \in \mathbb R^Na=(a0​,⋯,aN−1​)∈RN

∥a∥:=∥a⃗∥∞\|a\| := \|\vec a\|_{\infty}∥a∥:=∥a∥∞​，环元素的无穷范数

∥a∥1:=∥a⃗∥1\|a\|_1 := \|\vec a\|_1∥a∥1​:=∥a∥1​，环元素的L1 范数

ZM∗:={x∈ZM:gcd(x,M)=1}\mathbb Z_M^* := \{x \in \mathbb Z_M:gcd(x,M)=1\}ZM∗​:={x∈ZM​:gcd(x,M)=1}，乘法群

ξM:=exp(−2πi/M)\xi_M := exp(-2\pi i/M)ξM​:=exp(−2πi/M)，MMM 次本原单位根

规范嵌入（canonical embedding）σ:S→CN\sigma: S \to \mathbb C^Nσ:S→CN 定义为 σ(a):=(a(ξMj))j∈ZM∗\sigma(a) := (a(\xi_M^j))_{j \in \mathbb Z_M^*}σ(a):=(a(ξMj​))j∈ZM∗​​ 其中 a∈Q[x]/(ϕM(x))⊂Sa \in \mathbb Q[x]/(\phi_M(x)) \sub Sa∈Q[x]/(ϕM​(x))⊂S

∥a∥∞can:=∥σ(a)∥∞\|a\|_\infty^{can} := \|\sigma(a)\|_\infty∥a∥∞can​:=∥σ(a)∥∞​，规范嵌入范数（canonical embedding norm）

CRTMCRT_MCRTM​，MMM 次本原单位根 ξMj, j∈ZM∗\xi_M^j,\, j \in \mathbb Z_M^*ξMj​,j∈ZM∗​ 上的 Vandermonde 矩阵（可逆），使得 CRTM⋅a⃗=(a(ξMj))j∈ZM∗=σ(a)CRT_M \cdot \vec a = (a(\xi_M^j))_{j \in \mathbb Z_M^*} = \sigma(a)CRTM​⋅a=(a(ξMj​))j∈ZM∗​​=σ(a)（规范嵌入是线性变换）

∥U=(uij)∥∞:=max⁡i∑j∣uij∣\|U=(u_{ij})\|_\infty := \max_{i} \sum_j |u_{ij}|∥U=(uij​)∥∞​:=maxi​∑j​∣uij​∣，矩阵的无穷范数

cM:=∥CRTM−1∥∞c_M := \|CRT_M^{-1}\|_\inftycM​:=∥CRTM−1​∥∞​，环常数（ring constant），仅与 MMM 有关

性质：

定义线性子空间： H:={z⃗=(zj)j∈ZM∗∈CN: zj=zˉ−j, ∀j∈ZM∗}\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^* \}H:={z=(zj​)j∈ZM∗​​∈CN:zj​=zˉ−j​,∀j∈ZM∗​}

也就是所有满足共轭约束的向量。可以验证，作为内积空间（inner product space）H≅RN\mathbb H \cong \mathbb R^NH≅RN，关于幺正矩阵（unitary basis matrix，酉矩阵） U=[12Ii2J12J−i2I]∈CN×NU = \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}U=[2​1​I2​1​J​2​i​J2​−i​I​]∈CN×N

其中 I∈CN/2×N/2I \in C^{N/2 \times N/2}I∈CN/2×N/2 是单位阵，JJJ 是其翻转矩阵（reversal matrix） J=[⋯1⋯1⋮1⋯]∈CN/2×N/2J = \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}J=⎣⎡​001​⋯⋯⋮⋯​010​100​⎦⎤​∈CN/2×N/2

易知，共轭转置 UH=U−1U^H = U^{-1}UH=U−1，并且有：H=U⋅RN\mathbb H = U \cdot \mathbb R^NH=U⋅RN，UH⋅H=RNU^H \cdot \mathbb H = \mathbb R^NUH⋅H=RN

对于 r>r > 0r>0，定义 Gaussian function 为 ρr:Rn→(,1]\rho_r: \mathbb R^n \to (0,1]ρr​:Rn→(0,1] 为 ρr(z⃗)=exp⁡(−π∥z⃗∥22r2)\rho_r(\vec z) = \exp\left(\frac{-\pi \|\vec z\|_2^2}{r^2}\right)ρr​(z)=exp(r2−π∥z∥22​​)

对于 r⃗=(r1,⋯ ,rN)∈(R+)N\vec r = (r_1,\cdots,r_N) \in (\mathbb R^+)^Nr=(r1​,⋯,rN​)∈(R+)N，H\mathbb HH 上的 elliptical Gaussian distribution Γr⃗\Gamma_{\vec r}Γr​ 定义为：根据 Γri\Gamma_{r_i}Γri​​ 独立采样 zi∈Rz_i \in \mathbb Rzi​∈R，然后输出 U⋅z⃗U \cdot \vec zU⋅z

上述连续高斯分布同时诱导了环 S:=R[x]/(ϕM(x))S := \mathbb R[x]/(\phi_M(x))S:=R[x]/(ϕM​(x)) 上的分布 Ψr⃗\Psi_{\vec r}Ψr​，它的采样输出为：e⃗:=CRTM−1⋅U⋅z⃗\vec e := CRT_M^{-1} \cdot U \cdot \vec ze:=CRTM−1​⋅U⋅z，就是 e(x)∈Se(x) \in Se(x)∈S 在基 1,x,x2,⋯ ,xN−11,x,x^2,\cdots,x^{N-1}1,x,x2,⋯,xN−1 上的组合系数。

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

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

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

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

确切地说，由于 a∈Sa \in Sa∈S 是实系数多项式，因此 a(ξ−j)=a(ξj‾)=a(ξj)‾a(\xi^{-j}) = a(\overline{\xi^j}) = \overline{a(\xi^j)}a(ξ−j)=a(ξj​)=a(ξj)​，规范嵌入的像 Im(σ)=H⊂CNIm(\sigma) = \mathbb H \sub \mathbb C^NIm(σ)=H⊂CN，容易看出同构 H≅S\mathbb H \cong SH≅S

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

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

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

现在，我们已经有了 S→HS \to \mathbb HS→H 的同构 σ\sigmaσ，以及 H→CN/2\mathbb H \to \mathbb C^{N/2}H→CN/2 的同构 π\piπ，那么就有同构映射 π∘σ:(S, ∥⋅∥∞can)→(CN/2, ∥⋅∥∞)\pi \circ \sigma: (S,\, \|\cdot\|_\infty^{can}) \to \mathbb (C^{N/2},\, \|\cdot\|_\infty)π∘σ:(S,∥⋅∥∞can​)→(CN/2,∥⋅∥∞​)

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

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

CKKS 的编码、解码算法为：

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

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

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

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

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

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

CKKS 方案如下：

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

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

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

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

一个明文多项式为 m(x)∈R⊂Q(ξM)m(x) \in R \sub \mathbb Q(\xi_M)m(x)∈R⊂Q(ξM​)，解码后对应的明文向量是 z⃗=π(σ(m(x)))∈CN/2\vec z = \pi(\sigma(m(x))) \in \mathbb C^{N/2}z=π(σ(m(x)))∈CN/2。对于任意的 i,j∈T⊂ZM∗i,j \in T \sub \mathbb Z_M^*i,j∈T⊂ZM∗​，令 k=j−1⋅imod  Mk = j^{-1} \cdot i \mod Mk=j−1⋅imodM，那么计算 m′=κk(m)m' = \kappa_k(m)m′=κk​(m)，满足 zj′=m′(ξMj)=κ(m(ξMj))=m(ξMjk)=m(ξMi)=ziz_j' = m'(\xi_M^j) = \kappa(m(\xi_M^j)) = m(\xi_M^{jk}) = m(\xi_M^{i}) = z_izj′​=m′(ξMj​)=κ(m(ξMj​))=m(ξMjk​)=m(ξMi​)=zi​

也就是说，自同构映射 κk\kappa_kκk​ 可以实现把明文信息从槽 iii 搬移到槽 jjj

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

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