Abstract

本文提出了CKKS的RNS变体。

首先本文引入了一种新的密文模结构，该结构允许对分圆多项式进行RNS分解，并对每个RNS分量进行NTT转换，实际上就是近似模组成的模链。

同时本文还提出了一种不需要RNS组合的近似模交换技术，即在密文在RNS表示下可以使用近似模交换技术变得到模交换后的结果。

实际上可以看到，这里全部使用到了CKKS的核心概念，误差是明文的一部分，只要误差足够小就可以接受。

1.预备知识

1.1CKKS17的知识

1.2 CRT和RNS

给定大整数$q={\prod }_{i=1}^k{q}_i$，其中$q_i$之间两两互素。CRT阐述了一个环同构的存在，即:
$${\mathbb{Z}}_q\simeq \prod _{i=1}^k{\mathbb{Z}}_{q_i}$$
根据该环同构，CRT蕴含了一个余数系统(RNS)，即可以将模$q$上的大整数运算同构到模$q_1,q_2,...,q_k$上的平行小整数运算，即:
$$a(modq)\simeq (a_1,a_2,...,a_k),其中a_i\equiv a(mod{q}_i)$$
根据$CRT$，由$RNS$表示的数字$a_1,a_2,...,a_k$可以在模$q$的意义下，唯一恢复得到$a$，计算过程如下:
$$a=\sum _{i=1}^k{Q}_i\cdot [Q_i^{-1}{]}_{q_i}\cdot a_i(modq)$$
其中$Q_i=q/q_i$，$[Q_i^{-1}{]}_{q_i}$表示$Q_i$在模$q_i$下的逆。

1.3 Fast RNS Base Conversion(该算法首先被提出在RNS-FV中)

给定两组基链，分别为$C=q_1,q_2,...,q_k$和$B=m_1,m_2,...,m_l$，且满足$q={\prod }_{i=1}^k$和$m={\prod }_{j=1}^l{m}_j$。给定$a(modq)$对基链C的RNS表示$(a_1,a_2,...,a_k)$。则Fast RNS Base Conversion的目的为将$(a_1,a_2,...,a_k)$直接转换为在基链$B$下的RNS表示，而不需要进行RNS组合操作，该算法定义如下:
$$FastBConv(a,C,B)=(\sum _{i=1}^k{Q}_i\cdot [Q_i^{-1}{]}_{q_i}\cdot a_{i}mod{m}_j{)}_{1\le j\le l}$$
不妨假设$amodq$在基链$B$下的RNS表示为$(b_1,b_2,...,b_l)$。则我们本意希望的是这个RNS表示满足如下计算:
$$b_i=amod{m}_j$$
但实际上我们知道
$$\sum _{i=1}^k{Q}_i\cdot [Q_i^{-1}{]}_{q_i}\cdot a_i=a+e\cdot q$$
故实际上经过$FastBConv(\ast )$算法后我们得到的是$a+e\cdot q$在基链$B$下的RNS表示$(b_1,b_2,...,b_l)$，实际上满足如下计算:
$$b_i=a+e\cdot qmod{m}_j$$
若此时将$(b_1,b_2,...,b_l)$恢复成模$m$的大整数，则得到的大整数是$a+e\cdot q(modm)$。

也就是说FastBConv算法会引入些许误差，这实际上是通过误差换时间的想法。

此时在回到CKKS的思想上，只要这个误差足够小，那么在CKKS算法中就可以接受。

1.4 近似基链——为RNS-CKKS特意引入的新的密文模结构

(1) 首先回顾CKKS17中RS操作的概念。

---

选择缩放因子$\Delta =q>0$，设置密文模结构为:
$$Q_l=q^l,其中0\le l\le L$$
给定明文多项式$m$的$l$ 级密文$ct\in R_{Q_l}^2$。

则CKKS17中$RS$ 操作为计算:
$$c{t}_{rs}=\lfloor q^{-1}\cdot ct\rceil \in R_{Q_{l-1}}^2$$
即$RS$ 操作会得到$q^{-1}\cdot m$的近似加密$c{t}_{rs}$，且这是$l-1$级的密文。

可以看到$RS$ 每次操作后，密文内部的缩放因子$\Delta$是不变的。

---

(2) 现在定义RNS-CKKS中的近似基概念

---

RNS表示的先决条件就是基链中的元素是互素的。

