Rotation
rotation操作的论文出处：Bootstrapping for approximate homomorphic encryption sec4.2
一些数学上的问题
-
数学资料 + CKKS rotation：同态加密：CKKS原理之旋转（Rotation）_PenguinLeee的博客-CSDN博客
-
同态加密：以CKKS为例的Bootstrapping操作介绍（不定期更新）_PenguinLeee的博客-CSDN博客 的评论区
问：在ckks中的bootstrapping中的打包编码，为什么要选取本原根的 \(5^i\) 次方呢？就是选取的本原根为\(\xi^{5^i}\),好像是为了旋转操作用的，但是具体有什么作用呢？
答：原文里说明了使用5的原因。在编码中，为了实现旋转操作，自然嵌入的根\(\xi\)的排列会有一些讲究。本文主要说的是Bootstrapping的原理和步骤，旋转的内容得等一阵再加。
-
22:45 The CKKS (a.k.a. HEAAN) FHE Scheme 伽罗瓦群 同构于 由 5 和 -1 生成的乘法群。即，
Based on the evaluation of automorphism \(X \mapsto X^{k}\) in \(\operatorname{Gal}(K / \mathbb{Q}) \approx \mathbb{Z}_{2 n}^{\times}=\langle 5,-1\rangle\)
If \(c_{0}(X)+c_{1}(X) \cdot s(X)=\mu(X)\), then \(c_{0}\left(X^{k}\right)+c_{1}\left(X^{k}\right) \cdot s\left(X^{k}\right)=\mu\left(X^{k}\right)\)
\(k=5\) : rotation on \(\left\langle\zeta^{5}\right\rangle=\left\{\zeta, \zeta^{5}, \ldots, \zeta^{2 n-3}\right\}\) (as well as plaintext slots)
\(k=-1\) : complex conjugate
示例
rotation key的生成
-
对于与CKKS中 \(\Phi_M\) 的 \(M\) 互素的 \(k\) ，有环 \(\mathcal{P}=\mathbb{R}[X]/(X^N+1)\) 上自同构映射 \(\kappa_k:m(X)\mapsto m(X^k) (\mod \Phi_M(X))\)
- 对于 使用 \(\texttt{sk}=(1,s)\) 加密多项式 \(m\) 得到的密文 \(\texttt{ct}\) ，\(\kappa_k(\texttt{ct})\) 表示对密文向量的每个分量都做 \(\kappa_k\) 映射。
- 利用 key-switching 技术，可以使用原始的 密钥 \(\texttt{sk}\) 解密密文 \(\kappa_k(ct)\) 得到 \(\kappa_k(m)\)
- 本段参考论文 Bootstrapping for approximate homomorphic encryption， p10
-
rotation 用到的公钥 \(pk\) 有 \(\texttt{rk}_r\gets \texttt{KSGen}_\texttt{sk}(\kappa_{5^r}(\texttt{sk}))\)
i.e. \(pk_\texttt{leftRot,r} = (-a_0\cdot s + e_0 + p\cdot s(x^k), a_0) (\text{mod } p\cdot q_l)\)
-
取定 \(\Delta\) 和 方案的乘法深度 \(L\) 后，有 \(Q=\Delta^L\)。
然后，基于 安全参数 \(\lambda\) 和 LWE parameter estimator 我们得到多项式次数 \(N\)。
-
\(a_0\) uniformly sampled from \(\mathcal{R}_{p\cdot q_l}\)
-
\(r\) 表示 rotate 的位数减\(1\)。（参考前文示例可知，\(r=1,k=5\) 时，左旋转两位）
-
left rotation 有 \(k=5^r \mod 2N\)
-
right rotation 有 \(k=5^{-r} \mod 2N\)
-
conjugation 有 \(k=2N-1 \mod 2N\)
-
以上主要参考pdf HEAAN/slide-HEAAN.pdf at 1.1 · snucrypto/HEAAN 第五页
-
\(p\) 是一个和 \(Q^L\) 有相同位宽的大整数（参考pdf HEAAN/slide-HEAAN.pdf at 1.1 · snucrypto/HEAAN 第四页）
-
\(q_l\) 是指，我们此时考虑一个在 level \(l\) 的 \(\texttt{ct}=(c_0,c_1)\)
-
计算 ct'=rotation (ct)
前文的 \(pk_\texttt{leftRot,r}\) 即为下文中的 \({\texttt{rk}_r}\)，记号 \(p, k,r\) 的意义与前文相同。
\[\begin{aligned} &\texttt{ct'}\gets\texttt{KS}_{\texttt{rk}_r}(\kappa_{5^r}(\texttt{ct}))\\ &=\texttt{KS}_{\texttt{rk}_r}((c_0(x^k),c_1(x^k)))\\ &=(c_0(x^k),0)+\lfloor p^{-1}\cdot c_1(x^k)\cdot\texttt{rk}_r\rceil(\mod q_l)\\ &=(c_0(x^k),0)+\lfloor p^{-1}\cdot c_1(x^k)\cdot(-a_0\cdot s(x) + e_0 + p\cdot s(x^k), a_0) \rceil(\mod q_l)\\ &\text{以下是为查看解密正确性而写的冗长展开}\\ &=(c_0(x^k),0)\\ &\quad +\lfloor (p^{-1}\cdot c_1(x^k)\cdot(-a_0)\cdot s(x) + p^{-1}\cdot c_1(x^k)\cdot e_0 + c_1(x^k) \cdot p^{-1}\cdot p\cdot s(x^k), \qquad p^{-1}\cdot c_1(x^k)\cdot a_0) \rceil(\mod q_l)\\ &=(c_0(x^k)+ \lfloor p^{-1}\cdot c_1(x^k)\cdot(-a_0)\cdot s(x) + p^{-1}\cdot c_1(x^k)\cdot e_0 + c_1(x^k)\cdot s(x^k)\rceil, \qquad \lfloor p^{-1}\cdot c_1(x^k)\cdot a_0\rceil)(\mod q_l)\\ \end{aligned} \]验证正确性
对于上述 \(\texttt{ct'}\) 和 \(\texttt{sk}=(1,s)\)，代入解密流程，有 \(Dec(\texttt{ct'},sk)=\kappa_k(m)\)
\[\begin{aligned} &Dec(\texttt{ct'},sk)\\ &=(c_0(x^k)+ p^{-1}\cdot c_1(x^k)\cdot(-a_0)\cdot s(x) + p^{-1}\cdot c_1(x^k)\cdot e_0 + c_1(x^k)\cdot s(x^k), \qquad p^{-1}\cdot c_1(x^k)\cdot a_0)\cdot(1,s(x))(\mod q_l)\\ &=c_0(x^k)- p^{-1}\cdot c_1(x^k)\cdot a_0\cdot s(x) + p^{-1}\cdot c_1(x^k)\cdot e_0 + c_1(x^k)\cdot s(x^k)+ p^{-1}\cdot c_1(x^k)\cdot a_0\cdot s(x) (\mod q_l)\\ &=c_0(x^k) + c_1(x^k)\cdot s(x^k) + p^{-1}\cdot c_1(x^k)\cdot e_0 - p^{-1}\cdot c_1(x^k)\cdot a_0\cdot s(x)+p^{-1}\cdot c_1(x^k)\cdot a_0\cdot s(x)(\mod q_l)\\ &=c_0(x^k)+ c_1(x^k)\cdot s(x^k)+ p^{-1}\cdot c_1(x^k)\cdot e_0(\mod q_l)\\ &\approx\kappa_k(m)(\mod q_l)\\ \end{aligned} \]对密文的某一部分进行rotation操作
问题：利用SEAL库对密文的某一部分进行rotation操作
答案：
- 利用 mask 向量先提取原密文要操作的部分并进行旋转；
- 再利用 mask' 提取原密文不需要操作的部分，
- 将两部分密文结果相加即可
注：
-
第二步的 mask’ 即为 第一步的 mask 取反（或者说取补）。
-
思路来源Operations for rotations in ciphertext using SEAL - Stack Overflow
-
此文最后一部分也有说明：同态加密：CKKS原理之旋转（Rotation）_PenguinLeee的博客-CSDN博客