全同态加密知识体系整理

文章由AdijeShen整理，供个人学习使用。

整理了到2022年为止，同态加密比较重要的知识和方法。

文章目录 引基础知识基于RLWE的同态加密方案(BGV,BFV,CKKS)通用的格式效率和功能方面加解密流程私钥加密流程 E n c s k Enc_{sk} Encsk​公钥加密流程 E n c p k Enc_{pk} Encpk​解密 D e c s k Dec_{sk} Decsk​ 同态性质加法明文密文加明文密文乘乘法密钥替换（重现性化） 噪声控制模数替换Modulus Switching（CKKS，BGV）Scale Invariant（BFV）总结 Bootstrapping（通用方法）编码（SIMD,encoding）基于NTT&FFT基于FFT的编码（CKKS）基于NTT的编码（BGV，BFV）总结 密钥替换的应用2：自同构（旋转，置换） FHEW类型同态加密BlindRotateFunctional Bootstrapping 同态加密应用隐私集合求交PSI隐匿查询PIR作为MPC的组件作为FL的组件 通用的优化方法计算效率（RNS，NTT，Montgomery）通信开销（随机种子，模数替换） 前沿研究CKKS的安全性问题将FHEW类型的密文和RLWE类型的同态加密结合研究如何进行快速的Bootstrapping将RLWE类型的同态加密与MPC结合，通过MPC实现Bootstrapping过程 同态加密参数（实现相关）推荐参数参数与效率代码中参数的解释开源库效率测试：SEAL Lattigo

引

我将现代的FHE技术视作两类，一种是基于RLWE的层次同态加密（LHE），包括了BGV，BFV和CKKS，这种方案一般来说支持多项式打包技术，可以一次性运算（加法乘法）多个数据，效率上较高，但LHE目前来说Bootstrapping开销比较大，一般来说只当作支持有限次数的运算的同态加密方法使用。

而第二类技术以FHEW和TFHE为代表的高效自举（Bootstrapping）技术，但问题在于这类的方案对于多项式打包并不友好。但也有优势，对于LHE类型的方案来说，只支持加法和乘法 *** 作，对于一下非多项式的函数，比如激活函数，需要使用高次多项式拟合。而第FHEW类型的方案可以在自举的同时运算一个任意的函数。

基础知识

用粗体小写 a \bf a a来表示一个向量，小写 a a a表示一个标量或者多项式， R q R_q Rq​表示一个模 q q q和模 X n + 1 X^n+1 Xn+1多项式环， ∥ a ∥ ∞ \|a\|_{\infty} ∥a∥∞​表示向量或多项式的无穷范数，即 a a a中的最大项。 σ \sigma σ表示一个随机分布（一般具体为高斯分布）。

多项式环：

R R R：定义为 Z   m o d   X n + 1 \Z \bmod X^{n}+1 ZmodXn+1，

R q R_q Rq​， R t R_t Rt​，包含参数 n n n， q q q， t t t。

R q : R   m o d   q R_q: R \bmod q Rq​:Rmodq。

一般形式： ∑ i ∈ [ 0... n − 1 ] a i ⋅ x i , a i ∈ Z q \sum_{i\in[0...n-1]}a_i\cdot x^{i},a_i \in \Z_q ∑i∈[0...n−1]​ai​⋅xi,ai​∈Zq​。

例子：

n=8， 16 x 7 + 2 x 6 + ⋯ + 15 x + 2 ∈ R 17 16x^7+2x^6+\cdots+15x+2\in R_{17} 16x7+2x6+⋯+15x+2∈R17​。

一般来说明文空间为 R t R_t Rt​或 R R R，密文空间为 R q 2 R_q^2 Rq2​。

L W E \sf LWE LWE问题：

有一个秘密向量 s \bf s s，给定多组 ( a , b ) ∈ Z q n + 1 (\mathbf{a},b)\in \Z_q^{n+1} (a,b)∈Zqn+1​，其中 a ∈ Z q n {\bf a} \in {\Z}_q^{n} a∈Zqn​是随机选取的向量 b = ⟨ a , s ⟩ + e b=\langle {\bf a,s} \rangle+e b=⟨a,s⟩+e， e ∈ σ e \in \sigma e∈σ，通过 ( a , b ) ({\bf a},b) (a,b)推出 s \bf s s是困难的。

R L W E \sf RLWE RLWE问题：

有一个秘密多项式 s s s，给定多组 ( a , b ) ∈ R q 2 (a,b)\in R_q^2 (a,b)∈Rq2​，其中 a ∈ R q a\in R_q a∈Rq​是随机选取的多项式， b = a s + e b=as+e b=as+e， e ∈ σ n e\in \sigma^{n} e∈σn，通过 ( a , b ) (a,b) (a,b)推出 s s s是困难的。

基于RLWE的同态加密方案(BGV,BFV,CKKS) 通用的格式

RLWE类型的同态加密（BGV，BFV，CKKS）密文的通用格式为 c t = ( c 0 , c 1 ) ∈ R q 2 {\sf ct}=(c_0,c_1)\in R_q^2 ct=(c0​,c1​)∈Rq2​，有时候也写作 c t = ( a , b ) {\sf ct}=(a,b) ct=(a,b)，其中 b = a s + e + m b=as+e+m b=as+e+m。

这里三个方案有一点小小的区别：

BGV的明文空间为 R t R_t Rt​，密文格式为 ( a , a s + t e + m ) (a,as+te+m) (a,as+te+m)，

BFV的明文空间为 R t R_t Rt​，密文格式为 ( a , a s + e + Δ m ) , Δ = ⌊ q t ⌋ (a,as+e+\Delta m), \Delta = \lfloor\frac{q}{t}\rfloor (a,as+e+Δm),Δ=⌊tq​⌋，

CKKS的明文空间为 R R R，密文格式为 ( a , a s + e + Δ m ) , Δ = 2 k (a,as+e+\Delta m), \Delta=2^k (a,as+e+Δm),Δ=2k。

注意到BFV和CKKS中 Δ \Delta Δ的定义是不一致的，BFV中 Δ \Delta Δ作用是为了与BGV中的 t t t类似，是为了保证明文空间 R t R_t Rt​范围内解密的精确性。

而CKKS中 Δ \Delta Δ是为了能够在 Z q \Z_q Zq​中表示浮点数，以(k=10)的情况为例，可用 1280 1280 1280表示 1.25 ⋅ 2 10 1.25\cdot 2^{10} 1.25⋅210。在应用中， k k k可以取到60。

效率和功能方面

目前来说，我会把BGV和BFV放在一类，都是对于整数( Z t \Z_t Zt​)的同态加密方案。他们的计算能力（即噪声增长）和性能都差不多，在 t > 2 16 t>2^{16} t>216时，BGV效率会更优一些。但BFV的易用度要高于BGV，因为BGV的模数会不断变小，处理不同模数下密文之间的 *** 作会比较麻烦，而BFV的模数是保持不变的。 t t t最小取 2 2 2，最大取 ∼ 2 59 \sim2^{59} ∼259

但由于BGV特殊的modulus switching机制，所以对于模数的选取有特殊要求，因此很多开源库没有实现BGV。都是将CKKS和BFV实现了，这两个协议可以共用一套参数（ R q R_q Rq​相同）。

可参考资料：BGV与BFV对比

对于CKKS来说，他的主要优势在于可以计算浮点数或者说复数 C \mathbb{C} C（但复数使用较少），效率方面与BGV和BFV相差不多，但有对于浮点数的计算有误差存在，不像BGV和BFV是精确的加密。

总结：三者的效率差不多。BGV和BFV是整数方案，精确。CKKS支持浮点数，不精确。

---

加解密流程

下面以CKKS举例说明一下RLWE类型密文的加密解密过程：

私钥加密流程 E n c s k Enc_{sk} Encsk​

公开参数：多项式环 R q R_q Rq​，包含模数 q q q，多项式的阶 n n n。高斯分布 σ \sigma σ

输入：私钥 s s s，明文 m m m。

