1. 提出背景
1978年，Rivest、Adleman和Dertouzos在文献[1]中就贷款公司数据库的保密问题与计算问题进行了讨论，并首次提出了同态加密的加密方式。后来，随着云计算、大数据、人工智能、机器学习等新兴技术不断兴起，人们越来越发现同态加密对于现阶段信息安全的重要性。2009年，Gentry首次提出自举技术[2]，实现了第一个全同态加密方案。2010年，Dijk又首次实现了基于整数环上FHE的DGHV方案[4]。2012年，Kipnis等人给出了基于矩阵和多项式的无噪声FHE方案[5]。2016年，Jaschke等人通过将有理数近似表示为整数[6]，实现了明文空间为实数的FHE方案。2017年，Cheon等人实现了可进行浮点数近似计算的层次型FHE方案[3]（下文称CKKS方案），一年后，Cheon等人又通过自举技术，将CKKS方案扩展为全同态加密方案[7]，同年，也通过RNS实现了CKKS方案的RNS变体[8]。
2. 方案原理
同态加密就是在数据仍处于密文的状态下，对密文数据信息进行各种计算，从而使得其结果在变回明文后和对明文进行相应运算时的结果等值。
对于函数
f
f
f，若
f
f
f满足
f
(
a
)
+
f
(
b
)
=
f
(
a
+
b
)
f(a) + f(b) = f(a+b)
f(a)+f(b)=f(a+b)或
f
(
a
)
?
f
(
b
)
=
f
(
a
?
b
)
f(a) \cdot f(b) = f(a \cdot b)
f(a)?f(b)=f(a?b)其一，则称其为半同态，若对于加法与乘法均满足，则称该函数为全同态。我们在这里将加密操作 看作是一个满足同态性质的函数，那么，其密文
E
n
c
(
m
)
Enc(m)
Enc(m)就有
E
n
c
(
m
1
)
+
E
n
c
(
m
2
)
=
E
n
c
(
m
1
+
m
2
)
或
E
n
c
(
m
1
)
?
E
n
c
(
m
2
)
=
E
n
c
(
m
1
?
m
2
)
Enc(m_1) + Enc(m_2) = Enc(m_1 + m_2)或\\ Enc(m_1) \cdot Enc(m_2) = Enc(m_1 \cdot m_2)
Enc(m1?)+Enc(m2?)=Enc(m1?+m2?)或Enc(m1?)?Enc(m2?)=Enc(m1??m2?)的性质，而且加密函数没有变化，故仍可以用相同的解密函数
D
e
c
Dec
Dec进行解密，并且解密后的明文与对明文直接进行运算的结果相等：
D
e
c
(
E
n
c
(
m
1
)
+
E
n
c
(
m
2
)
)
=
m
1
+
m
2
或
D
e
c
(
E
n
c
(
m
1
)
?
E
n
c
(
m
2
)
)
=
m
1
?
m
2
Dec(Enc(m_1) + Enc(m_2)) = m_1 + m_2或\\ Dec(Enc(m_1) \cdot Enc(m_2)) = m_1 \cdot m_2
Dec(Enc(m1?)+Enc(m2?))=m1?+m2?或Dec(Enc(m1?)?Enc(m2?))=m1??m2?
同理，若加法与乘法均满足，则称该方案为全同态加密方案。
Cheon等人给出的CKKS方案，实现了明文为浮点数的近似计算。该方案首先通过编码技术将明文槽上的 N / 2 N/2 N/2维复向量变换为 N N N次整系数多项式；接着假设其具有循环安全性，引入同态乘密钥 e v k evk evk，将同态乘法带来的密文维数扩张加以控制；最后在同态乘法结束后进行“重缩放”，有效地控制噪声对明文的影响。
3. 算法描述
设CKKS方案的安全系数为 λ \lambda λ，明文空间 M = C N / 2 \mathcal{M} = \mathbb{C}^{N/2} M=CN/2，映射 τ \tau τ为： τ : Z q [ x ] / ? x N + 1 ? → C N / 2 \tau:\mathbb{Z}_q[x]/\langle x^N + 1\rangle \to \mathbb{C}^{N/2} τ:Zq?[x]/?xN+1?→CN/2即 m ( x ) ? m m(x) \mapsto \mathbf{m} m(x)?m，具体关系为 z j = m ( ζ M j ) z_j = m(\zeta _M ^j) zj?=m(ζMj?)，其中 ζ M = exp ? ( ? 2 π i / M ) \zeta _M = \exp(-2\pi i/M) ζM?=exp(?2πi/M)。方案详细描述如下：
- C K K S . K e y G e n ( 1 λ ) CKKS.KeyGen(1^{\lambda}) CKKS.KeyGen(1λ)
- 选择一个2的方幂的整数 M = M ( λ , q L ) M=M(\lambda,q_L) M=M(λ,qL?), 一个整数 h = h ( λ , q L ) h=h(\lambda,q_L) h=h(λ,qL?), 一个大整数 P = P ( λ , q L ) P = P(\lambda,q_L) P=P(λ,qL?)，和一个实数 σ = σ ( λ , q L ) \sigma=\sigma(\lambda,q_L) σ=σ(λ,qL?)；
- 采样 s ← H W T ( h ) s \leftarrow HWT(h) s←HWT(h)， a ← R q L a \leftarrow R_{q_L} a←RqL??， e ← D G ( σ 2 ) e \leftarrow DG(\sigma ^2) e←DG(σ2)，设私钥 s k = ( 1 , s ) sk = (1,s) sk=(1,s)，公钥为 p k = ( b , a ) ∈ R q L 2 pk = (b,a) \in R_{q_L}^2 pk=(b,a)∈RqL?2?，其中 b ← ? a s + e ? ( m o d ?? q L ) b \leftarrow -as + e \ (mod\;q_L) b←?as+e?(modqL?)；
- 采样 a ′ ← R q L a' \leftarrow R_{q_L} a′←RqL??， e ′ ← D G ( σ 2 ) e' \leftarrow DG(\sigma ^2) e′←DG(σ2)，设同态乘密钥 e v k ← ( b ′ , a ′ ) ∈ R P ? q L 2 evk \leftarrow (b',a') \in R_{P \cdot q_L}^2 evk←(b′,a′)∈RP?qL?2?，其中 b ′ = ? a ′ s + e ′ + P s 2 ?? ( m o d P ? q L ) b' = -a's + e' + Ps^2 \; (mod P \cdot q_L) b′=?a′s+e′+Ps2(modP?qL?)。
- C K K S . E n c o d e ( m , Δ ) CKKS.Encode(\mathbf{m},\Delta) CKKS.Encode(m,Δ)
- 对于明文向量 m \mathbf{m} m，首先对其等比放大 ? Δ ? m ? \left\lfloor \Delta \cdot \mathbf{m} \right\rceil ?Δ?m?；
- 接着通过 τ \tau τ映射的逆 τ ? 1 \tau^{-1} τ?1将 ? Δ ? m ? \left\lfloor \Delta \cdot \mathbf{m} \right\rceil ?Δ?m?转化为多项式 m = ? τ ? 1 ( ? Δ ? m ? ) ? m = \left\lfloor \tau ^{-1}(\left\lfloor \Delta \cdot \mathbf{m} \right\rceil) \right\rceil m=?τ?1(?Δ?m?)?
- C K K S . D e c o d e ( m , Δ ) CKKS.Decode(m,\Delta) CKKS.Decode(m,Δ)
- 对于明文多项式 m m m，使用 τ \tau τ映射还原为向量 m \mathbf{m} m并等比缩小 m = ? Δ ? 1 ( ? τ ( m ) ? ) ? \mathbf{m} = \left\lfloor \Delta ^{-1} (\left\lfloor \tau (m) \right\rceil) \right\rceil m=?Δ?1(?τ(m)?)?
- C K K S . E n c p k ( m ) CKKS.Enc_{pk}(m) CKKS.Encpk?(m)
- 采样 v ← Z O ( 0.5 ) v \leftarrow ZO(0.5) v←ZO(0.5)， e 0 , e 1 ← D G ( σ 2 ) e_0,e_1 \leftarrow DG(\sigma ^2) e0?,e1?←DG(σ2)，输出密文： c = v ? p k + ( m + e 0 , e 1 ) ?? ( m o d q L ) \mathbf{c} = v \cdot pk + (m + e_0,e_1)\;(mod q_L) c=v?pk+(m+e0?,e1?)(modqL?)
- C K K S . D e c s k ( c ) CKKS.Dec_{sk}(\mathbf{c}) CKKS.Decsk?(c)
- 对于 c = ( b , a ) \mathbf{c} = (b,a) c=(b,a)，解密算法为 [ ? c , s k ? ] q l [\langle \mathbf{c}, \mathbf{sk}\rangle ]q_l [?c,sk?]ql?，即 m = b + a s ?? ( m o d q l ) m = b + as\;(mod q_l) m=b+as(modql?)
由于CKKS方案在加密时引入了噪声，所以其解密函数生成的明文与原始明文是不同的，但误差的数量级是远远小于明文的，所以该误差是完全可以忽略的。
- C K K S . A d d ( c 1 , c 2 ) CKKS.Add(\mathbf{c_1},\mathbf{c_2}) CKKS.Add(c1?,c2?)
- 对于 c 1 = ( b 1 , a 1 ) \mathbf{c_1} = (b_1,a_1) c1?=(b1?,a1?)， c 2 = ( b 2 , a 2 ) \mathbf{c_2} = (b_2,a_2) c2?=(b2?,a2?)，密文的同态加法为相应位直接相加 c A d d = [ ( b 1 + b 2 , a 1 + a 2 ) ] q l \mathbf{c_{Add}} = [(b_1 + b_2,a_1 + a_2)]q_l cAdd?=[(b1?+b2?,a1?+a2?)]ql?
由于密文的同态乘法会导致密文规模扩大，这将影响到解密算法的执行，从而使得密钥规模随乘法深度的增加而增大。故Cheon等人在方案设计时引入同态乘密钥（ e v k evk evk）实现对乘法密文的缩放，使其规模保持在 R q L 2 R_{q_L}^2 RqL?2?中。
- C K K S . M u l t e v k ( c 1 , c 2 ) CKKS.Mult_{evk}(\mathbf{c_1},\mathbf{c_2}) CKKS.Multevk?(c1?,c2?)
- 对于 c 1 = ( b 1 , a 1 ) \mathbf{c_1} = (b_1,a_1) c1?=(b1?,a1?)， c 2 = ( b 2 , a 2 ) \mathbf{c_2} = (b_2,a_2) c2?=(b2?,a2?)，我们记 ( d 0 , d 1 , d 2 ) = [ ( b 1 b 2 , a 1 b 2 + a 2 b 1 , a 1 a 2 ) ] q l (d_0,d_1,d_2) = [(b_1b_2,a_1b_2 + a_2b_1,a_1a_2)]_{q_l} (d0?,d1?,d2?)=[(b1?b2?,a1?b2?+a2?b1?,a1?a2?)]ql??
- 则 c 1 \mathbf{c_1} c1?、 c 2 \mathbf{c_2} c2?的同态乘法表示为 c M u l t = ( d 0 , d 1 ) + ? P ? 1 ? d 2 ? e v k ? \mathbf{c_{Mult}} = (d_0 , d_1) + \left\lfloor P^{-1} \cdot d_2 \cdot evk \right\rceil cMult?=(d0?,d1?)+?P?1?d2??evk?
但乘法操作会导致噪声增大，从而出现无法正确解密的情况，这时就需要在每次乘法之后进行一个“重缩放”的操作。
- C K K S . R S l → l ′ ( c ) CKKS.RS_{l \to l'}(\mathbf{c}) CKKS.RSl→l′?(c)
- 对于密文 c \mathbf{c} c，我们对其进行“重缩放” c ′ = ? q l ′ q l c ? \mathbf{c'} = \left\lfloor \frac{q'_{l}}{q_l} \mathbf{c} \right\rceil c′=?ql?ql′??c?经“重缩放”后，其密文模数降低为 q l ′ q_l' ql′?。
4.方案改进
在之后的研究中，人们又对该方案进行了不同程度的改进，如下图：
欧密18[7] 给出了CKKS方案的自举方案，欧密19[9] 对其进行了改进；而SAC18[8] 则是提出了CKKS方案的RNS变体，但是其使用的是欧密18中的自举方案，自举精度远达不到实际需求；故在RSA20[10] 中，又结合欧密19中的自举改进对RNS-CKKS方案的自举进行了改进；21年的欧密会上，又有两个方案被相继提出，一个是在RSA20的基础上对自举精度进行了提升[11] ，另一个则是提出了一种新的自举方案[12]，相较之前的方案，精度、效率和安全性上都有了明显的提升。
4.1 自举方案
这里只对欧密18中提到的自举方案进行说明。
由于明文槽上的任意线性变换都可表示为
z
?
A
?
z
+
B
?
z
￣
\mathbf{z} \mapsto A \cdot \mathbf{z} + B \cdot \overline{\mathbf{z}}
z?A?z+B?z，即对于任意线性变换，我们都可以使用两个
N
/
2
N/2
N/2维的矩阵表示。故我们在同态计算编解码操作时需要用到
M
a
t
M
u
l
t
(
c
t
,
A
)
MatMult(\mathbf{ct},A)
MatMult(ct,A)函数以实现同态计算矩阵乘法，其中
c
t
∈
R
q
2
\mathbf{ct} \in R_q^2
ct∈Rq2?并且
A
∈
C
N
/
2
×
N
/
2
A \in \mathbb{C}^{N/2 \times N/2}
A∈CN/2×N/2，这个函数相当于对
c
t
\mathbf{ct}
ct加密的向量
m
\mathbf{m}
m进行了如下的操作：
A
?
m
=
∑
0
?
j
<
N
/
2
(
a
j
⊙
ρ
(
m
;
j
)
)
A \cdot \mathbf{m} = \sum_{0 \leqslant j < N/2} (\mathbf{a}_j \odot \rho (\mathbf{m};j))
A?m=0?j<N/2∑?(aj?⊙ρ(m;j))其中，
⊙
\odot
⊙为向量按位乘法，
ρ
\rho
ρ为循环向左移位。
而对于模运算，Cheon等人首先模运算近似为正弦函数上的运算：
[
t
]
q
=
q
2
π
?
sin
?
(
2
π
q
?
t
)
[t]_q = \frac{q}{2\pi}\cdot \sin (\frac{2\pi}{q}\cdot t)
[t]q?=2πq??sin(q2π??t)
接着，再通过欧拉公式，
{
exp
?
(
i
θ
)
=
cos
?
θ
+
i
sin
?
θ
exp
?
(
?
i
θ
)
=
cos
?
θ
?
i
sin
?
θ
\begin{cases} \exp(i\theta ) = \cos \theta + i \sin \theta \\ \exp(-i\theta ) = \cos \theta - i \sin \theta \end{cases}
{exp(iθ)=cosθ+isinθexp(?iθ)=cosθ?isinθ?将正弦函数上的运算转换到指数函数上的运算：
sin
?
θ
=
1
2
i
exp
?
(
i
θ
)
?
exp
?
(
?
i
θ
)
\sin \theta = \frac{1}{2i} \exp(i\theta) - \exp(-i\theta)
sinθ=2i1?exp(iθ)?exp(?iθ)最后利用文献[4]给出的计算指数函数的算法进行运算即可：
[
t
]
q
=
q
4
π
i
[
exp
?
(
2
π
i
q
t
)
?
exp
?
(
?
2
π
i
q
t
)
]
[t]_q = \frac{q}{4\pi i} [\exp (\frac{2\pi i}{q} t) - \exp (-\frac{2\pi i}{q} t)]
[t]q?=4πiq?[exp(q2πi?t)?exp(?q2πi?t)]
4.2 RNS变体
为了有效地实现多项式运算，Gentry等人基于CRT提出了一种双CRT表示的分圆多项式表示方案[13]。第一层CRT层通过使用RNS将多项式分解成具有较小模的多项式分量。第二层则是通过NTT的方法，将每个小多项式转换为整数向量。在双CRT表示中，任意多项式都可以用由小整数组成的矩阵来识别，并且可以通过执行不同分量的模操作来实现有效的多项式运算。
Cheon等人提出了CKKS方案的RNS变体[9]，实现了在RNS上的近似全同态加密方案，具体算法如下：
- R N S . S e t u p ( q , L , η ) RNS.Setup(q,L,\eta ) RNS.Setup(q,L,η)
- 输入基本整数 q q q，深度 L L L，比特精度 η \eta η；
- 选择一个基 C = { q 0 , q 1 , ? ? , q L } \mathcal{C} = \{q_0,q_1,\cdots,q_L\} C={q0?,q1?,?,qL?}，满足 q / q l ∈ ( 1 ? 2 ? η , 1 + 2 ? η ) q/q_l \in (1 - 2^{-\eta},1 + 2^{-\eta}) q/ql?∈(1?2?η,1+2?η)，并且对于乘法深度为 l l l的密文模数 Q l = ∏ i = 0 l q i Q_l = \prod_{i = 0}^l q_i Ql?=∏i=0l?qi?，其相邻模数模数具有相同的比率 Q l / Q l ? 1 = q l ≈ q Q_l/Q_{l-1} = q_l \approx q Ql?/Ql?1?=ql?≈q；
- 选择一个 K S G e n ( s 1 , s 2 ) KSGen(s_1,s_2) KSGen(s1?,s2?)算法需要的模数 P = ∏ i = 0 k ? 1 p i P = \prod_{i = 0}^{k-1} p_i P=∏i=0k?1?pi?；
- 生成基 D = { p 0 , p 1 , ? ? , p k ? 1 , q 0 , q 1 , ? ? , q l ? 1 } \mathcal{D} = \{p_0,p_1,\cdots,p_{k-1},q_0,q_1,\cdots,q_{l-1}\} D={p0?,p1?,?,pk?1?,q0?,q1?,?,ql?1?}， B = { p 0 , p 1 , ? ? , p k ? 1 } \mathcal{B} = \{p_0,p_1,\cdots,p_{k-1}\} B={p0?,p1?,?,pk?1?}， C l = { q 0 , q 1 , ? ? , q l ? 1 } \mathcal{C}_l = \{q_0,q_1,\cdots,q_{l-1}\} Cl?={q0?,q1?,?,ql?1?}；
- 选择一个2的幂整数 N N N， R \mathbb{R} R上的私钥分布 χ k e y \chi _{key} χkey?，加密参数分布 χ e n c \chi _{enc} χenc?和误差分布 χ e r r \chi _{err} χerr?。
- R N S . K S G e n ( s 1 , s 2 ) RNS.KSGen(s_1,s_2) RNS.KSGen(s1?,s2?)
- 采样 ( a 0 ′ , a 1 ′ , ? ? , a k + L ′ ) ← U ( ∏ i = 0 k ? 1 R p i × ∏ j = 0 L R q j ) (a'_0,a'_1,\cdots,a'_{k + L}) \leftarrow U(\prod_{i = 0}^{k-1}\mathbb{R}_{p_i}\times\prod_{j = 0}^{L}\mathbb{R}_{q_j}) (a0′?,a1′?,?,ak+L′?)←U(∏i=0k?1?Rpi??×∏j=0L?Rqj??)， e ′ ← χ e r r e' \leftarrow \chi _{err} e′←χerr?；
- 对于给定的秘密多项式
s
1
,
s
2
∈
R
s_1,s_2 \in \mathbb{R}
s1?,s2?∈R，计算
当 0 ? i < k 0 \leqslant i < k 0?i<k时， b i ′ = ? a i ′ ? s 2 + e ′ ? m o d ?? p i b'_i = -a'_i\cdot s_2 + e' \ mod\;p_i bi′?=?ai′??s2?+e′?modpi?当 0 ? j ? L 0 \leqslant j \leqslant L 0?j?L时， b k + j ′ = ? a k + j ′ ? s 2 + [ P ] q j ? s 1 + e ′ ? m o d ?? q j b'_{k+j} = -a'_{k+j}\cdot s_2 + [P]_{q_j} \cdot s_1 + e' \ mod\;q_j bk+j′?=?ak+j′??s2?+[P]qj???s1?+e′?modqj? - 输出转换密钥 s w k \mathbf{swk} swk为： s w k = ( s w k 0 , s w k 1 , ? ? , s w k k + L ) ∈ ∏ i = 0 k ? 1 R p i 2 × ∏ j = 0 L R q j 2 \mathbf{swk} = (\mathbf{swk}_0,\mathbf{swk}_1,\cdots,\mathbf{swk}_{k+L}) \in \prod_{i = 0}^{k-1}\mathbb{R}_{p_i}^2\times\prod_{j = 0}^{L}\mathbb{R}_{q_j}^2 swk=(swk0?,swk1?,?,swkk+L?)∈i=0∏k?1?Rpi?2?×j=0∏L?Rqj?2?其中， s w k i = ( b i ′ , a i ′ ) \mathbf{swk}_i = (b'_i,a'_i) swki?=(bi′?,ai′?)。
- R N S . K e y G e n ( ) RNS.KeyGen() RNS.KeyGen()
- 采样 ( a 0 ′ , a 1 ′ , ? ? , a L ′ ) ← U ( ∏ j = 0 L R q j ) (a'_0,a'_1,\cdots,a'_L) \leftarrow U(\prod_{j = 0}^{L}R_{q_j}) (a0′?,a1′?,?,aL′?)←U(∏j=0L?Rqj??)， e ← χ e r r e \leftarrow \chi _{err} e←χerr?， s ← χ k e y s \leftarrow \chi _{key} s←χkey?，并记私钥为 s k = ( 1 , s ) \mathbf{sk} = (1,s) sk=(1,s)；
- 计算 b i = ? a i ? s + e ? m o d ?? q j b_i = -a_i\cdot s + e \ mod\;q_j bi?=?ai??s+e?modqj?， 0 ? j ? L 0 \leqslant j \leqslant L 0?j?L；
- 生成同态乘密钥 e v k = K S G e n ( s 2 , s ) \mathbf{evk} = KSGen(\mathbf{s}^2,\mathbf{s}) evk=KSGen(s2,s)
- R N S . E n c o d e ( m , Δ ) RNS.Encode(\mathbf{m},\Delta) RNS.Encode(m,Δ)
- 对于明文向量 m \mathbf{m} m，首先对其等比放大 ? Δ ? m ? \left\lfloor \Delta \cdot \mathbf{m} \right\rceil ?Δ?m?；
- 接着通过 τ \tau τ映射的逆 τ ? 1 \tau^{-1} τ?1将 ? Δ ? m ? \left\lfloor \Delta \cdot \mathbf{m} \right\rceil ?Δ?m?转化为多项式 m = ? τ ? 1 ( ? Δ ? m ? ) ? m = \left\lfloor \tau ^{-1}(\left\lfloor \Delta \cdot \mathbf{m} \right\rceil) \right\rceil m=?τ?1(?Δ?m?)?
- R N S . D e c o d e ( m , Δ ) RNS.Decode(m,\Delta) RNS.Decode(m,Δ)
- 对于明文多项式 m m m，使用 τ \tau τ映射还原为向量 m \mathbf{m} m并等比缩小 m = ? Δ ? 1 ( ? τ ( m ) ? ) ? \mathbf{m} = \left\lfloor \Delta ^{-1} (\left\lfloor \tau (m) \right\rceil) \right\rceil m=?Δ?1(?τ(m)?)?
- R N S . E n c p k ( m ) RNS.Enc_{\mathbf{pk}}(m) RNS.Encpk?(m)
- 采样 v ← χ e n c v \leftarrow \chi _{enc} v←χenc?， e 0 , e 1 ← χ e r r e_0,e_1 \leftarrow \chi _{err} e0?,e1?←χerr?；
- 输出密文 c t = ( c t 0 , c t 1 , ? ? , c t L ) ∈ ∏ j = 0 L R q j 2 \mathbf{ct} = (\mathbf{ct}_0,\mathbf{ct}_1,\cdots,\mathbf{ct}_L) \in \prod_{j = 0}^{L}\mathbb{R}_{q_j}^2 ct=(ct0?,ct1?,?,ctL?)∈j=0∏L?Rqj?2?其中， c t j = ( v ? p k j + ( m + e 0 , e 1 ) ) ? m o d ?? q j \mathbf{ct}_j = (v \cdot \mathbf{pk}_j + (m + e_0,e_1)) \ mod\;q_j ctj?=(v?pkj?+(m+e0?,e1?))?modqj?。
- R N S . D e c s k ( c t ) RNS.Dec_{\mathbf{sk}}(\mathbf{ct}) RNS.Decsk?(ct)
- 对于密文 c t \mathbf{ct} ct，输出 [ ? c t 0 , s k ? ] q 0 [\left\langle \mathbf{ct}_0,\mathbf{sk}\right\rangle]_{q_0} [?ct0?,sk?]q0??，即 m = b 0 + a 0 ? s ? m o d ?? q 0 m = b_0 + a_0 \cdot s \ mod\;q_0 m=b0?+a0??s?modq0?
之后便是运算部分，由于RNS的特性，在该表征系统上的运算均可分解为各个基上的运算，并且相互独立。故RNS上运算的具体算法展示如下：
- R N S . A d d ( c t , c t ′ ) RNS.Add(\mathbf{ct},\mathbf{ct}') RNS.Add(ct,ct′)
- 给定两个密文 c t , c t ′ ∈ ∏ j = 0 l R q j 2 \mathbf{ct},\mathbf{ct}' \in \prod_{j = 0}^{l}\mathbb{R}_{q_j}^2 ct,ct′∈∏j=0l?Rqj?2?，分别表示为 c t = ( c t 0 , ? ? , c t l ) \mathbf{ct} = (\mathbf{ct}_0,\cdots,\mathbf{ct}_l) ct=(ct0?,?,ctl?)和 c t ′ = ( c t 0 ′ , ? ? , c t l ′ ) \mathbf{ct}' = (\mathbf{ct}'_0,\cdots,\mathbf{ct}'_l) ct′=(ct0′?,?,ctl′?)，RNS上的同态加法是对应位的元素分别相加，即 c t a d d = ( c t a d d 1 , c t a d d 2 , ? ? , c t a d d l , ) \mathbf{ct}_{add} = (\mathbf{ct}_{add_1},\mathbf{ct}_{add_2},\cdots,\mathbf{ct}_{add_l},) ctadd?=(ctadd1??,ctadd2??,?,ctaddl??,)其中， c t a d d i = ( c t i + c t i ′ ) ? m o d ?? q i \mathbf{ct}_{add_i} = (\mathbf{ct}_i + \mathbf{ct}'_i) \ mod\;q_i ctaddi??=(cti?+cti′?)?modqi?。
- R N S . M u l t e v k ( c t , c t ′ ) RNS.Mult_{\mathbf{evk}}(\mathbf{ct},\mathbf{ct}') RNS.Multevk?(ct,ct′)
- 给定两个密文 c t , c t ′ ∈ ∏ j = 0 l R q j 2 \mathbf{ct},\mathbf{ct}' \in \prod_{j = 0}^{l}\mathbb{R}_{q_j}^2 ct,ct′∈∏j=0l?Rqj?2?，分别表示为 c t = ( c t 0 , ? ? , c t l ) \mathbf{ct} = (\mathbf{ct}_0,\cdots,\mathbf{ct}_l) ct=(ct0?,?,ctl?)和 c t ′ = ( c t 0 ′ , ? ? , c t l ′ ) \mathbf{ct}' = (\mathbf{ct}'_0,\cdots,\mathbf{ct}'_l) ct′=(ct0′?,?,ctl′?)；
- 计算 d i 0 = c t i 0 ? c t i 0 ′ ? m o d ?? q j d i 1 = c t i 0 ? c t i 1 ′ + c t i 1 ? c t i 0 ′ ? m o d ?? q j d i 2 = c t i 1 ? c t i 1 ′ ? m o d ?? q j \begin{aligned} \mathbf{d}_{i_0} &= \mathbf{ct}_{i_0} \cdot \mathbf{ct}'_{i_0} \ mod\;q_j\\ \mathbf{d}_{i_1} &= \mathbf{ct}_{i_0} \cdot \mathbf{ct}'_{i_1} + \mathbf{ct}_{i_1} \cdot \mathbf{ct}'_{i_0} \ mod\;q_j\\ \mathbf{d}_{i_2} &= \mathbf{ct}_{i_1} \cdot \mathbf{ct}'_{i_1} \ mod\;q_j \end{aligned} di0??di1??di2???=cti0???cti0?′??modqj?=cti0???cti1?′?+cti1???cti0?′??modqj?=cti1???cti1?′??modqj??
- 使用近似模提升，将 d i 2 \mathbf{d}_{i_2} di2??的基由 C l \mathcal{C}_l Cl?提升到 D l \mathcal{D}_l Dl? M o d u p C l → D l ( d 2 0 , ? ? , d 2 l ) = ( d ~ 2 0 , ? ? , d ~ 2 k ? 1 , d 2 0 , ? ? , d 2 l ) Modup_{\mathcal{C}_l \to \mathcal{D}_l}(\mathbf{d}_{2_0},\cdots,\mathbf{d}_{2_l}) = (\widetilde{\mathbf{d}}_{2_0},\cdots,\widetilde{\mathbf{d}}_{2_{k-1}},\mathbf{d}_{2_0},\cdots,\mathbf{d}_{2_l}) ModupCl?→Dl??(d20??,?,d2l??)=(d 20??,?,d 2k?1??,d20??,?,d2l??)
- 重线性化 c t ~ = ( c t ~ 0 , c t ~ 1 , ? ? , c t ~ k + l ) \widetilde{\mathbf{ct}} = (\widetilde{\mathbf{ct}}_0,\widetilde{\mathbf{ct}}_1,\cdots,\widetilde{\mathbf{ct}}_{k+l}) ct =(ct 0?,ct 1?,?,ct k+l?)其中 c t ~ i = d ~ 2 i ? e v k i ? m o d ?? p i ??? 0 ? i < k c t ~ k + j = d j ? e v k k + j ? m o d ?? q j ??? 0 ? j ? l \begin{aligned} \widetilde{\mathbf{ct}}_i &= \widetilde{\mathbf{d}}_{2_i} \cdot \mathbf{evk}_i \ mod\;p_i \ \ \ 0 \leqslant i < k\\ \widetilde{\mathbf{ct}}_{k+j} &= \mathbf{d}_{j} \cdot \mathbf{evk}_{k+j} \ mod\;q_j \ \ \ 0 \leqslant j \leqslant l \end{aligned} ct i?ct k+j??=d 2i???evki??modpi????0?i<k=dj??evkk+j??modqj????0?j?l?
- 再通过近似模降低，将 c t ~ \widetilde{\mathbf{ct}} ct 的基由 D l \mathcal{D}_l Dl?降低到 C l \mathcal{C}_l Cl? M o d d o w n D l → C l ( c t ~ 0 , ? ? , c t ~ k + l ) = ( c t ^ 0 , ? ? , c t ^ l ) Moddown_{\mathcal{D}_l \to \mathcal{C}_l}(\widetilde{\mathbf{ct}}_0,\cdots,\widetilde{\mathbf{ct}}_{k+l}) = (\widehat{\mathbf{ct}}_0,\cdots,\widehat{\mathbf{ct}}_l ) ModdownDl?→Cl??(ct 0?,?,ct k+l?)=(ct 0?,?,ct l?)
- 输出 c t m u l t = ( c t m u l t 0 , c t m u l t 1 , ? ? , c t m u l t l ) \mathbf{ct}_{mult} = (\mathbf{ct}_{mult_0},\mathbf{ct}_{mult_1},\cdots,\mathbf{ct}_{mult_l}) ctmult?=(ctmult0??,ctmult1??,?,ctmultl??)其中， c t m u l t i = ( c t ^ i 0 + d 0 i , c t ^ i 1 + d 1 i ) ? m o d ?? q i \mathbf{ct}_{mult_i} = (\widehat{\mathbf{ct}}_{i_0} + \mathbf{d}_{0_i},\widehat{\mathbf{ct}}_{i_1} + \mathbf{d}_{1_i}) \ mod\;q_i ctmulti??=(ct i0??+d0i??,ct i1??+d1i??)?modqi?。
- R N S . R S ( c t ) RNS.RS(\mathbf{ct}) RNS.RS(ct)
- 对于 l l l级密文 c t = ( c t 0 , c t 1 , ? ? , c t l ) ∈ ∏ j = 0 l R q j 2 \mathbf{ct} = (\mathbf{ct}_0,\mathbf{ct}_1,\cdots,\mathbf{ct}_l) \in \prod_{j = 0}^{l}\mathbb{R}_{q_j}^2 ct=(ct0?,ct1?,?,ctl?)∈∏j=0l?Rqj?2?，输出 c t ′ = ( c t 0 ′ , c t 1 ′ , ? ? , c t l ? 1 ′ ) ∈ ∏ j = 0 l ? 1 R q j 2 \mathbf{ct}' = (\mathbf{ct}'_0,\mathbf{ct}'_1,\cdots,\mathbf{ct}'_{l-1}) \in \prod_{j = 0}^{l-1}\mathbb{R}_{q_j}^2 ct′=(ct0′?,ct1′?,?,ctl?1′?)∈j=0∏l?1?Rqj?2?其中， c t j ′ = ( q l ? 1 ? ( c 0 j ? c 0 l ) , q l ? 1 ? ( c 1 j ? c 1 l ) ) ? m o d ?? q j \mathbf{ct}'_j = (q_l^{-1} \cdot (c_{0_j} - c_{0_l}),q_l^{-1} \cdot (c_{1_j} - c_{1_l})) \ mod\;q_j ctj′?=(ql?1??(c0j???c0l??),ql?1??(c1j???c1l??))?modqj?。
系列论文我会在下载资源中给出。
参考文献
[1] Rivest R L , Adleman L M , Dertouzos M L . On Data Banks and Privacy Homomorphisms[J]. Foundations of Secure Compuation, 1978.
[2] Gentry C . Fully homomorphic encryption using ideal lattices[J]. Stoc, 2009.
[3] 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.-1
[4] Dijk M V , Gentry C , Halevi S , et al. Fully Homomorphic Encryption over the Integers[C]// International Conference on Theory & Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2010.
[5] Aviad Kipnis E H . 1 Efficient Methods for Practical Fully-Homomorphic Symmetric-key Encryption, Randomization, and Verification[J]. Urban Research & Practice, 2012, 7(3):255-257.
[6] Jschke A , Armknecht F . Accelerating Homomorphic Computations on Rational Numbers[J]. Springer, Cham, 2016.
[7] Cheon J H , Han K , Kim A , et al. Bootstrapping for Approximate Homomorphic Encryption[J]. Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018.-2
[8] Cheon J H , Han K , Kim A , et al. A Full RNS Variant of Approximate Homomorphic Encryption[J]. Selected areas in cryptography :. annual international workshop, SAC. proceedings. SAC (Conference), 11349:347-368.-2
[9] Chen H , Chillotti I , Song Y . Improved Bootstrapping for Approximate Homomorphic Encryption[C]// International Conference on the Theory & Applications of Cryptographic Techniques. Springer, Cham, 2019.-3
[10] Han K , D Ki. Better Bootstrapping for Approximate Homomorphic Encryption[C]// Cryptographers’ Track at the RSA Conference. Springer, Cham, 2020.-4
[11] Lee J W , Lee E , Lee Y , et al. High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function[M]. 2021.-5
[12] Bossuat J P , Mouchet C , Troncoso-Pastoriza J , et al. Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys[M]. 2021.-5
[13] Gentry C , Halevi S , Smart N P . Homomorphic Evaluation of the AES Circuit[C]// Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012.