Nussbaumer Transform 以及 Amortized FHEW bootstrapping

参考文献:

  1. [Nuss80] Nussbaumer H. Fast polynomial transform methods for multidimensional DFTs[C]//ICASSP’80. IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 1980, 5: 235-237.
  2. [SV11] Smart N P, Vercauteren F. Fully homomorphic SIMD operations[J]. Designs, codes and cryptography, 2014, 71: 57-81.
  3. [GHS12a] Gentry C, Halevi S, Smart N P. Fully homomorphic encryption with polylog overhead[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 465-482.
  4. [GHS12b] Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic evaluation of the AES circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 850–867, Santa Barbara, CA, USA, August 19–23, 2012. Springer, Heidelberg, Germany
  5. [GHS12c] Gentry C, Halevi S, Smart N P. Better bootstrapping in fully homomorphic encryption[C]//International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 1-16.
  6. [GHS12d] Gentry C, Halevi S, Peikert C, et al. Ring switching in BGV-style homomorphic encryption[C]//International Conference on Security and Cryptography for Networks. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 19-37.
  7. [GHPS12] Gentry C, Halevi S, Peikert C, et al. Field switching in BGV-style homomorphic encryption[J]. Journal of Computer Security, 2013, 21(5): 663-684.
  8. [AP13] Alperin-Sheriff J, Peikert C. Practical bootstrapping in quasilinear time[C]//Annual Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 1-20.
  9. [AP14] J. Alperin-Sheriff and C. Peikert. Faster bootstrapping with polynomial error. In CRYPTO 2014, volume 8616 of Lecture Notes in Computer Science, pages 297–314, 2014.
  10. [BV14] Brakerski Z, Vaikuntanathan V. Lattice-based FHE as secure as PKE[C]//Proceedings of the 5th conference on Innovations in theoretical computer science. 2014: 1-12.
  11. [DM15] L. Ducas and D. Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In EUROCRYPT (1), volume 9056 of Lecture Notes in Computer Science, pages 617–640. Springer, 2015.
  12. [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.

文章目录

  • Nussbaumer Transform
    • Multi-dimensional DFT
    • Polynomial Transform
    • Breaking Polynomials in Parts
  • Amortized FHEW bootstrapping
    • High level outline
    • Modulus Switching
    • Ring packing
    • Homomorphic Registers
    • Slow Multiplication
    • Homomorphic DFT
    • Ring Decrypt
    • MSB Extract
    • Refreshing
    • Recursive optimization

Nussbaumer Transform

Multi-dimensional DFT

p 1 , p 2 , . . . , p b p_1,p_2,...,p_b p1,p2,...,pb b b b 个整数,令 ζ j = e − 2 π i / p j \zeta_j = e^{-2 \pi i/p_j} ζj=e2πi/pj p j p_j pj 阶单位根,其中 i 2 + 1 = 0 i^2+1=0 i2+1=0。定义有限群 G : = Z p 1 × Z p 2 × ⋯ × Z p b G:= Z_{p_1} \times Z_{p_2} \times \dots \times Z_{p_b} G:=Zp1×Zp2××Zpb,容易验证 G G G 是拥有 p 1 p 2 … p b p_1p_2 \dots p_b p1p2pb 个元素的群。对于群元素 x ∈ G x \in G xG,我们简单记做向量形式 ( x 1 , x 2 , … , x b ) , x j ∈ Z p j (x_1,x_2, \dots, x_b),\, x_j \in Z_{p_j} (x1,x2,,xb),xjZpj

函数 f : G → C f:G \rightarrow C f:GC(索引为 x ∈ G ≅ [ p j ] j x \in G \cong [p_j]_j xG[pj]j 的高阶查找表)执行离散傅里叶变换,得到 F : G → C F:G \rightarrow C F:GC (索引为 α ∈ G ≅ [ p j ] j \alpha \in G \cong [p_j]_j αG[pj]j 的另一个高阶查找表),
F ( α ) = D F T ( f , [ ζ j ] j ) : = ∑ x ∈ G ( f ( x ) ⋅ ∏ j = 1 b ζ j α j x j ) F(\alpha) = DFT(f,[\zeta_j]_j) := \sum_{x \in G} \left( f(x) \cdot \prod_{j=1}^{b} \zeta_{j}^{\alpha_j x_j} \right) F(α)=DFT(f,[ζj]j):=xG(f(x)j=1bζjαjxj)
逆离散傅里叶变换的公式为:
f ( x ) = I n v D F T ( F , [ ζ j ] j ) : = 1 p 1 p 2 … p b ∑ α ∈ G ( F ( α ) ⋅ ∏ j = 1 b ζ j − α j x j ) f(x) = InvDFT(F,[\zeta_j]_j) := \frac{1}{p_1p_2 \dots p_b} \sum_{\alpha \in G} \left( F(\alpha) \cdot \prod_{j=1}^{b} \zeta_{j}^{ - \alpha_j x_j} \right) f(x)=InvDFT(F,[ζj]j):=p1p2pb1αG(F(α)j=1bζjαjxj)

容易验证,上式是正确的。由于 ζ j 0 = 1 \zeta_j^{0} = 1 ζj0=1,并且有 ζ j 0 + ζ j 1 + ⋯ + ζ j p j − 1 = 0 , ∀ j \zeta_j^0+\zeta_j^1+ \dots + \zeta_j^{p_j-1} = 0,\forall j ζj0+ζj1++ζjpj1=0,j,因此:
∑ α ∈ G ( ∏ j = 1 b ζ j α j ( x j − x j ′ ) ) = { ∣ G ∣ x = x ′ 0 x ≠ x ′ \sum_{\alpha \in G}( \prod_{j=1}^{b} \zeta_{j}^{ \alpha_j (x_j-x_j')} ) = \left\{ \begin{aligned} |G| && x = x'\\ 0 && x \not = x'\\ \end{aligned} \right. αG(j=1bζjαj(xjxj))={G0x=xx=x

其中 ∣ G ∣ = p 1 p 2 … p b |G| = p_1p_2 \dots p_b G=p1p2pb,所以 DFT 公式和 InvDFT 公式之间多了一个因子
I n v D F T ( F , [ ζ j ] j ) : = 1 ∣ G ∣ ⋅ D F T ( F , [ ζ j − 1 ] j ) InvDFT(F,[\zeta_j]_j) := \frac{1}{|G|} \cdot DFT(F,[\zeta_j^{-1}]_j) InvDFT(F,[ζj]j):=G1DFT(F,[ζj1]j)

Polynomial Transform

对于维度 N × N , N = 2 t N \times N,N=2^t N×N,N=2t 的数组 { x n 1 , n 2 } n 1 , n 2 ∈ [ N ] \{x_{n_1,n_2}\}_{n_1,n_2 \in [N]} {xn1,n2}n1,n2[N],它的 DFT 公式为
x ˉ k 1 , k 2 = ∑ n 1 = 0 N − 1 ∑ n 2 = 0 N − 1 x n 1 , n 2 ζ N n 1 k 2 + n 2 k 2 \bar x_{k_1,k_2} = \sum_{n_1=0}^{N-1} \sum_{n_2=0}^{N-1} x_{n_1,n_2}\zeta_N^{n_1k_2+n_2k_2} xˉk1,k2=n1=0N1n2=0N1xn1,n2ζNn1k2+n2k2

w = ζ N w=\sqrt{\zeta_N} w=ζN ,我们对这个数组 { x n 1 , n 2 } n 1 , n 2 \{x_{n_1,n_2}\}_{n_1,n_2} {xn1,n2}n1,n2 按列抽取,扭曲后组成多项式,第 n 2 n_2 n2 列表示为:
x n 2 ( z ) : = ∑ n 1 ( x n 1 , n 2 ⋅ w − n 1 ) ⋅ z n 1 x_{n_2}(z) := \sum_{n_1} (x_{n_1,n_2} \cdot w^{-n_1})\cdot z^{n_1} xn2(z):=n1(xn1,n2wn1)zn1

以它们作为系数,构造多项式:
x ˉ k 2 ( z ) : = ∑ n 2 x n 2 ( z ) ⋅ w 2 n 2 k 2 ( m o d z N + 1 ) \bar x_{k_2}(z) := \sum_{n_2} x_{n_2}(z) \cdot w^{2n_2k_2} \pmod{z^N+1} xˉk2(z):=n2xn2(z)w2n2k2(modzN+1)

那么可以验证,二维 DFT 被表示为在 z = w 2 k 1 + 1 z=w^{2k_1+1} z=w2k1+1 的求值:
x ˉ k 1 , k 2 = x ˉ k 2 ( z ) ( m o d z − w 2 k 1 + 1 ) \bar x_{k_1,k_2} = \bar x_{k_2}(z) \pmod{z-w^{2k_1+1}} xˉk1,k2=xˉk2(z)(modzw2k1+1)

由于 gcd ⁡ ( 2 k 1 + 1 , N ) = 1 \gcd(2k_1+1,N)=1 gcd(2k1+1,N)=1,因此 k 2 ↦ ( 2 k 1 + 1 ) k 2 ( m o d N ) k_2 \mapsto (2k_1+1)k_2 \pmod N k2(2k1+1)k2(modN) 是一个置换。我们重写 x ˉ k 2 \bar x_{k_2} xˉk2 为如下形式(不需要实际置换,仅仅是一种表示),
x ˉ ( 2 k 1 + 1 ) k 2 ( z ) = ∑ n 2 x n 2 ( z ) ⋅ z 2 n 2 k 2 ( m o d z N + 1 ) \bar x_{(2k_1+1)k_2}(z) = \sum_{n_2} x_{n_2}(z) \cdot z^{2n_2k_2} \pmod{z^N+1} xˉ(2k1+1)k2(z)=n2xn2(z)z2n2k2(modzN+1)

对应的,
x ˉ k 1 , ( 2 k 1 + 1 ) k 2 = x ˉ ( 2 k 1 + 1 ) k 2 ( z ) ( m o d z − w 2 k 1 + 1 ) \bar x_{k_1,(2k_1+1)k_2} = \bar x_{(2k_1+1)k_2}(z) \pmod{z-w^{2k_1+1}} xˉk1,(2k1+1)k2=xˉ(2k1+1)k2(z)(modzw2k1+1)

由于 deg ⁡ x ˉ ( 2 k 1 + 1 ) k 2 ( z ) ≤ N − 1 \deg\bar x_{(2k_1+1)k_2}(z) \le N-1 degxˉ(2k1+1)k2(z)N1,因此可以把它记为
x ˉ ( 2 k 1 + 1 ) k 2 ( z ) = ∑ l = 0 N − 1 y k 2 , l ⋅ z l \bar x_{(2k_1+1)k_2}(z) = \sum_{l=0}^{N-1} y_{k_2,l} \cdot z^l xˉ(2k1+1)k2(z)=l=0N1yk2,lzl

因此二维 DFT 表示为
x ˉ k 1 , ( 2 k 1 + 1 ) k 2 = ∑ l = 0 N − 1 y k 2 , l ⋅ ( w 2 k 1 + 1 ) l = ∑ l = 0 N − 1 ( y k 2 , l ⋅ w l ) ⋅ w 2 l k 1 \begin{aligned} \bar x_{k_1,(2k_1+1)k_2} &= \sum_{l=0}^{N-1} y_{k_2,l} \cdot (w^{2k_1+1})^l\\ &= \sum_{l=0}^{N-1} (y_{k_2,l}\cdot w^l) \cdot w^{2lk_1}\\ \end{aligned} xˉk1,(2k1+1)k2=l=0N1yk2,l(w2k1+1)l=l=0N1(yk2,lwl)w2lk1

总结一下,二维数组的 DFT 的计算方法为:

  1. 输入数组 { x n 1 , n 2 } n 1 , n 2 ∈ [ N ] \{x_{n_1,n_2}\}_{n_1,n_2 \in [N]} {xn1,n2}n1,n2[N]
  2. 对所有的 x n 1 , n 2 x_{n_1,n_2} xn1,n2 扭曲角度 w − n 1 w^{-n_1} wn1,构造出 N N N 个长度 N N N 的小多项式 x n 2 ( z ) x_{n_2}(z) xn2(z)
  3. 对于不同的 k 2 k_2 k2,将它们作为系数,分别组合出 N N N 个系数的多项式 x ˉ k 2 ( z ) \bar x_{k_2}(z) xˉk2(z)
  4. 对于每个 k 2 k_2 k2,扭曲 x ˉ k 2 ( z ) \bar x_{k_2}(z) xˉk2(z) 的系数 [ y k 2 , l ] l [y_{k_2,l}]_l [yk2,l]l 角度 w l w^l wl,得到长度 N N N 的一维样本 [ y k 2 , l ⋅ w l ] l [y_{k_2,l}\cdot w^l]_l [yk2,lwl]l
  5. 对于每个 k 2 k_2 k2,对样本 [ y k 2 , l ⋅ w l ] l [y_{k_2,l}\cdot w^l]_l [yk2,lwl]l 做关于 w 2 k 1 , k 1 ∈ [ N ] w^{2k_1},k_1\in [N] w2k1,k1[N] 的一维 FFT/NTT(同时执行 N N N x ˉ ( 2 k 1 + 1 ) k 2 ( w 2 k 1 ) \bar x_{(2k_1+1)k_2}(w^{2k_1}) xˉ(2k1+1)k2(w2k1) 的求值),就可以实现二维 DFT 的计算

step 2 需要 O ( N 2 ) O(N^2) O(N2) 次数乘,step 3 需要 O ( N 2 ) O(N^2) O(N2) 次加法,step 4 需要 O ( N 2 ) O(N^2) O(N2) 次数乘,step 5 需要 O ( N ) O(N) O(N) 次长度为 O ( N ) O(N) O(N) 的 FFT/DFT 子例程,总的复杂度为 O ( N 2 log ⁡ N ) O(N^2\log N) O(N2logN)

Breaking Polynomials in Parts

[GHS12d] 中为了实现分园环上的 Ring Switching 任务,也采取了类似的多项式切分策略。后续的另一篇文章 [GHPS12] 则采取了完全不同的技术路径,使用分园环塔上的 Trace 来实现 Field Switching 任务。这个技术可以用于加速 BGV 的 Bootstrapping 过程,甚至可以加速同态运算本身。

我们定义 R m = Z [ x ] / ( Φ m ( x ) ) R_m=\mathbb Z[x]/(\Phi_m(x)) Rm=Z[x]/(Φm(x)),定义 C m = Z [ x ] / ( x m − 1 ) C_m=\mathbb Z[x]/(x^m-1) Cm=Z[x]/(xm1)。利用 Modulus Lift 技术,存在多项式 G ( x ) ∈ Z [ x ] G(x) \in \mathbb Z[x] G(x)Z[x],使得 a ( x ) ∈ R m ↦ G ( x ) ⋅ a ( x ) ∈ C m a(x) \in R_m \mapsto G(x) \cdot a(x) \in C_m a(x)RmG(x)a(x)Cm 是单的加群同态。

对于 m = u ⋅ w m=u \cdot w m=uw,就有以下的良好性质:

  1. 给定三个次数至多为 ϕ ( w ) − 1 \phi(w)-1 ϕ(w)1 的多项式 f , g , h f,g,h f,g,h,如果满足 h ( x ) = f ( x ) ⋅ g ( x ) ( m o d Φ w ( x ) ) h(x) = f(x) \cdot g(x) \pmod{\Phi_w(x)} h(x)=f(x)g(x)(modΦw(x)),那么 h ( x u ) = f ( x u ) ⋅ g ( x u ) ( m o d Φ m ( x ) ) h(x^u) = f(x^u) \cdot g(x^u) \pmod{\Phi_m(x)} h(xu)=f(xu)g(xu)(modΦm(x))
  2. 给定三个次数至多为 w − 1 w-1 w1 的多项式 f , g , h f,g,h f,g,h,如果满足 h ( x ) = f ( x ) ⋅ g ( x ) ( m o d x w − 1 ) h(x) = f(x) \cdot g(x) \pmod{x^w-1} h(x)=f(x)g(x)(modxw1),那么 h ( x u ) = f ( x u ) ⋅ g ( x u ) ( m o d x m − 1 ) h(x^u) = f(x^u) \cdot g(x^u) \pmod{x^m-1} h(xu)=f(xu)g(xu)(modxm1)

假设 m = u ⋅ w m=u \cdot w m=uw,那么 C w C_w Cw 可以视为 C m C_m Cm 的子环,以及 R w R_w Rw 可以视为 R m R_m Rm 的子环,对应的环嵌入是 x ↦ x u x \mapsto x^u xxu。给定 Z [ x ] / ( x m − 1 ) \mathbb Z[x]/(x^m-1) Z[x]/(xm1) 中的多项式,
a ( x ) = ∑ i = 0 m − 1 a i ⋅ x i = ∑ k = 0 u − 1 ∑ j = 0 w − 1 a u j + k ⋅ x u j + k = ∑ k = 0 u − 1 ( ∑ j = 0 w − 1 a u j + k ⋅ x u j ) ⋅ x k \begin{aligned} a(x) &= \sum_{i=0}^{m-1} a_i \cdot x^i\\ &= \sum_{k=0}^{u-1}\sum_{j=0}^{w-1} a_{uj+k} \cdot x^{uj+k}\\ &= \sum_{k=0}^{u-1}\left(\sum_{j=0}^{w-1} a_{uj+k} \cdot x^{uj}\right) \cdot x^k\\ \end{aligned} a(x)=i=0m1aixi=k=0u1j=0w1auj+kxuj+k=k=0u1(j=0w1auj+kxuj)xk

定义 a ( k ) = ∑ j = 0 w − 1 a u j + k ⋅ x j ∈ Z [ x ] / ( x w − 1 ) a_{(k)} = \sum_{j=0}^{w-1} a_{uj+k} \cdot x^{j} \in \mathbb Z[x]/(x^w-1) a(k)=j=0w1auj+kxjZ[x]/(xw1),那么
a ( x ) = ∑ k = 0 u − 1 a ( k ) ( x u ) ⋅ x k a(x) = \sum_{k=0}^{u-1} a_{(k)}(x^u) \cdot x^k a(x)=k=0u1a(k)(xu)xk

[GHPS12] 将上述的 a ∈ C m ↦ [ a ( k ) ] k ∈ C w u a \in C_m \mapsto [a_{(k)}]_k \in C_w^u aCm[a(k)]kCwu 切分过程称为 split coefficients。容易看出它是可逆的,其逆过程称为 reconstruction。特别地,切分过程是投影,而重构过程是线性组合,从而它们可以和其他的线性函数(比如解密函数)交换。[GHPS12] 提出了 Ring-Switching,首先把大环 R m R_m Rm 上密文的秘钥切换到子环 R w R_w Rw 上(需保证子环维度足够大,从而安全),接着执行 Modulus Lift 把密文映射到 C m C_m Cm 上,然后 Split 得到 C w C_w Cw 上的若干碎片,最后取模获得小环 R w R_w Rw 上的若干密文。可以证明,这些小环密文的明文槽中,加密了大环密文的明文槽(但是有额外的槽内线性变换)。

Amortized FHEW bootstrapping

[MS18] 给出了第一个 “困难假设的近似因子为多项式” 并且 “自举复杂度是(均摊)亚线性” 的 FHE 方案。虽然单次自举的复杂度略高于 FHEW,但是可以批处理,因此均摊下来减少了大约 O ( n ) O(n) O(n) 因子。

High level outline

[BGV12] 提出 BGV 方案时,便给出了 Batching Bootstrapping 的设计,使用底层代数自带的 Rotation 实现各个槽之间的迁移,同时自举 O ~ ( λ ) \tilde O(\lambda) O~(λ) 个密文,获得了拟线性的均摊自举时间。 但是,[BGV12] 使用的是布尔电路,因此速度很慢。

[GHS12c] 提出了特殊密文模数 q 0 = p t q_0=p^t q0=pt 的快速解密例程(完全算术的),然后采取 p-adic number 以及 Hensel Lifting,扩展了 [SV11] 的 SIMD 技术,使得明文槽成为环 Z p t \mathbb Z_{p^t} Zpt 而非有限域 G F ( p t ) GF(p^t) GF(pt),最后再通过 [GHS12a] 的 Slot Permutation 技术,执行同态 DFT 来实现 coeff packing 和 slot packing 之间的转换,于是实现了并行的解密。

[AP13] 并不采用 Benes 置换网络来实现同态 DFT,而是通过[GHS12D] 和 [GHPS12] 的 Field Switching(用 Trace 实现任意的线性函数),以及分园环的 Tensorial Decomposition,直接将 coeff 映射到 slot 上。另外 [AP13] 使用分园环上的 Ideal Factorization 来推广 [SV11] 的 SIMD 技术到环 Z p t \mathbb Z_{p^t} Zpt 的明文槽,而非 p-进数。

不过,上述的这些 BGV 的并行自举方案,都导致噪声的超多项式增长,因此需要假设近似因子为超多项式的格上问题困难。基于 GSW 方案,[BV14] 给出了第一个近似因子为多项式的 FHE 方案,但是解需要利用 5-PBP 实现布尔解密电路,计算复杂度。之后 [AP14] 使用 GSW 构造出 HE-Perm 方案(实际就是同态累加器),用它来自举任意的单个 LWE 密文,计算复杂度仅为 O ~ ( λ ) \tilde O(\lambda) O~(λ),同时所依赖的假设近似因子是多项式的。

[MS18] 给出了第一个 “困难假设的近似因子为多项式” 并且 “自举复杂度是(均摊)亚线性” 的 FHE 方案。虽然单次自举的复杂度略高于 FHEW,但是可以批处理,因此均摊下来减少了大约 O ( n ) O(n) O(n) 因子。一些方案的计算复杂度比较,如图所示:

在这里插入图片描述

大体思路为:

  1. 选取 L W E n 2 / q LWE^{2/q}_n LWEn2/q 的参数:代数结构 Z q n + 1 \mathbb Z_q^{n+1} Zqn+1,密文模数 q q q,明文模数 t = 2 t=2 t=2,维度 n = 2 l − 1 n=2^{l-1} n=2l1
  2. 选取 R L W E d 2 / 2 n RLWE^{2/2n}_d RLWEd2/2n 的参数:代数结构 Z 2 n [ x ] / ( Φ d ( x ) ) \mathbb Z_{2n}[x]/(\Phi_d(x)) Z2n[x]/(Φd(x)),密文模数 2 n 2n 2n,明文模数 t = 2 t=2 t=2,维度 ϕ ( d ) \phi(d) ϕ(d)
  3. 选取 R G S W N 2 n / Q RGSW^{2n/Q}_N RGSWN2n/Q 的参数:代数结构 Z Q [ x ] / ( Φ N ( x ) ) \mathbb Z_Q[x]/(\Phi_N(x)) ZQ[x]/(ΦN(x)),密文模数 Q Q Q,维度 2 n ∣ ϕ ( N ) 2n\mid\phi(N) 2nϕ(N),被编码在多项式的指数上的明文空间大小为 2 n 2n 2n
  4. 我们使用 RGSW 构造一个比 FHEW 的累加器(仅支持加法)更强的同态寄存器 R E G 2 n / Q REG^{2n/Q} REG2n/Q,它支持 Z 2 n \mathbb Z_{2n} Z2n 中的加法和减法不支持数乘
  5. 为了同态解密 b − a ⋅ s ∈ R d , 2 n b-a \cdot s \in R_{d,2n} basRd,2n,我们把私钥预处理为 DFT 格式 D F T ( s ) DFT(s) DFT(s),设置自举秘钥为 B K : = R E G 2 n / Q ( [ 2 j ⋅ D F T ( s ) i ] i , j ) BK:=REG^{2n/Q}([2^j \cdot DFT(s)_i]_{i,j}) BK:=REG2n/Q([2jDFT(s)i]i,j)
  6. 我们首先把 ϕ ( d ) \phi(d) ϕ(d) 个 LWE 密文,打包到单个 RLWE 密文中,并执行模切换将模数从 q q q 降低到 2 n 2n 2n
  7. 然后对这个打包的 RLWE 密文 ( a , b ) ∈ R d , 2 n 2 (a,b) \in R_{d,2n}^2 (a,b)Rd,2n2 做同态解密:将 a a a 视为常数多项式,明文下转化为 D F T ( a ) DFT(a) DFT(a),然后和 B K BK BK阿达玛积(数乘),得到 D F T ( s ⋅ a ) i ∈ Z 2 n DFT(s \cdot a)_i \in \mathbb Z_{2n} DFT(sa)iZ2n 的累加器状态
  8. 现在执行同态 InvDFT,这个过程中我们仅仅能够使用 R E G 2 n / Q REG^{2n/Q} REG2n/Q 所支持的加法和乘法操作。其中的与单位根的数乘,通过 Nussbaumer Transform 变为子环的旋转(取模运算需要 Z 2 n \mathbb Z_{2n} Z2n 上的减法)
  9. 经过一些转换,现在我们得到了加密 s ⋅ a ∈ R d , 2 n s \cdot a \in R_{d,2n} saRd,2n 各个系数的寄存器,从而可以计算出 m ≈ b − a ⋅ s m\approx b-a \cdot s mbas 的寄存器(共有 O ( d ) O(d) O(d) 个 RGSW 密文分别加密 m ( x ) m(x) m(x) 的各个系数)
  10. 最后,利用 R G S W N 2 n / Q RGSW_N^{2n/Q} RGSWN2n/Q 的明文 one-hot 性质,利用各个系数对应的寄存器,查找舍入函数的 Lookup Table(反循环向量)获取 m i = M S B ( m i + e ) m_i=MSB(m_i+e) mi=MSB(mi+e) 的值,这便是我们一开始输入的那些 LWE 密文的明文

现在有如下几个问题:怎么打包 LWE 到 RLWE、怎么构造支持减法的寄存器、怎么将 InvDFT 的数乘运算仅使用加/减法实现。其他的诸如模切换、提取 MSB 都是简单的。

Modulus Switching

[MS18] 采取了随机化园整的模切换变体。定义随机函数 $\lfloor \cdot \rceil_$: \mathbb R \to \mathbb Z$,
⌊ x ⌉ $ : = { ⌊ x ⌋ , P r = ⌈ x ⌉ − x ⌈ x ⌉ , P r = x − ⌊ x ⌋ \lfloor x \rceil_\$ := \left\{\begin{aligned} \lfloor x\rfloor,&& Pr=\lceil x\rceil-x\\ \lceil x\rceil,&& Pr=x-\lfloor x\rfloor\\ \end{aligned}\right. x$:={x,x,Pr=xxPr=xx

舍入噪声为 $-1< x-\lfloor x \rceil_$<1$,因此它是参数 2 π \sqrt{2\pi} 2π 的亚高斯分布。

模切换算法为

在这里插入图片描述

对于 LWE 密文:它的输入是 L W E s t / Q [ m , β ] LWE^{t/Q}_s[m,\beta] LWEst/Q[m,β],其输出为 L W E s t / q [ m , β ′ ] LWE^{t/q}_s[m,\beta'] LWEst/q[m,β],简记 $e=(\lfloor (n/q)b \rceil_$,\lfloor (n/q)a \rceil_$)$(参数 2 π \sqrt{2\pi} 2π 的亚高斯),那么噪声界以极高的概率为
β ′ = q Q ⋅ β + ∥ e ⋅ ( 1 , − s ) ∥ = q Q ⋅ β + O ( ∥ s ∥ ) \beta' = \dfrac{q}{Q}\cdot\beta + \|e\cdot(1,-s)\| = \dfrac{q}{Q}\cdot\beta + O(\|s\|) β=Qqβ+e(1,s)=Qqβ+O(s)

对于 RLWE 密文:它的输入是 R L W E z t / q [ m , β ] RLWE^{t/q}_z[m,\beta] RLWEzt/q[m,β],其输出为 L W E s t / n [ m , β ′ ] LWE^{t/n}_s[m,\beta'] LWEst/n[m,β],简记 $e_0=\lfloor (n/q)b \rceil_$$ 和 $e_1=\lfloor (n/q)a \rceil_$$(参数 2 π \sqrt{2\pi} 2π 的亚高斯),那么噪声界以极高的概率为
β ′ = n q ⋅ β + ∥ e 0 ∥ + ∥ e 1 ⋅ z ∥ = n q ⋅ β + w ( d log ⁡ d ) ⋅ ∥ z ∥ \beta' = \dfrac{n}{q}\cdot\beta + \|e_0\|+\|e_1\cdot z\| = \dfrac{n}{q}\cdot\beta + w\left(\sqrt{d \log d}\right) \cdot \|z\| β=qnβ+e0+e1z=qnβ+w(dlogd )z

Ring packing

类似于 TFHE 的 functional Key-switch 例程,我们可以把一些 LWE 密文打包到单个 RLWE 密文中。

算法如下:

在这里插入图片描述

打包秘钥 K j , l P ∈ R L W E z q / q [ s l ⋅ 2 j , β P ] K_{j,l}^P \in RLWE^{q/q}_z[s_l\cdot 2^j,\beta_P] Kj,lPRLWEzq/q[sl2j,βP],输入 ϕ ( d ) \phi(d) ϕ(d) L W E n t / q [ m i , Δ ] LWE^{t/q}_n[m_i,\Delta] LWEnt/q[mi,Δ],输出单个 R L W E z t / q [ m ( x ) , β ] RLWE^{t/q}_z[m(x),\beta] RLWEzt/q[m(x),β],其中 m ( x ) = ∑ i m i x i m(x) = \sum_i m_ix^{i} m(x)=imixi,它的噪声界是
β = O ( d ⋅ Δ + d n log ⁡ q ⋅ β P ) \beta = O(\sqrt d\cdot \Delta + \sqrt{dn\log q}\cdot \beta_P) β=O(d Δ+dnlogq βP)

在对这个打包的 RLWE 密文执行同态解密之前,执行 Modulus Switching 将模数从 q q q 降低到 2 n 2n 2n(环面以 1 / 2 n 1/2n 1/2n 精度离散化),从而可以被 RGSW 自举(没看懂为啥 RGSW 的维度要和 LWE 的维度有关,没必要吧?)

此时我们拥有了打包密文 ( a , b ) ∈ R L W E z t / 2 n [ m ( x ) , β ] ⊆ R d , 2 n 2 (a,b) \in RLWE^{t/2n}_z[m(x),\beta] \subseteq R_{d,2n}^2 (a,b)RLWEzt/2n[m(x),β]Rd,2n2,秘钥为 z ∈ R d , 2 n z \in R_{d,2n} zRd,2n,我们接下来需要同态地计算 b − a ⋅ z ∈ R d , 2 n b-a \cdot z \in R_{d,2n} bazRd,2n 并且同态地园整。

Homomorphic Registers

FHEW 的累加器仅支持同态加法,不支持减法( homomorphic inversion),难以支持数乘( homomorphic exponentiation)。[MS18] 类似于 FHEW 采取 RGSW 来构建同态累加器(而非 TFHE 采用的 RLWE),但是通过冗余,增强实现了支持减法的寄存器。

对于加密系统 R G S W N 2 n / Q RGSW^{2n/Q}_N RGSWN2n/Q,这里的上角标 2 n / Q 2n/Q 2n/Q 并非纠错码缩放倍率,而是指的明文空间为 Z 2 n \mathbb Z_{2n} Z2n(编码在多项式指数上)。对于 v ∈ Z 2 n v \in \mathbb Z_{2n} vZ2n,假设 Y = X N / 2 n Y=X^{N/2n} Y=XN/2n 2 n 2n 2n 次本原单位根,FHEW 的累加器为 R G S W N 2 n / Q ( u ⋅ Y v ) RGSW^{2n/Q}_N(u \cdot Y^v) RGSWN2n/Q(uYv),其中的 u ≈ Q / 2 t u\approx Q/2t uQ/2t 是 RLWE 的纠错码缩放倍率。我们选取 t = 4 t=4 t=4,它对应于 Z 4 \mathbb Z_4 Z4 的纠错编码倍率 Q / t Q/t Q/t 的一半(反循环函数)

FHEW 的累加器:

  • 初始化(Initialization):记为 v ← w v \gets w vw,状态为无噪密文
    C = u ⋅ X w G ∈ R G S W z 2 n / Q ( u ⋅ X w ) C=u \cdot X^w G \in RGSW^{2n/Q}_z(u \cdot X^w) C=uXwGRGSWz2n/Q(uXw)

  • 常数加法(Increment):记为 v ← v + c v \gets v+c vv+c,状态转换为
    C ⋅ X c ∈ R G S W z 2 n / Q ( u ⋅ X w + c ) C \cdot X^c \in RGSW^{2n/Q}_z(u \cdot X^{w+c}) CXcRGSWz2n/Q(uXw+c)

  • 密文加法(Addition):记为 v ← v + C ′ v \gets v+C' vv+C,状态转换为
    ( u − 1 ⋅ C ) ⋅ G − 1 ( C ′ ) ∈ R G S W z 2 n / Q ( u ⋅ X v + w ) (u^{-1} \cdot C) \cdot G^{-1}(C') \in RGSW^{2n/Q}_z(u \cdot X^{v+w}) (u1C)G1(C)RGSWz2n/Q(uXv+w)

  • 密文提取(Extraction):从 C C C 中提取出 LWE 密文

为了使得同态寄存器也支持减法,[MS18] 将数值 v ∈ Z 2 n v \in \mathbb Z_{2n} vZ2n 存储为冗余的一对 RGSW 密文(两个反向的累加器),
R E G z 2 n / Q [ v , β ] : = ( R G S W z 2 n / Q ( u ⋅ X v ) , R G S W z 2 n / Q ( u ⋅ X − v ) ) REG^{2n/Q}_z[v,\beta] := \left(RGSW^{2n/Q}_z(u \cdot X^{v}),\,\, RGSW^{2n/Q}_z(u \cdot X^{-v})\right) REGz2n/Q[v,β]:=(RGSWz2n/Q(uXv),RGSWz2n/Q(uXv))

这个寄存器的:初始化、常数加法、密文加法,都是从累加器自然继承的。密文提取就是对第一分量 C C C 的密文提取。它额外支持减法:简单交换两个累加器 ( C , C ′ ) ↦ ( C ′ , C ) (C,C') \mapsto (C',C) (C,C)(C,C)

后文中,我们使用符号 [ ⁣ [ v ] ⁣ ] [\![v]\!] [[v]] 简记加密 v ∈ Z 2 n [ x ] ≅ Z 2 n ∞ v \in \mathbb Z_{2n}[x] \cong \mathbb Z_{2n}^\infty vZ2n[x]Z2n 的一组寄存器。

Slow Multiplication

现在,我们看一下如何在 R E G 2 n / Q REG^{2n/Q} REG2n/Q 下,计算 R d , 2 n R_{d,2n} Rd,2n 中环元素的数乘 a ⋅ [ ⁣ [ z ] ⁣ ] a \cdot [\![z]\!] a[[z]]

由于 z ∈ R d , 2 n z \in R_{d,2n} zRd,2n 是各个系数单独加密在 REG 内的,并且 a ∈ R d , 2 n a \in R_{d,2n} aRd,2n 的各个系数都已知的 l = log ⁡ n + 1 l=\log n+1 l=logn+1 比特常数。因此我们可以在 REG 中存储私钥的二的幂 f ( z ) : = [ z k 2 j ] k , j ∈ Z 2 n l × ϕ ( d ) f(z) := [z_k2^j]_{k,j} \in \mathbb Z_{2n}^{l \times \phi(d)} f(z):=[zk2j]k,jZ2nl×ϕ(d) 的值,然后将 a i ∈ Z 2 n a_i \in \mathbb Z_{2n} aiZ2n二进制分解 ∑ j = 0 l − 1 a i j 2 j \sum_{j=0}^{l-1} a_{ij}2^j j=0l1aij2j

定义计算标量数乘 a i ⋅ z k ∈ Z 2 n a_i \cdot z_k \in \mathbb Z_{2n} aizkZ2n 的同态电路
C a i ( [ ⁣ [ f ( z ) ] ⁣ ] , k ) : = ∑ j ∈ [ l ] , a i j = 1 [ ⁣ [ z k 2 j ] ⁣ ] C_{a_i}([\![f(z)]\!], k) := \sum_{j \in [l],\,\, a_{ij}=1} [\![z_k2^j]\!] Cai([[f(z)]],k):=j[l],aij=1[[zk2j]]

上述过程中,仅仅需要同态加法(不需要计算幂次),这是寄存器所支持的。

于是环元素数乘 a ⋅ z ∈ R d , 2 n a \cdot z \in R_{d,2n} azRd,2n 的同态电路 C a C_a Ca 为:

  1. R d , 2 n R_{d,2n} Rd,2n 的长度为 d d d,因此我们先提升到整数多项式环,计算 a ⋅ z ∈ Z 2 n [ x ] a \cdot z \in\mathbb Z_{2n}[x] azZ2n[x],它的长度为 2 d − 1 2d-1 2d1
  2. 每个系数 ( a ⋅ z ) i = ∑ i = j + k a j ⋅ z k ∈ Z 2 n (a \cdot z)_i = \sum_{i=j+k} a_j \cdot z_k \in \mathbb Z_{2n} (az)i=i=j+kajzkZ2n若干数乘的加和,采取 C a j ( [ ⁣ [ f ( z ) ] ⁣ ] , k ) C_{a_j}([\![f(z)]\!], k) Caj([[f(z)]],k) 来实现,共计 O ( d 2 ⋅ l ) O(d^2\cdot l) O(d2l) 个同态加法
  3. 现在模掉 Φ d ( x ) \Phi_d(x) Φd(x) 回到分圆环 R d , 2 n R_{d,2n} Rd,2n 上,假如我们选取 d d d 是素数幂次,那么 Φ d ( x ) \Phi_d(x) Φd(x) 的系数都是 { 0 , 1 } \{0,1\} {0,1} 的,从而模约减只需要若干的减法

p p p 是素数, k k k是自然数,那么
Q p k ( x ) = x p k − 1 Q 1 ( x ) Q p ( x ) ⋯ Q p k − 1 ( x ) = x p k − 1 x p k − 1 − 1 = 1 + x p k − 1 + x 2 p k − 1 + ⋯ + x ( p − 1 ) p k − 1 \begin{aligned} Q_{p^k}(x) &= \dfrac{x^{p^{k}}-1}{Q_1(x)Q_p(x) \cdots Q_{p^{k-1}}(x)}\\ &= \dfrac{x^{p^{k}}-1}{x^{p^{k-1}}-1}\\ &= 1 + x^{p^{k-1}} + x^{2p^{k-1}} + \cdots + x^{(p-1)p^{k-1}} \end{aligned} Qpk(x)=Q1(x)Qp(x)Qpk1(x)xpk1=xpk11xpk1=1+xpk1+x2pk1++x(p1)pk1

它仅包含 p p p 个系数是 1 1 1,其他的系数都是 0 0 0,于是模约减容易的。素数 p p p 越小,模约减复杂度的常数因子越小。

假设 B g B_g Bg 是 RGSW 的 Gadget 矩阵的参数, d g = log ⁡ B g Q d_g=\log_{B_g} Q dg=logBgQ 是分解位数,那么存在算法 S l o w M u l t : R d , 2 n × R E G z l × ϕ ( d ) → R E G z ϕ ( d ) SlowMult: R_{d,2n}\times REG^{l \times \phi(d)}_z \to REG^{\phi(d)}_z SlowMult:Rd,2n×REGzl×ϕ(d)REGzϕ(d)
( a , [ R E G z 2 n / Q [ f ( z ) j , k , β ] ] j , k ) ↦ [ R E G z 2 n / Q [ ( a ⋅ z ) i , β ′ ] ] i \left( a, \left[REG^{2n/Q}_z[f(z)_{j,k}, \beta]\right]_{j,k} \right) \mapsto \left[ REG^{2n/Q}_z[(a\cdot z)_i, \beta'] \right]_i (a,[REGz2n/Q[f(z)j,k,β]]j,k)[REGz2n/Q[(az)i,β]]i

以压倒性概率 β ′ = O ~ ( β B g ⋅ n d g ⋅ d ) \beta' = \tilde O\left(\beta B_g \cdot \sqrt{n d_g\cdot d}\right) β=O~(βBgndgd ),它的计算复杂度为 O ~ ( d 2 ) \tilde O(d^2) O~(d2) 次同态加法/减法。

Homomorphic DFT

然而,上述 Slow Multiplication 的计算效率太低了(拟二次函数),即使 ϕ ( d ) \phi(d) ϕ(d) 个密文均摊下来复杂度依旧是拟线性的。我们希望把均摊成本降低到亚线性,也就是说多项式的同态乘法的复杂度应当为拟线性。如果可以在 DFT 域上计算阿达玛乘法,然后再利用 InvFFT 算法得到它的系数表示,计算复杂度就降低到了拟线性级别。

我们简记 R d : = Z [ x ] / ( Φ d ( x ) ) R_{d}:=\mathbb Z[x]/(\Phi_d(x)) Rd:=Z[x]/(Φd(x))分园数域的整数环 d d d 是任意整数),令商环 R d , q : = R d / q R d R_{d,q}:=R_d/qR_d Rd,q:=Rd/qRd,另外简记 C m : = R m : = Z [ x ] / ( x m − 1 ) C_m:=R_{m}:=\mathbb Z[x]/(x^m-1) Cm:=Rm:=Z[x]/(xm1)循环卷积环 m m m 是素数幂次)

C m C_m Cm 上的 DFT 的公式为,
x ˉ i = D F T ( x ) i : = ∑ k = 0 m − 1 x k ζ m i k x k = D F T − 1 ( x ) i : = ∑ i = 0 m − 1 x ˉ i ζ m − i k \begin{array}{ccrcl} \bar x_i &=& DFT(x)_i &:=& \sum_{k=0}^{m-1} x_k \zeta_m^{ik}\\ x_k &=& DFT^{-1}(x)_i &:=& \sum_{i=0}^{m-1} \bar x_i \zeta_m^{-ik}\\ \end{array} xˉixk==DFT(x)iDFT1(x)i:=:=k=0m1xkζmiki=0m1xˉiζmik

那么对于 a , z ∈ R d a,z \in R_d a,zRd 的多项式乘法,只要满足 deg ⁡ a ⋅ z < m \deg a\cdot z < m degaz<m(即 m > 2 ϕ ( d ) − 1 m>2\phi(d)-1 m>2ϕ(d)1),就可以先在 C m C_m Cm 的 DFT 域上计算阿达玛积,然后 InvFFT 回到 C m C_m Cm 上并且模掉 Φ d ( x ) \Phi_d(x) Φd(x) 得到 R d R_d Rd 上结果,
( a ( x ) ⋅ z ( x ) ( m o d x m − 1 ) ) ( m o d Φ d ( x ) ) = D F T − 1 ( 1 m D F T ( z ) ⊙ D F T ( a ) ) ( m o d Φ d ( x ) ) \left(a(x) \cdot z(x) \pmod{x^m-1}\right) \pmod{\Phi_d(x)} = DFT^{-1}\left( \dfrac{1}{m}DFT(z) \odot DFT(a) \right) \pmod{\Phi_d(x)} (a(x)z(x)(modxm1))(modΦd(x))=DFT1(m1DFT(z)DFT(a))(modΦd(x))

然而,我们的 RGSW 累加器(用同态乘法实现指数上的算术加法)难以计算数乘。DFT 可以在明文下预处理,然而 InvDFT 必须在密文下同态计算。但是让 R E G ( x ˉ i ) REG(\bar x_i) REG(xˉi) ζ m − i k ∈ C \zeta_m^{-ik} \in \mathbb C ζmikC 数乘,显然不是什么好主意。

[MS18] 使用 Nussbaumer Transform 来解决这个问题。它使用了更加代数化的语言,描述 Nussbaumer 的映射过程。给定 m ∣ d m|d md 都是素数 p ≥ 2 p \ge 2 p2 的幂次,并且满足 d ≥ p m 2 d\ge pm^2 dpm2(为了使得 p m ∣ d / m pm\mid d/m pmd/m 次本原根落在 R d / m R_{d/m} Rd/m 内),简记 r = ϕ ( d / m ) = ϕ ( d ) / m r=\phi(d/m)=\phi(d)/m r=ϕ(d/m)=ϕ(d)/m,那么单变元 ( x ) (x) (x) 的多项式,可以映射为双变元 ( x , y = x m ) (x,y=x^m) (x,y=xm) 的多项式。确切地,映射为(其实就只是一种表示而已,不需要实际的映射/置换),
ψ : R d , q → R d / m , q [ x ] / ( x m − y ) a ( x ) = ∑ i = 0 ϕ ( d ) a i x i ↦ a ( x , y ) = ∑ j = 0 m − 1 ( ∑ i = 0 r − 1 a m i + j y i ) x j \begin{array}{crcl} \psi:& R_{d,q} &\to& R_{d/m,q}[x]/(x^m-y)\\ & a(x)=\sum_{i=0}^{\phi(d)}a_ix^i &\mapsto& a(x,y)=\sum_{j=0}^{m-1}\left(\sum_{i=0}^{r-1}a_{mi+j}y^i\right)x^j \end{array} ψ:Rd,qa(x)=i=0ϕ(d)aixiRd/m,q[x]/(xmy)a(x,y)=j=0m1(i=0r1ami+jyi)xj

其中 a ( j ) ( y ) : = ∑ i = 0 r − 1 a m i + j y i ∈ Z q [ y ] / ( Φ d / m ( y ) ) a_{(j)}(y) := \sum_{i=0}^{r-1}a_{mi+j}y^i \in \mathbb Z_q[y]/(\Phi_{d/m}(y)) a(j)(y):=i=0r1ami+jyiZq[y]/(Φd/m(y)),由于 x x x d d d 次本原单位根,因此 y = x m ∈ R m , q y=x^m \in R_{m,q} y=xmRm,q d / m d/m d/m 次本原单位根。

为了快速计算多项式乘法,我们试图对 a ( x , y ) a(x,y) a(x,y) 做关于 R d / m , q [ x ] / ( x p m − 1 ) R_{d/m,q}[x]/(x^{pm}-1) Rd/m,q[x]/(xpm1) 的 DFT(简单的 Lift,两个关于 x x x 的次数至多为 m − 1 m-1 m1 的多项式,乘积的次数不会越过 p m − 1 pm-1 pm1,因此计算正确),那么就需要 p m pm pm 次本原单位根,而恰好 y d / ( p m 2 ) ∈ R d / m , q y^{d/(pm^2)} \in R_{d/m,q} yd/(pm2)Rd/m,q 就是!因此,DFT 中的关于本原根的大环中的数乘运算,完全的转化为了小环中的多项式旋转(寄存器加密了小环元素的 Z 2 n \mathbb Z_{2n} Z2n 上系数,并且 Φ d / m ( y ) \Phi_{d/m}(y) Φd/m(y) 是稀疏 { 0 , 1 } \{0,1\} {0,1} 系数的,因此系数旋转就是少量的减法)

现在我们整理下 a ⋅ s ∈ R d a \cdot s \in R_d asRd 的计算流程:

  1. 秘钥 s ∈ R d s \in R_d sRd 是关于 x x x 的度数 ϕ ( d ) − 1 \phi(d)-1 ϕ(d)1 单变元多项式,经过映射 ψ ( s ) ∈ R d / m [ x ] / ( x m − y ) \psi(s) \in R_{d/m}[x]/(x^m-y) ψ(s)Rd/m[x]/(xmy) 得到了关于 x x x 的度数 m − 1 m-1 m1 且关于 y y y 的度数 r − 1 r-1 r1 的双变元多项式
  2. 关于变元 x x x预计算 f = 1 m D F T ( ψ ( s ) ) f = \dfrac{1}{m}DFT(\psi(s)) f=m1DFT(ψ(s)),所使用的本原根是 y d / ( p m 2 ) ∈ R d / m y^{d/(pm^2)} \in R_{d/m} yd/(pm2)Rd/m,其中的 ψ ( s ) \psi(s) ψ(s)提升到了 R d / m [ x ] / ( x p m − 1 ) R_{d/m}[x]/(x^{pm}-1) Rd/m[x]/(xpm1)
  3. 将向量 f f f 按照各个系数(落在环 R d / m R_{d/m} Rd/m 中)分别加密到 RGSW 密文(二进制分解的冗余累加器,可计算加/减法数乘),简记为 [ E ( 2 j f k ) ] k , j [E(2^j f_k)]_{k,j} [E(2jfk)]k,j,每个 E ( 2 j f k ) E(2^j f_k) E(2jfk) 实际包含了小环 R d / m R_{d/m} Rd/m 中的 r r r 个系数 f k , i f_{k,i} fk,i 的密文
  4. 类似地,密文 a ∈ R d a \in R_d aRd 作为常数(因此 s , a s,a s,a 的 DFT 都不是同态计算的),计算出 a ˉ i = D F T ( ψ ( a ) ) i \bar a_i=DFT(\psi(a))_i aˉi=DFT(ψ(a))i
  5. 使用二进制分解手段,将 a ˉ i \bar a_i aˉi 数乘 f i f_i fi 转化为:使用 a i j a_{ij} aij 挑选 E ( 2 j f k ) E(2^jf_k) E(2jfk),共计算 p m pm pm R d / m R_{d/m} Rd/m 上的数乘,获得了 c ˉ : = 1 m D F T ( ψ ( z ) ) ⊙ D F T ( ψ ( a ) ) \bar c :=\dfrac{1}{m}DFT(\psi(z)) \odot DFT(\psi(a)) cˉ:=m1DFT(ψ(z))DFT(ψ(a))
  6. 现在,我们执行 InvDFT 操作,简单按照公式 c k = ∑ i = 0 m − 1 c ˉ i ζ m − i k c_k=\sum_{i=0}^{m-1} \bar c_i \zeta_m^{-ik} ck=i=0m1cˉiζmik 来计算即可(不要使用 FFT/NTT,多层迭代导致了无法利用 GSW 的不对称噪声增长特性),其中的数乘 ζ m − i k \zeta_m^{-ik} ζmik 就是在小环 R d / m R_{d/m} Rd/m 中旋转系数向量(需要模掉 Φ d / m ( y ) \Phi_{d/m}(y) Φd/m(y),它仅包含 p p p 项非零,因此通过稀疏的减法来实现)。
  7. 现在我们得到了 c : = ψ ( z ) ⋅ ψ ( a ) ∈ R d / m [ x ] / ( x p m − 1 ) c:=\psi(z) \cdot \psi(a) \in R_{d/m}[x]/(x^{pm}-1) c:=ψ(z)ψ(a)Rd/m[x]/(xpm1) 的(各个系数的系数)密文,把它同态的模掉 ( x m − y ) (x^m-y) (xmy) 得到 ψ ( z ⋅ a ) ∈ R d / m [ x ] / ( x m − y ) \psi(z \cdot a) \in R_{d/m}[x]/(x^m-y) ψ(za)Rd/m[x]/(xmy),它其实就是 z ⋅ a ∈ R d z \cdot a \in R_d zaRd

Ring Decrypt

我们选取三的幂次的分园环,设置 d = 3 k d=3^k d=3k,令 m = d ϵ = 3 ϵ k m=d^{\epsilon}=3^{\epsilon k} m=dϵ=3ϵk 满足 d ≥ 3 m 2 d \ge 3m^2 d3m2,简记 r = ϕ ( d / m ) = ϕ ( d 1 − ϵ ) r=\phi(d/m)=\phi(d^{1-\epsilon}) r=ϕ(d/m)=ϕ(d1ϵ),那么密文 ( a , b ) ∈ R L W E z t / 2 n (a,b) \in RLWE^{t/2n}_z (a,b)RLWEzt/2n 的 Nussbaumer 转换为:
ψ : R d , 2 n → R d / m , 2 n [ x ] / ( x m − y ) \psi: R_{d,2n} \to R_{d/m,2n}[x]/(x^m-y) ψ:Rd,2nRd/m,2n[x]/(xmy)

其中 ζ 3 m : = y d / ( 3 m 2 ) ∈ R d / m , 2 n \zeta_{3m}:=y^{d/(3m^2)} \in R_{d/m,2n} ζ3m:=yd/(3m2)Rd/m,2n 3 m 3m 3m 次本原单位根

同态线性解密的过程为:

  1. 我们将 a , z ∈ R d , 2 n a,z \in R_{d,2n} a,zRd,2n 映射为 ψ ( a ) , ψ ( z ) ∈ R d / m , 2 n [ x ] / ( x m − y ) \psi(a),\psi(z) \in R_{d/m,2n}[x]/(x^m-y) ψ(a),ψ(z)Rd/m,2n[x]/(xmy)

  2. 然后将 ψ ( a ) , ψ ( z ) \psi(a),\psi(z) ψ(a),ψ(z) 提升到 R d / m , 2 n [ x ] / ( x 3 m − 1 ) R_{d/m,2n}[x]/(x^{3m}-1) Rd/m,2n[x]/(x3m1),现在可以对 ψ ( a ) , ψ ( z ) \psi(a),\psi(z) ψ(a),ψ(z) 执行 DFT/InvDFT

  3. 我们定义私钥在 DFT 域的二的幂次
    f ( z ) = ( 1 , 2 , 4 , ⋯ , 2 l − 1 ) ⊗ [ 1 3 ⋅ D F T ( ψ ( z ) ) i ] i ∈ [ 3 m ] ∈ R d / m , 2 n l × 3 m f(z)=(1,2,4,\cdots,2^{l-1}) \otimes \left[\dfrac{1}{3}\cdot DFT(\psi(z))_i\right]_{i \in [3m]} \in R_{d/m,2n}^{l \times 3m} f(z)=(1,2,4,,2l1)[31DFT(ψ(z))i]i[3m]Rd/m,2nl×3m

    将它用寄存器加密为 [ ⁣ [ f ( z ) ] ⁣ ] [\![f(z)]\!] [[f(z)]]

  4. 计算 a ˉ i = D F T ( ψ ( a ) ) i \bar a_i = DFT(\psi(a))_i aˉi=DFT(ψ(a))i,然后用 SlowMult 电路 C a ˉ i ( [ ⁣ [ f ( z ) ] ⁣ ] ) C_{\bar a_i}([\![f(z)]\!]) Caˉi([[f(z)]]) 计算小环 R d / m , 2 n R_{d/m,2n} Rd/m,2n 上的阿达玛乘积

  5. 再令电路 C F C_{F} CF 是利用公式 ( a ⋅ z ) k = ∑ i = 0 3 m − 1 ( a ⋅ z ) i ‾ ζ 3 m − i k (a \cdot z)_k = \sum_{i=0}^{3m-1} \overline{(a \cdot z)_i} \zeta_{3m}^{-ik} (az)k=i=03m1(az)iζ3mik 同态计算 InvDFT 的电路(因为 ζ 3 m ∈ R d / m , 2 n \zeta_{3m} \in R_{d/m,2n} ζ3mRd/m,2n,所以只需要同态加/减法),那么计算 a ⋅ z ∈ R d , 2 n a \cdot z \in R_{d,2n} azRd,2n 的电路为
    [ ⁣ [ a ⋅ z ] ⁣ ] = C a ( [ ⁣ [ f ( z ) ] ⁣ ] ) : = C F ( [ C a ˉ i ( [ ⁣ [ f ( z ) ] ⁣ ] ) ] i ) ( m o d x m − y ) [\![a \cdot z]\!] = C_a([\![f(z)]\!]) := C_F(\left[C_{\bar a_i}([\![f(z)]\!])\right]_i) \pmod{x^m-y} [[az]]=Ca([[f(z)]]):=CF([Caˉi([[f(z)]])]i)(modxmy)

  6. 接着定义电路 C a , b ( [ ⁣ [ f ( z ) ] ⁣ ] ) = b − C a ( [ ⁣ [ f ( z ) ] ⁣ ] ) C_{a,b}([\![f(z)]\!])=b-C_a([\![f(z)]\!]) Ca,b([[f(z)]])=bCa([[f(z)]]) 是计算 b − a ⋅ z ∈ R d , 2 n b-a\cdot z \in R_{d,2n} bazRd,2n 的同态电路

我们设置 refreshing key 成为 3 m × l × r 3m \times l \times r 3m×l×r 的寄存器矩阵,
K R = K i j k R : = R E G z 2 n / Q [ 1 3 m ⋅ D F T ( ψ ( z ) ) i , k ⋅ 2 j , β R ] i ∈ [ 3 m ] , j ∈ [ l ] , k ∈ [ r ] K^R = K_{ijk}^R := REG_z^{2n/Q}\left[\dfrac{1}{3m} \cdot DFT(\psi(z))_{i,k} \cdot 2^j,\,\, \beta_R\right]_{i \in [3m], j \in [l], k \in [r]} KR=KijkR:=REGz2n/Q[3m1DFT(ψ(z))i,k2j,βR]i[3m],j[l],k[r]

解密算法为:

在这里插入图片描述

其中的 D F T − 1 DFT^{-1} DFT1,由于 m ∣ d m|d md 都是三的幂次,令 r = ϕ ( d ) / m r=\phi(d)/m r=ϕ(d)/m,变元 y d / m = 1 y^{d/m}=1 yd/m=1
Φ d / m ( y ) = y r + y r / 2 + 1 \Phi_{d/m}(y)=y^r+y^{r/2}+1 Φd/m(y)=yr+yr/2+1

于是数乘 ζ 3 m − i k \zeta_{3m}^{-ik} ζ3mik 可以表示为对 R d / m , 2 n R_{d/m,2n} Rd/m,2n 上的各个项 a ⋅ y v a\cdot y^v ayv 乘以某个 y i y^i yi,然后模掉稀疏的 Φ d / m ( y ) \Phi_{d/m}(y) Φd/m(y)。注意:我们分别加密 R d / m , 2 n R_{d/m,2n} Rd/m,2n 的各个系数,成为带索引的寄存器 ( R E G ( a ) , v ) (REG(a), v) (REG(a),v),而变元 y v y^v yv 并不被加密,乘以 y i y^i yi 就只是把系数的密文简单的置换到 y v + i y^{v+i} yv+i 位置。模约减的公式为:
( a ⋅ y v ) ⋅ y i ( m o d Φ d / m ( y ) ) = { a ⋅ y v + i , for  v + i < r − a ⋅ y v + i ( m o d r ) − a ⋅ y v + i + r / 2 ( m o d r ) , for  r ≤ v + i < d / m a ⋅ y v + i ( m o d d / m ) , for  v + i ≥ d / m (a\cdot y^v) \cdot y^i \pmod{\Phi_{d/m}(y)} = \left\{\begin{array}{l} a\cdot y^{v+i},& \text{for } v+i<r\\ -a\cdot y^{v+i\pmod{r}} - a\cdot y^{v+i+r/2\pmod{r}},& \text{for } r\le v+i<d/m\\ a\cdot y^{v+i\pmod{d/m}},& \text{for } v+i\ge d/m\\ \end{array}\right. (ayv)yi(modΦd/m(y))= ayv+i,ayv+i(modr)ayv+i+r/2(modr),ayv+i(modd/m),for v+i<rfor rv+i<d/mfor v+id/m

复杂度分析:

  • 朴素的 InvDFT 共计花费 ( 3 m ) 2 (3m)^2 (3m)2 次小环 R d / m , 2 n R_{d/m,2n} Rd/m,2n 的元素与 ζ 3 m − i k \zeta_{3m}^{-ik} ζ3mik 的数乘,每个数乘(旋转系数)的开销是 O ( r ) O(r) O(r)减法,共计 O ( ( 3 m ) 2 r ) O((3m)^2r) O((3m)2r) 次减法

  • 在 SlowMult 步骤,执行了 3 m 3m 3m 个小环 R d / m , 2 n R_{d/m,2n} Rd/m,2n 上的常数乘法,每个数乘(子集加和)开销是 O ( r 2 ⋅ l ) O(r^2 \cdot l) O(r2l) 次加法,共计 O ( 3 m r 2 l ) O(3mr^2l) O(3mr2l)加法

  • 其他运算的计算复杂度都很低

假设 d = 3 k d=3^k d=3k,由于 d > 3 m 2 d>3m^2 d>3m2,可推出 ϵ ≤ 1 2 − 1 2 k \epsilon \le \frac{1}{2} - \frac{1}{2k} ϵ212k1,因此 RingDecrypt 的(关于 REG 同态加/减法)总复杂度为:
O ( ( 3 m ) 2 r + 3 m r 2 l ) = O ~ ( d 1 + ϵ + d 2 − ϵ ) = O ~ ( d 2 − ϵ ) O((3m)^2r + 3mr^2l) = \tilde O(d^{1+\epsilon} + d^{2-\epsilon}) = \tilde O(d^{2-\epsilon}) O((3m)2r+3mr2l)=O~(d1+ϵ+d2ϵ)=O~(d2ϵ)

于是选取 m ≈ d , ϵ ≈ 0.5 m \approx \sqrt d, \epsilon \approx 0.5 md ,ϵ0.5 将会导致更好的性能。它输出了 ϕ ( d ) \phi(d) ϕ(d) 个寄存器 R E G z 2 n / Q [ m ~ i , β ′ ] REG^{2n/Q}_z[\tilde m_i, \beta'] REGz2n/Q[m~i,β],噪声界为
β ′ = O ~ ( β R B g 4 ⋅ ( n d g ) 3.5 ⋅ d ϵ + 0.5 ) \beta' = \tilde O(\beta_R B_g^4 \cdot (nd_g)^{3.5}\cdot d^{\epsilon+0.5}) β=O~(βRBg4(ndg)3.5dϵ+0.5)

它与原始 LWE 密文的噪声无关,仅依赖于自举秘钥 K R K^R KR 的噪声 β R \beta_R βR

MSB Extract

现在我们获得了 ϕ ( d ) \phi(d) ϕ(d) 个寄存器 R E G z 2 n / Q [ m ~ i , β ′ ] REG^{2n/Q}_z[\tilde m_i, \beta'] REGz2n/Q[m~i,β],类似于 FHEW 那样从寄存器第一分量 R G S W z 2 n / Q ( u ⋅ Y m ~ i ) RGSW^{2n/Q}_z(u \cdot Y^{\tilde m_i}) RGSWz2n/Q(uYm~i) 中提取出 R L W E z 2 n / Q ( u ⋅ Y m ~ i ) RLWE^{2n/Q}_z(u \cdot Y^{\tilde m_i}) RLWEz2n/Q(uYm~i),其中的 m ~ i = n ⋅ m i ∈ Z 2 n \tilde m_i = n\cdot m_i \in \mathbb Z_{2n} m~i=nmiZ2n

使用这个 RLWE 密文,作用于舍入函数(反循环函数)的 Lookup Table,提取出 m i ∈ Z 4 m_i \in \mathbb Z_4 miZ4 的 LWE 密文,编码倍率为 2 u = Q / 4 2u=Q/4 2u=Q/4

简记 ( ⁣ ⁣ ( z ) ⁣ ⁣ ) (\!\!(z)\!\!) ((z)) 是多项式 z ∈ R d , 2 n z \in R_{d,2n} zRd,2n 的系数向量,密文提取算法为:

在这里插入图片描述

现在的密文是 L W E ϕ ( d ) 4 / Q LWE^{4/Q}_{\phi(d)} LWEϕ(d)4/Q,我们还应当执行密钥-维度-模数切换,回到本来的 L W E n 4 / q LWE^{4/q}_n LWEn4/q 上。

Refreshing

综合上述的技术,我们就得到了亚线性(均摊)复杂度的自举方案。给定 packing key K P K^P KPrefreshing key K R K^R KR,批处理的自举算法的具体步骤如下:

在这里插入图片描述

它的计算复杂度和噪声增长为:
在这里插入图片描述

Recursive optimization

可以递归地使用 Nussbaumer 转换,每层的每个小环元素拆分出 m m m 个更小的环元素。对于固定的 ϵ \epsilon ϵ,确定某个递归深度 ρ \rho ρ,使得 Z 2 n [ y ′ ] / Φ d / m ρ ( y ′ ) \mathbb Z_{2n}[y']/\Phi_{d/m^\rho}(y') Z2n[y]/Φd/mρ(y) 中存在 3 m 3m 3m 次本原单位根。这要求 d / m ρ ≥ 3 m d/m^\rho \ge 3m d/mρ3m,其中 m = d ϵ m=d^\epsilon m=dϵ,求出最大深度为 ρ < 1 / ϵ − 1 \rho < 1/\epsilon-1 ρ<1/ϵ1

迭代方式的计算效率更高,但是噪声增长也更快:

在这里插入图片描述

在最优参数下复杂度为 O ~ ( d 1 + ϵ ) \tilde O(d^{1+\epsilon}) O~(d1+ϵ),批处理 ϕ ( d ) = O ( d ) \phi(d)=O(d) ϕ(d)=O(d) 个 LWE 密文的均摊成本仅为 O ~ ( d ϵ ) \tilde O(d^{\epsilon}) O~(dϵ)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/189038.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

出口美国操作要点汇总│走美国海运拼箱的注意事项│箱讯科技

01服务标准 美国的货物需要细致的服务&#xff0c;货物到港后的服务也是非常重要的。如果在货物到港15天内&#xff0c;如果没有报关行进行(PROCEED)&#xff0c;货物就会进入了G.O.仓库&#xff0c;G.O.仓库的收费标准是非常高的。 02代理资格审核 美国航线除了各家船公司&a…

基于SSM的停车场管理系统设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。你想解决的问题&#xff0c;今天给大家介绍…

低代码平台,业务开发的“银弹”

目录 一、为什么需要低代码平台 二、低代码平台的搭建能力 三、低代码其他能力 四、写在最后 随着互联网和信息技术的快速发展&#xff0c;各行各业都在积极拥抱数字化转型。在这个过程中&#xff0c;软件开发成为企业实现数字化转型的关键环节。然而&#xff0c;传统的软件开发…

YOLOv4: Optimal Speed and Accuracy of Object Detection(2020.4)

文章目录 AbstractIntroductionRelated workObject detection modelsBag of freebiesBag of specials MethodologySelection of architectureSelection of BoF and BoSAdditional improvementsYOLOv4 ExperimentsResults表8列出了使用Maxwell GPU的帧率对比结果表9列出了使用Pa…

Jenkins 质量扫描

代码质量扫描工具&#xff08;SonarQube&#xff09; 质量评审 SonarQube有四个关键组件 ◼ SonarQube Server运行有三个组件 ◆ Web Server&#xff1a;UI ◆ Search Server&#xff1a;为UI提供搜索功能&#xff0c;基于ElasticSearch ◆ Compute Engine Server&#xff1a…

Git GUI、SSH协议和IDEA中的Git使用详解

目录 前言 一、Git GUI的使用 1. 什么是Git GUI 2. 常见的Git GUI工具 3.使用 4.使用Git GUI工具的优缺点 优点&#xff1a; 缺点&#xff1a; 二、SSH协议 1.什么是SSH协议 2.SSH的主要特点和作用 3.SSH密钥认证的原理和流程 4. SSH协议的使用 三、IEDA使用git …

webrtc推拉流 srs报错:DTLS_HANG DTLS: > Hang, done=0, version=-1, arq=0

执行了./objs/srs -c conf/rtc.conf 打开了srs的推拉流网页&#xff1a; 推流 拉流 srs报错如下&#xff1a; [2023-11-08 21:55:23.489][Warn][44992][8xvf4d62][104][DTLS_HANG] DTLS: Hang, done0, version-1, arq0 观看srs日志&#xff0c;在sdp offer&#xff0c;answer…

【postgresql】 代替mysql的if函数

在postgresql 中用 COALESCE 来代替mysql中的 if &#xff1b; COALEASE 函数的语法如下&#xff1a; COALESCE(expression_1, expression_2, expression_3, ...) COALESCE 函数接受多个参数&#xff0c;并且返回第一个非空的参数值&#xff1b; 如果所有参数都为空值&…

[护网杯 2018]easy_tornado 1(两种解法!)

题目环境&#xff1a;发现有三个txt文本文件 /flag.txt/welcome.txt/hints.txt 依此点开 flag在/fllllllllllllag文件中 在hints.txt文件中发现md5计算 md5(cookie_secretmd5(filename)) 并且三个文件中都存在filehash&#xff08;文件名被哈希算法加密32位小写&#xff09; 猜…

java excel、word、PPT转换成pdf预览

先引入包&#xff1a;[lib下载地址](https://mp.csdn.net/mp_download/manage/download/UpDetailed)Controllerpublic AjaxResult fileToPdf(RequestBody VerifyCode url, HttpServletResponse response, HttpServletRequest request) throws IOException {String fileUrl req…

[pipe-自写管道] 强网拟态2023-water-ker

程序分析 保护当然都开了, 题目给了一次增加, 释放, 修改一字节堆块的能力, 这里释放堆块后没有将其指针置空从而导致了 UAF. 漏洞利用 这里的堆块大小为 512 字节并是 SLAB_ACCOUNT, 所以可以直接利用管道去构造自写管道从而构造任意读写系统, 详细见大佬博客:【CTF.0x08】D…

NSF服务器

1.简介 1.1 NFS背景介绍 NFS是一种古老的用于在UNIX/Linux主机之间进行文件共享的协议。它古老到你必须穿着白大补才能接近一台计算机的年代。在那个年代&#xff0c;所有的联网计算机都被认为是可信的&#xff0c;而不像现今这样&#xff0c;任何人都有多种多样方法能连接到你…

【解决】conda-script.py: error: argument COMMAND: invalid choice: ‘activate‘

运行conda activate base报错&#xff1a; 试了网上找到的解决方法都不行&#xff1a; 最后切换了一下terminal&#xff1a; 从powershell改回cmd&#xff08;不知道为什么一开始手贱换成powershell&#xff09; 就可以了

(一)七种元启发算法(DBO、LO、SWO、COA、LSO、KOA、GRO)求解无人机路径规划MATLAB

一、七种算法&#xff08;DBO、LO、SWO、COA、LSO、KOA、GRO&#xff09;简介 1、蜣螂优化算法DBO 蜣螂优化算法&#xff08;Dung beetle optimizer&#xff0c;DBO&#xff09;由Jiankai Xue和Bo Shen于2022年提出&#xff0c;该算法主要受蜣螂的滚球、跳舞、觅食、偷窃和繁…

Python - 利用 OCR 技术提取视频台词、字幕

目录 一.引言 二.视频处理 1.视频样式 2.视频截取 ◆ 裁切降帧 ◆ 处理效果 3.视频分段 三.OCR 处理 1.视频帧处理 2.文本识别结果 3.后续工作与优化 ◆ 识别去重 ◆ 多线程提效 ◆ 片头片尾优化 四.总结 一.引言 视频经常会配套对应的台词或者字幕&#xff0c…

4.HTML网页开发的工具

4. 网页开发的工具 4.1 快捷键 4.1.1 快速复制一行 快捷键&#xff1a;shiftalt下箭头&#xff08;上箭头&#xff09; 或者ctrlc 然后 ctrlv 4.1.2 选定多个相同的单词 快捷键&#xff1a; ctrld 4.1.3 添加多个光标 快捷键&#xff1a;ctrlalt上箭头&#xff08;下箭头&…

CS224W6.1——介绍图神经网络GNN

之前我们讨论了一些节点嵌入技术&#xff0c;它们可以通过随机游走的过程学习与任务无关的特征。从这篇开始&#xff0c;我们介绍了令人兴奋的图神经网络技术&#xff0c;该技术基于图结构用多层非线性变换对节点特征进行编码。图神经网络在各种任务中表现出非凡的性能&#xf…

vue3响应式api

响应式api——compositon api setup&#xff1a; 不要再想this问题执行是在beforeCreated之前 beforeCreated&#xff1a;也就是创建了一个实例 created&#xff1a;挂载了数据 通过形参props接收&#xff0c;只读 以后所有代码都写到setup中 判断是否只读&#xff1a;isReadon…

Zabbix SNMPv3

一、Snmpv3简述 SNMPv3是Simple Network Management Protocol version 3&#xff08;简单网络管理协议第三版&#xff09;的缩写。它是一种网络管理协议&#xff0c;用于监控和管理网络中的设备、系统和应用程序。 相对于之前的版本&#xff0c;SNMPv3具有更强的安全性和扩展…

spring-cloud-stream

系列文章目录 第一章 Java线程池技术应用 第二章 CountDownLatch和Semaphone的应用 第三章 Spring Cloud 简介 第四章 Spring Cloud Netflix 之 Eureka 第五章 Spring Cloud Netflix 之 Ribbon 第六章 Spring Cloud 之 OpenFeign 第七章 Spring Cloud 之 GateWay 第八章 Sprin…