Conversion Between (R)LWE

参考文献：

1. [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.
2. [BGGJ20] Boura C, Gama N, Georgieva M, et al. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes[J]. Journal of Mathematical Cryptology, 2020, 14(1): 316-338.
3. [CDKS21] Chen H, Dai W, Kim M, et al. Efficient homomorphic conversion between (ring) LWE ciphertexts[C]//International Conference on Applied Cryptography and Network Security. Cham: Springer International Publishing, 2021: 460-479.
4. [LHH+21] Lu W, Huang Z, Hong C, et al. PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption[C]//2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021: 1057-1073.

文章目录

• Conversion Between RLWE
• • Tower of Cyclotomic
  • LWE-to-LWE
  • LWE-to-RLWE
  • LWEs-to-RLWE
  • Lightweight Communication

[MS18] 为了实现均摊 FHEW 自举，提出了 Ring packing 技术：将多个 LWE 密文（行矢）堆叠为 $(A,b)$，然后按列转化为多项式 aj( x ) , b ( x )a_j(x), b(x)aj​(x),b(x)，使用 Key-Switch 执行同态线性解密 $A\cdot E(s)+b$（私钥被加密在多项式的常数项），最终获得打包了 μ ( x ) = ∑jμjxj \mu(x)=\sum_j \mu_jx^jμ(x)=∑j​μj​xj 的单个 RLWE 密文。虽然它是 Coeff Packing 的，但是 [MS18] 中的同态 InvDFT 的目标是加速同态的多项式乘法（线性解密部分），而非 SIMD 打包并行。但是其中的 SwK 是对于 LWE 私钥的各个分量分别用 RLWE 加密的 R L W E s ′( si⋅ gj)RLWE_{s’}(s_i \cdot g_j)RLWEs′​(si​⋅gj​)，规模大、速度慢。计算过程中不需要用到同态旋转（主要的开销是秘钥切换），仅仅是对于 $E(s)$ 的同态线性运算。

[BGGJ20] 提出的 Chimera 也使用类似的堆叠技术，将 TLWE 打包转换到 RLWE 密文上。不过它将堆叠出的矩阵 $C=(A,b)$ 直接乘以 InvDFT，于是 $(InvDFT\cdot C)\cdot s=InvDFT(\mu (x))$，这就将各个 μj \mu_jμj​ 编码到了明文槽。它的 SwK 也是各个私钥分量分别被加密在系数上 R G S W s ′( si)RGSW_{s’}(s_i)RGSWs′​(si​)，规模很大（GB 级别）

[CDKS21] 提出了新的 LWE 的 Key-Switch 技术（后文简记 KS），将 LWE 密文嵌入到 RLWE 密文上，对应的 SwK 将LWE 私钥作为单个多项式做 RLWE 加密 R L W E s ′( s ( x ) ⋅ gj)RLWE_{s’}(s(x) \cdot g_j)RLWEs′​(s(x)⋅gj​)，从而极大的提高了 KS 的速度（两个数量级）。需要使用分圆域的自同构的某些特殊性质，消除一些杂项。推广这个 KS 过程，可以获得 LWE 打包到 RLWE 的过程，不过它也是 Coeff Packing 的（还应该使用 Coeff-to-Slot 过程将它们编码到明文槽）。令 $N$ 是 RLWE 的维度，打包 $n=N$ 个 LWE 密文，复杂度为 $O(N)$ 次同态自同构，$O(N)$ 次同态数乘。

之后的 Pegasus 也使用密文堆叠技术，对于私钥 $s$ 的密文做线性变换，来实现 LWE-to-RLWE 过程。同态线性变换过程中，采取对角线乘法（旋转+阿达玛），LWE 私钥作为一个整体被加密在明文槽上 R L W E s ′( E c d ( s , Δ ) )RLWE_{s’}(Ecd(s,\Delta))RLWEs′​(Ecd(s,Δ))，规模大大减小（MB 级别），同态解密的结果直接在明文槽上。令 $N$ 是 RLWE 的维度，打包 $n=N$ 个 LWE 密文，复杂度为 O ( N)O(\sqrt{N})O(N ​) 次同态旋转（由若干个自同构组成，完全分裂的二的幂分圆环只需要一个），$O(N)$ 次同态数乘。

Conversion Between RLWE

Tower of Cyclotomic

令 m = 2 L + 1 m=2^{L+1}m=2L+1 是二的幂， N = ϕ ( m ) = 2L N=\phi(m)=2^LN=ϕ(m)=2L 也是二的幂，分圆域 K = Q ( ζm) ≅ Q [ X ] / ( XN+ 1 )K=\mathbb Q(\zeta_m) \cong \mathbb Q[X]/(X^N+1)K=Q(ζm​)≅Q[X]/(XN+1)，分圆整数环 R = Z [ ζm] ≅ Z [ X ] / ( XN+ 1 )R=\mathbb Z[\zeta_m] \cong \mathbb Z[X]/(X^N+1)R=Z[ζm​]≅Z[X]/(XN+1)，为了区分不同维度我们记为 KN, RN K_N,R_NKN​,RN​

根据代数理论，域扩张 $K/\mathbb{Q}$ 都是 Galois 扩张，Galois 群 G a l ( K / Q ) ≅ Zm∗= { 1 , 3 , ⋯  , 2 N − 1 }Gal(K/\mathbb Q) \cong \mathbb Z_m^*=\{1,3,\cdots,2N-1\}Gal(K/Q)≅Zm∗​={1,3,⋯,2N−1}，自同构：
τ d: ζ m→ ζ m d,∀d∈ Z m ∗\tau_d: \zeta_m \to \zeta_m^d, \forall d\in\mathbb Z_m^* τd​:ζm​→ζmd​,∀d∈Zm∗​
域的迹：
T r K/Q :a∈K↦ ∑ τ∈Gal(K/Q) τ(a)∈QTr_{K/\mathbb Q}: a \in K \mapsto \sum_{\tau \in Gal(K/\mathbb Q)} \tau(a) \in \mathbb Q TrK/Q​:a∈K↦τ∈Gal(K/Q)∑​τ(a)∈Q
根据代数知识， T r K / Q Tr_{K/\mathbb Q}TrK/Q​ 是 $\mathbb{Q}$–线性映射，并且满足

• T r K/Q (1)=[K:Q]=NTr_{K/\mathbb Q}(1)=[K:\mathbb Q]=N TrK/Q​(1)=[K:Q]=N
• T r K/Q ( X i)=0,∀i≠0Tr_{K/\mathbb Q}(X^i)=0, \forall i \neq 0 TrK/Q​(Xi)=0,∀i=0

对于分圆塔：
K= K N≥ K N/2 ≥⋯≥ K 1=QK=K_N \ge K_{N/2} \ge \cdots \ge K_1=\mathbb Q K=KN​≥KN/2​≥⋯≥K1​=Q
其中 Kn, n = 2l K_n,n=2^lKn​,n=2l 可以作为 KN K_NKN​ 的子域（ Rn≤ RN R_n \le R_NRn​≤RN​ 类似），设置 Y = X N / n Y=X^{N/n}Y=XN/n，
K n= { ∑ i ∈ [ n ]aiYi: ai∈ Q }⊆ K NK_n = \left\{\sum_{i \in [n]} a_i Y^i: a_i \in \mathbb Q\right\} \subseteq K_N Kn​=⎩ ⎨ ⎧​i∈[n]∑​ai​Yi:ai​∈Q⎭ ⎬ ⎫​⊆KN​
基于分圆塔，可以将迹分解：
T r K/Q =T rK 2/ K 1 ∘⋯∘ TK N/ K N/2Tr_{K/\mathbb Q} = Tr_{K_2/K_1} \circ \cdots \circ T_{K_N/K_{N/2}} TrK/Q​=TrK2​/K1​​∘⋯∘TKN​/KN/2​​
易知，相邻的域扩张的次数为 $2$，仅包含一个非凡自同构（另一个是恒等映射）：
Gal( K 2l / K 2 l − 1 )={ τ 1 ∣ K 2 l ,   τ2 l+1∣ K 2 l },    1≤l≤LGal(K_{2^l}/K_{2^{l-1}}) = \{\tau_1|_{K_{2^l}},\,\, \tau_{2^l+1}|_{K_{2^l}}\},\,\, 1 \le l \le L Gal(K2l​/K2l−1​)={τ1​∣K2l​​,τ2l+1​∣K2l​​},1≤l≤L
其中的 τ 2l+ 1∣ K 2l\tau_{2^l+1}|_{K_{2^l}}τ2l+1​∣K2l​​ 是自同构映射 τ 2l+ 1∈ G a l ( K / Q )\tau_{2^l+1} \in Gal(K/\mathbb Q)τ2l+1​∈Gal(K/Q) 限制在 K 2 l⊆ KN K_{2^l} \subseteq K_NK2l​⊆KN​ 上，容易验证它是 K 2 l K_{2^l}K2l​ 的 K 2 l−1K_{2^{l-1}}K2l−1​-自同构。进一步的，简记 n = 2l n=2^ln=2l， Y = X N / n Y=X^{N/n}Y=XN/n 是 Kn/ QK_n/\mathbb QKn​/Q 的扩张元，那么有：
T rK n/ K n/2( Y i)= { 2 Y i,∀2∣i0,∀2∤i Tr_{K_{n}/K_{n/2}}(Y^i) = \left\{\begin{aligned} 2Y^i, &&\forall 2\mid i\\ 0, &&\forall 2\nmid i\\ \end{aligned}\right. TrKn​/Kn/2​​(Yi)={2Yi,0,​​∀2∣i∀2∤i​
因此，映射 μ ∈ Kn↦ T r Kn/ K n / 2 ( μ ) ∈ K n / 2 \mu \in K_n \mapsto Tr_{K_{n}/K_{n/2}}(\mu) \in K_{n/2}μ∈Kn​↦TrKn​/Kn/2​​(μ)∈Kn/2​，记号 $a\Vert b$ 表示 “恰好整除”，

1. 将系数 $\mu [i],(2N/n)\Vert i$，加倍
2. 将系数 $\mu [i],(N/n)\Vert i$，清零
3. 元素 μ∈ K n⊆ K N\mu \in K_n \subseteq K_N μ∈Kn​⊆KN​ 的其他系数本来就是零，保持

我们定义 $[N]=\{0,1,\cdots ,N-1\}$ 的一组划分（子域的系数索引），
I k:={i∈[N]: 2 k∥i},    0≤k<LI_k := \{ i \in [N]: 2^k\|i \},\,\, 0 \le k< L Ik​:={i∈[N]:2k∥i},0≤k<L
特别地设置 IL= { 0 }I_L=\{0\}IL​={0}，容易验证 [ N ] = ⋃kIk [N] = \bigcup_k I_k[N]=⋃k​Ik​

对于 d = 2l+ 1 , 1 ≤ l ≤ Ld=2^l+1, 1\le l \le Ld=2l+1,1≤l≤L，简记 i = 2kj ∈ Ik i=2^kj \in I_ki=2kj∈Ik​，其中 $j$ 是奇数，
i⋅d= 2 k+l j+ 2 kj= {2 k( 2 lj+j)∈ I k∀0≤k≤L 2 kj=i( m o d 2N),∀k>L−l 2 L+ 2 kj=N+i( m o d 2N),k=L−l i \cdot d = 2^{k+l}j + 2^kj = \left\{\begin{array}{ll} 2^k(2^lj+j) \in I_k &\forall 0 \le k \le L\\ 2^kj = i \pmod{2N}, &\forall k>L-l\\ 2^L+2^kj = N+i \pmod{2N}, &k=L-l\\ \end{array}\right. i⋅d=2k+lj+2kj=⎩ ⎨ ⎧​2k(2lj+j)∈Ik​2kj=i(mod2N),2L+2kj=N+i(mod2N),​∀0≤k≤L∀k>L−lk=L−l​
因此， τd: ζi→ ζ i ⋅ d \tau_d: \zeta^i \to \zeta^{i\cdot d}τd​:ζi→ζi⋅d 是对各个索引 Ik I_kIk​ 做了符号置换（signed permutation）， ∀ i ∈ Ik, ∃ r ∈ Ik, τd( Xi) = ± Xr \forall i \in I_k,\exist r \in I_k,\tau_d(X^i) = \pm X^r∀i∈Ik​,∃r∈Ik​,τd​(Xi)=±Xr。特别地对于 $k\ge L-l$ 的那些 Ik I_kIk​，
τ d( X i)= {X i,∀i∈ ⋃ k>L−lI k− X i,∀i∈ I L−l …otherwise \tau_d(X^i) = \left\{\begin{aligned} X^i, &&\forall i \in \bigcup_{k>L-l}I_k\\ -X^i, &&\forall i \in I_{L-l}\\ … &&otherwise \end{aligned}\right. τd​(Xi)=⎩ ⎨ ⎧​Xi,−Xi,…​​∀i∈k>L−l⋃​Ik​∀i∈IL−l​otherwise​
因此，映射 μ ∈ KN↦ μ + τd( μ ) ∈ KN \mu \in K_N \mapsto \mu+\tau_d(\mu) \in K_Nμ∈KN​↦μ+τd​(μ)∈KN​，

1. 将系数 μ[i], 2 L−l+1 ∣i\mu[i],2^{L-l+1}|i μ[i],2L−l+1∣i，加倍
2. 将系数 μ[i],i∈ I L−l \mu[i], i \in I_{L-l} μ[i],i∈IL−l​，清零
3. 其他系数的变化较为复杂

LWE-to-LWE

LWE 密文 ( b , a ) ∈ Zq 1 + N (b,a) \in \mathbb Z_q^{1+N}(b,a)∈Zq1+N​，私钥 s ∈ ZN s \in \mathbb Z^Ns∈ZN，线性解密获得相位（不考虑纠错），
μ 0=b+⟨a,s⟩( m o d q)\mu_0 = b+\langle a,s \rangle \pmod q μ0​=b+⟨a,s⟩(modq)
执行 KS 时，抽象思路是 K = { L W E s ′( si) }K=\{LWE_{s’}(s_i)\}K={LWEs′​(si​)}，然后同态解密获得 L W E s ′( μ0)LWE_{s’}(\mu_0)LWEs′​(μ0​)，但是这么做的复杂度太高了。[CDKS21] 提出了一种新的 KS 过程：

1. 将 $a$ 转化为多项式 a(x)=ι(a)∈ R N,q a(x) = \iota(a) \in R_{N,q} a(x)=ι(a)∈RN,q​，其中的映射 ι: Z N→ R N\iota: \mathbb Z^N \to R_N ι:ZN→RN​ 是将向量作为多项式系数
2. 将 $s$ 转化为多项式 s(x)= τ −1 ∘ι(s)∈ R Ns(x) = \tau_{-1} \circ \iota(s) \in R_N s(x)=τ−1​∘ι(s)∈RN​，其中的 τ −1 \tau_{-1} τ−1​ 是因为多项式乘积是向量反卷积

那么，获得的 ( b , a ( x ) ) ∈ R N , q2 (b,a(x)) \in R_{N,q}^2(b,a(x))∈RN,q2​ 可以视为 $s(x)$ 加密的 RLWE 密文，容易验证 μ ( x ) = b + a ( x ) s ( x ) ∈ R N , q \mu(x) = b+a(x)s(x) \in R_{N,q}μ(x)=b+a(x)s(x)∈RN,q​，它的常数项 $\mu [0]$ 恰好就是 μ 0\mu_0 μ0​ 了。

因此我们可以使用 K = { R L W E s ′( s ( x ) ⋅ gi) }K=\{RLWE_{s’}(s(x) \cdot g_i)\}K={RLWEs′​(s(x)⋅gi​)} 作为 SwK，执行 RLWE 的秘钥切换，最后提取出常数项对应的 LWE 密文。其中的 g = ( g1, ⋯  , gd)g=(g_1,\cdots,g_d)g=(g1​,⋯,gd​) 是 Gadget Vector，可使用 [BGV12] 的 Base decomposition 或者 [BEHZ16] 的 Prime decomposition（用于兼容 RNS 系统）。

具体算法为：

LWE Key-Switch 的噪声为 e k s= ⟨ g − 1( c1) , e ⟩e_{ks} = \langle g^{-1}(c_1), e \rangleeks​=⟨g−1(c1​),e⟩，其中 e ← χσ e \gets \chi_\sigmae←χσ​ 是 SwK 的噪声。为了兼容 RNS 系统，我们使用素数分解 g − 1: a ↦ { [ a ] q i∈ R N , qi }g^{-1}: a \mapsto \{[a]_{q_i} \in R_{N,q_i}\}g−1:a↦{[a]qi​​∈RN,qi​​}，那么可以计算出 e k s e_{ks}eks​ 各个系数的方差
V ks ≤ 1 12N σ 2⋅ ∑ i q i 2V_{ks} \le \frac{1}{12}N\sigma^2 \cdot \sum_i q_i^2 Vks​≤121​Nσ2⋅i∑​qi2​
易知 LWE-to-LWE 的噪声就是 Key-Switch 的噪声。

LWE-to-RLWE

上述的 LWE-to-LWE 过程中，产生的 c t′ ct’ct′ 并非是有效 RLWE 密文（相位只有常数项是有意义的，其他位置都是无效数据）。[CDKS21] 使用迹 T r K / Q Tr_{K/\mathbb Q}TrK/Q​ 来消除 Xi, i ≠ 0X^i,i \neq 0Xi,i=0 的系数，只保留常数项（缩放因子 $N$）。

直接计算 T r K / Q Tr_{K/\mathbb Q}TrK/Q​ 需要分别计算各个 τd, d ∈ Zm∗ \tau_d, d\in \mathbb Z_m^*τd​,d∈Zm∗​，共计需要 $N$ 个自同构映射（每一次都需要做 KS 过程）。因此，借助分圆塔将 T r K/Q Tr_{K/\mathbb Q} TrK/Q​ 分解，成为 $L=\log N$ 个相邻分圆域的迹 T r K 2 l/ K 2 l−1 Tr_{K_{2^l}/K_{2^{l-1}}}TrK2l​/K2l−1​​ 的组合，这样就只需要计算 $\log N$ 个非凡自同构。

具体算法为：

为了消除 $N$ 缩放因子，可以预先对输入的 LWE 密文缩放 [ N − 1]q [N^{-1}]_q[N−1]q​ 因子，从而上述算法的输出自然地消除了它们。

因为自同构 τd \tau_dτd​ 是保长的，因此不会导致噪声过度膨胀。同态迹的噪声是
Var≤ 1 3(( N n ) 2−1)⋅ V ks Var \le \frac{1}{3}((\frac{N}{n})^2-1) \cdot V_{ks} Var≤31​((nN​)2−1)⋅Vks​
选取 $n=1$，LWE-to-RLWE 的噪声就是 V a r ≤ 13( N2− 1 ) ⋅ V k s Var \le \frac{1}{3}(N^2-1) \cdot V_{ks}Var≤31​(N2−1)⋅Vks​

LWEs-to-RLWE

假如我们希望将相位是 μj, j ∈ [ n ]\mu_j, j \in [n]μj​,j∈[n] 的多个 LWE 密文打包到单个 RLWE 密文中：直接使用上述的转换得到 c tj ct_jctj​，然后计算 c t′= ∑ j ∈ [ n ]c tj⋅ Yj, Y = X N / n ct’ = \sum_{j \in [n]} ct_j \cdot Y^j, Y=X^{N/n}ct′=∑j∈[n]​ctj​⋅Yj,Y=XN/n，那么它的相位就是：
μ ′=N⋅ ∑ j∈[n]μ j Y j∈ R n⊆ R N\mu’ = N \cdot \sum_{j \in [n]} \mu_j Y^j \in R_n \subseteq R_N μ′=N⋅j∈[n]∑​μj​Yj∈Rn​⊆RN​
然而上述算法的计算效率和噪声增长都不算好。[CDKS21] 提出了 FFT-style 递归算法：假设 n = 2l n=2^ln=2l，为了计算 μ′ \mu’μ′，可以将 μj \mu_jμj​ 分为大小 2 l − 1 2^{l-1}2l−1 的两组，分别计算出
μ e v e n′ =N/2⋅ ∑ j∈[n/2]μ 2jY 2j ∈ R n/2 μ o d d′ =N/2⋅ ∑ j∈[n/2]μ 2j+1Y 2j ∈ R n/2 \begin{aligned} \mu_{even}’ &= N/2 \cdot \sum_{j \in [n/2]} \mu_{2j} Y^{2j} \in R_{n/2}\\ \mu_{odd}’ &= N/2 \cdot \sum_{j \in [n/2]} \mu_{2j+1} Y^{2j} \in R_{n/2}\\ \end{aligned} μeven′​μodd′​​=N/2⋅j∈[n/2]∑​μ2j​Y2j∈Rn/2​=N/2⋅j∈[n/2]∑​μ2j+1​Y2j∈Rn/2​​
但是实际上我们只需要计算出 μ e v e n, μ o d d∈ RN \mu_{even},\mu_{odd} \in R_Nμeven​,μodd​∈RN​，使得它们的 Y 2 j Y^{2j}Y2j 系数组成了 μ e v e n′, μ o d d′∈ R n / 2 \mu_{even}’,\mu_{odd}’ \in R_{n/2}μeven′​,μodd′​∈Rn/2​，然后将 μ o d d \mu_{odd}μodd​ 旋转 $Y$ 加到 μ e v e n \mu_{even}μeven​ 上，并使用自同构 τ d,d= 2 l+1\tau_{d}, d=2^l+1 τd​,d=2l+1 来消除 μ odd \mu_{odd} μodd​ 那些恰好被旋转到 μ even′\mu_{even}’ μeven′​ 位置上的杂项：
μ=( μ even +Y⋅ μ odd )+ τ d( μ even −Y⋅ μ odd )\mu = (\mu_{even} + Y \cdot \mu_{odd}) + \tau_d(\mu_{even} – Y \cdot \mu_{odd}) μ=(μeven​+Y⋅μodd​)+τd​(μeven​−Y⋅μodd​)
由于 − Y ⋅ μ o d d -Y \cdot \mu_{odd}−Y⋅μodd​ 的有效系数 − μ 2 j + 1 -\mu_{2j+1}−μ2j+1​ 是在 Y 2 j + 1 Y^{2j+1}Y2j+1 上，因此 τd \tau_dτd​ 将它们取反为 μ 2 j + 1 \mu_{2j+1}μ2j+1​ ，而那些被旋转到 Y 2 j Y^{2j}Y2j 的杂项 $-e$ 则保持不变，正好和 Y ⋅ μ o d d Y \cdot \mu_{odd}Y⋅μodd​ 添加到 μ e v e n \mu_{even}μeven​ 上的杂项 $e$ 相互消除。最终，相位 μ ∈ RN \mu \in R_Nμ∈RN​ 的那些 Yj Y^jYj 的系数恰好是 N ⋅ μj N \cdot \mu_jN⋅μj​，只要再消除其他的杂项就可以得到 μ′∈ Rn \mu’ \in R_nμ′∈Rn​，这里可以使用 T r KN/ KnTr_{K_N/K_n}TrKN​/Kn​​ 来消除它们。

具体算法为：

这个算法 Step 2 需要 $n-1$ 次自同构，step 3 需要 $\log (N/n)$ 次自同构，均摊成本为 n + log ⁡ ( N / n ) − 1n \frac{n+\log(N/n)-1}{n}nn+log(N/n)−1​，只要打包的 LWEs 够多 $n=\Omega (\log N)$，均摊成本仅为 $O(1)$（但是打包 n ≥ 210 n \ge 2^{10}n≥210 个 LWEs 的延迟应该挺高了？）

注意到 μj \mu_jμj​ 是打包在系数上的，一般 FHE 可能需要使得消息是打包在明文槽里的，这可以使用 [GHS12] [HS15] [HHC19] 的 Coeff-to-Slot 技术进行转换。[CDKS21] 说这些转换的速度特别快（真的么？秒的量级吧，不算快），因此主要开销还是在 LWEs-to-RLWE 上面。

可以证明 LWEs-to-RLWE 的噪声也是 V a r ≤ 13( N2− 1 ) ⋅ V k s Var \le \frac{1}{3}(N^2-1) \cdot V_{ks}Var≤31​(N2−1)⋅Vks​

Lightweight Communication

三种转换的效率和噪声：

优势：

• 原始的 KS 过程，对于前两个参数，执行时间为 $203$、$1628$ 毫秒，因此嵌入到 RLWE 后的效率提升了 $2$ 个数量级（例如 $1.03$ 毫秒）
• 噪声仅为 $O(\log N)$-bit，因此可以使用 LWE 密文，留出足够的噪声空间， b∈ Z qb \in \mathbb Z_q b∈Zq​ 的大部分空间都可用于存储消息（例如 $389-23$ 比特）

对于云计算场景，我们使用对称版本的 LWE 加密方案，那么多个密文的 aj∈ ZqN a_j \in \mathbb Z_q^Naj​∈ZqN​ 完全可以被替代为随机种子， aj= P R F ( s e e d , j )a_j=PRF(seed,j)aj​=PRF(seed,j)，这导致了 Rate 高达 $1-o(1)$ 的对称加密。在同态运算之前，需要同态解密，因为 LWE-based 是 FHE 友好的（只需要部分的同态解密，不必纠错），直接使用上述的 LWEs-to-RLWE 就可以转化为合适的 FHE 密文（这三种转换都是保护相位的，通用于任意的 FHE 方案）