多密鑰TFHE學習筆記1-MKTFHE的整體流程

• MK-TFHE 的整體流程圖
• TFHE 的多密鑰變體的關鍵步驟
• • 1. 設定 - MKHE.Setup( 1 λ 1^{\lambda} 1λ )
  • 2. 密鑰生成 - MKHE.KeyGen()
  • 3. 加密 - MKHE.Enc( m m m )
  • 4. 解密 - MKHE.Dec( c t ‾ , { s i } i ∈ [ k ] \overline{ct}, \{ \pmb{s}_i \} _{i \in [k]} ct,{sssi​}i∈[k]​ )
  • 5. 與非門運算 - MKHE.NAND( c t 1 ‾ , c t 2 ‾ , { ( P K i , B K i , K S i ) } i ∈ [ k ] \overline{ct_1}, \overline{ct_2}, \{ (PK_i, BK_i, KS_i) \}_{i \in [k]} ct1​​,ct2​​,{(PKi​,BKi​,KSi​)}i∈[k]​ )

MK-TFHE 的整體流程圖

MK-TFHE的整體流程從使用者與伺服器的角度看大緻如下所示：

1. 首先生成公共參數 CRS，将參數發送給每個參與方以及伺服器（如果CRS生成不在伺服器）

   

2. 每個參與方獨立地生成自己的密鑰并加密消息，發送至伺服器

   

3. 伺服器進行同台評估過程，将結果傳回給參與方

   

4. （在聯合解密中）所有參與計算的參與方共同解密密文，得到結果

   

TFHE 的多密鑰變體的關鍵步驟

首先做一些約定：

• 除非特殊說明，否則算法以 2 為底數。
• 向量使用加粗的字型表示，矩陣使用加粗大寫的字型表示。
• 内積使用 < ⋅ , ⋅ > < \sdot , \sdot> <⋅,⋅> 表示。
• 對于實數 r r r ，使用 ⌊ r ⌉ \lfloor r \rceil ⌊r⌉ 表示取整（取距離 r r r 最近的整數，相等時向上舍入）。
• 使用 x ← D x \leftarrow D x←D 表示從分布 D D D 中取樣 (sample) x x x 。
• 對于有限集合 S S S ，使用 U ( S ) U(S) U(S) 表示集合 S S S 上的均勻分布。
• 使用 D α D_{\alpha} Dα​ 表示方差為 α 2 \alpha^{2} α2 的高斯分布。
• 使用 λ \lambda λ 表示安全參數。
• 所有已知的對該密碼方案的攻擊需要 Ω ( 2 λ ) \Omega(2^{\lambda}) Ω(2λ) 比特的操作。
• 對于正整數 k k k ，使用 [ k ] [k] [k] 表示其索引集合 { 1 , 2 , . . . , k } \{1, 2, ... ,k\} {1,2,...,k} 。

以下為多密鑰 TFHE (MKTFHE) 的重要步驟：

1. 設定 - MKHE.Setup( 1 λ 1^{\lambda} 1λ )

1. 調用 LWE.Setup ( 1 λ 1^\lambda 1λ ) 來生成 LWE 的參數 p p L W E = ( n , χ , α , B ′ , d ′ ) pp^{LWE} = (n, \chi, \alpha, B', d') ppLWE=(n,χ,α,B′,d′) 。其中 n n n 為 LWE 的次元， χ \chi χ 為 LWE 密鑰的分布， α \alpha α 為錯誤率， B ′ B' B′ 為分解基， d ′ d' d′ 為密鑰轉換 gadget 向量的次元。密鑰轉換 gadget 向量： g ′ = ( B ′ − 1 , . . . , B ′ − d ′ ) g' = (B'^{-1}, ... , B'^{-d'}) g′=(B′−1,...,B′−d′) 。
2. 調用 RLWE.Setup ( 1 λ 1^\lambda 1λ ) 來生成 RLWE 的參數 p p R L W E = ( N , ψ , β , B , d , a ) pp^{RLWE} = (N, \psi, \beta, B, d,\pmb{a}) ppRLWE=(N,ψ,β,B,d,aaa) 。其中 N N N 為 RLWE 的次元（2的幂）， ψ \psi ψ 為 RLWE 密鑰在 R R R 上的分布，并且錯誤率為 α \alpha α ， B ≥ 2 B \geq 2 B≥2 是整數基，分解次元為 d d d ， gadget 向量為 g = ( B − 1 , . . . , B − d ) g = (B^{-1}, ... , B^{-d}) g=(B−1,...,B−d) 。 a \pmb{a} aaa 為分布 T d T^d Td 上的均勻分布的采樣。
3. 傳回生成的公共參數 p p M K H E = ( p p L W E , p p R L W E ) pp^{MKHE} = (pp^{LWE}, pp^{RLWE}) ppMKHE=(ppLWE,ppRLWE) 。