输出：密文 c t = ( c 0 , c 1 ) {\sf ct}=(c_0,c_1) ct=(c0​,c1​)。有时写作 c t = ( a , b ) {\sf ct}=(a,b) ct=(a,b)，也有文章会写 c t = ( b , − a ) {\sf ct}=(b,-a) ct=(b,−a)，表达的意思是一致的。

过程：

选取随机的多项式 a ← R q a\gets R_q a←Rq​，以及 e ← σ e\gets \sigma e←σ，返回密文 c t = ( a , a s + Δ m + e ) {\sf ct}=(a,as+\Delta m+e) ct=(a,as+Δm+e)。

三个加密方案的区别在于第二步， a s + t e + m as+te+m as+te+m或 a s + Δ m + e as+\Delta m +e as+Δm+e

目前私钥 s s s一般是从 { 0 , 1 , − 1 } \{0,1,-1\} {0,1,−1}系数的多项式中选取，安全性与 s s s从 R q R_q Rq​中随机分布一致。

BFV和BGV中要求 t ≡ 1   m o d   2 n t\equiv 1 \bmod 2n t≡1mod2n，涉及到NTT编码

公钥加密流程 E n c p k Enc_{pk} Encpk​

输入：公钥 p k = E n c s k ( 0 ) = ( a , a s + t e ) pk = Enc_{sk}(0)=(a,as+te) pk=Encsk​(0)=(a,as+te)，明文 m m m。

输出：密文 c t = ( c 0 , c 1 ) {\sf ct}=(c_0,c_1) ct=(c0​,c1​)。

过程：

随机选取一个多项式 u ∈ { 0 , 1 } n u\in \{0,1\}^n u∈{0,1}n，以及 e 0 ← σ , e 1 ← σ e_0\gets \sigma,e_1\gets \sigma e0​←σ,e1​←σ， c t = ( u ⋅ p k 0 + e 0 , u ⋅ p k 1 + Δ m + e 1 ) {\sf ct}=(u\cdot pk_0+e_0,u\cdot pk_1+\Delta m+e_1) ct=(u⋅pk0​+e0​,u⋅pk1​+Δm+e1​)。 解密 D e c s k Dec_{sk} Decsk​

通用的解密公式为 c 1 − c 0 s   m o d   q c_1-c_0s \bmod q c1​−c0​smodq，

以私钥的CKKS为例，

c 1 − c 0 s ≡ Δ m + e   m o d   q c_1-c_0s \equiv \Delta m+e \bmod q c1​−c0​s≡Δm+emodq （私钥）or c 1 − c 0 s = Δ m + v   m o d   q c_1-c_0s = \Delta m+v \bmod q c1​−c0​s=Δm+vmodq (公钥)

要求 ∥ Δ m + e ∥ ∞ < q \|\Delta m+e\|_{\infty} < q ∥Δm+e∥∞​<q才可以正确的解密。这里的 ∥ e ∥ ∞ \|e\|_{\infty} ∥e∥∞​叫做噪声项。

如果采用的是中心取模，即 [ 0 , q / 2 ) [0,q/2) [0,q/2)表示正数 ( q / 2 , q ) (q/2,q) (q/2,q)表示负数的情况下，额外要求： ∥ Δ m + e ∥ ∞ < q / 2 \|\Delta m+e\|_{\infty}∥Δm+e∥∞​<q/2。

这里三个方案有点区别：

BGV计算 c 1 − c 0 s   m o d   q c_1-c_0s \bmod q c1​−c0​smodq后得到 m + t e m+te m+te，通过模 t t t来实现去掉噪声，得到 m ′ = ( m + t e   m o d   q )   m o d   t m'=(m+te \bmod q)\bmod t m′=(m+temodq)modt
​ 要求 ∥ ( t + 1 ) e ∥ ∞ < q / 2 → ∥ e ∥ ∞ < q / 2 t − 1 / 2 \|(t+1)e\|_{\infty}∥(t+1)e∥∞​<q/2→∥e∥∞​<q/2t−1/2。

BFV计算 c 1 − c 0 s   m o d   q c_1-c_0s\bmod q c1​−c0​smodq后得到 Δ m + e   m o d   q \Delta m+e \bmod q Δm+emodq，其中 Δ = ⌊ q / t ⌋ \Delta = \lfloor q/t \rfloor Δ=⌊q/t⌋，是通过乘 t / q t/q t/q然后四舍五入取整得到 m ′ = ⌊ m + t e / q + r ⌉ , r = q / t − ⌊ q / t ⌉ m'=\lfloor m + te/q + r\rceil, r=q/t-\lfloor q/t \rceil m′=⌊m+te/q+r⌉,r=q/t−⌊q/t⌉，
要求 ∥ t e / q + r ∥ ∞ < 1 / 2 → ∥ e ∥ ∞ < q / 2 t − r / 2 \|te/q+r\|_{\infty}<1/2\to \|e\|_{\infty}∥te/q+r∥∞​<1/2→∥e∥∞​<q/2t−r/2。

CKKS计算 c 1 − c 0 s   m o d   q c_1-c_0s \bmod q c1​−c0​smodq后得到 Δ m + e   m o d   q \Delta m +e\bmod q Δm+emodq，其中 Δ = 2 k \Delta = 2^{k} Δ=2k，直接除 Δ \Delta Δ来得到明文 m ′ = m + e / Δ m'=m+e/\Delta m′=m+e/Δ，
​ 要求 ∥ e ∥ ∞ < q / 2 \|e\|_{\infty}∥e∥∞​<q/2才能解密。

注意到CKKS和BGV，BFV的主要区别在于，CKKS直接将噪声项作为了解密后明文的一部分，所以CKKS是无法解密得到精确解的。

比如说，用CKKS加密 2.5 2.5 2.5，令 Δ = 2 30 \Delta = 2^{30} Δ=230， e = 18 e=18 e=18，那么解密后得到 2 30 ⋅ 2.5 + 18 2 30 = 2.5000000167638063 \frac{2^{30}\cdot 2.5 + 18}{2^{30}}=2.5000000167638063 230230⋅2.5+18​=2.5000000167638063，因此称CKKS是一个近似加密的，其中精度与 Δ \Delta Δ相关。

但精度越大，能做的乘法次数就越少。数量级关系差不多是 log ⁡ q / log ⁡ Δ \log q/\log \Delta logq/logΔ次乘法。

同态性质 加法

两个密文 c t 0 = ( a 0 , b 0 ) , c t 1 = ( a 1 , b 1 ) {\sf ct_0} = (a_0,b_0),{\sf ct_1}=(a_1,b_1) ct0​=(a0​,b0​),ct1​=(a1​,b1​)， b i = a i s + Δ m i + e i b_i=a_i s +\Delta m_i+ e_i bi​=ai​s+Δmi​+ei​，

c t a d d = ( a a d d = a 0 + a 1 , b a d d = b 0 + b 1 ) {\sf ct_{add}}=(a_{add}=a_0+a_1,b_{add}=b_0+b_1) ctadd​=(aadd​=a0​+a1​,badd​=b0​+b1​)，

解密：
b a d d − a a d d ⋅ s = a 0 s + Δ m + e 0 + a 1 s + Δ m + e 1 − a 0 s − a 1 s = Δ ( m 0 + m 1 ) + ( e 0 + e 1 ) \begin{aligned} b_{add}-a_{add}\cdot s&=a_0s + \Delta m +e_0 + a_1s + \Delta m +e_1-a_0s-a_1s\ &=\Delta(m_0+m_1) + (e_0+e_1) \end{aligned} badd​−aadd​⋅s​=a0​s+Δm+e0​+a1​s+Δm+e1​−a0​s−a1​s=Δ(m0​+m1​)+(e0​+e1​)​
加法的噪声是原来的两倍

明文密文加

考虑密文 c t = ( a , b = a s + Δ m 0 + e ) {\sf ct}=(a,b=as+\Delta m_0 + e) ct=(a,b=as+Δm0​+e)，明文 m 1 m_1 m1​。

