基于[Discretized] Torus的全同态加密指引(2)

2023-12-22 19:52:40

前序博客有:

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=1n?sj??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=1n?sj??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) cTLWEs?(μ),对于某已知(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?cTLWEs?(μ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 l1,其满足 B l ∣ q B^{l}|q Blq,对于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} uZ(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} vTqn+1?,有:
    G ? 1 ( v ) ? G T ≈ v \mathbf{G}^{-1}(\mathbf{v})\cdot \mathbf{G}^T\approx \mathbf{v} G?1(v)?GTv 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=1l?ui,j?Bl?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)} MTqm×(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)?GM

TGSW encryption加密方案:

  • gadget matrix可构建基于torus的Gentry–Sahai–Waters(GSW)加密方案变种。

令整数 p ∣ q p|q pq,其中 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 Blq G T \mathbf{G}^T GT中所有值要么为0,要么为 B ? j B^{-j} B?j格式,其中 1 ≤ j ≤ l 1\leq j\leq l 1jl
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}} mPˉ的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)} ZTq(n+1)×(n+1)?矩阵各行为对 0 0 0的TLWE加密,则对于任意(small)矩阵 A ∈ Z m × ( n + 1 ) \mathbf{A}\in\mathbb{Z}^{m\times (n+1)} AZm×(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?ZTqm×(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×TLWETLWE,(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??GTTq(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,1?a2,1??a(n+1)l,1??????a1,n?a2,n??a(n+1)l,n??b1?b2??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?)§ ?Tqn?bi?=j=1n?sj??ai,j?+(e1?)i??
    • 对于 1 ≤ i ≤ ( n + 1 ) l 1\leq i\leq (n+1)l 1i(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?)§ ?Tqn?b=j=1n?sj??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?+i2?modp,有 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} iZ/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) cEncryptsk1??(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) bskEncryptsk2??(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) cEncryptsk1??(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} cTLWEs?=(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=1n?sj??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=1n?sj??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?+v1?X+?+vN?1?XN?1TN,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?0j<Nfor?Nj<2N?
即,当 0 ≤ j < N 0\leq j<N 0j<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 pq

由于 μ ? ∈ 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 Nq,则有 0 ≤ μ ˉ ? < N 0\leq \bar{\mu}^*<N 0μˉ??<N。也即意味着,多项式 v \mathfrak{v} v的系数个数,多于, μ ˉ ? \bar{\mu}^* μˉ??的可能取值个数。因此,对于任意的 0 ≤ j < q 0\leq j <q 0j<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=1n?sj?aˉ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=1n?sj?aˉ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=1n?sj?a~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] vTN,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?1?vj?Xj)
其中 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=1n?sj?a~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=1j?si?a~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=1n?si?a~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?μ~???vPN?[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}})) cSampleExtract(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} cTLWEs?(μ)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} cTLWEs?(μ)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 0j<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] vTN?[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?1?p?pj/(2N)?modp?Xj

现在,已知函数 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?1?f(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) cTLWEs?(μ),输出为TLWE密文 c ′ ← T L W E s ( f ( μ ) ) \mathbf{c}'\leftarrow TLWE_{s}(f(\mu)) cTLWEs?(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

FHE系列博客

文章来源:https://blog.csdn.net/mutourend/article/details/135063012
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。