Nussbaumer Transform 以及 Amortized FHEW bootstrapping

Transform 以及 Amortized FHEW bootstrapping"/>

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​=e−2π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 p1​p2​…pb​ 个元素的群。对于群元素 x ∈ G x \in G x∈G，我们简单记做向量形式 ( 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​),xj​∈Zpj​​

函数 f : G → C f:G \rightarrow C f:G→C（索引为 x ∈ G ≅ [ p j ] j x \in G \cong [p_j]_j x∈G≅[pj​]j​ 的高阶查找表）执行离散傅里叶变换，得到 F : G → C F:G \rightarrow C F:G→C （索引为 α ∈ 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​):=x∈G∑​(f(x)⋅j=1∏b​ζjαj​xj​​)
逆离散傅里叶变换的公式为：
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​):=p1​p2​…pb​1​α∈G∑​(F(α)⋅j=1∏b​ζj−αj​xj​​)

容易验证，上式是正确的。由于 ζ 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​+⋯+ζjpj​−1​=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=1∏b​ζjαj​(xj​−xj′​)​)={∣G∣0​​x=x′x=x′​

其中 ∣ G ∣ = p 1 p 2 … p b |G| = p_1p_2 \dots p_b ∣G∣=p1​p2​…pb​，所以 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​):=∣G∣1​⋅DFT(F,[ζj−1​]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​=0∑N−1​n2​=0∑N−1​xn1​,n2​​ζNn1​k2​+n2​k2​​

令 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​,n2​​⋅w−n1​)⋅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):=n2​∑​xn2​​(z)⋅w2n2​k2​(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)(modz−w2k1​+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)=n2​∑​xn2​​(z)⋅z2n2​k2​(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)(modz−w2k1​+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)≤N−1，因此可以把它记为
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=0∑N−1​yk2​,l​⋅zl

因此二维 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=0∑N−1​yk2​,l​⋅(w2k1​+1)l=l=0∑N−1​(yk2​,l​⋅wl)⋅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} w−n1​，构造出 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​,l​⋅wl]l​
5. 对于每个 k 2 k_2 k2​，对样本 [ y k 2 , l ⋅ w l ] l [y_{k_2,l}\cdot w^l]_l [yk2​,l​⋅wl]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]/(xm−1)。利用 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)∈Rm​↦G(x)⋅a(x)∈Cm​ 是单的加群同态。

对于 m = u ⋅ w m=u \cdot w m=u⋅w，就有以下的良好性质：

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 w−1 的多项式 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)(modxw−1)，那么 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)(modxm−1)

假设 m = u ⋅ w m=u \cdot w m=u⋅w，那么 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 x↦xu。给定 Z [ x ] / ( x m − 1 ) \mathbb Z[x]/(x^m-1) Z[x]/(xm−1) 中的多项式，
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=0∑m−1​ai​⋅xi=k=0∑u−1​j=0∑w−1​auj+k​⋅xuj+k=k=0∑u−1​(j=0∑w−1​auj+k​⋅xuj)⋅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=0w−1​auj+k​⋅xj∈Z[x]/(xw−1)，那么
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=0∑u−1​a(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 a∈Cm​↦[a(k)​]k​∈Cwu​ 切分过程称为 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=2l−1
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} b−a⋅s∈Rd,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([2j⋅DFT(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(s⋅a)i​∈Z2n​ 的累加器状态
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} s⋅a∈Rd,2n​ 各个系数的寄存器，从而可以计算出 m ≈ b − a ⋅ s m\approx b-a \cdot s m≈b−a⋅s 的寄存器（共有 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=⌈x⌉−xPr=x−⌊x⌋​

舍入噪声为 $-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​∥+∥e1​⋅z∥=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,lP​∈RLWEzq/q​[sl​⋅2j,β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)=∑i​mi​xi，它的噪声界是
β = 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} z∈Rd,2n​，我们接下来需要同态地计算 b − a ⋅ z ∈ R d , 2 n b-a \cdot z \in R_{d,2n} b−a⋅z∈Rd,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} v∈Z2n​，假设 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​(u⋅Yv)，其中的 u ≈ Q / 2 t u\approx Q/2t u≈Q/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 v←w，状态为无噪密文
  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=u⋅XwG∈RGSWz2n/Q​(u⋅Xw)