c t a d d = ( a , b + m 1 ) {\sf ct}_{add}=(a,b+m_1) ctadd​=(a,b+m1​)。

没有引入额外的噪声项，噪声是不变的。

明文密文乘

考虑密文 c t = ( a , b = a s + Δ m 0 + e ) {\sf ct}=(a,b=as+\Delta m_0 + e) ct=(a,b=as+Δm0​+e)，明文 m 1 m_1 m1​。

c t a d d = ( a ⋅ m 1 , b ⋅ m 1 ) {\sf ct}_{add}=(a\cdot m_1,b\cdot m_1) ctadd​=(a⋅m1​,b⋅m1​)。

解密：
b ⋅ m 1 − a ⋅ m 1 ⋅ s = a ⋅ m 1 ⋅ s + Δ m 0 m 1 + m 1 e − a ⋅ m 1 ⋅ s = Δ m 0 m 1 + m 1 e \begin{aligned} b\cdot m_1-a\cdot m_1 \cdot s&=a\cdot m_1\cdot s + \Delta m_0 m_1 + m_1e- a\cdot m_1\cdot s\ &=\Delta m_0 m_1+m_1 e \end{aligned} b⋅m1​−a⋅m1​⋅s​=a⋅m1​⋅s+Δm0​m1​+m1​e−a⋅m1​⋅s=Δm0​m1​+m1​e​
噪声大小变为 m 1 m_1 m1​倍。

乘法

考虑两个密文 c t 0 = ( a 0 , b 0 = a 0 s + Δ m 0 + e 0 ) , c t 1 = ( a 1 , b 1 = a 1 s + Δ m 1 + e 1 ) {\sf ct_0}=(a_0,b_0=a_0s+\Delta m_0+e_0),{\sf ct}_{1}=(a_1,b_1=a_1s+\Delta m_1 + e_1) ct0​=(a0​,b0​=a0​s+Δm0​+e0​),ct1​=(a1​,b1​=a1​s+Δm1​+e1​)，

乘法密文为 c t m u l = ( a 0 a 1 , a 0 b 1 + a 1 b 0 , b 0 b 1 ) = ( f , g , h ) {\sf ct}_{mul}=(a_0a_1,a_0b_1+a_1b_0,b_0b_1)=(f,g,h) ctmul​=(a0​a1​,a0​b1​+a1​b0​,b0​b1​)=(f,g,h)。

解密：
f ⋅ s 2 − g ⋅ s + h = a 0 a 1 s 2 − a 0 b 1 s − a 1 b 0 s + b 0 b 1 = ( b 0 − a 0 s ) ( b 1 − a a s ) = ( Δ m 0 + e 0 ) ( Δ m 1 + e 1 ) = Δ 2 m 0 m 1 + e 0 e 1 \begin{aligned} f\cdot s^2-g\cdot s + h&=a_0a_1 s^2 - a_0b_1s- a_1b_0s + b_0b_1\ &=(b_0-a_0s)(b_1-a_as)\ &=(\Delta m_0 + e_0)(\Delta m_1+e_1)\ &=\Delta^2m_0m_1 + e_0e_1 \end{aligned} f⋅s2−g⋅s+h​=a0​a1​s2−a0​b1​s−a1​b0​s+b0​b1​=(b0​−a0​s)(b1​−aa​s)=(Δm0​+e0​)(Δm1​+e1​)=Δ2m0​m1​+e0​e1​​

噪声大小是原来的平方，如何将 Δ 2 \Delta ^2 Δ2变回 Δ \Delta Δ将在噪声控制节中讲述。

密钥替换（重现性化）

思路：

有一个密文 c t = ( a , b = a s + Δ m + e ) {\sf ct}=(a,b=as+\Delta m +e) ct=(a,b=as+Δm+e)，要将其转换为由密钥 s ′ s' s′加密的密文，步骤如下：

输入：密文 c t {\sf ct} ct，转换密钥 k s k = ( a k , b k = a k s ′ + s + e k ) ksk=(a_k,b_k=a_ks'+s+e_k) ksk=(ak​,bk​=ak​s′+s+ek​)，相当于用 s ′ s' s′加密的 s s s。

输出： c t ′ = ( 0 , b ) − a ⋅ k s k = ( a ′ = − a ⋅ a k , b ′ = b − a ⋅ b k ) {\sf ct}'=(0,b)-a\cdot ksk=(a'=-a\cdot a_k,b'=b-a\cdot b_k) ct′=(0,b)−a⋅ksk=(a′=−a⋅ak​,b′=b−a⋅bk​)。

正确性：
b ′ − a ′ s ′ = ( b − a ⋅ b k ) − ( − a ⋅ a k ) ⋅ s = a s + Δ m + e − a ( a k s ′ + s + e k ) + a ⋅ a k s = Δ m + e − a e k \begin{aligned} b'-a's'&=(b-a\cdot b_k)-(-a\cdot a_k)\cdot s\ &=as+\Delta m +e - a(a_ks' + s +e_k) + a\cdot a_k s\ &=\Delta m +e- ae_k \end{aligned} b′−a′s′​=(b−a⋅bk​)−(−a⋅ak​)⋅s=as+Δm+e−a(ak​s′+s+ek​)+a⋅ak​s=Δm+e−aek​​
但问题不能直接这么做，问题在于 a ∈ R q a\in R_q a∈Rq​， ∥ a ∥ ∞ ≈ q \|a\|_{\infty}\approx q ∥a∥∞​≈q，噪声大小会直接超过 q q q，解密会失败。

---

正确算法：

因此一般KeySwitch都采用分解方法。分为 D e c o m p B ( a ) Decomp_B(a) DecompB​(a)和 P o w B ( a ) Pow_B(a) PowB​(a)：分别为：

D e c o m p B ( a ) : [ d 0 , d 1 , d 2 , . . . , d ℓ ] , ℓ = l o g B ( q ) ， ∑ i ∈ [ ℓ ] d i ⋅ B i = a P o w B ( a ) : [ p 0 , p 1 , p 2 , . . . , p ℓ ] , ℓ = l o g B ( q ) ， p i = a ⋅ B i Decomp_B(a):[d_0,d_1,d_2,...,d_\ell],\ell=log_B(q)，\sum_{i\in [\ell]}d_i\cdot B^i=a\ Pow_B(a):[p_0,p_1,p_2,...,p_\ell],\ell =log_B(q)，p_i=a\cdot B^i DecompB​(a):[d0​,d1​,d2​,...,dℓ​],ℓ=logB​(q)，i∈[ℓ]∑​di​⋅Bi=aPowB​(a):[p0​,p1​,p2​,...,pℓ​],ℓ=logB​(q)，pi​=a⋅Bi
显然可以得到 a ⋅ s = ⟨ D e c o m p B ( a ) ⋅ P o w B ( s ) ⟩ a\cdot s=\langle Decomp_B(a)\cdot Pow_B(s)\rangle a⋅s=⟨DecompB​(a)⋅PowB​(s)⟩。

经过分解的转换算法：

