参考文献：
[LPR10] 给出了 Ring-LWE 的定义，其中的秘密 s ∈ R ∨ s in R^vee s∈R∨ 是取自环 R = O K R=mathcal O_K R=OK 的对偶理想。两个主定理为：
为了实现方便，我们希望移除对偶结构，变换到 s ∈ R s in R s∈R，但是还需要采样出正确格式的噪声，才能让上述归约存在。[DD12] 在扩环上采样球形噪声，然后取模，最后圆整得到整数环 R R R 下的噪声。[CP16] 在典范嵌入下采样球形噪声，然后乘以某个常数，扭曲出整数环 R R R 下的噪声。
任意的数域 K = Q ( ζ ) ≅ Z [ x ] / ( f ) K=mathbb Q(zeta) cong mathbb Z[x]/(f) K=Q(ζ)≅Z[x]/(f)，如果 deg f = n deg f=n degf=n，那么都恰好存在 n n n 个嵌入 σ i : ζ ↦ α i sigma_i: zeta mapsto alpha_i σi:ζ↦αi，其中 α i alpha_i αi 是极小多项式 f f f 在复数域上的所有根。假如有 s 1 s_1 s1 个实根， 2 s 2 2s_2 2s2 个复根（成对共轭），易知 n = s 1 + 2 s 2 n=s_1+2s_2 n=s1+2s2，那么定义它的典范嵌入（canonical embedding）：
σ : K ↦ R s 1 × C 2 s 2 x ↦ ( σ 1 ( x ) , ⋯ , σ n ( x ) ) begin{aligned} sigma: K &mapsto mathbb R^{s_1} times mathbb C^{2s_2}\ x &mapsto (sigma_1(x),cdots,sigma_n(x)) end{aligned} σ:Kx↦Rs1×C2s2↦(σ1(x),⋯,σn(x))
易知 σ sigma σ 是环同态，加法和乘法就是 point-wise 的加/乘。
元素 x ∈ K x in K x∈K 的典范范数，定义为：
∥ x ∥ p c a n : = ∥ σ ( x ) ∥ p = ( ∑ i = 1 n ∣ σ i ( x ) ∣ p ) 1 / p |x|_p^{can} := |sigma(x)|_p = left( sum_{i=1}^{n} |sigma_i(x)|^p right)^{1/p} ∥x∥pcan:=∥σ(x)∥p=(i=1∑n∣σi(x)∣p)1/p
我们定义 C n mathbb C^n Cn 的子空间：
H : = { ( x 1 , ⋯ , x n ) ∈ R s 1 × C 2 s 2 ∣ x s 1 + s 2 + j = x s 1 + j ‾ , ∀ j ∈ [ s 2 ] } H := {(x_1,cdots,x_n) in mathbb R^{s_1} times mathbb C^{2s_2} mid x_{s_1+s_2+j} = overline{x_{s_1+j}}, forall j in [s_2]} H:={(x1,⋯,xn)∈Rs1×C2s2∣xs1+s2+j=xs1+j,∀j∈[s2]}
作为内积空间（inner product space）有同构 H ≅ R n H cong mathbb R^n H≅Rn，单位正交基（列矢 h i h_i hi）表示为矩阵：
T = 1 2 ⋅ ( I s 1 O s 1 O s 1 O s 2 I s 2 i ⋅ I s 2 O s 2 I s 2 − i ⋅ I s 2 ) , H = { h ⋅ a ∣ ∀ a ∈ R n } T = dfrac{1}{sqrt2} cdot left(begin{array}{c|c|c} I_{s_1} & O_{s_1} & O_{s_1}\hline O_{s_2} & I_{s_2} & i cdot I_{s_2}\hline O_{s_2} & I_{s_2} & -i cdot I_{s_2}\ end{array}right),,, H = {h cdot a mid forall a in mathbb R^n} T=2 1⋅ Is1Os2Os2Os1Is2Is2Os1i⋅Is2−i⋅Is2 ,H={h⋅a∣∀a∈Rn}
像空间 σ ( K ) ⊆ H sigma(K) subseteq H σ(K)⊆H 是子集，坐标表示 σ ( x ) = ∑ i a i h i ∈ H sigma(x)=sum_i a_i h_i in H σ(x)=∑iaihi∈H，那么有：
∥ x ∥ p c a n = ( ∑ i = 1 s 1 ∣ a i ∣ p + 2 ∑ i = s 1 + 1 s 1 + s 2 ( a i 2 + a i + s 2 2 2 ) p / 2 ) 1 / p |x|_p^{can} = left( sum_{i=1}^{s_1} |a_i|^p + 2sum_{i=s_1+1}^{s_1+s_2}left( frac{a_i^2+a_{i+s_2}^2}{2} right)^{p/2} right)^{1/p} ∥x∥pcan=(i=1∑s1∣ai∣p+2i=s1+1∑s1+s2(2ai2+ai+s22)p/2)1/p
对于分圆数域 K = Q ( ζ ) K=mathbb Q(zeta) K=Q(ζ)，其中 ζ = ζ m zeta=zeta_m ζ=ζm（抽象的本原单位根）， f = Φ m ( x ) = ∑ i ∈ Z m ∗ ( x − w m i ) f=Phi_m(x)=sum_{i in mathbb Z_m^*}(x-w_m^i) f=Φm(x)=∑i∈Zm∗(x−wmi)，其中的 w m = exp ( 2 π i / m ) ∈ C w_m=exp(2pi i/m) in mathbb C wm=exp(2πi/m)∈C 是复数本原单位根。它的 Galois 群包含全部的自同构，形如 τ k : ζ ↦ ζ k , ∀ k ∈ Z m ∗ tau_k:zeta mapsto zeta^k, forall k in mathbb Z_m^* τk:ζ↦ζk,∀k∈Zm∗，于是
σ i ( τ k ( ζ ) ) = σ i ( ζ k ) = w m i k = σ i k ( ζ ) sigma_i(tau_k(zeta)) = sigma_i(zeta^k) = w_m^{ik} = sigma_{ik}(zeta) σi(τk(ζ))=σi(ζk)=wmik=σik(ζ)
也就是说，自同构 τ k tau_k τk 导致了典范嵌入 σ sigma σ 的各个分量做某个固定置换。
迹 T r K / Q : K → Q Tr_{K/mathbb Q}: K to mathbb Q TrK/Q:K→Q 和范数 N K / Q : K → Q N_{K/mathbb Q}: K to mathbb Q NK/Q:K→Q 定义为嵌入的加和、乘积，
T r ( x ) = ∑ i ∈ [ n ] σ i ( x ) , N ( x ) = ∏ i ∈ [ n ] σ i ( x ) Tr(x)=sum_{i in [n]} sigma_i(x),,, N(x)=prod_{i in [n]} sigma_i(x) Tr(x)=i∈[n]∑σi(x),N(x)=i∈[n]∏σi(x)
可以证明，乘积的迹等于典范嵌入的（复空间）典范内积，
T r ( x ⋅ y ) = ∑ i ∈ [ n ] σ i ( x ) ⋅ σ i ( y ) = ⟨ σ ( x ) , σ ( y ) ‾ ⟩ Tr(x cdot y) = sum_{i in [n]}sigma_i(x) cdot sigma_i(y) = langle sigma(x),overline{sigma(y)}rangle Tr(x⋅y)=i∈[n]∑σi(x)⋅σi(y)=⟨σ(x),σ(y)⟩
因此 T r ( x ⋅ y ) Tr(x cdot y) Tr(x⋅y) 是一个双线性函数。
数域 K ≅ Q n K cong mathbb Q^n K≅Qn，整数环 R = O K R=mathcal O_K R=OK，易知 R R R 是一个秩为 n n n 的自由 Z mathbb Z Z-模，存在整基（integral basis）
B = { b 1 , ⋯ , b n } ⊆ R , R = { ∑ i ∈ [ n ] b i ⋅ x i ∣ x i ∈ Z } B={b_1,cdots,b_n}subseteq R,,, R={sum_{i in [n]} b_icdot x_i mid x_i in mathbb Z} B={b1,⋯,bn}⊆R,R={i∈[n]∑bi⋅xi∣xi∈Z}
整理想 I ⊆ R I subseteq R I⊆R 也是秩为 n n n 的自由 Z mathbb Z Z-模，也存在一组整基 U I = { u 1 , ⋯ , u n } ∈ R U_I={u_1,cdots,u_n} in R UI={u1,⋯,un}∈R，理想的范数定义为它作为子加群的指标 N ( I ) : = ∣ R / I ∣ N(I):=|R/I| N(I):=∣R/I∣，理想的乘积满足 N ( I J ) = N ( I ) N ( J ) N(IJ)=N(I)N(J) N(IJ)=N(I)N(J)，主理想的范数 N ( ⟨ x ⟩ ) = ∣ N ( x ) ∣ N(langle xrangle)=|N(x)| N(⟨x⟩)=∣N(x)∣，并且 ∣ N ( x ) ∣ ≥ N ( I ) , ∀ x ∈ I |N(x)| ge N(I),forall x in I ∣N(x)∣≥N(I),∀x∈I
分式理想 I ⊆ K I subseteq K I⊆K，存在某个 d ∈ R d in R d∈R 使得 d I ⊆ R dI subseteq R dI⊆R 成为整理想，即 I = 1 d R I=frac{1}{d}R I=d1R，范数为 N ( I ) = N ( d I ) / ∣ N ( d ) ∣ N(I)=N(dI)/|N(d)| N(I)=N(dI)/∣N(d)∣。全部的分式理想，在理想的乘积下构成了群，并且 norm 是一个群同态。整理想是 d = 1 d=1 d=1 的特殊分式理想。
分式理想 I I I 的典范嵌入 σ ( I ) ⊆ H sigma(I) subseteq H σ(I)⊆H，具有一组整基 σ ( U ) = { σ ( u 1 ) , ⋯ , σ ( u n ) } ⊆ H sigma(U)={sigma(u_1),cdots,sigma(u_n)} subseteq H σ(U)={σ(u1),⋯,σ(un)}⊆H，因此我们将 fractional ideal 视为 H ≅ R n H cong mathbb R^n H≅Rn 中的 lattice（离散线性空间）
由于 B B B 既是整数环 R R R 的 Z mathbb Z Z-基，同时也是数域 K K K 的 Q mathbb Q Q-基，因此 x ∈ R , K x in R,K x∈R,K 都可以表示为坐标形式 ∑ i b i ⋅ x i , ∀ x i ∈ Z , Q sum_i b_i cdot x_i, forall x_i in mathbb Z,mathbb Q ∑ibi⋅xi,∀xi∈Z,Q，那么有
x ⋅ y = ∑ i , j ∈ [ n ] ( x i ⋅ b i ) ( y j ⋅ b j ) x cdot y = sum_{i,j in [n]} (x_icdot b_i)(y_j cdot b_j) x⋅y=i,j∈[n]∑(xi⋅bi)(yj⋅bj)
于是只要预计算 b i b j , ∀ i , j ∈ [ n ] b_ib_j,forall i,j in [n] bibj,∀i,j∈[n]，则环元素乘法就可以被线性化。同样的，整理想 I ⊆ R I subseteq R I⊆R 中的元素可以用基底 U I U_I UI 描述，而分式理想 J = 1 d I ⊆ K J =frac{1}{d}I subseteq K J=d1I⊆K 中的元素可以用基底 U I U_I UI 以及额外的 d ∈ R din R d∈R 来描述。分式理想的范数、逆、对偶、积、采样，都可以有效计算。
数域 K ≅ Q n K cong mathbb Q^n K≅Qn，任取一组 Q mathbb Q Q-基 B B B，它的 Z mathbb Z Z-span 构成了一个格 L L L，对偶格定义为：
L ∨ : = { x ∈ K ∣ T r ( x L ) ⊆ Z } L^vee := { x in K mid Tr(xL) subseteq mathbb Z } L∨:={x∈K∣Tr(xL)⊆Z}
也就是说，那些将格 L L L 映射到 Z mathbb Z Z 子集的全部线性态射 x x x 组成了对偶格。根据 T r Tr Tr 和 σ i sigma_i σi 的关系，也可以写成：
L ∨ : = { x ∈ K ∣ ⟨ σ ( x ) , σ ( L ) ‾ ⟩ = 0 ( m o d 1 ) } L^vee := { x in K mid langlesigma(x), overline{sigma(L)}rangle =0 pmod1 } L∨:={x∈K∣⟨σ(x),σ(L)⟩=0(mod1)}
对于平凡的数域 K = Q K=mathbb Q K=Q，整数环 R = Z R=mathbb Z R=Z，因此 R ∨ = R = Z R^vee=R=mathbb Z R∨=R=Z 是自对偶的（self-dual），并且理想 I = d Z I=dmathbb Z I=dZ 和它的形式逆 I − 1 = 1 d Z I^{-1}=frac{1}{d}mathbb Z I−1=d1Z 是相互对偶。
对于非凡的数域 K K K 和分式理想 I ⊆ K I subseteq K I⊆K，并没有上述的两条性质，但是依然有：
I ∨ = I − 1 ⋅ R ∨ I^vee = I^{-1} cdot R^vee I∨=I−1⋅R∨
即两者只相差一个因子 R ∨ R^vee R∨，它被称为 codifferent。它的逆 ( R ∨ ) − 1 (R^vee)^{-1} (R∨)−1 被称为 different ideal。对于二的幂分圆域 n = ϕ ( m ) = m / 2 n=phi(m)=m/2 n=ϕ(m)=m/2，有 R ∨ = n − 1 R R^{vee}=n^{-1}R R∨=n−1R，它仅仅为 R R R 的缩放，因此可以直接选取 s ∈ R s in R s∈R，噪声 e e e 简单地是 R R R 上的球形高斯。根据 [Con09]，分圆环 Z [ ζ m ] mathbb Z[zeta_m] Z[ζm] 的对偶，可以写成如下的主分式理想：
Z [ ζ m ] ∨ = 1 Φ m ′ ( ζ m ) Z [ ζ m ] mathbb Z[zeta_m]^vee = dfrac{1}{Phi_m'(zeta_m)}mathbb Z[zeta_m] Z[ζm]∨=Φm′(ζm)1Z[ζm]
其中的 Φ m ′ ( x ) Phi_m'(x) Φm′(x) 是形式导数。也可以选取其他的生成元，也许会更加高效。
利用 CRT，[LPR10] 给出了以下的引理：
存在并且可以快速找出 t ∈ I ⊆ R t in I subseteq R t∈I⊆R，使得函数 θ t : u ∈ K ↦ t ⋅ u ∈ K theta_t: u in K mapsto t cdot u in K θt:u∈K↦t⋅u∈K 诱导了同构映射 θ t : w ( m o d J M ) ↦ t ⋅ w ( m o d I J M ) theta_t: w pmod{JM} mapsto t cdot w pmod{IJM} θt:w(modJM)↦t⋅w(modIJM)，它将被用于 non-dual form 的噪声生成过程。
代数（algebra over a field）：域 K K K 上的代数 A A A 是一个向量空间 K n K^n Kn，运算包括向量加法 + : A × A → A +:A times A to A +:A×A→A、标量乘法 ⋅ : K × A → A cdot:K times A to A ⋅:K×A→A，以及一个双线性乘法 ⟨ ⋅ , ⋅ ⟩ : A × A → A langlecdot,cdotrangle:A times A to A ⟨⋅,⋅⟩:A×A→A，我们把 A A A 叫做 K K K-代数，而 K K K 被称为 A A A 的基域（base field）
域的张量积（field tensor product）：记作 K 1 ⊗ L K 2 K_1 otimes_L K_2 K1⊗LK2，两个域 K 1 , K 2 K_1,K_2 K1,K2 有公共子域 L L L，它们作为 L L L-代数（两个向量空间）做张量积。对于没有显式指定的子域，默认 L L L 是素域，这要求 K 1 , K 2 K_1,K_2 K1,K2 有相同的特征。
数域 K ≅ Q n K cong mathbb Q^n K≅Qn，我们定义域张量积
K R : = K ⊗ Q R K_mathbb R := K otimes_mathbb Q mathbb R KR:=K⊗QR
作为 Q mathbb Q Q-代数有同构 K R ≅ R n ≅ H K_mathbb R cong mathbb R^n cong H KR≅Rn≅H，它的同构映射就是嵌入 σ sigma σ，其中的双线性乘法就是 point-wise 乘法。我们在数域 K R K_mathbb R KR 上定义高维椭圆高斯分布 D r ⃗ , r ⃗ ∈ ( R + ) n D_{vec r},vec r in (mathbb R^+)^n Dr ,r ∈(R+)n，对于元素 x ∈ K R x in K_mathbb R x∈KR，扭曲的分布为 x ⋅ D r ⃗ = D r ⃗ ′ x cdot D_{vec r} = D_{vec r'} x⋅Dr =Dr ′，其中 r i ′ = r i ⋅ ∣ σ i ( x ) ∣ r_i' = r_i cdot |sigma_i(x)| ri′=ri⋅∣σi(x)∣，这是根据 H H H 中双线性乘法得出的。
我们定义 “一族有界的椭圆高斯分布” 的随机分布 Υ α Upsilon_alpha Υα，
在 RLWE 的定义中，需要模掉对偶格 R ∨ R^vee R∨，因此需要让 α alpha α 不超过它的平滑参数，使得 RLWE 分布并非统计接近均匀分布，从而不是平凡的问题。
一些符号：任意数域 K K K，它的整数环 R R R，模数 q q q，分式理想（ K K K 的 R R R-子模，子加群） J ⊆ K J subseteq K J⊆K 的商群 J q : = J / q J J_q:=J/qJ Jq:=J/qJ， 对偶分式理想 R ∨ R^vee R∨（视为对偶格），环面 T : = K R / R ∨ mathbb T:=K_mathbb R/R^vee T:=KR/R∨
[LPR10] 给出的 Ring-LWE 分布是 “dual form”，秘密 s ∈ R q ∨ s in R_q^vee s∈Rq∨ 取自对偶格：
由于 s ∈ R q ∨ s in R_q^vee s∈Rq∨ 属于分式理想，因此吸收 a ⋅ s ∈ R ∨ / q R ∨ a cdot s in R^vee/qR^vee a⋅s∈R∨/qR∨，得到 a ⋅ s / q ∈ 1 q R ∨ / R ∨ a cdot s/q in frac{1}{q}R^vee/R^vee a⋅s/q∈q1R∨/R∨，然而噪声 e ∈ K R e in K_mathbb R e∈KR，需要将它模掉 R ∨ R^vee R∨ 进入 T mathbb T T
S-RLWE 和 D-RLWE 的定义为：
对于 m = 2 k m=2^k m=2k 的分圆域， R ∨ = n − 1 R R^vee=n^{-1}R R∨=n−1R 仅仅是缩放，于是上述的 RLWE 分布可以做变换 s ′ = n ⋅ s ∈ R q s'=ncdot s in R_q s′=n⋅s∈Rq 和 e ′ = n ⋅ e e'=n cdot e e′=n⋅e，转换为样本 ( a , b ′ = a ⋅ s ′ / q + e ′ ) ∈ R q × K R / R (a,b'=acdot s'/q+e') in R_q times K_mathbb R/R (a,b′=a⋅s′/q+e′)∈Rq×KR/R，这就是我们常用的形式了。
Right Defifinition of Ring-LWE：[LPR10] 解释了为何秘密需要从对偶分式理想中选取，
[LPR10] 证明了 RLWE 可以归约到 Ideal Lattice 上的 SVP、SIVP、BDD 问题。
主定理：存在从 worst-case approx-SIVP 到 average-case D-RLWE 的量子归约。对于有界数量样本（数量 l l l 较小），随机的椭圆高斯可以替换为固定的球形高斯，分布 D ξ D_xi Dξ 接近于从 Υ α Upsilon_alpha Υα 采样出的 ψ psi ψ 分布。
注意，在归约过程中，[LPR10] 用到了模数 q q q 在 K K K 上完全分裂为 n n n 个素理想的技术，因此要求 q ≡ 1 ( m o d m ) qequiv 1pmod{m} q≡1(modm)。不过通过模切换技术 [Muk16]，任意的模数 q q q 都可以保持 RLWE 实例的伪随机性。不过一般人们需要使用 FFT/NTT 加速，它的条件依旧是 q ≡ 1 ( m o d m ) qequiv 1pmod{m} q≡1(modm)（或者条件更弱一些，Incomplete NTT、PtNTT）。
[Pei16] 研究了一些不安全的 RLWE 实例，发现它们的根本原因都是噪声分布的不充分传播。[Pei16] 给出的建议是，困难实例的 D r D_r Dr 的参数选取为 r ≥ 2 r ge 2 r≥2，这使得若干攻击失效。此外，文章还介绍了对偶版本和非对偶版本的等价性。
dual form of RLWE：秘密 s ∈ R q ∨ s in R_q^vee s∈Rq∨ 是均匀采样的，噪声分布 ψ psi ψ 是（近似）球形的，样本形如
( a i , b i : = s ⋅ a i + e i ( m o d q R ∨ ) ) ∈ R q × K R / q R ∨ (a_i, b_i := s cdot a_i + e_i pmod{qR^vee}) in R_q times K_mathbb R/qR^vee (ai,bi:=s⋅ai+ei(modqR∨))∈Rq×KR/qR∨
non-dual form of RLWE：秘密 s ∈ R q s in R_q s∈Rq 是均匀采样的，噪声分布 ψ psi ψ 需要被正确地设置（可能是长扁的椭球），样本形如
( a i , b i : = s ⋅ a i + e i ( m o d q R ) ) ∈ R q × K R / q R (a_i, b_i := s cdot a_i + e_i pmod{qR}) in R_q times K_mathbb R/qR (ai,bi:=s⋅ai+ei(modqR))∈Rq×KR/qR
两者通过一个恰当的扭曲因子（tweak factor）等价，这在 [AP13] 和 [Pei14] 中最早出现。根据 [LPR10]，对于任意的分式理想 I , J I,J I,J，都存在常数 t ∈ K t in K t∈K，使得两个函数
θ t : u ∈ I q ↦ t ⋅ u ∈ J q κ t : u ∈ K R / q I ↦ t ⋅ u ∈ K R / q J begin{array}{clcl} theta_t:& u in I_q &mapsto& t cdot u in J_q\ kappa_t:& u in K_mathbb R/qI &mapsto& t cdot u in K_mathbb R/qJ end{array} θt:κt:u∈Iqu∈KR/qI↦↦t⋅u∈Jqt⋅u∈KR/qJ
都是高效可逆的双射。设置 I = R ∨ I=R^vee I=R∨ 和 J = R J=R J=R，假如分式理想 R ∨ R^vee R∨ 是主的 I = R x , ∃ x ∈ K I=Rx,exists x in K I=Rx,∃x∈K，可以简单选取 t = x − 1 ∈ K t=x^{-1} in K t=x−1∈K，就有 t R ∨ = R tR^vee=R tR∨=R。即使不是主的， t t t 也总存在，但是找出它更加繁琐些，用到 CRT 和素理想分解。
对于分圆环，[LPR13] 给出了 t t t 的构造：对于 m m m 次分圆环 R R R，定义元素
g m : = ∏ odd prime p ∣ m ( 1 − ζ p ) ∈ R g_m := prod_{text{odd prime }p|m} (1-zeta_p) in R gm:=odd prime p∣m∏(1−ζp)∈R
再定义整数
m ^ : = { m / 2 , m is even m , m is odd hat m := left{begin{aligned} m/2,&& mtext{ is even}\ m,&& mtext{ is odd}\ end{aligned}right. m^:={m/2,m,m is evenm is odd
那么总是有 t m : = m ^ / g m ∈ R t_m := hat m/g_m in R tm:=m^/gm∈R，并且 R ∨ = ⟨ t m − 1 ⟩ R^vee = langle t_m^{-1} rangle R∨=⟨tm−1⟩ 是主的，因此 t m ⋅ R ∨ = R t_m cdot R^vee = R tm⋅R∨=R，这便得到了扭曲因子。
[Pei14] 使用了分布 ψ : = t m ⋅ D r psi := t_m cdot D_r ψ:=tm⋅Dr 在 R R R 上的离散化 χ : = ⌊ χ ⌉ chi := lfloor chi rceil χ:=⌊χ⌉ 作为噪声分布。我们考虑 D r D_r Dr 下的 dual form 样本 ( a , b : = s ⋅ a + e ) ∈ R q × K R / q R ∨ (a,b:=scdot a+e) in R_q times K_mathbb R/qR^vee (a,b:=s⋅a+e)∈Rq×KR/qR∨，将第二分量乘以 t m t_m tm，得到
b ′ = κ t ( b ) = t m ⋅ ( s ⋅ a + e ) = s ′ ⋅ a + e ′ ∈ K R / q R b' = kappa_{t}(b) = t_m cdot (s cdot a + e) = s' cdot a + e' in K_mathbb R/qR b′=κt(b)=tm⋅(s⋅a+e)=s′⋅a+e′∈KR/qR
其中 s ′ = t m ⋅ s = θ t ( s ) ∈ R q s'=t_m cdot s=theta_t(s) in R_q s′=tm⋅s=θt(s)∈Rq 是 non-dual 的秘密，噪声 e ′ = t m ⋅ e ∈ K R e'=t_m cdot e in K_mathbb R e′=tm⋅e∈KR 的分布为 t m ⋅ D r = ψ t_m cdot D_r = psi tm⋅Dr=ψ
于是两者是等价的： dual D-RLWE q , D r ⟺ non-dual D-RLWE q , ψ text{dual D-RLWE}_{q,D_r} iff text{non-dual D-RLWE}_{q,psi} dual D-RLWEq,Dr⟺non-dual D-RLWEq,ψ，dual 使用的是球形高斯噪声，而 non-dual 使用的是椭球形高斯噪声（在典范嵌入下）。
[Pei16] 认为 RLWE 可以视为特殊的 LWE：考虑 non-dual form RLWE 样本 ( a , b = s a + e ) ∈ R q × K R / q R (a,b=sa+e) in R_q times K_mathbb R/qR (a,b=sa+e)∈Rq×KR/qR，由于 R R R 的一组 Z mathbb Z Z-基 B B B 也是 K R K_mathbb R KR 的一组 R mathbb R R-基，从而可将私钥写成 s ⃗ ∈ Z q n vec s in mathbb Z_q^n s ∈Zqn 使得 s = ∑ s i b i s=sum s_i b_i s=∑sibi，可将 a a a 扩写矩阵 A ∈ Z q n × n A in mathbb Z_q^{n times n} A∈Zqn×n 使得 s ⋅ a = s ⃗ t A s cdot a=vec s^t A s⋅a=s tA，第 i i i 行是 A i = ∑ j a j b i b j A_i=sum_j a_jb_ib_j Ai=∑jajbibj，噪声写成 e ⃗ ∈ R n vec e in mathbb R^n e ∈Rn 使得 e = ∑ e i b i e=sum e_i b_i e=∑eibi，那么 ( A i , s ⃗ t A i + e i ) ∈ Z q n × R / q Z (A_i, vec s^tA_i+e_i) in mathbb Z_q^n times mathbb R/qmathbb Z (Ai,s tAi+ei)∈Zqn×R/qZ 就是 n n n 个标准 LWE 样本。虽然它们之间不独立，单个 RLWE 样本总是可以转换出一个 LWE 样本，因此有归约 RLWE ≤ LWE text{RLWE} le text{LWE} RLWE≤LWE
对于二的幂的分圆域， m ^ = n , g m = 1 , t m = n ∈ Q hat m=n, g_m=1, t_m=n in mathbb Q m^=n,gm=1,tm=n∈Q，因此 ψ = n ⋅ D r psi=n cdot D_r ψ=n⋅Dr 依旧是球形的，我们可以直接对 K R K_mathbb R KR 的各个分量（在 power basis 下的）分别独立采样。
但是对于一般的分圆域，元素 t m ∈ R t_m in R tm∈R 并不属于 Q mathbb Q Q，这就导致了 ψ = t m ⋅ D r psi = t_m cdot D_r ψ=tm⋅Dr 是倾斜的，直接对各个分量 i.i.d 采样，这显然是不对的。
由于 [LPR10] 的归约是针对于 “分圆环对偶理想” 和 “噪声分布的典范嵌入是近似球形高斯” 来说的，因此想要移除对偶结构，需要乘以元素 t m ∈ R t_m in R tm∈R，确切地：
[DD12] 给出了一种更简单的转换方案：
对于分圆域 K = Q ( ζ m ) ≅ Q [ x ] / ( Φ m ) K=mathbb Q(zeta_m) cong mathbb Q[x]/(Phi_m) K=Q(ζm)≅Q[x]/(Φm)，令 n = ϕ ( m ) n=phi(m) n=ϕ(m)，矩阵
T = 1 2 ⋅ ( I n / 2 i ⋅ I n / 2 I n / 2 − i ⋅ I n / 2 ) T = dfrac{1}{sqrt2} cdot left(begin{array}{c|c} I_{n/2} & i cdot I_{n/2}\hline I_{n/2} & -i cdot I_{n/2}\ end{array}right) T=2 1⋅(In/2In/2i⋅In/2−i⋅In/2)
那么 2 ⋅ T sqrt2cdot T 2 ⋅T 是 embedding space H : = σ ( K ) ⊆ C n H:=sigma(K) subseteq mathbb C^n H:=σ(K)⊆Cn 的一组 Q mathbb Q Q-基，即 H ≅ Q n H cong mathbb Q^n H≅Qn 的同构映射为 v ⃗ ↦ 2 ⋅ T ⋅ v ⃗ vec v mapsto sqrt2cdot Tcdotvec v v ↦2 ⋅T⋅v 。为了生成球形高斯分布，可以 i.i.d 采样各个坐标 v i ∈ Q v_i in mathbb Q vi∈Q，然后计算出 H H H 中元素，最后回到 K K K 中。
根据 [Con09]， Z [ ζ m ] ∨ = 1 Φ m ′ ( ζ m ) Z [ ζ m ] mathbb Z[zeta_m]^vee = frac{1}{Phi_m'(zeta_m)}mathbb Z[zeta_m] Z[ζm]∨=Φm′(ζm)1Z[ζm]，采用 [LPR13] 定义的 m ^ hat m m^，[DD12] 证明了 m ^ Φ m ′ ( ζ m ) ∈ Z [ ζ ] frac{hat m}{Phi_m'(zeta_m)} in mathbb Z[zeta] Φm′(ζm)m^∈Z[ζ]，总是有 R ≅ Z [ ζ m ] ⊇ m R ∨ Rcong mathbb Z[zeta_m] supseteq mR^vee R≅Z[ζm]⊇mR∨，也就是 m ^ R ∨ hat mR^vee m^R∨ 是 R R R 的一个加法子群。
因此，我们可以将 R ∨ R^vee R∨ 映射到 R R R 中，
现在我们考虑如何高效采样噪声。一种自然方法是在 H H H 上采样，然后计算逆范德蒙矩阵 σ − 1 sigma^{-1} σ−1。对于二的幂情况， σ sigma σ 是正交阵（FFT），求逆速度很快；但是对于一般的 m m m，这个操作十分低效。
我们定义：
Θ m ( x ) = { x m / 2 + 1 , m is even x m − 1 , m is odd Theta_m(x) = left{begin{aligned} x^{m/2}+1,&& mtext{ is even}\ x^{m}-1,&& mtext{ is odd}\ end{aligned}right. Θm(x)={xm/2+1,xm−1,m is evenm is odd
易知 Φ m ( x ) ∣ Θ m ( x ) Phi_m(x) mid Theta_m(x) Φm(x)∣Θm(x)，[DD12] 在扩环 Q [ x ] / ( Θ m ) mathbb Q[x]/(Theta_m) Q[x]/(Θm) 上快速采样，并且证明了它确实是一个球形高斯，满足 [LPR10] 的归约条件。
因为对于许多大类 m m m，取模运算 ( m o d Φ m ( x ) ) pmod{Phi_m(x)} (modΦm(x)) 存在 power basis 下的稀疏矩阵表示，计算速度较快。比如对于 m = 2 k p i , k ≥ 0 , i ≥ 1 m=2^kp^i, kge 0,ige1 m=2kpi,k≥0,i≥1，就有：
并且 ∥ B ∥ 1 = 2 |B|_1 = 2 ∥B∥1=2（按行矢），因此有 ∥ β ( f ) ∥ ∞ ≤ 2 ∥ f ∥ ∞ |beta(f)|_infty le 2|f|_infty ∥β(f)∥∞≤2∥f∥∞，取模后的范数增长也不算大。
[GHS11] 也采用了类似的 Θ m ( x ) Theta_m(x) Θm(x) 以及 G m ( x ) G_m(x) Gm(x)，但是被用于加速解密的计算，延迟模约简。[DD12] 在加密阶段使用，lift-then-map，生成正确噪声分布。
[DD12] 给出了 LPR10 主定理的变体：
实际采样时，我们简单使用 s = m ′ α q ≥ w ( m ′ log m ) s=sqrt{m'}alpha q ge w(sqrt{m'log m}) s=m′ αq≥w(m′logm )，忽略后面的复杂因子。根据 Arora-Ge 算法，如果标准差为 o ( ϕ ( m ) ) o(sqrt{phi(m)}) o(ϕ(m) )，那么可以在压指数时间求解 SVP 问题，从而上述 s s s 的选取是紧的。
[CP16] 设计了一个算法工具包 “ Λ ∘ λ Lambda circ lambda Λ∘λ”（奇奇怪怪的名字），它是格密码的通用框架（PQC、FHE），支持任意分圆环上的快速噪声采样。
它的采样算法就是 [Pei14] 的扭曲思路，先采样球形高斯噪声 e ′ e' e′，然后乘以 t m t_m tm 并圆整，获得 e = ⌊ e ′ ⋅ t m ⌉ ∈ R e=lfloor e' cdot t_m rceil in R e=⌊e′⋅tm⌉∈R。不过，存在更加高效的算法来计算它：利用 [LPR13] 的 decoding basis 和相关算法，可高效地采样 R ∨ R^vee R∨ 球形高斯分布；我们将它们扭曲到 R R R 上，依然保持性能。
本文发布于:2024-01-30 13:26:37，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170659239820329.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