• 常数加法（Increment）：记为 v ← v + c v \gets v+c v←v+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}) C⋅Xc∈RGSWz2n/Q​(u⋅Xw+c)

• 密文加法（Addition）：记为 v ← v + C ′ v \gets v+C' v←v+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}) (u−1⋅C)⋅G−1(C′)∈RGSWz2n/Q​(u⋅Xv+w)

• 密文提取（Extraction）：从 C C C 中提取出 LWE 密文

为了使得同态寄存器也支持减法，[MS18] 将数值 v ∈ Z 2 n v \in \mathbb Z_{2n} v∈Z2n​ 存储为冗余的一对 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​(u⋅Xv),RGSWz2n/Q​(u⋅X−v))

这个寄存器的：初始化、常数加法、密文加法，都是从累加器自然继承的。密文提取就是对第一分量 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 v∈Z2n​[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} z∈Rd,2n​ 是各个系数单独加密在 REG 内的，并且 a ∈ R d , 2 n a \in R_{d,2n} a∈Rd,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):=[zk​2j]k,j​∈Z2nl×ϕ(d)​ 的值，然后将 a i ∈ Z 2 n a_i \in \mathbb Z_{2n} ai​∈Z2n​ 做二进制分解 ∑ j = 0 l − 1 a i j 2 j \sum_{j=0}^{l-1} a_{ij}2^j ∑j=0l−1​aij​2j

定义计算标量数乘 a i ⋅ z k ∈ Z 2 n a_i \cdot z_k \in \mathbb Z_{2n} ai​⋅zk​∈Z2n​ 的同态电路
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∑​[[zk​2j]]

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

于是环元素数乘 a ⋅ z ∈ R d , 2 n a \cdot z \in R_{d,2n} a⋅z∈Rd,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] a⋅z∈Z2n​[x]，它的长度为 2 d − 1 2d-1 2d−1
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} (a⋅z)i​=∑i=j+k​aj​⋅zk​∈Z2n​ 是若干数乘的加和，采取 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(d2⋅l) 个同态加法
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)⋯Qpk−1​(x)xpk−1​=xpk−1−1xpk−1​=1+xpk−1+x2pk−1+⋯+x(p−1)pk−1​

它仅包含 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​=logBg​​Q 是分解位数，那么存在算法 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​[(a⋅z)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~(βBg​⋅ndg​⋅d ​)，它的计算复杂度为 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]/(xm−1) 是循环卷积环（ 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ˉi​xk​​==​DFT(x)i​DFT−1(x)i​​:=:=​∑k=0m−1​xk​ζmik​∑i=0m−1​xˉi​ζm−ik​​