输入：密文 c t {\sf ct} ct，转换密钥 k s k = ( a k ⃗ , b k ⃗ = a k ⃗ s ′ + P o w ( s ) + e k ⃗ ) ∈ R q 2 ⋅ ℓ ksk=(\vec{a_k},\vec{b_k}=\vec{a_k}s'+ Pow(s)+\vec{e_k})\in R_q^{2\cdot \ell} ksk=(ak​ ​,bk​ ​=ak​ ​s′+Pow(s)+ek​ ​)∈Rq2⋅ℓ​。

输出： c t ′ = ( 0 , b ) − ⟨ D e c o m p ( a ) , k s k ⟩ = ( a ′ = − ⟨ D e c o m p ( a ) , a k ⃗ ⟩ , b ′ = b − ⟨ D e c o m p ( a ) , b k ⃗ ⟩ ) {\sf ct}'=(0,b)- \langle Decomp(a),ksk \rangle = (a'=- \langle Decomp(a),\vec{a_k}\rangle , b'=b-\langle Decomp(a),\vec{b_k}\rangle) ct′=(0,b)−⟨Decomp(a),ksk⟩=(a′=−⟨Decomp(a),ak​ ​⟩,b′=b−⟨Decomp(a),bk​ ​⟩)

正确性：
b ′ − a ′ s ′ = b − ⟨ D e c o m p ( a ) , b k ⃗ ⟩ − ⟨ D e c o m p ( a ) , a k ⃗ ⟩ ⋅ s ′ = b − ( ⟨ D e c o m p ( a ) , a k ⃗ s ′ ⟩ + ⟨ D e c o m p ( a ) , P o w ( s ) ⟩ + ⟨ D e c o m p ( a ) , e k ⃗ ⟩ ) − ⟨ D e c o m p ( a ) , a k ⃗ s ′ ⟩ = b − a s − ⟨ D e c o m p ( a ) , e k ⃗ ⟩ = Δ m + e − ⟨ D e c o m p ( a ) , e k ⃗ ⟩ \begin{aligned} b' -a's' &= b -\langle Decomp(a),\vec{b_k}\rangle - \langle Decomp(a),\vec{a_k}\rangle \cdot s'\ &=b-(\langle Decomp(a),\vec{a_k}s'\rangle + \langle Decomp(a),Pow(s)\rangle + \langle Decomp(a),\vec{e_k}\rangle) - \langle Decomp(a),\vec{a_k}s'\rangle\ &=b-as- \langle Decomp(a),\vec{e_k}\rangle\ &=\Delta m + e - \langle Decomp(a),\vec{e_k}\rangle \end{aligned} b′−a′s′​=b−⟨Decomp(a),bk​ ​⟩−⟨Decomp(a),ak​ ​⟩⋅s′=b−(⟨Decomp(a),ak​ ​s′⟩+⟨Decomp(a),Pow(s)⟩+⟨Decomp(a),ek​ ​⟩)−⟨Decomp(a),ak​ ​s′⟩=b−as−⟨Decomp(a),ek​ ​⟩=Δm+e−⟨Decomp(a),ek​ ​⟩​
这个噪声项 ⟨ D e c o m p ( a ) , e k ⃗ ⟩ \langle Decomp(a),\vec{e_k}\rangle ⟨Decomp(a),ek​ ​⟩是远远小于没分解时的噪声项 a e k ae_k aek​的。

例子：

若 q = 13 q=13 q=13， B = 2 B=2 B=2， a = 10 a=10 a=10， e = 3 e=3 e=3，

那么未分解时的噪声是 a e = 30 ae=30 ae=30，

分解之后的噪声是 D e c o m p ( a ) = [ 1 , 0 , 1 , 0 ] Decomp(a)=[1,0,1,0] Decomp(a)=[1,0,1,0]， ⟨ D e c o m p ( a ) , e ⃗ ⟩ = 6 \langle Decomp(a),\vec{e}\rangle = 6 ⟨Decomp(a),e ⟩=6。

在最坏的情况下（即 D e c o m p Decomp Decomp数组全是1），也可以将原本增大 q q q倍的噪声缩小为增大 l o g B ( q ) log_B(q) logB​(q)倍。

---

密钥替换的应用1：（重现性化）

在做完一次乘法之后，乘法密文变为了 c t m u l = ( a 0 a 1 , a 0 b 1 + a 1 b 0 , b 0 b 1 ) = ( f , g , h ) {\sf ct}_{mul}=(a_0a_1,a_0b_1+a_1b_0,b_0b_1)=(f,g,h) ctmul​=(a0​a1​,a0​b1​+a1​b0​,b0​b1​)=(f,g,h)。

可以通过密钥替换的方法，让 c t m u l ′ = ( a ′ , b ′ ) {\sf ct}_{mul}'=(a',b') ctmul′​=(a′,b′)，满足 b ′ − a ′ s = b 0 b 1 − ( a 0 b 1 + a 1 b 0 ) s + a 0 a 1 s 2 b'-a's=b_0b_1-(a_0b_1+a_1b_0)s+a_0a_1s^2 b′−a′s=b0​b1​−(a0​b1​+a1​b0​)s+a0​a1​s2。

输入：密文 c t m u l = ( a 0 a 1 , a 0 b 1 + a 1 b 0 , b 0 b 1 ) = ( f , g , h ) {\sf ct}_{mul}=(a_0a_1,a_0b_1+a_1b_0,b_0b_1)=(f,g,h) ctmul​=(a0​a1​,a0​b1​+a1​b0​,b0​b1​)=(f,g,h)，替换密钥 r l k = ( a k , b k = a k s + s 2 + e k ) rlk=(a_k,b_k=a_ks+s^2+e_k) rlk=(ak​,bk​=ak​s+s2+ek​)，为了书写简单，没有写成Decomp形式，可自行替换。

过程：
c t m u l ′ = ( g , h ) + a 0 a 1 ⋅ ( r l k ) = ( a 0 b 1 + a 1 b 0 + a 0 a 1 ⋅ a k , b 0 b 1 + a 0 a 1 ⋅ b k ) \begin{aligned} {\sf ct}_{mul}'&= (g,h)+a_0a_1\cdot (rlk)\ &=(a_0b_1 + a_1b_0 + a_0a_1 \cdot a_k, b_0b_1+a_0a_1\cdot b_k) \end{aligned} ctmul′​​=(g,h)+a0​a1​⋅(rlk)=(a0​b1​+a1​b0​+a0​a1​⋅ak​,b0​b1​+a0​a1​⋅bk​)​
正确性：
b ′ − a ′ s = b 0 b 1 + a 0 a 1 ⋅ ( a k s + s 2 + e k ) − ( a 0 b 1 + a 1 b 0 + a 0 a 1 a k ) s = b 0 b 1 + a 0 a 1 a k s + a 0 a 1 s 2 + a 0 a 1 e k − a 0 b 1 s − a 1 b 0 s − a 0 a 1 a k s = b 0 b 1 − a 0 b 1 s − a 1 b 0 s + a 0 a 1 s 2 + a 0 a 1 e k = ( b 0 − a 0 s ) ( b 1 − a 1 s ) + a 0 a 1 e k = ( Δ m 0 + e 0 ) ( Δ m 1 + e 1 ) + a 0 a 1 e k \begin{aligned} b'-a's&=b_0b_1+a_0a_1 \cdot (a_ks+s^2+e_k) - (a_0b_1+a_1b_0+a_0a_1a_k)s\ &=b_0b_1+a_0a_1a_ks+a_0a_1s^2+a_0a_1e_k-a_0b_1s-a_1b_0s-a_0a_1a_ks\ &=b_0b_1-a_0b_1s-a_1b_0s+a_0a_1s^2+a_0a_1e_k\ &=(b_0-a_0s)(b_1-a_1s)+a_0a_1e_k\ &=(\Delta m_0+e_0)(\Delta m_1+e_1)+a_0a_1e_k\ \end{aligned} b′−a′s​=b0​b1​+a0​a1​⋅(ak​s+s2+ek​)−(a0​b1​+a1​b0​+a0​a1​ak​)s=b0​b1​+a0​a1​ak​s+a0​a1​s2+a0​a1​ek​−a0​b1​s−a1​b0​s−a0​a1​ak​s=b0​b1​−a0​b1​s−a1​b0​s+a0​a1​s2+a0​a1​ek​=(b0​−a0​s)(b1​−a1​s)+a0​a1​ek​=(Δm0​+e0​)(Δm1​+e1​)+a0​a1​ek​​
注意，如果使用了比特分解，那么最后的噪声项为 ⟨ D e c o m p ( a 0 a 1 ) , e k ⃗ ⟩ \langle Decomp(a_0a_1),\vec{e_k} \rangle ⟨Decomp(a0​a1​),ek​ ​⟩

噪声控制 模数替换Modulus Switching（CKKS，BGV）

这里主要讲一下CKKS的MS过程，关于BGV的MS，可以参考这个链接

注意到，在CKKS方案中，做完了一次乘法之后，解密完的密文变为了： Δ 2 m 0 m 1 + Δ ( e 0 + e 1 ) + e 0 e 1   m o d   q \Delta^2m_0m_1+\Delta(e_0+e_1)+e_0e_1\bmod q Δ2m0​m1​+Δ(e0​+e1​)+e0​e1​modq。

这里会取一个接近 q / Δ = p q/\Delta =p q/Δ=p的数 p p p，然后将整个密文 c t   m o d   q {\sf ct} \bmod q ctmodq变为 p / q ⋅ c t   m o d   q p/q\cdot {\sf ct} \bmod q p/q⋅ctmodq。

在模数替换之后，模数会减少 log ⁡ ( Δ ) = k \log(\Delta)=k log(Δ)=k个比特，同样噪声也会缩小 Δ \Delta Δ倍，即减少 k k k个比特。

模数替换在减少噪声和模数的同时会引入额外的噪声 e M S e_{MS} eMS​。

模数替换后的解密得到的明文等于 Δ m 0 m 1 + e 0 + e 1 + e 0 e 1 / Δ + e M S \Delta m_0m_1 + e_0+e_1 + e_0e_1/\Delta + e_{MS} Δm0​m1​+e0​+e1​+e0​e1​/Δ+eMS​，

这里的 e M S e_{MS} eMS​的噪声的大小与初始噪声 e 0 e_0 e0​的大小相近。

因为是将scale factor Δ 2 \Delta^2 Δ2变回了 Δ \Delta Δ，所以在CKKS中，也把这种方法叫做rescale

Scale Invariant（BFV）

在BFV方案中，乘法后得到的明文形式是： Δ 2 m 0 m 1 + e o t h e r = q t Δ m 0 m 1 + e o t h e r + e s c a l e \Delta ^2 m_0m_1 + e_{other}=\frac{q}{t}\Delta m_0m_1 + e_{other}+e_{scale} Δ2m0​m1​+eother​=tq​Δm0​m1​+eother​+escale​，这里的 e s c a l e e_{scale} escale​是指 Δ 2 m 0 m 1 \Delta^2m_0m_1 Δ2m0​m1​与 q / t Δ m 0 m 1 q/t\Delta m_0m_1 q/tΔm0​m1​的差距，其中 Δ = ⌊ q / t ⌋ \Delta = \lfloor q/t \rfloor Δ=⌊q/t⌋。

BFV是将密文 c t m u l   m o d   q {\sf ct}_{mul} \bmod q ctmul​modq变为 c t m u l ′ = t / q ⋅ c t m u l   m o d   q {\sf ct}_{mul}'=t/q \cdot {\sf ct}_{mul} \bmod q ctmul′​=t/q⋅ctmul​modq。

没有改变模数 q q q而是直接改变密文，会引入额外的噪声 e s c a l e e_{scale} escale​。

这里的噪声增长接近 log ⁡ t \log t logt比特。

总结

如果不进行噪声控制，那么每次乘法之后噪声都会变成原本的平方，很容易大小就比 q q q要大，导致解密失败。

而使用MS方法可以将通过缩小模数 q q q的方法，来讲噪声控制在原来的水平，但一旦模数变为了比 e e e小，也会导致解密失败。

BFV类型的噪声控制是通过在密文上乘法 t / q t/q t/q来做到的，好处是不用减少模数。

BGV和CKKS的乘法能做的次数和BFV能做的次数是一致的。

在BGV和CKKS中，每次模数缩小的比特是 log ⁡ t \log t logt或 log ⁡ Δ \log \Delta logΔ比特，

在BFV中，每次噪声增加的比特是 log ⁡ t \log t logt比特。

模数 q q q越大， t t t越小（BGV，BFV）/ Δ \Delta Δ越小（CKKS），则能做的乘法次数越多。

Bootstrapping（通用方法）

最初由Gentry提出的Bootstrapping框架如上图所示。

用一个白色的框来表示明文 m m m首先对明文进行了加密，用蓝色的框框住明文表示一个密文 E n c p k 1 ( m ) Enc_{pk_1}(m) Encpk1​​(m)，密文旁边的条表示模数和噪声的关系，可以看到初始的噪声还是比较低的在对密文执行了一系列 *** 作之后，密文变为了 c = E n c p k 1 ( f ( m ) ) c=Enc_{pk_1}(f(m)) c=Encpk1​​(f(m))，他的噪声达到了一个较高的水准，继续进行同态加法或乘法可能会导致解密失败。这时候用某个同态加密方案来加密 c c c得到 E n c p k 2 ( c ) Enc_{pk_2}(c) Encpk2​​(c)。使用一个加密后的密钥 E n c p k 2 ( s k 1 ) Enc_{pk_2}(sk_1) Encpk2​​(sk1​)，在 E n c p k 2 ( c ) Enc_{pk_2}(c) Encpk2​​(c)与 E n c p k 2 ( s k 1 ) Enc_{pk_2}(sk_1) Encpk2​​(sk1​)上面同态地执行 D e c s k 1 ( c ) Dec_{sk_1}(c) Decsk1​​(c) *** 作。最后可以得到 E n c p k 2 ( D e c s k 1 ( c ) ) = E n c p k 2 ( f ( m ) ) Enc_{pk_2}(Dec_{sk_1}(c))=Enc_{pk_2}(f(m)) Encpk2​​(Decsk1​​(c))=Encpk2​​(f(m))。这里的噪声就与原来的噪声无关了，因为原本的噪声通过 D e c Dec Dec函数消除了。

可以看到这个方法的缺点比较明显，就是开销特别大。而且本身 D e c Dec Dec算法比较复杂，会导致最后运算出来的密文带有较大的噪声，可能只能执行很少次数的同态乘法 *** 作。

编码（SIMD,encoding）

编码的目的是为了将多条数据打包成一个明文，对明文的一次 *** 作可以对应多条数据的分别 *** 作。

在RLWE类型的同态加密中，明文是属于 R t R_t Rt​的，多项式包含了很多项，我们的需求是有效地利用起来这些项。

我们对于 Z t \Z_t Zt​中的密文会感觉比较直观一些，比如 m = 7 m=7 m=7, m = 9 m=9 m=9这样。

在明文是 R t R_t Rt​时，其实也可以这样表示，比如令 m = 7 + 0 x + 0 x 2 . . . m=7+0x+0x^2... m=7+0x+0x2...，那也可以做到与 Z t \Z_t Zt​相同的效果。但这样会噪声密文的浪费，因为多项式的系数有 n n n个，而这样只用到了 1 1 1个。

需求是，将这 n n n个系数都用上，一次性能计算 n n n个明文。

但是也不能直接将多个明文直接填入系数，那样就不满足同态乘法的性质了。

举例， R t = Z 17   m o d   X 4 + 1 R_t =\Z_{17} \bmod X^4+1 Rt​=Z17​modX4+1。

有一个明文数组 [ 1 ， 3 ， 7 ， 9 ] [1，3，7，9] [1，3，7，9]与另一个数组 [ 2 ， 4 ， 6 ， 8 ] [2，4，6，8] [2，4，6，8]，我们期望做他们之间的两两相加和两两相乘：

得到 [ 3 ， 7 ， 13 ， 0 ] [3，7，13，0] [3，7，13，0]与 [ 6 ， 12 ， 8 ， 4 ] [6，12，8，4] [6，12，8，4]。

如果直接按系数编码 m 1 ( x ) = 1 + 3 x + 7 x 2 + 9 x 3 m_1(x)=1+3x+7x^2+9x^3 m1​(x)=1+3x+7x2+9x3， m 2 ( x ) = 2 + 4 x + 6 x 2 + 8 x 3 m_2(x)=2+4x+6x^2+8x^3 m2​(x)=2+4x+6x2+8x3。

那么 m 1 ( x ) + m 2 ( x ) = 3 + 7 x + 13 x 2 m_1(x)+m_2(x)=3+7x+13x^2 m1​(x)+m2​(x)=3+7x+13x2。

m 1 ( x ) ⋅ m 2 ( x ) = ( 1 + 3 x + 7 x 2 + 9 x 3 ) ( 2 + 4 x + 6 x 2 + 8 x 3 ) = 2 + 2 x + 11 x 2 + 4 x 3 m_1(x)\cdot m_2(x)=(1+3x+7x^2+9x^3)(2+4x+6x^2+8x^3)=2+2x+11x^2+4x^3 m1​(x)⋅m2​(x)=(1+3x+7x2+9x3)(2+4x+6x2+8x3)=2+2x+11x2+4x3。

明显是不符合需求的。

基于NTT&FFT

这里简单介绍，想深入了解原理可以参考CKKS的Encoding

一种编码方式是使用点值多项式

比如一个明文数组 [ 1 ， 3 ， 7 ， 9 ] [1，3，7，9] [1，3，7，9]与另一个数组 [ 2 ， 4 ， 6 ， 8 ] [2，4，6，8] [2，4，6，8]相加和相乘。

先不考虑 R t R_t Rt​，考虑在广义的多项式中。

令 m 0 ( 1 ) = 1 , m 0 ( 2 ) = 3 , m 0 ( 3 ) = 7 , m 0 ( 4 ) = 9 m_0(1)=1,m_0(2)=3,m_0(3)=7,m_0(4)=9 m0​(1)=1,m0​(2)=3,m0​(3)=7,m0​(4)=9，则 m 0 ( x ) = 5 − 25 / 3 x + 5 x 2 − 2 / 3 x 3 m_0(x)=5-25/3x+5x^2-2/3x^3 m0​(x)=5−25/3x+5x2−2/3x3。

令 m 1 ( 1 ) = 2 , m 1 ( 2 ) = 4 , m 1 ( 3 ) = 6 , m 1 ( 4 ) = 8 m_1(1)=2,m_1(2)=4,m_1(3)=6,m_1(4)=8 m1​(1)=2,m1​(2)=4,m1​(3)=6,m1​(4)=8，则 m 1 ( x ) = 2 x m_1(x)=2x m1​(x)=2x。

m a d d ( x ) = m 0 ( x ) + m 1 ( x ) = 5 − 19 / 3 x + 5 x 2 − 2 / 3 x 3 m_{add}(x)=m_0(x)+m_1(x)=5-19/3x+5x^2-2/3x^3 madd​(x)=m0​(x)+m1​(x)=5−19/3x+5x2−2/3x3。

m m u l ( x ) = m 0 ( x ) ⋅ m 1 ( x ) = 10 x − 50 / 3 x 2 + 10 x 3 − 4 / 3 x 4 m_{mul}(x)=m_0(x)\cdot m_1(x)=10x-50/3x^2+10x^3-4/3x^4 mmul​(x)=m0​(x)⋅m1​(x)=10x−50/3x2+10x3−4/3x4。

带入四个点得

	x = 1 x=1 x=1	x = 2 x=2 x=2	x = 3 x=3 x=3	x = 3 x=3 x=3
m 0 ( x ) m_0(x) m0​(x)	1	3	7	9
m 1 ( x ) m_1(x) m1​(x)	2	4	6	8
m a d d ( x ) m_{add}(x) madd​(x)	3	7	13	17
m m u l ( x ) m_{mul}(x) mmul​(x)	2	12	42	72

满足我们需要的编码需求。

一个很重要的观察就是，多项式的乘法可以对应到点值的两两相乘。

所以用点值形式来表示明文是Encoding的基本思路。

在上述的例子中，我们打包 [ a , b , c , d ] [a,b,c,d] [a,b,c,d]这个数组的方法是令 m ( 1 ) = a , m ( 2 ) = b , m ( 3 ) = c , m ( 4 ) = d m(1)=a,m(2)=b,m(3)=c,m(4)=d m(1)=a,m(2)=b,m(3)=c,m(4)=d。这样的方法是可行的，但效率不行。

基于FFT的编码（CKKS）

我们可以采用快速傅里叶变换（FFT）的方法来构造多项式。

取 x 2 n = 1 x^{2n}=1 x2n=1的解 ξ \xi ξ，这样的取法好处在于可以采用FFT的方式进行点值多项式到系数多项式之间的转换。

ξ = e 2 π i 2 N \xi = e^{\frac{2 \pi i}{2N}} ξ=e2N2πi​。 N = 4 N=4 N=4时， ξ = 2 2 + 2 2 i , ξ 3 = − 2 2 + 2 2 i ,   ξ 5 = 2 2 − 2 2 i , ξ 7 = − 2 2 − 2 2 i \xi = \frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2}i,\xi^3 = -\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2}i,\,\xi ^{5}=\frac{\sqrt{2}}{2}-\frac{\sqrt{2}}{2}i,\xi^7=-\frac{\sqrt{2}}{2}-\frac{\sqrt{2}}{2}i ξ=22 ​​+22 ​​i,ξ3=−22 ​​+22 ​​i,ξ5=22 ​​−22 ​​i,ξ7=−22 ​​−22 ​​i。