*假設 MKHE 的算法都預設将 p p M K H E pp^{MKHE} ppMKHE 作為輸入。公共參數為 CRS ，可以了解為是所有人都知道的資訊。

2. 密鑰生成 - MKHE.KeyGen()

1. 生成 LWE 密鑰 s i ← L W E . K e y G e n ( ) s_i \leftarrow LWE.KeyGen() si​←LWE.KeyGen() 。這一步僅為從分布 χ \chi χ 中采樣密鑰。
2. 運作 ( z i , b i ) ← R L W E . K e y G e n ( ) (z_i, \pmb{b}_i) \leftarrow RLWE.KeyGen() (zi​,bbbi​)←RLWE.KeyGen() 并且設定公鑰為 P K i = b i PK_i = \pmb{b}_i PKi​=bbbi​ 。從分布 ψ \psi ψ 中采樣 z z z ，設 z = ( 1 , z ) \pmb{z} = (1, z) zzz=(1,z) 。從 D α d D_{\alpha}^d Dαd​ 中取一個誤差向量 e \pmb{e} eee ，計算公鑰 b = − z ⋅ a + e \pmb{b} = -z \sdot \pmb{a} + \pmb{e} bbb=−z⋅aaa+eee (mod 1) 。對于 z i = z 1 , 0 + z i , 1 X + . . . + z i , N − 1 X N − 1 z_i = z_{1,0} + z_{i,1}X + ... + z_{i,N-1}X^{N-1} zi​=z1,0​+zi,1​X+...+zi,N−1​XN−1 ，記 z i ∗ = ( z i , 0 , − z i , N − 1 , . . . , − z i , 1 ) ∈ Z N \pmb{z}_i^* = (z_{i,0},-z_{i,N-1}, ... , -z_{i,1}) \in \mathbb{Z}^N zzzi∗​=(zi,0​,−zi,N−1​,...,−zi,1​)∈ZN 。
3. 對于 j ∈ [ n ] j \in [n] j∈[n] ，生成 ( d i , j , F i , j ) ← R L W E . U n i E n c ( s i , j , z i ) (\pmb{d}_{i,j}, \pmb{F}_{i,j}) \leftarrow RLWE.UniEnc(s_{i,j},z_i) (dddi,j​,FFFi,j​)←RLWE.UniEnc(si,j​,zi​) ，即使用 RLWE 密鑰加密 LWE 密鑰。同時，設定自舉密鑰為 B K i = { ( d i , j , F i , j ) } j ∈ [ n ] BK_i = \{ (\pmb{d}_{i,j}, \pmb{F}_{i,j}) \}_{j \in [n]} BKi​={(dddi,j​,FFFi,j​)}j∈[n]​ 。從 ψ \psi ψ 中取一個随機值 r r r ，可将 d \pmb{d} ddd 看作是随機值 r r r 加密下的 LWE 密鑰 s s s ，将 F \pmb{F} FFF 看成是 RLWE 密鑰 z z z 加密下的随機值 r r r 。
4. 生成密鑰轉換密鑰 K S ← L W E . K S G e n ( z i ∗ , s i ) KS \leftarrow LWE.KSGen(\pmb{z}_i^*, \pmb{s}_i) KS←LWE.KSGen(zzzi∗​,sssi​) ，能夠将一個與 t ∈ Z N \pmb{t} \in \mathbb{Z}^N ttt∈ZN 對應的 LWE 密文轉換為同一消息在 s ∈ Z n \pmb{s} \in \mathbb{Z}^n sss∈Zn 加密下的另一個 LWE 密文。
5. 傳回密鑰 s i \pmb{s}_i sssi​ ，公開密鑰的三元組 ( P K i , B K i , K S i ) (PK_i, BK_i, KS_i) (PKi​,BKi​,KSi​) ，分别為公鑰、自舉密鑰、密鑰轉換密鑰。