那么对于 a , z ∈ R d a,z \in R_d a,z∈Rd​ 的多项式乘法，只要满足 deg ⁡ a ⋅ z < m \deg a\cdot z < m dega⋅z<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)(modxm−1))(modΦd​(x))=DFT−1(m1​DFT(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 ζm−ik​∈C 数乘，显然不是什么好主意。

[MS18] 使用 Nussbaumer Transform 来解决这个问题。它使用了更加代数化的语言，描述 Nussbaumer 的映射过程。给定 m ∣ d m|d m∣d 都是素数 p ≥ 2 p \ge 2 p≥2 的幂次，并且满足 d ≥ p m 2 d\ge pm^2 d≥pm2（为了使得 p m ∣ d / m pm\mid d/m pm∣d/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,q​a(x)=∑i=0ϕ(d)​ai​xi​→↦​Rd/m,q​[x]/(xm−y)a(x,y)=∑j=0m−1​(∑i=0r−1​ami+j​yi)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=0r−1​ami+j​yi∈Zq​[y]/(Φd/m​(y))，由于 x x x 是 d d d 次本原单位根，因此 y = x m ∈ R m , q y=x^m \in R_{m,q} y=xm∈Rm,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]/(xpm−1) 的 DFT（简单的 Lift，两个关于 x x x 的次数至多为 m − 1 m-1 m−1 的多项式，乘积的次数不会越过 p m − 1 pm-1 pm−1，因此计算正确），那么就需要 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 a⋅s∈Rd​ 的计算流程：

1. 秘钥 s ∈ R d s \in R_d s∈Rd​ 是关于 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]/(xm−y) 得到了关于 x x x 的度数 m − 1 m-1 m−1 且关于 y y y 的度数 r − 1 r-1 r−1 的双变元多项式
2. 关于变元 x x x，预计算 f = 1 m D F T ( ψ ( s ) ) f = \dfrac{1}{m}DFT(\psi(s)) f=m1​DFT(ψ(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]/(xpm−1) 上
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 a∈Rd​ 作为常数（因此 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ˉ:=m1​DFT(ψ(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=0m−1​cˉi​ζm−ik​ 来计算即可（不要使用 FFT/NTT，多层迭代导致了无法利用 GSW 的不对称噪声增长特性），其中的数乘 ζ m − i k \zeta_m^{-ik} ζm−ik​ 就是在小环 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]/(xpm−1) 的（各个系数的系数）密文，把它同态的模掉 ( x m − y ) (x^m-y) (xm−y) 得到 ψ ( z ⋅ a ) ∈ R d / m [ x ] / ( x m − y ) \psi(z \cdot a) \in R_{d/m}[x]/(x^m-y) ψ(z⋅a)∈Rd/m​[x]/(xm−y)，它其实就是 z ⋅ a ∈ R d z \cdot a \in R_d z⋅a∈Rd​

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 d≥3m2，简记 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,2n​→Rd/m,2n​[x]/(xm−y)

其中 ζ 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,z∈Rd,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]/(xm−y)

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]/(x3m−1)，现在可以对 ψ ( 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,⋯,2l−1)⊗[31​⋅DFT(ψ(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} (a⋅z)k​=∑i=03m−1​(a⋅z)i​​ζ3m−ik​ 同态计算 InvDFT 的电路（因为 ζ 3 m ∈ R d / m , 2 n \zeta_{3m} \in R_{d/m,2n} ζ3m​∈Rd/m,2n​，所以只需要同态加/减法），那么计算 a ⋅ z ∈ R d , 2 n a \cdot z \in R_{d,2n} a⋅z∈Rd,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} [[a⋅z]]=Ca​([[f(z)]]):=CF​([Caˉi​​([[f(z)]])]i​)(modxm−y)

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)]])=b−Ca​([[f(z)]]) 是计算 b − a ⋅ z ∈ R d , 2 n b-a\cdot z \in R_{d,2n} b−a⋅z∈Rd,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​[3m1​⋅DFT(ψ(z))i,k​⋅2j,βR​]i∈[3m],j∈[l],k∈[r]​

解密算法为：

其中的 D F T − 1 DFT^{-1} DFT−1，由于 m ∣ d m|d m∣d 都是三的幂次，令 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} ζ3m−ik​ 可以表示为对 R d / m , 2 n R_{d/m,2n} Rd/m,2n​ 上的各个项 a ⋅ y v a\cdot y^v a⋅yv 乘以某个 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. (a⋅yv)⋅yi(modΦd/m​(y))=⎩ ⎨ ⎧​a⋅yv+i,−a⋅yv+i(modr)−a⋅yv+i+r/2(modr),a⋅yv+i(modd/m),​for v+i<rfor r≤v+i<d/mfor v+i≥d/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} ζ3m−ik​ 的数乘，每个数乘（旋转系数）的开销是 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(r2⋅l) 次加法，共计 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} ϵ≤21​−2k1​，因此 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 m≈d ​,ϵ≈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~(βR​Bg4​⋅(ndg​)3.5⋅dϵ+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​(u⋅Ym~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​(u⋅Ym~i​)，其中的 m ~ i = n ⋅ m i ∈ Z 2 n \tilde m_i = n\cdot m_i \in \mathbb Z_{2n} m~i​=n⋅mi​∈Z2n​

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

简记 ( ⁣ ⁣ ( z ) ⁣ ⁣ ) (\!\!(z)\!\!) ((z)) 是多项式 z ∈ R d , 2 n z \in R_{d,2n} z∈Rd,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 KP 和 refreshing 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ϵ)