为什么FFT？因为这样的解是在单位元上面的一个对称的结构，可以通过二分的思想来加速运算，点值多项式到系数多项式之间的互相转换的复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

为什么是 ξ \xi ξ而不是 ω \omega ω，因为我们采用的多项式环是基于分圆多项式 X n + 1 X^n+1 Xn+1的商环，他的跟是 x n = − 1 x^{n}=-1 xn=−1即 x 2 n = 1 x^{2n}=1 x2n=1。

那照理来说，编码一个数组 [ a , b , c , d ] [a,b,c,d] [a,b,c,d]，就直接将 m ( ξ ) = a m(\xi)=a m(ξ)=a， m ( ξ 3 ) = b m(\xi^3)=b m(ξ3)=b， m ( ξ 5 ) = c m(\xi^5)=c m(ξ5)=c， m ( ξ 7 ) = d m(\xi^7)=d m(ξ7)=d这样来构造一个多项式就行了。

但直接这样构造存在一个问题，就是出来的多项式的系数可能是复数。而我们加密所需要的多项式是一个整系数多项式，为了避免这一点，我们只用一半的点值，另一半存共轭，即：

数组 [ a + b i , c + d i ] [a+bi,c+di] [a+bi,c+di]，构造多项式满足 m ( ξ ) = a + b i , m ( ξ 3 ) = c + d i , m ( ξ 5 ) = a − b i , m ( ξ 7 ) = c − d i m(\xi)=a+bi,m(\xi^3)=c+di,m(\xi ^5)=a-bi,m(\xi^7)=c-di m(ξ)=a+bi,m(ξ3)=c+di,m(ξ5)=a−bi,m(ξ7)=c−di。

