全同态加密知识体系整理

全同态加密知识体系整理,第1张

文章由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...n1]aixi,aiZq

例子:

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+2R17

一般来说明文空间为 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} aZqn是随机选取的向量 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 aRq是随机选取的多项式, 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.25210。在应用中, 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 aRq,以及 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 t1mod2n,涉及到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=(upk0+e0,upk1+Δ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 c1c0smodq

以私钥的CKKS为例,

c 1 − c 0 s ≡ Δ m + e   m o d   q c_1-c_0s \equiv \Delta m+e \bmod q c1c0sΔm+emodq (私钥)or c 1 − c 0 s = Δ m + v   m o d   q c_1-c_0s = \Delta m+v \bmod q c1c0s=Δ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 c1c0smodq后得到 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/2e<q/2t1/2

BFV计算 c 1 − c 0 s   m o d   q c_1-c_0s\bmod q c1c0smodq后得到 Δ 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/tq/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/2e<q/2tr/2

CKKS计算 c 1 − c 0 s   m o d   q c_1-c_0s \bmod q c1c0smodq后得到 Δ 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 2302302.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=ais+Δ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} baddaadds=a0s+Δm+e0+a1s+Δm+e1a0sa1s=Δ(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=(am1,bm1)

解密:
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} bm1am1s=am1s+Δm0m1+m1eam1s=Δm0m1+m1e
噪声大小变为 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=a0s+Δm0+e0),ct1=(a1,b1=a1s+Δ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=(a0a1,a0b1+a1b0,b0b1)=(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} fs2gs+h=a0a1s2a0b1sa1b0s+b0b1=(b0a0s)(b1aas)=(Δm0+e0)(Δm1+e1)=Δ2m0m1+e0e1

噪声大小是原来的平方,如何将 Δ 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=aks+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)aksk=(a=aak,b=babk)

正确性:
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} bas=(babk)(aak)s=as+Δm+ea(aks+s+ek)+aaks=Δm+eaek
但问题不能直接这么做,问题在于 a ∈ R q a\in R_q aRq ∥ a ∥ ∞ ≈ q \|a\|_{\infty}\approx q aq,噪声大小会直接超过 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[]diBi=aPowB(a):[p0,p1,p2,...,p],=logB(q)pi=aBi
显然可以得到 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 as=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=bDecomp(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} bas=bDecomp(a),bk Decomp(a),ak s=b(⟨Decomp(a),ak s+Decomp(a),Pow(s)⟩+Decomp(a),ek ⟩)Decomp(a),ak s=basDecomp(a),ek =Δm+eDecomp(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=(a0a1,a0b1+a1b0,b0b1)=(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 bas=b0b1(a0b1+a1b0)s+a0a1s2

输入:密文 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=(a0a1,a0b1+a1b0,b0b1)=(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=aks+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)+a0a1(rlk)=(a0b1+a1b0+a0a1ak,b0b1+a0a1bk)
正确性:
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} bas=b0b1+a0a1(aks+s2+ek)(a0b1+a1b0+a0a1ak)s=b0b1+a0a1aks+a0a1s2+a0a1eka0b1sa1b0sa0a1aks=b0b1a0b1sa1b0s+a0a1s2+a0a1ek=(b0a0s)(b1a1s)+a0a1ek=(Δm0+e0)(Δm1+e1)+a0a1ek
注意,如果使用了比特分解,那么最后的噪声项为 ⟨ D e c o m p ( a 0 a 1 ) , e k ⃗ ⟩ \langle Decomp(a_0a_1),\vec{e_k} \rangle Decomp(a0a1),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 Δ2m0m1+Δ(e0+e1)+e0e1modq

这里会取一个接近 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/qctmodq

在模数替换之后,模数会减少 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} Δm0m1+e0+e1+e0e1+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} Δ2m0m1+eother=tqΔm0m1+eother+escale,这里的 e s c a l e e_{scale} escale是指 Δ 2 m 0 m 1 \Delta^2m_0m_1 Δ2m0m1 q / t Δ m 0 m 1 q/t\Delta m_0m_1 q/tΔm0m1的差距,其中 Δ = ⌊ q / t ⌋ \Delta = \lfloor q/t \rfloor Δ=q/t

BFV是将密文 c t m u l   m o d   q {\sf ct}_{mul} \bmod q ctmulmodq变为 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/qctmulmodq

没有改变模数 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=Z17modX4+1

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

得到 [ 3 , 7 , 13 , 0 ] [3,7,13,0] [37130] [ 6 , 12 , 8 , 4 ] [6,12,8,4] [61284]

如果直接按系数编码 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] [1379]与另一个数组 [ 2 , 4 , 6 , 8 ] [2,4,6,8] [2468]相加和相乘。

先不考虑 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)=525/3x+5x22/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)=519/3x+5x22/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)=10x50/3x2+10x34/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)1379
m 1 ( x ) m_1(x) m1(x)2468
m a d d ( x ) m_{add}(x) madd(x)371317
m m u l ( x ) m_{mul}(x) mmul(x)2124272

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

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

所以用点值形式来表示明文是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)=abi,m(ξ7)=cdi

所以在说到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)=Δ(abi),m(ξ7)=Δ(cdi)

基于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=bas

那么假如有一个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=aks+φ(s)+ek)。就可以将 c t ′ {\sf ct}' ct从由 φ ( s ) \varphi(s) φ(s)加密的密文变为了由 s s s加密的密文。

这里的 φ \varphi φ可以是 φ : X → X 3 \varphi:X\to X^3 φ:XX3,比如 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 rc大小的矩阵乘以 c ∗ 1 c*1 c1大小的向量,如果 n > r ∗ c n>r*c n>rc,那么可以将矩阵编码进一个密文中,然后通过旋转的方式,执行矩阵乘向量。这种方法一般被叫做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)bootstrappEnc(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 AB,但彼此不暴露其他信息。

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

对于 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](cibj)

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=q0q1q2q3

原本一个 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 Δ2mmodq0q1q2变为 Δ m   m o d   q 0 q 1 \Delta m\bmod q_0q_1 Δmmodq0q1,也就是除掉一个和 Δ \Delta Δ大小类似的数 q 2 q_2 q2

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

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)
Encode110244/
Decode167406/
Encrypt(sk)343629383371
Encrypt(pk)51475233/
Add(Ct)33052152
Add(Pt)45927
Mul(Ct)215501332521621
Mul(Pt)30483118
Relin54534939
Rotates53165048

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/2991701.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存