*每個參與方都獨立進行該步驟，下标 i i i 表示第 i i i 個參與方。

*注意對于任意 a = a 0 + a 1 X + . . . + a N − 1 X N − 1 ∈ T a = a_0 + a_1X + ... + a_{N-1}X^{N-1} \in T a=a0​+a1​X+...+aN−1​XN−1∈T 和它的系數構成的向量 ( a 0 , . . . , a N − 1 ) ∈ T N (a_0, ... , a_{N-1}) \in \mathbb{T}^N (a0​,...,aN−1​)∈TN ， a ⋅ z ∈ T a \sdot z \in T a⋅z∈T 的常數項等價于 < a , z ⋆ > < \pmb{a}, \pmb{z}^{\star}> <aaa,zzz⋆> 模 1 ，其中 T = T [ X ] / ( X N + 1 ) T = \mathbb{T} [X] / (X^N + 1) T=T[X]/(XN+1) 。

3. 加密 - MKHE.Enc( m m m )

對于輸入比特 m ∈ { 0 , 1 } m \in \{ 0, 1 \} m∈{0,1} ，運作 L W E . E n c ( m ) LWE.Enc(m) LWE.Enc(m) 并傳回一個 LWE 密文，其中 scaling factor = 1 4 \frac{1}{4} 41​ （與 FHEW/TFHE 方案中意義相同）。這是一個标準的 LWE 加密，從 T n \mathbb{T}^n Tn 中均勻采樣得到 a \pmb{a} aaa 作為 mask ，從 D α D_{\alpha} Dα​ 中采樣得到 e e e 作為誤差。輸出密文 c t = ( b , a ) ∈ T n + 1 ct = (b, \pmb{a}) \in \mathbb{T}^{n+1} ct=(b,aaa)∈Tn+1 滿足 b + < a , s > ≈ 1 4 m ( m o d 1 ) b + < \pmb{a} , \pmb{s} > \approx \frac{1}{4}m \quad (mod 1) b+<aaa,sss>≈41​m(mod1) 。

*同态計算後密文的次元增加，應存儲參與方的索引以便解密和進行同态操作。

4. 解密 - MKHE.Dec( c t ‾ , { s i } i ∈ [ k ] \overline{ct}, \{ \pmb{s}_i \} _{i \in [k]} ct,{sssi​}i∈[k]​ )

對于密文 c t ‾ = ( b , a 1 , . . . , a k ) ∈ T k n + 1 \overline{ct} = (b, \pmb{a}_1, ... , \pmb{a}_k) \in \mathbb{T}^{kn+1} ct=(b,aaa1​,...,aaak​)∈Tkn+1 和一組密鑰 ( s 1 , . . . , s k ) (\pmb{s}_1, ..., \pmb{s}_k) (sss1​,...,sssk​) ，傳回比特 m ∈ { 0 , 1 } m \in \{ 0, 1 \} m∈{0,1} 使得 ∣ b + ∑ i = 1 k < a i , s i > − 1 4 m ∣ |b + \sum_{i = 1}^{k} <\pmb{a}_i , \pmb{s}_i> - \frac{1}{4}m | ∣b+∑i=1k​<aaai​,sssi​>−41​m∣ 最小。

5. 與非門運算 - MKHE.NAND( c t 1 ‾ , c t 2 ‾ , { ( P K i , B K i , K S i ) } i ∈ [ k ] \overline{ct_1}, \overline{ct_2}, \{ (PK_i, BK_i, KS_i) \}_{i \in [k]} ct1​​,ct2​​,{(PKi​,BKi​,KSi​)}i∈[k]​ )