所以在说到CKKS的可利用槽的时候，一般说是 n / 2 n/2 n/2，而不是 n n n。因为有一半的空间要用作存放共轭。

为了表示精度，这里一般是
m ( ξ ) = Δ ( a + b i ) , m ( ξ 3 ) = Δ ( c + d i ) , m ( ξ 5 ) = Δ ( a − b i ) , m ( ξ 7 ) = Δ ( c − d i ) m(\xi)=\Delta (a+bi),m(\xi^3)=\Delta (c+di),m(\xi ^5)=\Delta (a-bi),m(\xi^7)=\Delta (c-di) m(ξ)=Δ(a+bi),m(ξ3)=Δ(c+di),m(ξ5)=Δ(a−bi),m(ξ7)=Δ(c−di)

基于NTT的编码（BGV，BFV）

对于BFV这样在 R t R_t Rt​中的多项式来说，使用编码时，

我们取 x 2 n = 1   m o d   t x^{2n}=1 \bmod t x2n=1modt的解 ξ \xi ξ作为点值多项式的横坐标值。

那么编码一个数组 [ a , b , c , d ] [a,b,c,d] [a,b,c,d]，就可以直接令 m ( ξ ) = a m(\xi)=a m(ξ)=a， m ( ξ 3 ) = b m(\xi^3)=b m(ξ3)=b， m ( ξ 5 ) = c m(\xi^5)=c m(ξ5)=c， m ( ξ 7 ) = d m(\xi^7)=d m(ξ7)=d。

