前序博客有:
5. 基于已加密数据处理
很显然,TLWE加密方案和TGLWE加密方案均具有加法同态性。[GSW13] Gentry–Sahai–Waters 方法使用matrix product来将TLWE加密方案和TGLWE加密方案,转换为支持有限乘法次数的方案。
5.1 TLWE密文
5.1.1 TLWE密文加法
令( T q n + 1 \mathbb{T}_q^{n+1} Tqn+1中的) c 1 ← T L W E s ( μ 1 ) \mathbf{c}_1\leftarrow TLWE_{\mathbf{s}}(\mu_1) c1←TLWEs(μ1)和 c 2 ← T L W E s ( μ 2 ) \mathbf{c}_2\leftarrow TLWE_{\mathbf{s}}(\mu_2) c2←TLWEs(μ2),分别为( P \mathcal{P} P中) μ 1 , μ 2 \mu_1,\mu_2 μ1,μ2的TLWE加密:
c 1 = ( a 1 , ⋯ , a n , b ) , c 2 = ( a 1 ′ , ⋯ , a n ′ , b ′ ) \mathbf{c}_1=(a_1,\cdots,a_n,b),\mathbf{c}_2=(a_1',\cdots,a_n',b') c1=(a1,⋯,an,b),c2=(a1′,⋯,an′,b′)
其中:
- ( a 1 , ⋯ , a n ) ← § T q n (a_1,\cdots,a_n)\xleftarrow{\S}\mathbb{T}_q^n (a1,⋯,an)§Tqn, b = ∑ j = 1 n s j ⋅ a j + μ 1 + e 1 b=\sum_{j=1}^{n}s_j\cdot a_j+\mu_1+e_1 b=∑j=1nsj⋅aj+μ1+e1
- ( a 1 ′ , ⋯ , a n ′ ) ← § T q n (a_1',\cdots,a_n')\xleftarrow{\S}\mathbb{T}_q^n (a1′,⋯,an′)§Tqn, b ′ = ∑ j = 1 n s j ⋅ a j ′ + μ 2 + e 2 b'=\sum_{j=1}^{n}s_j\cdot a_j'+\mu_2+e_2 b′=∑j=1nsj⋅aj′+μ2+e2
- e 1 , e 2 e_1,e_2 e1,e2均为“small”。
则有:
- ( T q n + 1 \mathbb{T}_q^{n+1} Tqn+1中的) c 3 : = c 1 + c 2 \mathbf{c}_3:=\mathbf{c}_1+\mathbf{c}_2 c3:=c1+c2 为( P \mathcal{P} P中) μ 3 : = μ 1 + μ 2 \mu_3:=\mu_1+\mu_2 μ3:=μ1+μ2的有效加密。
即:
密文的加法,解释了为何在TLWE加密定义中,选择 P \mathcal{P} P为 T q \mathbb{T}_q Tq的加法子群。这样,就暗示了,若 μ 1 , μ 2 ∈ P \mu_1,\mu_2\in\mathcal{P} μ1,μ2∈P,则有 μ 3 = μ 1 + μ 2 ∈ P \mu_3=\mu_1+\mu_2\in\mathcal{P} μ3=μ1+μ2∈P。
5.1.2 TLWE密文与某已知常量值的乘法
与某常量值的乘法,可通过一系列加法来实现。因此,已知 μ ∈ P \mu\in\mathcal{P} μ∈P的TLWE密文 c ← T L W E s ( μ ) \mathbf{c}\leftarrow TLWE_{\mathbf{s}}(\mu) c←TLWEs(μ),对于某已知(small)整数 K ≠ 0 K\neq 0 K=0:
- 若 K > 0 K>0 K>0,则 K ⋅ μ K\cdot \mu K⋅μ的TLWE密文可表示为:
- 若 K < 0 K<0 K<0,则 K ⋅ μ K\cdot \mu K⋅μ的TLWE密文可表示为: K ⋅ c = ( − K ) ⋅ ( − c ) K\cdot \mathbf{c}=(-K)\cdot (-\mathbf{c}) K⋅c=(−K)⋅(−c)。
更准确来说,是将 c \mathbf{c} c向量中的每个元素与 K K K相乘,即若 c = ( a 1 , ⋯ , a n , b ) ∈ T q n + 1 \mathbf{c}=(a_1,\cdots,a_n,b)\in\mathbb{T}_q^{n+1} c=(a1,⋯,an,b)∈Tqn+1,则有:
K ⋅ c = ( K ⋅ a 1 , ⋯ , K ⋅ a n , K ⋅ b ) K\cdot \mathbf{c}=(K\cdot a_1,\cdots,K\cdot a_n,K\cdot b) K⋅c=(K⋅a1,⋯,K⋅an,K⋅b)。
只要最终的噪声仍是“small”的,则( T q n + 1 \mathbb{T}_q^{n+1} Tqn+1中的) K ⋅ c ← T L W E s ( μ 1 ) K\cdot \mathbf{c}\leftarrow TLWE_{\mathbf{s}}(\mu_1) K⋅c←TLWEs(μ1)为( P \mathcal{P} P中的) K ⋅ μ K\cdot \mu K⋅μ的有效TLWE加密。
5.1.3 TLWE密文之间的乘法运算
对已加密数据操作的主要调整,在于密文间的乘法运算。
为让[GSW13] Gentry–Sahai–Waters 方法可行,需将TLWE所加密的密文以矩阵表示。
Gadget matrix:
Flattening:
- 为不影响dot products而修改vectors的方法[BGV14, Bra12]
- 有助于控制noise
接下来展示基于discretized torus T q = q − 1 Z / Z \mathbb{T}_q=q^{-1}\mathbb{Z}/\mathbb{Z} Tq=q−1Z/Z,其中 q q q为通用整数(即无需为power of 2),的“gadget decomposition”技术。
对于某radix B B B和整数 l ≥ 1 l\geq 1 l≥1,其满足 B l ∣ q B^{l}|q Bl∣q,对于gadget matrix G ( n + 1 ) × ( n + 1 ) l \mathbf{G}^{(n+1)\times (n+1)l} G(n+1)×(n+1)l有:
其中 g = ( 1 / B , ⋯ , 1 / B l ) ∈ T q l \mathbf{g}=(1/B,\cdots,1/B^l)\in\mathbb{T}_q^l g=(1/B,⋯,1/Bl)∈Tql,因此:
- 对于输入向量 u ∈ Z ( n + 1 ) l \mathbf{u}\in\mathbb{Z}^{(n+1)l} u∈Z(n+1)l,product u ⋅ G T \mathbf{u\cdot G}^T u⋅GT的结果为 T q n + 1 \mathbb{T}_q^{n+1} Tqn+1中向量。
- 对于逆变换 G − 1 : T q n + 1 → Z ( n + 1 ) l \mathbf{G}^{-1}:\mathbb{T}_q^{n+1}\rightarrow \mathbb{Z}^{(n+1)l} G−1:Tqn+1→Z(n+1)l,对任意向量 v ∈ T q n + 1 \mathbf{v}\in\mathbb{T}_q^{n+1} v∈Tqn+1,有:
G − 1 ( v ) ⋅ G T ≈ v \mathbf{G}^{-1}(\mathbf{v})\cdot \mathbf{G}^T\approx \mathbf{v} G−1(v)⋅GT≈v且 G − 1 ( v ) \mathbf{G}^{-1}(\mathbf{v}) G−1(v)为“small”。
该逆变换,会将向量中的每个元素替换为其signed radix- B B B expansion。
准确来说,若 v = ( v 1 , ⋯ , v n + 1 ) ∈ T q n + 1 \mathbf{v}=(v_1,\cdots,v_{n+1})\in\mathbb{T}_q^{n+1} v=(v1,⋯,vn+1)∈Tqn+1,其中 v i ∈ [ − 1 2 , 1 2 ) v_i\in[-\frac{1}{2},\frac{1}{2}) vi∈[−21,21),设置 v ˉ i = ⌊ B l v i ⌉ \bar{v}_i=\lfloor B^lv_i\rceil vˉi=⌊Blvi⌉,并表示成:
v ˉ i ≡ ∑ j = 1 l u i , j B l − j ( m o d B l ) \bar{v}_i\equiv \sum_{j=1}^{l}u_{i,j}B^{l-j}(\mod B^l) vˉi≡∑j=1lui,jBl−j(modBl),其中 u i , j ∈ [ − ⌊ B / 2 ⌋ , ⌈ B / 2 ⌉ ) u_{i,j}\in[-\lfloor B/2\rfloor,\lceil B/2\rceil) ui,j∈[−⌊B/2⌋,⌈B/2⌉)。
定义 g − 1 ( v i ) = ( u i , 1 , ⋯ , u i , l ) ∈ Z l \mathbf{g}^{-1}(v_i)=(u_{i,1},\cdots,u_{i,l})\in\mathbb{Z}^l g−1(vi)=(ui,1,⋯,ui,l)∈Zl,则有:
G − 1 ( v ) : = ( g − 1 ( v 1 ) , g − 1 ( v 2 ) , ⋯ , g − 1 ( v n + 1 ) ) = ( u 1 , 1 , ⋯ , u 1 , l , u 2 , 1 , ⋯ , u 2 , l , ⋯ , u n + 1 , 1 , ⋯ , u n + 1 , l ) ∈ Z ( n + 1 ) l \mathbf{G}^{-1}(\mathbf{v}):=(\mathbf{g}^{-1}(v_1),\mathbf{g}^{-1}(v_2),\cdots,\mathbf{g}^{-1}(v_{n+1}))\\=(u_{1,1},\cdots,u_{1,l},u_{2,1},\cdots,u_{2,l},\cdots,u_{n+1,1},\cdots,u_{n+1,l})\in\mathbb{Z}^{(n+1)l} G−1(v):=(g−1(v1),g−1(v2),⋯,g−1(vn+1))=(u1,1,⋯,u1,l,u2,1,⋯,u2,l,⋯,un+1,1,⋯,un+1,l)∈Z(n+1)l。
注意,当 B l = q B^l=q Bl=q时, v \mathbf{v} v中所有元素 v i ∈ [ − 1 2 , 1 2 ) v_i\in[-\frac{1}{2},\frac{1}{2}) vi∈[−21,21)均满足 v ˉ i = B l v i \bar{v}_i=B^lv_i vˉi=Blvi。然后基于 T q \mathbb{T}_q Tq,有 G − 1 ( v ) ⋅ G T = v \mathbf{G}^{-1}(\mathbf{v})\cdot \mathbf{G}^T=\mathbf{v} G−1(v)⋅GT=v成立。
举例:
Remark 5:
逆变换 G − 1 \mathbf{G}^{-1} G−1自然扩展了矩阵。对于矩阵 M ∈ T q m × ( n + 1 ) \mathbf{M}\in\mathbb{T}_q^{m\times (n+1)} M∈Tqm×(n+1),对应的 G − 1 ( M ) ∈ Z m × ( n + 1 ) l \mathbf{G}^{-1}(\mathbf{M})\in\mathbb{Z}^{m\times (n+1)l} G−1(M)∈Zm×(n+1)l定义为 m × ( n + 1 ) l m\times (n+1)l m×(n+1)l矩阵,其第 # i \#i #i行为 G − 1 ( m i ) \mathbf{G}^{-1}(m_i) G−1(mi),其中 m i m_i mi为 M \mathbf{M} M的第 # i \#i #i行。满足 G − 1 ( M ) ⋅ G ≈ M \mathbf{G}^{-1}(\mathbf{M})\cdot \mathbf{G}\approx \mathbf{M} G−1(M)⋅G≈M。
TGSW encryption加密方案:
- gadget matrix可构建基于torus的Gentry–Sahai–Waters(GSW)加密方案变种。
令整数 p ∣ q p|q p∣q,其中 q = 2 Ω q=2^{\Omega} q=2Ω。基于 T q \mathbb{T}_q Tq的gadget decomposition中,整数 B , l B,l B,l满足 B l ∣ q B^l|q Bl∣q。 G T \mathbf{G}^T GT中所有值要么为0,要么为 B − j B^{-j} B−j格式,其中 1 ≤ j ≤ l 1\leq j\leq l 1≤j≤l。
gadget matrix G \mathbf{G} G实际是基于 B − l Z / Z ⊆ T q B^{-l}\mathbb{Z}/\mathbb{Z}\subseteq\mathbb{T}_q B−lZ/Z⊆Tq定义的。
TGSW encryption加密方案中假设 p = B l p=B^l p=Bl,gadget matrix G \mathbf{G} G实际是基于 T p = p − 1 Z / Z \mathbb{T}_p=p^{-1}\mathbb{Z}/\mathbb{Z} Tp=p−1Z/Z定义的。
私钥为 s = ( s 1 , ⋯ , s n ) ∈ B n \mathbf{s}=(s_1,\cdots,s_n)\in\mathbb{B}^n s=(s1,⋯,sn)∈Bn,明文空间为 P ˉ : = Z / p Z \bar{\mathcal{P}}:=\mathbb{Z}/p\mathbb{Z} Pˉ:=Z/pZ。用私钥 s \mathbf{s} s对 m ∈ P ˉ m\in\bar{\mathcal{P}} m∈Pˉ的TGSW加密定义为:
T G S W s ( m ) = Z + m ⋅ G T ( ∈ T q ( n + 1 ) l × ( n + 1 ) ) TGSW_{\mathbf{s}}(m)=\mathbf{Z}+m\cdot \mathbf{G}^T(\in\mathbb{T}_q^{(n+1)l\times (n+1)}) TGSWs(m)=Z+m⋅GT(∈Tq(n+1)l×(n+1))
其中:
T G S W s ( m ) ∈ T q ( n + 1 ) l × ( n + 1 ) TGSW_{\mathbf{s}}(m)\in\mathbb{T}_q^{(n+1)l\times (n+1)} TGSWs(m)∈Tq(n+1)l×(n+1)中最后一行是 T L W E s ( 0 ) + m ⋅ ( 0 , ⋯ , 0 , 1 B l ) ∈ T q n + 1 TLWE_{\mathbf{s}}(0)+m\cdot (0,\cdots,0,\frac{1}{B^l})\in\mathbb{T}_q^{n+1} TLWEs(0)+m⋅(0,⋯,0,Bl1)∈Tqn+1,即为对 μ : = m B l ∈ P \mu:=\frac{m}{B^l}\in\mathcal{P} μ:=Blm∈P的TLWE encryption,其中 P = T p \mathcal{P}=\mathbb{T}_p P=Tp。
TGSW明文基于ring P ˉ = Z / p Z \bar{\mathcal{P}}=\mathbb{Z}/p\mathbb{Z} Pˉ=Z/pZ定义。对于 m 1 , m 2 ∈ P ˉ m_1,m_2\in\bar{\mathcal{P}} m1,m2∈Pˉ,及其相应的密文 C 1 ← T G S W s ( m 1 ) \mathbf{C}_1\leftarrow TGSW_{\mathbf{s}}(m_1) C1←TGSWs(m1)和 C 2 ← T G S W s ( m 2 ) \mathbf{C}_2\leftarrow TGSW_{\mathbf{s}}(m_2) C2←TGSWs(m2)。令 C 3 = C 1 ⊠ C 2 : = G − 1 ( C 2 ) ⋅ C 1 \mathbf{C}_3=\mathbf{C}_1\boxtimes \mathbf{C}_2:=\mathbf{G}^{-1}(\mathbf{C}_2)\cdot \mathbf{C}_1 C3=C1⊠C2:=G−1(C2)⋅C1——这就是密文的[internal] product [GSW13, AP14, DM15]。
可验证 C 3 = C 1 ⊠ C 2 \mathbf{C}_3=\mathbf{C}_1\boxtimes \mathbf{C}_2 C3=C1⊠C2为具有一定rounding error 和 multiplicative noise的 m 3 = m 1 × m 2 ( m o d p ) m_3=m_1\times m_2(\mod p) m3=m1×m2(modp)的TGSW。
对应的证明为:
若 Z ∈ T q ( n + 1 ) × ( n + 1 ) \mathbf{Z}\in\mathbb{T}_q^{(n+1)\times (n+1)} Z∈Tq(n+1)×(n+1)矩阵各行为对 0 0 0的TLWE加密,则对于任意(small)矩阵 A ∈ Z m × ( n + 1 ) \mathbf{A}\in\mathbb{Z}^{m\times (n+1)} A∈Zm×(n+1),矩阵 Z ′ = A ⋅ Z ∈ T q m × ( n + 1 ) \mathbf{Z}'=\mathbf{A\cdot Z}\in\mathbb{T}_q^{m\times(n+1)} Z′=A⋅Z∈Tqm×(n+1)中各行为TLWE encryption of 0(up to the noise)。
举个例子:
注意,以上证明中, Z 3 \mathbf{Z}_3 Z3中的错误项由三部分组成:
- 1)源自 Z 1 \mathbf{Z}_1 Z1的噪声,放大了 G − 1 ( C 2 ) \mathbf{G}^{-1}(\mathbf{C}_2) G−1(C2)倍。
倍乘的噪声增长很快。不过若所使用的gadget矩阵满足 ∥ G − 1 ( C 2 ) ∥ ∞ ≤ B / 2 \begin{Vmatrix} \mathbf{G}^{-1}(\mathbf{C}_2) \end{Vmatrix}_{\infty}\leq B/2 G−1(C2) ∞≤B/2。 - 2)源自 Z 2 \mathbf{Z}_2 Z2的噪声,放大了 m 1 m_1 m1倍。
- 3)源自rounding error ϵ 2 \epsilon_2 ϵ2,放大了 m 1 m_1 m1倍。
若明文 m 1 m_1 m1保持small(如限定 m 1 m_1 m1为 { 0 , 1 } \{0,1\} { 0,1}中元素),则上面2)3)项的噪声和错误也可控制住。
密文的external product:
TLWE密文要远短于TGSW密文,因此优选TLWE密文。
- 对于某正数 m 1 ∈ P ˉ m_1\in\bar{\mathcal{P}} m1∈Pˉ和明文 μ 2 ∈ P ⊂ T q \mu_2\in\mathcal{P}\sub \mathbb{T}_q μ2∈P⊂Tq可将TLWE看成是明文的external product: m 1 ⋅ μ 2 m_1\cdot \mu_2 m1⋅μ2。
- 对应 m 1 ⋅ μ 2 m_1\cdot \mu_2 m1⋅μ2的密文external product,以 ⊡ \boxdot ⊡来表示:
⊡ : T G S W × T L W E → T L W E , ( C 1 , c 2 ) ↦ C 1 ⊡ c 2 = G − 1 ( c 2 ) ⋅ C 1 \boxdot:TGSW\times TLWE \rightarrow TLWE,(\mathbf{C}_1,\mathbf{c}_2)\mapsto \mathbf{C}_1\boxdot\mathbf{c}_2=\mathbf{G}^{-1}(\mathbf{c}_2)\cdot \mathbf{C}_1 ⊡:TGSW×TLWE→TLWE,(C1,c2)↦C1⊡c2=G−1(c2)⋅C1
其中:
- C 1 ← T G S W s ( m 1 ) \mathbf{C}_1\leftarrow TGSW_{\mathbf{s}}(m_1) C1←TGSWs(m1),其中 m 1 ∈ P ˉ m_1\in\bar{\mathcal{P}} m1∈Pˉ。有:
C 1 = Z 1 + m 1 ⋅ G T ∈ T q ( n + 1 ) l × ( n + 1 ) \mathbf{C}_1=\mathbf{Z}_1+m_1\cdot \mathbf{G}^T\in\mathbb{T}_q^{(n+1)l\times (n+1)} C1=Z1+m1⋅GT∈Tq(n+1)l×(n+1),其中:- Z 1 = ( a 1 , 1 ⋯ a 1 , n b 1 a 2 , 1 ⋯ a 2 , n b 2 ⋮ ⋮ ⋮ a ( n + 1 ) l , 1 ⋯ a ( n + 1 ) l , n b ( n + 1 ) l ) \mathbf{Z}_1=\begin{pmatrix} a_{1,1} & \cdots & a_{1,n} & b_1\\ a_{2,1} & \cdots & a_{2,n} & b_2\\ \vdots & & \vdots & \vdots \\ a_{(n+1)l,1} & \cdots & a_{(n+1)l,n} & b_{(n+1)l} \end{pmatrix} Z1= a1,1a2,1⋮a(n+1)l,1⋯⋯⋯a1,na2,n⋮a(n+1)l,nb1b2⋮b(n+1)l
- { ( a i , 1 , ⋯ , a i , n ) ← § T q n b i = ∑ j = 1 n s j ⋅ a i , j + ( e 1 ) i \left\{\begin{matrix} (a_{i,1},\cdots,a_{i,n})\xleftarrow{\S} \mathbb{T}_q^n \\ b_i=\sum_{j=1}^{n}s_j\cdot a_{i,j}+(e_1)_i \end{matrix}\right. { (ai,1,⋯,ai,n)§Tqnbi=∑j=1nsj⋅ai,j+(e1)i
- 对于 1 ≤ i ≤ ( n + 1 ) l 1\leq i\leq (n+1)l 1≤i≤(n+1)l, ( e 1 ) i (e_1)_i (e1)i为“small”的。
- c 2 ← T L W E s ( μ 2 ) \mathbf{c}_2\leftarrow TLWE_{\mathbf{s}}(\mu_2) c2←TLWEs(μ2),其中 μ 2 ∈ P \mu_2\in\mathcal{P} μ2∈P。有:
c 2 = ( a 1 ′ , ⋯ , a n ′ , b ′ ) \mathbf{c}_2=(a_1',\cdots,a_n',b') c2=(a1′,⋯,an′,b′),其中:- { ( a 1 ′ , ⋯ , a n ′ ) ← § T q n b ′ = ∑ j = 1 n s j ⋅ a j ′ + μ 2 + e 2 \left\{\begin{matrix} (a_{1}',\cdots,a_{n}')\xleftarrow{\S} \mathbb{T}_q^n \\ b'=\sum_{j=1}^{n}s_j\cdot a_{j}'+\mu_2+e_2 \end{matrix}\right. { (a1′,⋯,an′)§Tqnb′=∑j=1nsj⋅aj′+μ2+e2
- e 2 e_2 e2为“small”的。
从而有:
为对 μ 3 : = m 1 ⋅ μ 2 ∈ P \mu_3:=m_1\cdot \mu_2\in\mathcal{P} μ3:=m1⋅μ2∈P的有效valid TLWE加密,若满足如下条件:
- 1)rounding error ∥ G − 1 ( c 2 ) ⋅ G T − c 2 ∥ ∞ \begin{Vmatrix} \mathbf{G}^{-1}(\mathbf{c}_2)\cdot \mathbf{G}^T-\mathbf{c}_2 \end{Vmatrix}_{\infty} G−1(c2)⋅GT−c2 ∞保持“small”。
- 2)倍乘后的噪声 e 3 : = G − 1 ( c 2 ) ⋅ e 1 T + m 1 ⋅ e 2 e_3:=\mathbf{G}^{-1}(\mathbf{c}_2)\cdot \mathbf{e}_1^{T}+m_1\cdot e_2 e3:=G−1(c2)⋅e1T+m1⋅e2保持“small”,其中 e 1 = ( ( e 1 ) 1 , ⋯ , ( e 1 ) ( n + 1 ) l ) \mathbf{e}_1=((e_1)_1,\cdots,(e_1)_{(n+1)l}) e1=((e1)1,⋯,(e1)(n+1)l)。
5.2 TGLWE密文
TLWE和TGSW的底层计算和运算可扩展到多项式。以Torus多项式来替换Torus元素。加法和外乘做模 X N + 1 X^N+1 XN+1。使用(基于 T N , q [ X ] \mathbb{T}_{N,q}[X] TN,q[X])的gadget matrix来控制噪声增长。
5.2.1 TGLWE密文加法运算
5.2.2 TGLWE密文与已知多项式的乘法运算
5.2.3 TGLWE密文之间乘法运算
相应的gadget matrix为:
需注意,TGLWE密文,可看成是: T G L W E s ( u ) ≡ T G L W E s ( 0 ) + ( 0 , ⋯ , 0 , 1 ) ⋅ u TGLWE_{\mathfrak{s}}(\mathfrak{u})\equiv TGLWE_{\mathfrak{s}}(0)+(0,\cdots,0,1)\cdot \mathfrak{u} TGLWEs(u)≡TGLWEs(0)+(0,⋯,0,1)⋅u。
相应的TGGSW密文定义为:
TGGSW密文与TGLWE密文的external product运算定义为:【结果为某TGLWE密文】
TFHE中,TGGSW密文与TGLWE密文的external product运算,的主要应用场景为:
- “controlled” multiplexer,或简称为CMUX。
具体为:
- 已知2个TGLWE密文 c 0 ← T G L W E s ( u 0 ) \mathfrak{c}_0\leftarrow TGLWE_{\mathfrak{s}}(\mathfrak{u}_0) c0←TGLWEs(u0)和 c 1 ← T G L W E s ( u 1 ) \mathfrak{c}_1\leftarrow TGLWE_{\mathfrak{s}}(\mathfrak{u}_1) c1←TGLWEs(u1)
- CMux operator,用作selector,根据某control bit b ∈ { 0 , 1 } b\in\{0,1\} b∈{ 0,1}的TGGSW密文 C b ← T G L W E s ( b ) \mathfrak{C}_b\leftarrow TGLWE_{\mathfrak{s}}(b) Cb←TGLWEs(b),在 c 0 \mathfrak{c}_0 c0和 c 0 \mathfrak{c}_0 c0之间做选择。
- 可通过如下external product来实现:【其输出即为 u b \mathfrak{u}_b ub的TGLWE密文。】
5.3 基于已加密数据处理注意事项
对整数模 p p p的编码(包括 p = 2 p=2 p=2的情况),见 论文 Guide to Fully Homomorphic Encryption over the [Discretized] Torus 2.2节。
这种编码是同态的,并遵循加密的同态结构。
具体为:【同理,这些编码对论文 Guide to Fully Homomorphic Encryption over the [Discretized] Torus 2.2节 固定精度的torus元素也成立。】
- 对任意的 i 1 , i 2 ∈ Z / p Z i_1,i_2\in\mathbb{Z}/p\mathbb{Z} i1,i2∈Z/pZ。令 i 3 = i 1 + i 2 m o d p i_3=i_1+i_2\mod p i3=i1+i2modp,有 E n c o d e ( i 3 ) = E n c o d e ( i 1 ) + E n c o d e ( i 2 ) Encode(i_3)=Encode(i_1)+Encode(i_2) Encode(i3)=Encode(i1)+Encode(i2) in T p \mathbb{T}_p Tp。
- 对任意的 i ∈ Z / p Z i\in\mathbb{Z}/p\mathbb{Z} i∈Z/pZ和整数 k k k。令 i k = k ⋅ i m o d p i_k=k\cdot i\mod p ik=k⋅imodp,有 E n c o d e ( i k ) = k ⋅ E n c o d e ( i ) Encode(i_k)=k\cdot Encode(i) Encode(ik)=k⋅Encode(i) in T p \mathbb{T}_p Tp。
6. Programmable Bootstrapping可编程自举
之前已提及,TLWE和TGLWE加密均需要实现特定操作——bootstrapping自举:
- 其核心为刷新含噪声的TLWE密文
- 应可编程,以同时对某选定函数进行evaluate。
6.1 Gentry’s Recryption
对于(对称)全同态加密算法 E n c r y p t Encrypt Encrypt:
- 已知,私钥 s k sk sk对 x x x的密文 E n c r y p t s k ( x ) Encrypt_{sk}(x) Encryptsk(x)
- 对某单变量函数 f f f的同态evaluation结果为,对 f ( x ) f(x) f(x)的密文 E n c r y p t s k ( f ( x ) ) Encrypt_{sk}(f(x)) Encryptsk(f(x))
[Gen10] Gentry用于降低密文中噪声的核心思想为:采用采用同态加密自身的解密密钥,来对密文的解密进行同态evaluate。该解密密钥的加密(与用于生成密文的加密密钥匹配),构成了bootstrapping key自举密钥。
令:
- c ← E n c r y p t s k 1 ( m ) c\leftarrow \mathfrak{E}ncrypt_{sk_1}(m) c←Encryptsk1(m):表示对明文 m m m的有噪声密文加密。
- b s k ← E n c r y p t s k 2 ( s k 1 ) bsk\leftarrow Encrypt_{sk_2}(sk_1) bsk←Encryptsk2(sk1):表示自举密钥。
假设上图中的 f f f函数,为针对密文 c c c的解密函数,可将其看成是单变量函数 D e c r y p t ( ⋅ , c ) \mathfrak{D}ecrypt(\cdot,c) Decrypt(⋅,c)。则令 x = s k 1 x=sk_1 x=sk1,对 f f f的同态evaluation值为:
E n c r y p t s k 2 ( f ( x ) ) = E n c r y p t s k 2 ( D e c r y p t ( s k 1 , c ) ) = E n c r y p t s k 2 ( m ) Encrypt_{sk_2}(f(x))=Encrypt_{sk2}(\mathfrak{D}ecrypt(sk_1,c))=Encrypt_{sk_2}(m) Encryptsk2(f(x))=Encryptsk2(Decrypt(sk1,c))=Encryptsk2(m)
整个流程如下图所示:
针对有噪声密文 c ← E n c r y p t s k 1 ( m ) c\leftarrow \mathfrak{E}ncrypt_{sk_1}(m) c←Encryptsk1(m),该recryption流程输出,对相同明文 m m m加密的 新密文 E n c r y p t s k 2 ( m ) Encrypt_{sk_2}(m) Encryptsk2(m)。注意,这2个加密密钥是不同的。加密算法 E n c r y p t Encrypt Encrypt和 E n c r y p t \mathfrak{E}ncrypt Encrypt可以相同,也可以不同。若加密算法 E n c r y p t Encrypt Encrypt和 E n c r y p t \mathfrak{E}ncrypt Encrypt相同,则借助标准的key-switching技术,所生成的密文可再revert回基于初始密钥 s k 1 sk_1 sk1的密文。
6.2 Bootstrapping
对于 s = ( s 1 , ⋯ , s n ) ∈ B n \mathbf{s}=(s_1,\cdots,s_n)\in\mathbb{B}^n s=(s1,⋯,sn)∈Bn。
对 μ ∈ P \mu\in\mathcal{P} μ∈P的TWLE加密为:
- c ← T L W E s = ( a 1 , ⋯ , a n , b ) ∈ T q n + 1 \mathbf{c}\leftarrow TLWE_{\mathbf{s}}=(a_1,\cdots,a_n,b)\in\mathbb{T}_q^{n+1} c←TLWEs=(a1,⋯,an,b)∈Tqn+1
其中:
- a j ← § T q a_j\xleftarrow{\S}\mathbb{T}_q aj§Tq
- b = ∑ j = 1 n s j ⋅ a j + μ ∗ b=\sum_{j=1}^{n}s_j\cdot a_j+\mu^* b=∑j=1nsj⋅aj+μ∗, μ ∗ = μ + e \mu^*=\mu+e μ∗=μ+e, e e e为"small" noise error。
bootstrapping的目的是:
- 生成相同明文的TLWE密文,但具有减少的noise e ′ < e e'<e e′<e。
目前为止,已知的对密文自举的方式,仅为Gentry的recryption技术。
在TFHE场景下,其包含2个步骤:
- 1)获取噪声明文 μ ∗ \mu^* μ∗为 μ ∗ = b − ∑ j = 1 n s j ⋅ a j ∈ T q \mu^*=b-\sum_{j=1}^{n}s_j\cdot a_j\in\mathbb{T}_q μ∗=b−∑j=1nsj⋅aj∈Tq。
已知 s j s_j sj的密文,该计算是线性的。 - 2)对 μ ∗ \mu^* μ∗四舍五入恢复到最近的明文 μ \mu μ,具体为 μ = ⌊ p μ ∗ ⌉ m o d p p ∈ P \mu=\frac{\lfloor p\mu^*\rceil\mod p}{p}\in\mathcal{P} μ=p⌊pμ∗⌉modp∈P。
以上这2个步骤可基于已加密数据来操作。第一个步骤中,已知 s j s_j sj的密文,该计算是线性的。第二个rounding四舍五入步骤,会更困难,可借助多项式来解决。
rounding with polynomials:
已知多项式 v = v 0 + v 1 X + ⋯ + v N − 1 X N − 1 ∈ T N , p [ X ] = T p [ X ] / ( X N + 1 ) \mathfrak{v}=v_0+v_1X+\cdots +v_{N-1}X^{N-1}\in\mathbb{T}_{N,p}[X]=\mathbb{T}_p[X]/(X^N+1) v=v0+v1X+⋯+vN−1XN−1∈TN,p[X]=Tp[X]/(XN+1)。其与单项式 X − j X^{-j} X−j的外乘表示为:【见本论文3.3节】
X − j ⋅ v ( X ) = X 2 N − j ⋅ v ( X ) = { v j + ⋯ for 0 ≤ j < N − v j + ⋯ for N ≤ j < 2 N X^{-j}\cdot \mathfrak{v}(X)=X^{2N-j}\cdot \mathfrak{v}(X)=\left\{\begin{matrix} v_j+\cdots & \text{for } 0\leq j<N \\ -v_j+\cdots & \text{for } N\leq j<2N \end{matrix}\right. X−j⋅v(X)=X2N−j⋅v(X)={ vj+⋯−vj+⋯for 0≤j<Nfor N≤j<2N
即,当 0 ≤ j < N 0\leq j<N 0≤j<N时,多项式 X − j ⋅ v ( X ) X^{-j}\cdot \mathfrak{v}(X) X−j⋅v(X)的常量项为 v j v_j vj。利用可特点,可用于将torus元素 μ ∗ ∈ T q \mu^*\in\mathbb{T}_q μ∗∈Tq round 为 某元素 μ ∈ T p \mu\in\mathbb{T}_p μ∈Tp,其中 p ∣ q p|q p∣q。
由于 μ ∗ ∈ T q \mu^*\in\mathbb{T}_q μ∗∈Tq,可写成 μ ∗ = μ ˉ ∗ / q \mu^*=\bar{\mu}^*/q μ∗=μˉ∗/q,其中 μ ˉ ∗ : = ⌊ q μ ∗ ⌉ m o d q \bar{\mu}^*:=\lfloor q\mu^*\rceil\mod q μˉ∗:=⌊qμ∗⌉modq,其中 0 ≤ μ ˉ ∗ < q 0\leq \bar{\mu}^*<q 0≤μˉ∗<q。假设有 N ≥ q N\geq q N≥q,则有 0 ≤ μ ˉ ∗ < N 0\leq \bar{\mu}^*<N 0≤μˉ∗<N。也即意味着,多项式 v \mathfrak{v} v的系数个数,多于, μ ˉ ∗ \bar{\mu}^* μˉ∗的可能取值个数。因此,对于任意的 0 ≤ j < q 0\leq j <q 0≤j<q,应用 X − j ⋅ v ( X ) X^{-j}\cdot \mathfrak{v}(X) X−j⋅v(X)可生成 v j + ⋯ v_j+\cdots vj+⋯,从而选定 v j v_j vj值。特别地, X − j ⋅ v ( X ) = v j + ⋯ X^{-j}\cdot \mathfrak{v}(X)=v_j+\cdots X−j⋅v(X)=vj+⋯关系中,若选择 v j : = ⌊ ( p j ) / q ⌉ m o d p p v_j:=\frac{\lfloor (pj)/q\rceil\mod p}{p} vj:=p⌊(pj)/q⌉modp,并取 j = μ ˉ ∗ j=\bar{\mu}^* j=μˉ∗,则有:
X − μ ˉ ∗ ⋅ v ( X ) = ⌊ ( p μ ˉ ∗ ) / q ⌉ m o d p p + ⋯ = ⌊ p μ ∗ ⌉ m o d p p + ⋯ = μ + ⋯ X^{-\bar{\mu}^*}\cdot \mathfrak{v}(X)=\frac{\lfloor (p\bar{\mu}^*)/q\rceil\mod p}{p}+\cdots=\frac{\lfloor p\mu^*\rceil\mod p}{p}+\cdots=\mu+\cdots X−μˉ∗⋅v(X)=p⌊(pμˉ∗)/q⌉modp+⋯=p⌊pμ∗⌉modp+⋯=μ+⋯
这样,该多项式的常量项即为rounded值 μ ∈ T p \mu\in\mathbb{T}_p μ∈Tp。
举个例子:
6.2.1 blind rotation
令 μ ˉ ∗ = ⌊ q μ ∗ ⌉ m o d q \bar{\mu}^*=\lfloor q\mu^*\rceil\mod q μˉ∗=⌊qμ∗⌉modq,同时令 a ˉ j = ⌊ q a j ⌉ m o d q \bar{a}_j=\lfloor qa_j\rceil\mod q aˉj=⌊qaj⌉modq和 b ˉ j = ⌊ q b j ⌉ m o d q \bar{b}_j=\lfloor qb_j\rceil\mod q bˉj=⌊qbj⌉modq。
为bootstrap,可将(无rounding)的decryption看成是:
− μ ˉ ∗ = − b ˉ + ∑ j = 1 n s j a ˉ j ( m o d q ) -\bar{\mu}^*=-\bar{b}+\sum_{j=1}^{n}s_j\bar{a}_j(\mod q) −μˉ∗=−bˉ+∑j=1nsjaˉj(modq)
根据该值构建单项式 X − μ ˉ ∗ X^{-\bar{\mu}^*} X−μˉ∗,对 X − μ ˉ ∗ ⋅ v ( X ) X^{-\bar{\mu}^*}\cdot \mathfrak{v}(X) X−μˉ∗⋅v(X) evaluate可获得明文 μ \mu μ。该思想的并发症在于其假设 q < N q<N q<N,而实际设置中未验证该假设。经典密码学参数有: N ∈ { 2 10 , 2 11 , 2 12 } N\in\{2^{10},2^{11},2^{12}\} N∈{ 210,211,212}和 q ∈ { 2 32 , 2 64 } q\in\{2^{32},2^{64}\} q∈{ 232,264}:
1)首先, X − μ ˉ ∗ ⋅ v ( X ) X^{-\bar{\mu}^*}\cdot \mathfrak{v}(X) X−μˉ∗⋅v(X)关系定义于模 X N + 1 X^N+1 XN+1,即意味着,与 Z N [ X ] \mathbb{Z}_N[X] ZN[X]元素相乘后, x x x的order为 X 2 N X^{2N} X2N(即 X 2 N = 1 X^{2N}=1 X2N=1),从而 X − μ ˉ ∗ ⋅ v ( X ) X^{-\bar{\mu}^*}\cdot \mathfrak{v}(X) X−μˉ∗⋅v(X)中的指数 − μ ˉ ∗ -\bar{\mu}^* −μˉ∗定义于模 2 N 2N 2N。 μ ˉ ∗ \bar{\mu}^* μˉ∗值需重新调整为模 2 N 2N 2N。
对应的结果就是,并不再是依赖 − μ ˉ ∗ = − b ˉ + ∑ j = 1 n s j a ˉ j ( m o d q ) -\bar{\mu}^*=-\bar{b}+\sum_{j=1}^{n}s_j\bar{a}_j(\mod q) −μˉ∗=−bˉ+∑j=1nsjaˉj(modq),而改为依赖近似值:
− μ ~ ∗ = − b ~ + ∑ j = 1 n s j a ~ j ( m o d 2 N ) -\tilde{\mu}^*=-\tilde{b}+\sum_{j=1}^{n}s_j\tilde{a}_j(\mod 2N) −μ~∗=−b~+∑j=1nsja~j(mod2N)
其中:- b ~ = ⌊ 2 N b ⌉ m o d 2 N \tilde{b}=\lfloor 2Nb\rceil \mod 2N b~=⌊2Nb⌉mod2N
- a ~ j = ⌊ 2 N a j ⌉ m o d 2 N \tilde{a}_j=\lfloor 2Na_j\rceil \mod 2N a~j=⌊2Naj⌉mod2N
该近似值可能会给噪声添加一个额外的small error。
通过离散化模 2 N 2N 2N额外引入的error称为drift。可通过仔细选择参数来处理其对结果的影响。
2)由于多项式 v ∈ T N , p [ X ] \mathfrak{v}\in\mathbb{T}_{N,p}[X] v∈TN,p[X],因此其有 N N N个系数,最多可为 μ ~ ∗ \tilde{\mu}^* μ~∗编码 N N N个值。具体解决方案为:确保 μ ~ ∗ \tilde{\mu}^* μ~∗的最高有效位为0。这样, μ ~ ∗ \tilde{\mu}^* μ~∗就最多有 N N N个可能值。
基于以上考虑,定义test多项式 v \mathfrak{v} v为:
v : = v ( X ) = ∑ j = 0 N − 1 v j X j ) \mathfrak{v}:=\mathfrak{v}(X)=\sum_{j=0}^{N-1}v_jX^j) v:=v(X)=∑j=0N−1vjXj)
其中 v j = ⌊ p j 2 N ⌉ m o d p p ∈ P v_j=\frac{\lfloor \frac{pj}{2N}\rceil \mod p}{p}\in\mathcal{P} vj=p⌊2Npj⌉modp∈P
若该drift is contained,且 0 ≤ ( μ ~ ∗ m o d 2 N ) < N 0\leq (\tilde{\mu}^*\mod 2N)<N 0≤(μ~∗mod2N)<N,则relation:
X − b ~ + ∑ j = 1 n s j a ~ j ⋅ v ( X ) = X − μ ~ ∗ ⋅ v ( X ) = μ + ⋯ X^{-\tilde{b}+\sum_{j=1}^{n}s_j\tilde{a}_j}\cdot \mathfrak{v}(X)=X^{-\tilde{\mu}^*}\cdot \mathfrak{v}(X)=\mu+\cdots X−b~+∑j=1nsja~j⋅v(X)=X−μ~∗⋅v(X)=μ+⋯
成立。
更具体来说,令 q j = X − b ~ + ∑ i = 1 j s i a ~ i ⋅ v \mathfrak{q}_j=X^{-\tilde{b}+\sum_{i=1}^{j}s_i\tilde{a}_i}\cdot \mathfrak{v} qj=X−b~+∑i=1jsia~i⋅v,则该外乘具有同态性:
从而提供了基于 q 0 = X − b ~ ⋅ v \mathfrak{q}_0=X^{-\tilde{b}}\cdot \mathfrak{v} q0=X−b~⋅v, j j j由1到 n n n,迭代计算 q n = X − b ~ + ∑ i = 1 n s i a ~ i ⋅ v \mathfrak{q}_n=X^{-\tilde{b}+\sum_{i=1}^{n}s_i\tilde{a}_i}\cdot \mathfrak{v} qn=X−b~+∑i=1nsia~i⋅v的方法。
Gentry的recrption类似,但基于的是已加密数据,由于rounding方法中包含了多项式,需依赖TGLWE加密方案。
6.2.2 Sample extraction
上一节的转换步骤,可将明文 μ ∈ P \mu\in\mathcal{P} μ∈P的TLWE密文,转换为,常量项为 μ \mu μ的多项式明文 μ ( X ) : = X − μ ~ ∗ ⋅ v ∈ P N [ X ] \mu(X):=X^{-\tilde{\mu}^*}\cdot \mathfrak{v}\in\mathcal{P}_N[X] μ(X):=X−μ~∗⋅v∈PN[X] 的TGLWE密文。基于不同的key,通过 μ \mu μ的refreshed TLWE加密,可提取该常量项。该过程称为sample extraction。
需注意,尽管其用于常量项,该技术也可调整为用于提取 μ \mu μ的其它元素。
6.2.3 Key switching
至此,几乎快实现整个流程了。
以上流程中,密文 c \mathbf{c} c和 c ′ ← S a m p l e E x t r a c t ( B l i n d R o t a t e b s k ( c , c ~ ) ) \mathbf{c}'\leftarrow SampleExtract(BlindRotate_{bsk}(\mathfrak{c},\tilde{\mathfrak{c}})) c′←SampleExtract(BlindRotatebsk(c,c~)),均为明文 μ \mu μ的加密,但其使用不同的参数集合:
c ← T L W E s ( μ ) ∈ T q n + 1 \mathbf{c}\leftarrow TLWE_{s}(\mu)\in\mathbb{T}_q^{n+1} c←TLWEs(μ)∈Tqn+1
c ′ ← T L W E s ′ ( μ ) ∈ T q k N + 1 \mathbf{c}'\leftarrow TLWE_{s'}(\mu)\in\mathbb{T}_q^{kN+1} c′←TLWEs′(μ)∈TqkN+1
key switching算法用于,将某key下的密文,转换为,另一key下的密文。其实现需要key-switching keys,即会对,对应原始key s s s的key s ′ s' s′的bits,做TLWE加密。该流程理论上看起来与bootstrapping类似,但二者的本质区别在于:
- bootstrapping用于降低噪声,且计算要求高
- key switching用于增加噪声,但evaluate更便宜。
6.2.4 Putting it all together
完整的bootstrapping流程为:
6.3 Programmable Bootstrapping
(常规的)bootstrapping本质上依赖于:
- 对于任意的 0 ≤ j < N 0\leq j<N 0≤j<N,有 X − j ⋅ v ( X ) = v j + ⋯ X^{-j}\cdot \mathfrak{v}(X)=v_j+\cdots X−j⋅v(X)=vj+⋯
以上各章节中,test多项式 v ∈ T N [ X ] \mathfrak{v}\in\mathbb{T}_N[X] v∈TN[X]定义为:
v ( X ) = ∑ j = 0 N − 1 ⌊ p j / ( 2 N ) ⌉ m o d p p X j \mathfrak{v}(X)=\sum_{j=0}^{N-1}\frac{\lfloor pj/(2N)\rceil\mod p}{p}X^j v(X)=∑j=0N−1p⌊pj/(2N)⌉modpXj
现在,已知函数 f : T p → T p f:\mathbb{T}_p\rightarrow \mathbb{T}_p f:Tp→Tp,定义test多项式 v \mathfrak{v} v为:
v ( X ) = ∑ j = 0 N − 1 f ( ⌊ p j / ( 2 N ) ⌉ m o d p p ) X j \mathfrak{v}(X)=\sum_{j=0}^{N-1}f(\frac{\lfloor pj/(2N)\rceil\mod p}{p})X^j v(X)=∑j=0N−1f(p⌊pj/(2N)⌉modp)Xj
注意,该resulting多项式 X − μ ~ ∗ ⋅ v ( X ) X^{-\tilde{\mu}^*}\cdot\mathfrak{v}(X) X−μ~∗⋅v(X),假设drift的影响可忽略,且 0 ≤ ( μ ~ ∗ m o d 2 N ) < N 0\leq (\tilde{\mu}^*\mod 2N)<N 0≤(μ~∗mod2N)<N,其具有常量项:
f ( ⌊ p μ ~ ∗ / ( 2 N ) ⌉ m o d p p ) = f ( μ ) f(\frac{\lfloor p\tilde{\mu}^*/(2N)\rceil\mod p}{p})=f(\mu) f(p⌊pμ~∗/(2N)⌉modp)=f(μ)
因此,对于上一节的bootstrapping流程,其输入为某(noisy)密文 c ← T L W E s ( μ ) \mathbf{c}\leftarrow TLWE_{s}(\mu) c←TLWEs(μ),输出为TLWE密文 c ′ ← T L W E s ( f ( μ ) ) \mathbf{c}'\leftarrow TLWE_{s}(f(\mu)) c′←TLWEs(f(μ)),其中引入了少量噪声。
注意,该常规bootstrapping对应 f f f的identity function。
同时注意:当函数 f f f为negacyclic(即,若 f ( μ + 1 2 ) = − f ( μ ) , ∀ μ ∈ T p f(\mu+\frac{1}{2})=-f(\mu),\forall \mu\in\mathbb{T}_p f(μ+21)=−f(μ),∀μ∈Tp),可解除对 μ ~ ∗ \tilde{\mu}^* μ~∗的范围限制。基于torus的“sign”函数,即为一种negacyclic函数。
6.4 更多技术
上面的bootstrapping和programmable bootstrapping技术,可在不同方向进行扩展,如:
任意函数:
更大精度:
multi-value programmable bootstrapping:
Ternary keys and more:
参考资料
[1] Zama团队的Marc Joye 2021年论文 Guide to Fully Homomorphic Encryption over the [Discretized] Torus