首先我们仍然选择缩放因子为$\Delta =q>0$，同时我们设置一个预定义的精度$\eta$，然后我们选择一组基如下:
C = { q 0 , q 1 , . . . , q L } C=\{q_0,q_1,...,q_L\} C={q0​,q1​,...,qL​}
$C$中的每个元素都需要满足以下条件:
$$q_i/q\in (1-2^{-\eta },1+2^{-\eta }),其中q_i遍历C$$
发现$C$中的每个元素都是缩放因子$\Delta$的近似，这就是近似基的由来。

重新设置密文模结构如下:
$$Q_l=\prod _{i=0}^l{q}_i$$
如此一来每次$RS$ 操作的元素就变成了$C$中的元素。

很明显可以观察到，现在每次$RS$ 操作后，密文内部的缩放因子会发生改变，换句话说，这就是RS操作引入的误差，还是利用CKKS的核心思想，只要这个误差足够小，那我们就可以接受。

1.5 近似模交换

(1) 模交换（Modulus—Switching）

MS操作被介绍在BGV12中，

简单来说就是将模$Q_1$下的密文转换为模$Q_2$​下的密文。

(2) 基的选择

给出RNS-CKKS中基的选择如下:
{ B = { p 0 , p 1 , . . . , p k − 1 } C = { q 0 , q 1 , . . . , q l − 1 } D = { p 0 , p 1 , . . . , p k − 1 , q 0 , q 1 , . . . , q l − 1 } \begin{cases} B=\{p_0,p_1,...,p_{k-1}\} \\ C=\{q_0,q_1,...,q_{l-1}\} \\ D=\{p_0,p_1,...,p_{k-1}, q_0,q_1,...,q_{l-1}\} \\ \end{cases} ⎩ ⎨ ⎧​B={p0​,p1​,...,pk−1​}C={q0​,q1​,...,ql−1​}D={p0​,p1​,...,pk−1​,q0​,q1​,...,ql−1​}​
其中，$P={\prod }_{i=0}^{k-1}{p}_i$, $Q={\prod }_{j=0}^{l-1}{q}_j$。

(3) 近似模交换（$ApproximateModulusSwitching$）

RNS-CKKS中的模交换分为两个步骤，分别为$ApproximateModulusRaising$和$ApproximateModulusReduction$​

首先介绍$ApproximateModulusRaising$算法:

---

$Algorithm1:ApproximateModulusRaising$

---

$1.input$:
$$[a{]}_C=(a^{(0)},a^{(1)},...,a^{(l-1)}),wherea\in {\mathbb{Z}}_Q$$
$2.procedure:ModU{p}_{C\to D}([a{]}_C)$:
$$({\tilde{a}}^{(0)},{\tilde{a}}^{(1)},...,{\tilde{a}}^{(k-1)})\leftarrow Co{n}_{C\to D}([a{]}_C)$$
$3.retrun$:
$$({\tilde{a}}^{(0)},{\tilde{a}}^{(1)},...,{\tilde{a}}^{(k-1)},a^{(0)},a^{(1)},...,a^{(l-1)})$$

---

算法分析:

1. 最后得到的RNS表示实际上是$\tilde{a}=a+e\cdot Q$在$D$上的RNS表示。
2. 当误差足够小，我们可以近似的认为得到的是$a$在$D$上的RNS表示。

算法功能描述:

1. 该算法输入$a\in {\mathbb{Z}}_Q$在$C$上的RNS表示，近似返回$a\in {\mathbb{Z}}_{PQ}$在$D$上的RNS表示。

---

---

然后介绍$ApproximateModulusReduction$算法:

---

$Algorithm2:ApproximateModulusReduction$

---

$1.input$:
$$[\tilde{b}{]}_D=({\tilde{b}}^{(0)},{\tilde{b}}^{(1)},...,{\tilde{b}}^{(k+l-1)})=([\tilde{b}{]}_B,[\tilde{b}{]}_C),其中\tilde{b}\in {\mathbb{Z}}_{P\cdot Q}$$
$2.procedure:ModDow{n}_{D\to C}([\tilde{b}{]}_D)$

​ $2.1提取[\tilde{b}{]}_D的前k个元素，可以得到$:
$$[\tilde{b}modP{]}_B=({\tilde{b}}^{(0)},{\tilde{b}}^{(1)},...,{\tilde{b}}^{(k-1)})$$
​ $2.2进行基变换$：
$$({\tilde{a}}^{(0)},{\tilde{a}}^{(1)},...,{\tilde{a}}^{(l-1)})\leftarrow Co{n}_{B\to C}([\tilde{b}modP{]}_B)$$
​ $2.3计算$:
$$b^{(j)}=P^{-1}\cdot ({\tilde{b}}^{k+j}-{\tilde{a}}^{(j)})mod{q}_j,forall0\le j\le l-1$$
$3.retrun$:
$$[b{]}_C=(b^{(0)},b^{(1)},...,b^{(l-1)})$$

---

算法分析:

1. 由$[\tilde{b}{]}_D$可以计算得到$\tilde{b}\in {\mathbb{Z}}_{P\cdot Q}$，而由$[\tilde{b}{]}_B$只能得到$\tilde{b}modP\in {\mathbb{Z}}_P$，由$[\tilde{b}{]}_C$只能得到$\tilde{b}modQ\in {\mathbb{Z}}_Q$。

2. 在2.3步骤的计算中，每一次计算的值为:

$$b^{(j)}=P^{-1}\cdot (\tilde{b}-(\tilde{b}modP)-e\cdot P(mod{q}_j)$$

3. 也就是说最后输出的结果为:

$$[b{]}_C=[P^{-1}\cdot (\tilde{b}-(\tilde{b}modP)-e\cdot P){]}_C$$

4. 即此时我们可以根据$[b{]}_C$计算得到:

$$b=P^{-1}\cdot (\tilde{b}-(\tilde{b}modP)-e\cdot P)\in {\mathbb{Z}}_Q$$

5. 实际上这是一个近似值:

$$b\approx P^{-1}\cdot \tilde{b}$$

算法功能描述:

1. 该算法输入$\tilde{b}$在$D$上的RNS表示，近似返回$b\approx P^{-1}\cdot \tilde{b}$在$C$上的RNS表示。

---

---

(4) 算法扩展

$ModU{p}_{C\to D}(\cdot )$和$ModDow{n}_{D\to C}(\cdot )$可以直接扩展到多形式环中，如下所示:
$$\{\begin{array}{ll}ModU{p}_{C\to D}(\cdot )& :{\prod }_{j=0}^{l-1}{R}_{q_j}\to {\prod }_{i=0}^{k-1}{R}_{p_i}\times {\prod }_{j=0}^{l-1}{R}_{q_j}\\ ModDow{n}_{D\to C}(\cdot )& :{\prod }_{i=0}^{k-1}{R}_{p_i}\times {\prod }_{j=0}^{l-1}{R}_{q_j}\to {\prod }_{j=0}^{l-1}{R}_{q_j}\end{array}$$
该算法可以实现近似模交换的功能:
$$b=ModDow{n}_{D\to C}(ModU{p}_{C\to D}(a))\approx P^{-1}\cdot a$$

2. RNS-CKKS算法

将CKKS算法表达到RNS域上，核心是:

$(1)$​近似模数的选择:

​ 近似模数的选择可以将CKKS的公钥$pk$，计算密钥$evk$，密文$ct$，放到RNS域上，即普通的RNS分解即可。

$(2) $近似模交换算法:

​ 该算法主要用在KS操作中，KS操作的对象是一个密文和一个计算密钥。

​ 首先通过$ModUp(\ast )$算法将$C_l$基上需要进行密钥交换的密文放到$D_l$基上。然后同$D_l$基上的计算密钥进行RNS组件级的乘法。然后通过$ModDown(\ast )$算法将$D_l$基上的密文重新放到$C_l$​基上并乘以$P^{-1}$。

​ 一个$ModDown(\ast )$算法被用在$RS(ct)$算法中，可以将一个$C_l$基上的密文放到$C_{l-1}$基上并乘以$q_l^{-1}$。

---

$Setup(q,L,\eta ,1^{\lambda })$:

初始化操作

---

$KSGen(s_1,s_2)$:

给定两个秘密多项式$s_1,s_2\in R$，均匀采样$e^{\prime }\leftarrow {\chi }_{err}$。

以RNS的形式均匀采样元素:
$$(a^{\prime (0)},a^{\prime (1)},...,a^{\prime (k+L)})\leftarrow (\prod _{i=0}^{k-1}{R}_{p_i}\times \prod _{j=0}^L{R}_{q_j})$$
输出swk:
$$(sw{k}^{(0)}=(b^{\prime (0)},a^{\prime (0)}),...,sw{k}^{(k+L)}=(b^{\prime (k+L)},a^{\prime (k+L)}))\leftarrow (\prod _{i=0}^{k-1}{R}_{p_i}\times \prod _{j=0}^L{R}_{q_j})$$
其中每一项满足下述关系:
$$\{\begin{array}{l}{b}^{\prime (i)}\leftarrow -a^{\prime (i)}\cdot s_2+e^{\prime }(mod{p}_i),for0\le i<k\\ b^{\prime (k+j)}\leftarrow -a^{\prime (k+j)}\cdot s_2+[P{]}_{q_i}\cdot s_1+e^{\prime }(mod{q}_i),for0\le j<L\end{array}$$

---

$KeyGen$:

$skGen$: 采样$s\leftarrow {\chi }_{key}$，设置密钥为$sk\leftarrow (1,s)$。

$pkGen$: 采样$e\leftarrow {\chi }_{err}$。

以RNS的形式均匀采样元素:
$$(a^{(0)},a^{(1)},...,a^{(L)})\leftarrow (\prod _{j=0}^L{R}_{q_j})$$
输出$pk$:
$$pk\leftarrow (p{k}^{(j)}=(b^{(j)},a^{(j)})\in R_{q_j}^2{)}_{0\le j\le L}$$
其中$b^{(j)}\leftarrow -a^{(j)}\cdot s+e(mod{q}_j)$​

$rlkGen:$
$$rlk\leftarrow KSGen(s^2,s)$$

---

$En{c}_{pk}(m)$:

​ 给定消息$m\in R$，采样$v\leftarrow {\chi }_{enc}$和$e_0,e_1\leftarrow {\chi }_{err}$。输出:
$$ct=(c{t}^{(0)},c{t}^{(1)},...,c{t}^{(L)})\in \prod _{j=0}^L{R}_{q_j}^2$$
​ 其中
$$c{t}^{(j)}\leftarrow v\cdot p{k}^{(j)}+(m+e_0,e_1)(mod{q}_j)$$
​ 可以看到消息是没有被RNS分解的。也就是说单独一个RNS组件上就可以解密得到消息$m$。

$De{c}_{s}k(m)$:
$$<c{t}^{(0)},sk>(mod{q}_0)$$

---

$Add(ct,c{t}^{\prime })$

$Mul{t}_{evk}(ct,c{t}^{\prime })$:乘法操作涉及到重线性化操作，即KS操作。

$RS(ct)$:

$Rotat{e}_{evk}(ct)$:旋转操作即KS操作。

---

3.KS算法分析

KS算法包括重线性化操作、旋转操作和共轭操作，下面来详细介绍RNS-CKKS中的KS算法。

由于后续的文章里有对KS算法的优化，而且需要考虑全局的情况，因此这里会对KS算法进行RNS组合，二者对比分析。

3.1 重线性化操作

$RNS$分解形式的重线性化操作分析:

---

给定两个$l$ 级别的密文$ct=(c{t}^{(j)}=(c_0^{(j)},c_1^{(j)}){)}_{0\le j\le l}$和$c{t}^{\prime }=(c{t}^{\prime (j)}=(c_0^{\prime (j)},c_1^{\prime (j)}){)}_{0\le j\le l}$​。

$1.For0\le j\le ldo:$
$$\begin{gathered} d_0^{(j)}\leftarrow c_0^{(j)}{c}_0^{\prime (j)}(mod{q}_j) \\ {d}_1^{(j)}\leftarrow c_0^{(j)}{c}_1^{\prime (j)}+c_1^{(j)}{c}_0^{\prime (j)}(mod{q}_j) \\ {d}_2^{(j)}\leftarrow c_1^{(j)}{c}_1^{\prime (j)}(mod{q}_j) \end{gathered}$$

$2.$计算:

$$ModU{p}_{C_l\to D_l}(d_2^{(0)},d_2^{(1)},...,d_2^{(l)})=({\tilde{d}}_2^{(0)},...,{\tilde{d}}_2^{(k-1)},d_2^{(0)},...,d_2^{(l)})$$

---

如同在CKKS中的重线性化一样，同计算密钥直接计算的是$d_2$，所以这里也需要将$C_l$基上的$d_2$放到重线性化公钥$rlk$所在的$D_l$​基上。然后二者执行RNS组件级的乘法。

为什么一定要放到$D_l$基上呢？

如果我们仔细分析$ModDown(\ast )$算法，可以发现该算法执行完毕后，舍弃的一些基的乘积，正好是算法结束后需要除以掉的部分。在KS操作中，发现舍弃掉的基为 { p 0 , p 1 , . . . , p k − 1 } \{p_0,p_1,...,p_{k-1}\} {p0​,p1​,...,pk−1​}，故这个值是$P={\prod }_{i=0}^{k-1}$，而在RS操作中这个值就是$q_l$​。

---

$3.$计算:
$$\widetilde{ct}=({\widetilde{ct}}^{(0)}=({\tilde{c}}_0^{(0)},{\tilde{c}}_1^{(0)}),...,{\widetilde{ct}}^{(k+l)}=({\tilde{c}}_0^{(k+l)},{\tilde{c}}_1^{(k+l)}))\in \prod _{i=0}^{k-1}{R}_{p_i}^2\times \prod _{j=0}^l{R}_{q_j}^2$$
其中
$${\widetilde{ct}}^{(i)}={\tilde{d}}_2^{(i)}\cdot rl{k}^{(i)}(mod{p}_i)$$

$${\widetilde{ct}}^{(k+j)}=d_2^{(j)}\cdot rl{k}^{(k+j)}(mod{q}_j)$$

$4.$计算:
$$\begin{gathered} ({\hat{c}}_0^0,...,{\hat{c}}_0^l)\leftarrow ModDow{n}_{D_l\to C_l}({\tilde{c}}_0^0,...,{\tilde{c}}_0^{k+l}) \\ ({\hat{c}}_1^0,...,{\hat{c}}_1^l)\leftarrow ModDow{n}_{D_l\to C_l}({\tilde{c}}_1^0,...,{\tilde{c}}_1^{k+l}) \end{gathered}$$
$5.$输出:
$$c{t}_{mult}=(c{t}_{mult}^{(0)},c{t}_{mult}^{(1)},...,c{t}_{mult}^{(l)})$$
其中
$$c{t}_{mult}^{(j)}\leftarrow (d_0^{(j)},d_1^{(j)})+({\hat{c}}_0^j,{\hat{c}}_1^j)(mod{q}_j)$$

3.2 旋转操作

待更新。。。。。。

3.3 共轭操作

待更新。。。。。。

3.4 KS算法全局分析

回想前边的$KSGen$​​步骤

---

$KSGen(s_1,s_2)$:

给定两个秘密多项式$s_1,s_2\in R$，均匀采样$e^{\prime }\leftarrow {\chi }_{err}$。

以RNS的形式均匀采样元素:
$$(a^{\prime (0)},a^{\prime (1)},...,a^{\prime (k+L)})\leftarrow (\prod _{i=0}^{k-1}{R}_{p_i}\times \prod _{j=0}^L{R}_{q_j})$$
输出swk:
$$(sw{k}^{(0)}=(b^{\prime (0)},a^{\prime (0)}),...,sw{k}^{(k+L)}=(b^{\prime (k+L)},a^{\prime (k+L)}))\leftarrow (\prod _{i=0}^{k-1}{R}_{p_i}\times \prod _{j=0}^L{R}_{q_j})$$
其中每一项满足下述关系:
$$\{\begin{array}{l}{b}^{\prime (i)}\leftarrow -a^{\prime (i)}\cdot s_2+e^{\prime }(mod{p}_i),for0\le i<k\\ b^{\prime (k+j)}\leftarrow -a^{\prime (k+j)}\cdot s_2+[P{]}_{q_i}\cdot s_1+e^{\prime }(mod{q}_i),for0\le j<L\end{array}$$

---

实际上相当于采样$a^{\prime }\in R_{PQ}$，取
$$swk=(b^{\prime },a^{\prime })\in R_{PQ}^2$$
其中
$$b^{\prime }\leftarrow -a^{\prime }\cdot s_2+P\cdot s_1+e^{\prime }(modPQ)$$
我们从这个角度重新将$swk$转化到$RNS$域上，可得

$$[swk{]}_D=(sw{k}^{(0)}=(b^{\prime (0)},a^{\prime (0)}),...,sw{k}^{(k_L)}=(b^{\prime (k+L)},a^{\prime (k+L)}))$$

---

从这里可以看到可以先生成一个在模$PQ$上的swk，然后再将其分解到$D_L$基上进行RNS表示。

也可以直接从RNS域上生成$swk$的RNS表示。

---

为了后续的优化算法，这里我们需要记住一个事情，那就是RNS-CKKS中生成的$swk$是一个。

---

4.RS算法分析

RNS-CKKS中的$RS$操作与CKKS中的$RS$操作有些许不同，这里进行分析。

待更新。。。。。。