总结

BFV：消息 Z t n → \Z_t ^{n}\to Ztn​→明文 R t → R_t\to Rt​→密文 R q 2 R_q^2 Rq2​。

CKKS：消息 C n / 2 → \mathbb{C}^{n/2}\to Cn/2→明文 R → R\to R→密文 R q 2 R_q^2 Rq2​。

密钥替换的应用2：自同构（旋转，置换）

对于编码之后的明文 [ a , b , c , d ] [a,b,c,d] [a,b,c,d]，我们可以在密文上执行一个旋转 *** 作，使其变为 [ b , c , d , a ] [b,c,d,a] [b,c,d,a]。

或者可以执行交换 *** 作，使其变为 [ c , d , a , b ] [c,d,a,b] [c,d,a,b]。

注意点：这里例举的是CKKS密文， [ a , b , c , d ] [a,b,c,d] [a,b,c,d]对应的 n = 8 n=8 n=8，用到了 n / 2 n/2 n/2个slot。

原理：对于密文 c t = ( a , b ) {\sf ct}=(a,b) ct=(a,b)来说， m = b − a s m=b-as m=b−as。

那么假如有一个galois自同构变换 φ ( m ) \varphi(m) φ(m)，那么 φ ( m ) = φ ( b ) − φ ( a ) φ ( s ) \varphi(m) = \varphi(b) - \varphi(a)\varphi(s) φ(m)=φ(b)−φ(a)φ(s)。

可以直接对密文进行 φ \varphi φ变换成为 c t ′ = ( φ ( a ) , φ ( b ) ) {\sf ct}'=(\varphi(a),\varphi(b)) ct′=(φ(a),φ(b))。这是一个用 φ ( s ) \varphi(s) φ(s)加密的密文。

那么就可以使用keyswitch *** 作，令 k s k = ( a k , b k = a k s + φ ( s ) + e k ) ksk = (a_k, b_k = a_ks + \varphi(s) + e_k) ksk=(ak​,bk​=ak​s+φ(s)+ek​)。就可以将 c t ′ {\sf ct}' ct′从由 φ ( s ) \varphi(s) φ(s)加密的密文变为了由 s s s加密的密文。

这里的 φ \varphi φ可以是 φ : X → X 3 \varphi:X\to X^3 φ:X→X3，比如 a ( x ) = 1 + 2 x + 3 x 2 a(x)=1+2x+3x^2 a(x)=1+2x+3x2， φ ( a ( x ) ) = 1 + 2 x 3 + 3 x 6 \varphi(a(x))=1+2x^3+3x^6 φ(a(x))=1+2x3+3x6。

考虑 n = 8 n=8 n=8的情况，编码 [ a , b , c , d ] [a,b,c,d] [a,b,c,d]。

m ( ξ ) = a , m ( ξ 3 ) = b , m ( ξ 9 ) = c , m ( ξ 11 ) = d m(\xi)=a,m(\xi^3)=b,m(\xi^9)=c,m(\xi^{11})=d m(ξ)=a,m(ξ3)=b,m(ξ9)=c,m(ξ11)=d。

对 m ( x ) m(x) m(x)执行 m ′ ( x ) = φ ( m ( x ) ) = m ( x 3 ) m'(x)=\varphi(m(x))=m(x^3) m′(x)=φ(m(x))=m(x3)。

那么 m ′ ( ξ ) = m ( ξ 3 ) = b , m ′ ( ξ 3 ) = m ( ξ 9 ) = c , m ′ ( ξ 9 ) = m ( ξ 11 ) = d , m ′ ( ξ 11 ) = m ( ξ ) = a m'(\xi)=m(\xi^3)=b,m'(\xi^3)=m(\xi^9)=c,m'(\xi^9)=m(\xi^{11})=d,m'(\xi^{11})=m(\xi)=a m′(ξ)=m(ξ3)=b,m′(ξ3)=m(ξ9)=c,m′(ξ9)=m(ξ11)=d,m′(ξ11)=m(ξ)=a。

旋转 *** 作有什么用？

在一些涉及到矩阵乘法的应用中，比如 r ∗ c r*c r∗c大小的矩阵乘以 c ∗ 1 c*1 c∗1大小的向量，如果 n > r ∗ c n>r*c n>r∗c，那么可以将矩阵编码进一个密文中，然后通过旋转的方式，执行矩阵乘向量。这种方法一般被叫做BSGS（小步大步法），在用FHE做机器学习训练或预测时非常常用。

φ \varphi φ除了表示旋转[1,2,3,4]变为[2,3,4,1]。

还可以表示换位：[1,2,3,4]变为[3,4,1,2]。

FHEW类型同态加密

这里先略过，FHEW类型的同态加密，优点在于Bootstrapping较快，缺点是每次只能刷新几个比特的密文，且不支持SIMD。

有一个特性在于可以在Bootstrapping的同时对刷新的这几个比特执行一个任意的函数 f f f，即 E n c ( m ) ⟶ b o o t s t r a p p E n c ( f ( m ) ) Enc(m) \stackrel{bootstrapp}{\longrightarrow} Enc(f(m)) Enc(m)⟶bootstrapp​Enc(f(m))。

感兴趣的可参考这个链接

BlindRotate

刷新几比特密文，略

Functional Bootstrapping

刷新的同时运算某个函数，略

可参考：TFHE拓展：Programmable Bootstrapping

同态加密应用 隐私集合求交PSI

PSI场景：

Alice有数据库 A A A，Bob有数据库 B B B。

现在Alice想要知道自己的数据库和Bob重合的部分有哪些，即 A ∩ B A\cap B A∩B，但彼此不暴露其他信息。

使用同态实现的基础思路：

对于 A A A中的数据 A = { a 1 , . . . a n } A=\{a_1,...a_n\} A={a1​,...an​}，Alice使用同态加密 c i = E n c p k ( a i ) i = 1... n c_i=Enc_{pk}(a_i)_{i=1...n} ci​=Encpk​(ai​)i=1...n​。

Bob收到后，运算对于每条 B = { b 1 , . . . , b k } B=\{b_1,...,b_k\} B={b1​,...,bk​}，运算并返回 c i ′ = ∏ j ∈ [ k ] ( c i − b j ) c_i'=\prod_{j\in [k]}(c_i-b_j) ci′​=∏j∈[k]​(ci​−bj​)。