給定兩個 LWE 密文 c t 1 ‾ ∈ T k 1 n + 1 \overline{ct_1} \in \mathbb{T}^{k_1n+1} ct1​​∈Tk1​n+1 和 c t 2 ‾ ∈ T k 2 n + 1 \overline{ct_2} \in \mathbb{T}^{k_2n+1} ct2​​∈Tk2​n+1 ，令 k k k 為參與者的數量，與 c t 1 ‾ \overline{ct_1} ct1​​ 或 c t 2 ‾ \overline{ct_2} ct2​​ 相關。對于 i ∈ [ k ] i \in [k] i∈[k] ， P K i = b i , B K i = { ( d i , j , F i , j ) } i ∈ [ k ] , K S i PK_i = \pmb{b}_i , BK_i = \{ (\pmb{d}_{i,j}, \pmb{F}_{i,j}) \}_{i \in [k]}, KS_i PKi​=bbbi​,BKi​={(dddi,j​,FFFi,j​)}i∈[k]​,KSi​ 分别為第 j j j 個參與方的 公鑰、自舉密鑰、密鑰轉換密鑰。

1. 拓展輸入的 LWE 密文并且在密文比特上同态評估與非門 m = m 1 ⊼ m 2 m = m_1 \barwedge m_2 m=m1​⊼m2​ 。
   1. 将密文 c t 1 ‾ \overline{ct_1} ct1​​ 和 c t 2 ‾ \overline{ct_2} ct2​​ 拓展至 c t 1 ‾ ′ ， c t 2 ‾ ′ ∈ T k n + 1 \overline{ct_1}'，\overline{ct_2}' \in \mathbb{T}^{kn + 1} ct1​​′，ct2​​′∈Tkn+1 ：聯合密鑰 s ‾ = ( s 1 , . . . , s k ) ∈ Z k n \overline{\pmb{s}} = (\pmb{s}_1, ... , \pmb{s}_k) \in \mathbb{Z}^{kn} sss=(sss1​,...,sssk​)∈Zkn 加密下的相同消息。隻需要重新排列并在空槽 (slots) 中放入 0 即可。
   2. 計算 c t ‾ ′ = ( 5 8 , 0 , . . . , 0 ) − c t 1 ‾ ′ − c t 2 ‾ ′ \overline{ct}' = (\frac{5}{8}, \pmb{0}, ... , \pmb{0}) - \overline{ct_1}' - \overline{ct_2}' ct′=(85​,000,...,000)−ct1​​′−ct2​​′ (mod 1) 。這個是與非門的标志步驟。
