密码学学习笔记（五）——CKKS同态加密方案

• 1. 提出背景
• 2. 方案原理
• 3. 算法描述
• 4.方案改进
• • 4.1 自举方案
  • 4.2 RNS变体

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]。

同态加密就是在数据仍处于密文的状态下，对密文数据信息进行各种计算，从而使得其结果在变回明文后和对明文进行相应运算时的结果等值。

对于函数 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，将同态乘法带来的密文维数扩张加以控制；最后在同态乘法结束后进行“重缩放”，有效地控制噪声对明文的影响。

设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 + 1rangle 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(-2pi i/M) ζM​=exp(−2πi/M)。方案详细描述如下：

1. 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​)。

2. C K K S . E n c o d e ( m , Δ ) CKKS.Encode(mathbf{m},Delta) CKKS.Encode(m,Δ)

• 对于明文向量 m mathbf{m} m，首先对其等比放大 ⌊ Δ ⋅ m ⌉ leftlfloor Delta cdot mathbf{m} rightrceil ⌊Δ⋅m⌉；
• 接着通过 τ tau τ映射的逆 τ − 1 tau^{-1} τ−1将 ⌊ Δ ⋅ m ⌉ leftlfloor Delta cdot mathbf{m} rightrceil ⌊Δ⋅m⌉转化为多项式 m = ⌊ τ − 1 ( ⌊ Δ ⋅ m ⌉ ) ⌉ m = leftlfloor tau ^{-1}(leftlfloor Delta cdot mathbf{m} rightrceil) rightrceil m=⌊τ−1(⌊Δ⋅m⌉)⌉

3. 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} = leftlfloor Delta ^{-1} (leftlfloor tau (m) rightrceil) rightrceil m=⌊Δ−1(⌊τ(m)⌉)⌉

4. 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​)

5. 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方案在加密时引入了噪声，所以其解密函数生成的明文与原始明文是不同的，但误差的数量级是远远小于明文的，所以该误差是完全可以忽略的。

6. 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​中。

7. 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) + leftlfloor P^{-1} cdot d_2 cdot evk rightrceil cMult​=(d0​,d1​)+⌊P−1⋅d2​⋅evk⌉

但乘法操作会导致噪声增大，从而出现无法正确解密的情况，这时就需要在每次乘法之后进行一个“重缩放”的操作。

8. 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'} = leftlfloor frac{q'_{l}}{q_l} mathbf{c} rightrceil c′=⌊ql​ql′​​c⌉经“重缩放”后，其密文模数降低为 q l ′ q_l' ql′​。

在之后的研究中，人们又对该方案进行了不同程度的改进，如下图：
欧密18^[7] 给出了CKKS方案的自举方案，欧密19^[9] 对其进行了改进；而SAC18^[8] 则是提出了CKKS方案的RNS变体，但是其使用的是欧密18中的自举方案，自举精度远达不到实际需求；故在RSA20^[10] 中，又结合欧密19中的自举改进对RNS-CKKS方案的自举进行了改进；21年的欧密会上，又有两个方案被相继提出，一个是在RSA20的基础上对自举精度进行了提升^[11] ，另一个则是提出了一种新的自举方案^[12]，相较之前的方案，精度、效率和安全性上都有了明显的提升。

这里只对欧密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

而对于模运算，Cheon等人首先模运算近似为正弦函数上的运算： [ t ] q = q 2 π ⋅ sin ⁡ ( 2 π q ⋅ t ) [t]_q = frac{q}{2pi}cdot sin (frac{2pi}{q}cdot t) [t]q​=2πq​⋅sin(q2π​⋅t)

接着，再通过欧拉公式， { exp ⁡ ( i θ ) = cos ⁡ θ + i sin ⁡ θ exp ⁡ ( − i θ ) = cos ⁡ θ − i sin ⁡ θ begin{cases} exp(itheta ) = cos theta + i sin theta \ exp(-itheta ) = 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(itheta) - exp(-itheta) 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}{4pi i} [exp (frac{2pi i}{q} t) - exp (-frac{2pi i}{q} t)] [t]q​=4πiq​[exp(q2πi​t)−exp(−q2πi​t)]

为了有效地实现多项式运算，Gentry等人基于CRT提出了一种双CRT表示的分圆多项式表示方案[13]。第一层CRT层通过使用RNS将多项式分解成具有较小模的多项式分量。第二层则是通过NTT的方法，将每个小多项式转换为整数向量。在双CRT表示中，任意多项式都可以用由小整数组成的矩阵来识别，并且可以通过执行不同分量的模操作来实现有效的多项式运算。

Cheon等人提出了CKKS方案的RNS变体[9]，实现了在RNS上的近似全同态加密方案，具体算法如下：

1. 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​。

2. 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}timesprod_{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
• 输出转换密钥 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}^2timesprod_{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′​)。

3. 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_icdot 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)

4. R N S . E n c o d e ( m , Δ ) RNS.Encode(mathbf{m},Delta) RNS.Encode(m,Δ)

• 对于明文向量 m mathbf{m} m，首先对其等比放大 ⌊ Δ ⋅ m ⌉ leftlfloor Delta cdot mathbf{m} rightrceil ⌊Δ⋅m⌉；
• 接着通过 τ tau τ映射的逆 τ − 1 tau^{-1} τ−1将 ⌊ Δ ⋅ m ⌉ leftlfloor Delta cdot mathbf{m} rightrceil ⌊Δ⋅m⌉转化为多项式 m = ⌊ τ − 1 ( ⌊ Δ ⋅ m ⌉ ) ⌉ m = leftlfloor tau ^{-1}(leftlfloor Delta cdot mathbf{m} rightrceil) rightrceil m=⌊τ−1(⌊Δ⋅m⌉)⌉

5. 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} = leftlfloor Delta ^{-1} (leftlfloor tau (m) rightrceil) rightrceil m=⌊Δ−1(⌊τ(m)⌉)⌉

6. 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​。

7. 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 [leftlangle mathbf{ct}_0,mathbf{sk}rightrangle]_{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上运算的具体算法展示如下：

8. 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​。

9. 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
• 再通过近似模降低，将 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​。

11. 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.