Alice解密 { c i ′ } i = 1... n \{c_i'\}_{i=1...n} {ci′​}i=1...n​，若结果为0，则表示 a i a_i ai​在 B B B的数据库中。

以上为基础思路，优化的方法可见

[1] [Labeled PSI from Fully Homomorphic Encryption with Malicious Security(2018)](Labeled PSI from Fully Homomorphic Encryption with Malicious Security)

[2] Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication(2021)

效率：

2 28 2^{28} 228的量级是两亿。 2 22 2^{22} 222是400万。

在unbalanced情况下，通信开销是非常小的。

隐匿查询PIR

PIR场景：

Alice有一个索引 i i i，Bob有一个数据库 D = { D 1 , . . . , D n } D=\{D_1,...,D_n\} D={D1​,...,Dn​}。

Alice想在不暴露 i i i的情况下得到 D i D_i Di​。

使用同态加密实现的基础思路：

Alice构造一个查询序列： s i ⃗ = { s i , 1 . . . s i , n } \vec{s_i}=\{s_{i,1}...s_{i,n}\} si​ ​={si,1​...si,n​}，其中 s i , i = 1 , s i , j = 0 ( i ≠ j ) s_{i,i}=1,s_{i,j}=0(i\ne j) si,i​=1,si,j​=0(i=j)。

Alice加密这个查询序列： c i ⃗ = E n c ( s i ⃗ ) i = 1... n \vec{c_i}=Enc(\vec{s_i})_{i=1...n} ci​ ​=Enc(si​ ​)i=1...n​，并发送给Bob。

Bob进行运算 c = ⟨ c i ⃗ ， D ⟩ c=\langle \vec{c_i}，D \rangle c=⟨ci​ ​，D⟩并返回给Alice。

Alice解密 c c c得到 D i D_i Di​。

以上为基础思路，优化方法可见：

[1] Communication–Computation Trade-offs in PIR (2019)

[2] microsoft/SealPIR: Example implementation of the SealPIR protocol (github.com)

[3] OpenMined/PIR: Private Information Retrieval protocol (github.com)

效率：

作为MPC的组件

生成Beaver Triple，略

作为FL的组件

作为加法同态做聚合，略

通用的优化方法 计算效率（RNS，NTT，Montgomery）

NTT加速：多项式之间的计算可通过NTT来加速，略。

Montgomery：快速的取模运算，针对很多数据对同一个素数取模的运算，略。

主要介绍一下RNS：

计算机原生支持64bit的模加和模乘算法

uint64_t a,b;
c = a + b; // a + b mod 2^64
c = a * b; // a * b mod 2^64

但在同态加密的构造中往往模数 q > > 64 q>>64 q>>64，比如 200 200 200比特。

为了避免使用高精度大整数库，我们将 200 200 200比特的 q q q分成 4 4 4个小 q i q_i qi​， q = q 0 q 1 q 2 q 3 q=q_0q_1q_2q_3 q=q0​q1​q2​q3​，

原本一个 a   m o d   q a \bmod q amodq的数字，我们分别用四个数字 [ a 0 , a 1 , a 2 , a 3 ] [a_0,a_1,a_2,a_3] [a0​,a1​,a2​,a3​]来表示，分别为 a i = a   m o d   q i a_i = a \bmod q_i ai​=amodqi​。

在同态加密库中，比如CKKS和BFV，会看到 m o d u l u s = { 60 , 40 , 40 , 60 } modulus = \{60,40,40,60\} modulus={60,40,40,60}这样的表达，

其实就是取了 4 4 4个素数 q i q_i qi​来表达 200 200 200比特的模数 q q q。

通信开销（随机种子，模数替换）

随机种子，可以用于传输 c t = ( a , b = a s + e ) {\sf ct}=(a,b=as+e) ct=(a,b=as+e)中，只发送生成 a a a的随机数种子和 b b b，能节省一半的通信开销，略。

模数替换，降低模数就是降低表达一个密文所需要用到的比特的数量，略。

前沿研究 CKKS的安全性问题

CKKS因为解密带噪声，所以会有安全性问题。

比如 D e c ( c t ) = m + e / Δ Dec({\sf ct})=m +e/\Delta Dec(ct)=m+e/Δ。

而 c t = ( a , b = a s + Δ m + e ) {\sf ct}=(a,b=as + \Delta m +e) ct=(a,b=as+Δm+e)，

所以完全可以计算 b − Δ ⋅ D e c ( c t ) b-\Delta \cdot Dec({\sf ct}) b−Δ⋅Dec(ct)来得到 a s as as，那么就很容易推出密钥 s s s了。

现在各大同态加密库都解决了这个问题了。

可参考:

[1] On the Security of Homomorphic Encryption on Approximate Numbers

将FHEW类型的密文和RLWE类型的同态加密结合

比如PEGASUS，CHIMERA。都是用RLWE来算加法乘法运算，用FHEW类型的 *** 作来算激活函数之类的。

可参考：

[1] CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes

[2] PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption

研究如何进行快速的Bootstrapping

通过扩模方式来实现Bootstrapping。

可参考：

[1] General Bootstrapping Approach for RLWE-based Homomorphic Encryption (iacr.org)

将RLWE类型的同态加密与MPC结合，通过MPC实现Bootstrapping过程

可参考：

[1] Efficient Privacy Preserving Logistic Regression Inference and Training (iacr.org)

同态加密参数（实现相关） 推荐参数

关于安全的参数选取的标准在Standard – Homomorphic Encryption Standardization中有给出几个推荐的参数集合。

解释一下几个表头：

表头	含义
distribution	表示私钥 s s s的分布，这里是在(-1,1)中选取
n	表示 R q R_q Rq​的多项式模数 X n + 1 X^n+1 Xn+1中的多项式阶
security level	安全等级
logq	表示 R q R_q Rq​中模数 q q q的比特数
nSVP，dec，dual	三种针对LWE问题的攻击方式，以及在这种攻击方式下能达到的安全性

如果不使用推荐的参数，而是用自行选取的参数，可以使用lwe-estimator)来计算出当前选取参数的安全等级。

参数与效率

一般来说， n n n取得越大，安全性越高， q q q取得越大，安全性越低。这两项一般是同时增加或同时减小以满足相同等级的安全性。

而这两项增加会导致运算效率变低。但会增加计算的能力，也就是乘法的层数。

在CKKS中有scale factor Δ \Delta Δ，BFV中有明文空间 R t R_t Rt​的模数 t t t，这两项与效率无关。

Δ \Delta Δ和 t t t与明文的表达能力有关，越大则能表达越精确或越多的数。但会减少计算的能力，一般来说 Δ \Delta Δ或 t t t越小，能运算乘法的次数越多。

代码中参数的解释

以SEAL库为例，

CKKS：

    EncryptionParameters parms(scheme_type::ckks);
    size_t poly_modulus_degree = 8192;
    parms.set_poly_modulus_degree(poly_modulus_degree);
    parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 60, 40, 40, 60 }));
    double scale = pow(2.0, 40);

第一行创建了一个params类型，指定了方案为CKKS。

第二三行设置了多项式的阶为 n = 8192 n=8192 n=8192，根据之前的参数表，模数的比特数为 log ⁡ q = 218 \log q=218 logq=218时能达到128bit安全。 q q q越小，安全性是越高的。

第四行创建了4个素数 q 0 , q 1 , q 2 , q 3 q_0,q_1,q_2,q_3 q0​,q1​,q2​,q3​，他们的比特数分别为 { 60 , 40 , 40 , 60 } \{60,40,40,60\} {60,40,40,60}，这里具体说明一下，首先四个模数加起来是200bit，小于需要218bit，所以这里能达到128位的安全性。

最后一个模数是一个特殊模数，用于在Keyswitch中减小噪声，可以暂时不去看他。

主要的模数是 60 , 40 , 40 60,40,40 60,40,40，一般来说，除了第一个模数，后面的模数的大小都是和扩张因子 Δ \Delta Δ长度相同的。

因为在CKKS中，没做完一次乘法，就要采用模数替换的方法，将 Δ 2 m   m o d   q 0 q 1 q 2 \Delta ^2 m \bmod q_0q_1q_2 Δ2mmodq0​q1​q2​变为 Δ m   m o d   q 0 q 1 \Delta m\bmod q_0q_1 Δmmodq0​q1​，也就是除掉一个和 Δ \Delta Δ大小类似的数 q 2 q_2 q2​。

而第一个模数是决定了CKKS明文能表示的精度和整数位。因为采用了 Δ m \Delta m Δm的方式来表示一个数字，因此 Δ \Delta Δ的大小代表了能表示多少小数位， log ⁡ q 0 − log ⁡ Δ \log q_0 - \log\Delta logq0​−logΔ的大小代表了整数部分能有多少位。

BFV：

    parms.set_plain_modulus(786433);

BFV与CKKS在设置参数上面的区别在于，CKKS需要设置scale，即 Δ \Delta Δ。而BFV设置的是plain_modulus，即 t t t。

开源库效率测试： SEAL

Lattigo

BFV n=8192,q=218。

算法/库	C++ SEAL( μ s \mu s μs)	Go Lattigo( μ s \mu s μs)	Python TenSEAL( μ s \mu s μs)
Encode	110	244	/
Decode	167	406	/
Encrypt(sk)	3436	2938	3371
Encrypt(pk)	5147	5233	/
Add(Ct)	330	52	152
Add(Pt)	459	27
Mul(Ct)	21550	13325	21621
Mul(Pt)	3048	3118
Relin	5453	4939
Rotates	5316	5048