2. 同态累加 (homomorphic accumulator) ：使用 RSGW 方案的外積來評估拓展 LWE 密文的解密電路，來實作自舉。

   1. 初始化累加器 c ˉ \bar{\pmb{c}} cccˉ ：令 c t ‾ ′ = ( b ′ , a 1 ′ , . . . , a k ′ ) ∈ T k n + 1 \overline{ct}' = (b', \pmb{a}_1', ... , \pmb{a}_k') \in \mathbb{T}^{kn+1} ct′=(b′,aaa1′​,...,aaak′​)∈Tkn+1 ，計算 b ~ = ⌊ 2 N ⋅ b ′ ⌉ \widetilde{b} = \lfloor 2N \sdot b' \rceil b

      =⌊2N⋅b′⌉ 和 a ~ i = ⌊ 2 N ⋅ a i ′ ⌉ \widetilde{\pmb{a}}_i = \lfloor 2N \sdot \pmb{a}_i' \rceil aaa

      i​=⌊2N⋅aaai′​⌉ 。初始化 RLWE 密文為 c ‾ = ( − 1 8 h ( X ) ⋅ X b ~ , 0 ) ∈ T k + 1 \overline{\pmb{c}} = (- \frac{1}{8}h(X) \sdot X ^{\tilde{b}},\pmb{0}) \in T^{k + 1} ccc=(−81​h(X)⋅Xb~,000)∈Tk+1 其中 h = ∑ − N 2 < j < N 2 X j = 1 + X + . . . + X N 2 − 1 − X N 2 + 1 − . . . − X N − 1 h = \sum_{- \frac{N}{2} < j < \frac{N}{2}} X^j = 1 + X + ... + X^{\frac{N}{2}-1} - X^{\frac{N}{2} + 1} - ... - X^{N-1} h=∑−2N​<j<2N​​Xj=1+X+...+X2N​−1−X2N​+1−...−XN−1 。這是 − 1 8 h ( X ) ⋅ X b ~ - \frac{1}{8}h(X) \sdot X ^{\tilde{b}} −81​h(X)⋅Xb~ 的平凡的 (trivial) RLWE 密文。

   2. 使用 Mux 門來實作主要的計算：對于 i ∈ [ k ] i \in [k] i∈[k] ，令 a ~ i = ( a ~ i , j ) j ∈ [ n ] \tilde{\pmb{a}}_i = (\tilde{a}_{i,j})_{j \in [n]} aaa~i​=(a~i,j​)j∈[n]​ 。對于 i ∈ [ k ] i \in [k] i∈[k] 和 j ∈ [ n ] j \in [n] j∈[n] ，遞歸地計算 c ˉ ← R L W E . C M u x ( c ˉ , X a ~ i , j ⋅ c ˉ , ( d i , j , F i , j ) , { b l } l ∈ ⌈ k ⌉ ) \bar{\pmb{c}} \leftarrow RLWE.CMux(\bar{\pmb{c}}, X^{\tilde{a}_{i,j}} \sdot \bar{\pmb{c}}, (\pmb{d}_{i,j}, \pmb{F}_{i,j}), \{ \pmb{b}_l \}_{l \in \lceil k \rceil}) cccˉ←RLWE.CMux(cccˉ,Xa~i,j​⋅cccˉ,(dddi,j​,FFFi,j​),{bbbl​}l∈⌈k⌉​) 。
   3. 傳回 c ˉ ← ( 1 8 , 0 ) + c ˉ \bar{\pmb{c}} \leftarrow (\frac{1}{8}, \pmb{0}) + \bar{\pmb{c}} cccˉ←(81​,000)+cccˉ (mod 1) 。
3. 将 c ‾ \overline{\pmb{c}} ccc 轉換為 LWE 密文并運作多密鑰的密鑰轉換算法。
   1. 對于 c ˉ = ( c 0 , c 1 , . . . , c k ) ∈ T k + 1 \bar{\pmb{c}} = (c_0, c_1, ... , c_k) \in T^{k + 1} cccˉ=(c0​,c1​,...,ck​)∈Tk+1 ，令 b ∗ b^* b∗ 為 c 0 c_0 c0​ 的常數項，對于 i ∈ [ k ] i \in [k] i∈[k] ，令 a i ∗ \pmb{a}_i^* aaai∗​ 為 c i c_i ci​ 的系數向量。計算 LWE 密文 c t ‾ ∗ = ( b ∗ , a 1 ∗ , . . . , a k ∗ ) ∈ T k N + 1 \overline{ct}^* = (b^*, \pmb{a}_1^*, ... , \pmb{a}_k^*) \in \mathbb{T}^{kN + 1} ct∗=(b∗,aaa1∗​,...,aaak∗​)∈TkN+1 。
   2. 令 K S ‾ = { K S i } i ∈ [ k ] \overline{KS} = \{ KS_i \}_{i \in [k]} KS={KSi​}i∈[k]​ ，執行多密鑰的密鑰轉換算法 (multi-key-switching) 并傳回密文 c t ‾ ′ ′ ← L W E . M K S w i t c h ( c t ‾ ∗ , K S ‾ ) \overline{ct}'' \leftarrow LWE.MKSwitch(\overline{ct}^*, \overline{KS}) ct′′←LWE.MKSwitch(ct∗,KS) 。這個密鑰轉換算法輸入拓展密文和一系列密鑰轉換密鑰，傳回相同消息在聯合密鑰加密下的密文。

實作以上五個步驟可實作 MKHE。

主要參考論文：

• Chen H, Chillotti I, Song Y. Multi-key homomorphic encryption from TFHE[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2019: 446-472.

網址：https://link.springer.com/chapter/10.1007/978-3-030-34621-8_16

算法庫：https://github.com/ilachill/MK-TFHE