Conversion Between (R)LWE
参考文献:
- [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.
- [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.
- [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.
- [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.
文章目录
[MS18] 为了实现均摊 FHEW 自举,提出了 Ring packing 技术:将多个 LWE 密文(行矢)堆叠为
(
A
,
b
)
(A,b)
(A,b),然后按列转化为多项式
a
j
(
x
)
,
b
(
x
)
a_j(x), b(x)
aj(x),b(x),使用 Key-Switch 执行同态线性解密
A
⋅
E
(
s
)
+
b
Acdot E(s)+b
A⋅E(s)+b(私钥被加密在多项式的常数项),最终获得打包了
μ
(
x
)
=
∑
j
μ
j
x
j
mu(x)=sum_j mu_jx^j
μ(x)=∑jμjxj 的单个 RLWE 密文。虽然它是 Coeff Packing 的,但是 [MS18] 中的同态 InvDFT 的目标是加速同态的多项式乘法(线性解密部分),而非 SIMD 打包并行。但是其中的 SwK 是对于 LWE 私钥的各个分量分别用 RLWE 加密的
R
L
W
E
s
′
(
s
i
⋅
g
j
)
RLWE_{s'}(s_i cdot g_j)
RLWEs′(si⋅gj),规模大、速度慢。计算过程中不需要用到同态旋转(主要的开销是秘钥切换),仅仅是对于
E
(
s
)
E(s)
E(s) 的同态线性运算。
[BGGJ20] 提出的 Chimera 也使用类似的堆叠技术,将 TLWE 打包转换到 RLWE 密文上。不过它将堆叠出的矩阵
C
=
(
A
,
b
)
C=(A,b)
C=(A,b) 直接乘以 InvDFT,于是
(
I
n
v
D
F
T
⋅
C
)
⋅
s
=
I
n
v
D
F
T
(
μ
(
x
)
)
(InvDFT cdot C) cdot s=InvDFT(mu(x))
(InvDFT⋅C)⋅s=InvDFT(μ(x)),这就将各个
μ
j
mu_j
μj 编码到了明文槽。它的 SwK 也是各个私钥分量分别被加密在系数上
R
G
S
W
s
′
(
s
i
)
RGSW_{s'}(s_i)
RGSWs′(si),规模很大(GB 级别)
[CDKS21] 提出了新的 LWE 的 Key-Switch 技术(后文简记 KS),将 LWE 密文嵌入到 RLWE 密文上,对应的 SwK 将LWE 私钥作为单个多项式做 RLWE 加密
R
L
W
E
s
′
(
s
(
x
)
⋅
g
j
)
RLWE_{s'}(s(x) cdot g_j)
RLWEs′(s(x)⋅gj),从而极大的提高了 KS 的速度(两个数量级)。需要使用分圆域的自同构的某些特殊性质,消除一些杂项。推广这个 KS 过程,可以获得 LWE 打包到 RLWE 的过程,不过它也是 Coeff Packing 的(还应该使用 Coeff-to-Slot 过程将它们编码到明文槽)。令
N
N
N 是 RLWE 的维度,打包
n
=
N
n=N
n=N 个 LWE 密文,复杂度为
O
(
N
)
O(N)
O(N) 次同态自同构,
O
(
N
)
O(N)
O(N) 次同态数乘。
之后的 Pegasus 也使用密文堆叠技术,对于私钥
s
s
s 的密文做线性变换,来实现 LWE-to-RLWE 过程。同态线性变换过程中,采取对角线乘法(旋转+阿达玛),LWE 私钥作为一个整体被加密在明文槽上
R
L
W
E
s
′
(
E
c
d
(
s
,
Δ
)
)
RLWE_{s'}(Ecd(s,Delta))
RLWEs′(Ecd(s,Δ)),规模大大减小(MB 级别),同态解密的结果直接在明文槽上。令
N
N
N 是 RLWE 的维度,打包
n
=
N
n=N
n=N 个 LWE 密文,复杂度为
O
(
N
)
O(sqrt{N})
O(N
) 次同态旋转(由若干个自同构组成,完全分裂的二的幂分圆环只需要一个),
O
(
N
)
O(N)
O(N) 次同态数乘。
Conversion Between RLWE
Tower of Cyclotomic
令
m
=
2
L
+
1
m=2^{L+1}
m=2L+1 是二的幂,
N
=
ϕ
(
m
)
=
2
L
N=phi(m)=2^L
N=ϕ(m)=2L 也是二的幂,分圆域
K
=
Q
(
ζ
m
)
≅
Q
[
X
]
/
(
X
N
+
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
]
/
(
X
N
+
1
)
R=mathbb Z[zeta_m] cong mathbb Z[X]/(X^N+1)
R=Z[ζm]≅Z[X]/(XN+1),为了区分不同维度我们记为
K
N
,
R
N
K_N,R_N
KN,RN
根据代数理论,域扩张
K
/
Q
K/mathbb Q
K/Q 都是 Galois 扩张,Galois 群
G
a
l
(
K
/
Q
)
≅
Z
m
∗
=
{
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 dinmathbb Z_m^*
τd:ζm→ζmd,∀d∈Zm∗
域的迹:
T
r
K
/
Q
:
a
∈
K
↦
∑
τ
∈
G
a
l
(
K
/
Q
)
τ
(
a
)
∈
Q
Tr_{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 是
Q
mathbb Q
Q-线性映射,并且满足
-
T
r
K
/
Q
(
1
)
=
[
K
:
Q
]
=
N
Tr_{K/mathbb Q}(1)=[K:mathbb Q]=N
-
T
r
K
/
Q
(
X
i
)
=
0
,
∀
i
≠
0
Tr_{K/mathbb Q}(X^i)=0, forall i neq 0
对于分圆塔:
K
=
K
N
≥
K
N
/
2
≥
⋯
≥
K
1
=
Q
K=K_N ge K_{N/2} ge cdots ge K_1=mathbb Q
K=KN≥KN/2≥⋯≥K1=Q
其中
K
n
,
n
=
2
l
K_n,n=2^l
Kn,n=2l 可以作为
K
N
K_N
KN 的子域(
R
n
≤
R
N
R_n le R_N
Rn≤RN 类似),设置
Y
=
X
N
/
n
Y=X^{N/n}
Y=XN/n,
K
n
=
{
∑
i
∈
[
n
]
a
i
Y
i
:
a
i
∈
Q
}
⊆
K
N
K_n = left{sum_{i in [n]} a_i Y^i: a_i in mathbb Qright} subseteq K_N
Kn=⎩
⎨
⎧i∈[n]∑aiYi:ai∈Q⎭
⎬
⎫⊆KN
基于分圆塔,可以将迹分解:
T
r
K
/
Q
=
T
r
K
2
/
K
1
∘
⋯
∘
T
K
N
/
K
N
/
2
Tr_{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
2
2,仅包含一个非凡自同构(另一个是恒等映射):
G
a
l
(
K
2
l
/
K
2
l
−
1
)
=
{
τ
1
∣
K
2
l
,
τ
2
l
+
1
∣
K
2
l
}
,
1
≤
l
≤
L
Gal(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
其中的
τ
2
l
+
1
∣
K
2
l
tau_{2^l+1}|_{K_{2^l}}
τ2l+1∣K2l 是自同构映射
τ
2
l
+
1
∈
G
a
l
(
K
/
Q
)
tau_{2^l+1} in Gal(K/mathbb Q)
τ2l+1∈Gal(K/Q) 限制在
K
2
l
⊆
K
N
K_{2^l} subseteq K_N
K2l⊆KN 上,容易验证它是
K
2
l
K_{2^l}
K2l 的
K
2
l
−
1
K_{2^{l-1}}
K2l−1-自同构。进一步的,简记
n
=
2
l
n=2^l
n=2l,
Y
=
X
N
/
n
Y=X^{N/n}
Y=XN/n 是
K
n
/
Q
K_n/mathbb Q
Kn/Q 的扩张元,那么有:
T
r
K
n
/
K
n
/
2
(
Y
i
)
=
{
2
Y
i
,
∀
2
∣
i
0
,
∀
2
∤
i
Tr_{K_{n}/K_{n/2}}(Y^i) = left{begin{aligned} 2Y^i, &&forall 2mid i\ 0, &&forall 2nmid i\ end{aligned}right.
TrKn/Kn/2(Yi)={2Yi,0,∀2∣i∀2∤i
因此,映射
μ
∈
K
n
↦
T
r
K
n
/
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
∥
b
a|b
a∥b 表示 “恰好整除”,
- 将系数
μ
[
i
]
,
(
2
N
/
n
)
∥
i
mu[i], (2N/n)|i
- 将系数
μ
[
i
]
,
(
N
/
n
)
∥
i
mu[i], (N/n)|i
- 元素
μ
∈
K
n
⊆
K
N
mu in K_n subseteq K_N
我们定义
[
N
]
=
{
0
,
1
,
⋯
,
N
−
1
}
[N]={0,1,cdots,N-1}
[N]={0,1,⋯,N−1} 的一组划分(子域的系数索引),
I
k
:
=
{
i
∈
[
N
]
:
2
k
∥
i
}
,
0
≤
k
<
L
I_k := { i in [N]: 2^k|i },,, 0 le k< L
Ik:={i∈[N]:2k∥i},0≤k<L
特别地设置
I
L
=
{
0
}
I_L={0}
IL={0},容易验证
[
N
]
=
⋃
k
I
k
[N] = bigcup_k I_k
[N]=⋃kIk
对于
d
=
2
l
+
1
,
1
≤
l
≤
L
d=2^l+1, 1le l le L
d=2l+1,1≤l≤L,简记
i
=
2
k
j
∈
I
k
i=2^kj in I_k
i=2kj∈Ik,其中
j
j
j 是奇数,
i
⋅
d
=
2
k
+
l
j
+
2
k
j
=
{
2
k
(
2
l
j
+
j
)
∈
I
k
∀
0
≤
k
≤
L
2
k
j
=
i
(
m
o
d
2
N
)
,
∀
k
>
L
−
l
2
L
+
2
k
j
=
N
+
i
(
m
o
d
2
N
)
,
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)∈Ik2kj=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^{icdot d}
τd:ζi→ζi⋅d 是对各个索引
I
k
I_k
Ik 做了符号置换(signed permutation),
∀
i
∈
I
k
,
∃
r
∈
I
k
,
τ
d
(
X
i
)
=
±
X
r
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
≥
L
−
l
k ge L-l
k≥L−l 的那些
I
k
I_k
Ik,
τ
d
(
X
i
)
=
{
X
i
,
∀
i
∈
⋃
k
>
L
−
l
I
k
−
X
i
,
∀
i
∈
I
L
−
l
.
.
.
o
t
h
e
r
w
i
s
e
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−lotherwise
因此,映射
μ
∈
K
N
↦
μ
+
τ
d
(
μ
)
∈
K
N
mu in K_N mapsto mu+tau_d(mu) in K_N
μ∈KN↦μ+τd(μ)∈KN,
- 将系数
μ
[
i
]
,
2
L
−
l
+
1
∣
i
mu[i],2^{L-l+1}|i
- 将系数
μ
[
i
]
,
i
∈
I
L
−
l
mu[i], i in I_{L-l}
- 其他系数的变化较为复杂
LWE-to-LWE
LWE 密文
(
b
,
a
)
∈
Z
q
1
+
N
(b,a) in mathbb Z_q^{1+N}
(b,a)∈Zq1+N,私钥
s
∈
Z
N
s in mathbb Z^N
s∈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
′
(
s
i
)
}
K={LWE_{s'}(s_i)}
K={LWEs′(si)},然后同态解密获得
L
W
E
s
′
(
μ
0
)
LWE_{s'}(mu_0)
LWEs′(μ0),但是这么做的复杂度太高了。[CDKS21] 提出了一种新的 KS 过程:
- 将
a
a
a
(
x
)
=
ι
(
a
)
∈
R
N
,
q
a(x) = iota(a) in R_{N,q}
ι
:
Z
N
→
R
N
iota: mathbb Z^N to R_N
- 将
s
s
s
(
x
)
=
τ
−
1
∘
ι
(
s
)
∈
R
N
s(x) = tau_{-1} circ iota(s) in R_N
τ
−
1
tau_{-1}
那么,获得的
(
b
,
a
(
x
)
)
∈
R
N
,
q
2
(b,a(x)) in R_{N,q}^2
(b,a(x))∈RN,q2 可以视为
s
(
x
)
s(x)
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,它的常数项
μ
[
0
]
mu[0]
μ[0] 恰好就是
μ
0
mu_0
μ0 了。
因此我们可以使用
K
=
{
R
L
W
E
s
′
(
s
(
x
)
⋅
g
i
)
}
K={RLWE_{s'}(s(x) cdot g_i)}
K={RLWEs′(s(x)⋅gi)} 作为 SwK,执行 RLWE 的秘钥切换,最后提取出常数项对应的 LWE 密文。其中的
g
=
(
g
1
,
⋯
,
g
d
)
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
(
c
1
)
,
e
⟩
e_{ks} = langle g^{-1}(c_1), e rangle
eks=⟨g−1(c1),e⟩,其中
e
←
χ
σ
e gets chi_sigma
e←χσ 是 SwK 的噪声。为了兼容 RNS 系统,我们使用素数分解
g
−
1
:
a
↦
{
[
a
]
q
i
∈
R
N
,
q
i
}
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
k
s
≤
1
12
N
σ
2
⋅
∑
i
q
i
2
V_{ks} le frac{1}{12}Nsigma^2 cdot sum_i q_i^2
Vks≤121Nσ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 来消除
X
i
,
i
≠
0
X^i,i neq 0
Xi,i=0 的系数,只保留常数项(缩放因子
N
N
N)。
直接计算
T
r
K
/
Q
Tr_{K/mathbb Q}
TrK/Q 需要分别计算各个
τ
d
,
d
∈
Z
m
∗
tau_d, din mathbb Z_m^*
τd,d∈Zm∗,共计需要
N
N
N 个自同构映射(每一次都需要做 KS 过程)。因此,借助分圆塔将
T
r
K
/
Q
Tr_{K/mathbb Q}
TrK/Q 分解,成为
L
=
log
N
L=log N
L=logN 个相邻分圆域的迹
T
r
K
2
l
/
K
2
l
−
1
Tr_{K_{2^l}/K_{2^{l-1}}}
TrK2l/K2l−1 的组合,这样就只需要计算
log
N
log N
logN 个非凡自同构。
具体算法为:
为了消除
N
N
N 缩放因子,可以预先对输入的 LWE 密文缩放
[
N
−
1
]
q
[N^{-1}]_q
[N−1]q 因子,从而上述算法的输出自然地消除了它们。
因为自同构
τ
d
tau_d
τd 是保长的,因此不会导致噪声过度膨胀。同态迹的噪声是
V
a
r
≤
1
3
(
(
N
n
)
2
−
1
)
⋅
V
k
s
Var le frac{1}{3}((frac{N}{n})^2-1) cdot V_{ks}
Var≤31((nN)2−1)⋅Vks
选取
n
=
1
n=1
n=1,LWE-to-RLWE 的噪声就是
V
a
r
≤
1
3
(
N
2
−
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
t
j
ct_j
ctj,然后计算
c
t
′
=
∑
j
∈
[
n
]
c
t
j
⋅
Y
j
,
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]∑μjYj∈Rn⊆RN
然而上述算法的计算效率和噪声增长都不算好。[CDKS21] 提出了 FFT-style 递归算法:假设
n
=
2
l
n=2^l
n=2l,为了计算
μ
′
mu'
μ′,可以将
μ
j
mu_j
μj 分为大小
2
l
−
1
2^{l-1}
2l−1 的两组,分别计算出
μ
e
v
e
n
′
=
N
/
2
⋅
∑
j
∈
[
n
/
2
]
μ
2
j
Y
2
j
∈
R
n
/
2
μ
o
d
d
′
=
N
/
2
⋅
∑
j
∈
[
n
/
2
]
μ
2
j
+
1
Y
2
j
∈
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]∑μ2jY2j∈Rn/2=N/2⋅j∈[n/2]∑μ2j+1Y2j∈Rn/2
但是实际上我们只需要计算出
μ
e
v
e
n
,
μ
o
d
d
∈
R
N
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
Y
Y 加到
μ
e
v
e
n
mu_{even}
μeven 上,并使用自同构
τ
d
,
d
=
2
l
+
1
tau_{d}, d=2^l+1
τd,d=2l+1 来消除
μ
o
d
d
mu_{odd}
μodd 那些恰好被旋转到
μ
e
v
e
n
′
mu_{even}'
μeven′ 位置上的杂项:
μ
=
(
μ
e
v
e
n
+
Y
⋅
μ
o
d
d
)
+
τ
d
(
μ
e
v
e
n
−
Y
⋅
μ
o
d
d
)
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
-e
−e 则保持不变,正好和
Y
⋅
μ
o
d
d
Y cdot mu_{odd}
Y⋅μodd 添加到
μ
e
v
e
n
mu_{even}
μeven 上的杂项
e
e
e 相互消除。最终,相位
μ
∈
R
N
mu in R_N
μ∈RN 的那些
Y
j
Y^j
Yj 的系数恰好是
N
⋅
μ
j
N cdot mu_j
N⋅μj,只要再消除其他的杂项就可以得到
μ
′
∈
R
n
mu' in R_n
μ′∈Rn,这里可以使用
T
r
K
N
/
K
n
Tr_{K_N/K_n}
TrKN/Kn 来消除它们。
具体算法为:
这个算法 Step 2 需要
n
−
1
n-1
n−1 次自同构,step 3 需要
log
(
N
/
n
)
log(N/n)
log(N/n) 次自同构,均摊成本为
n
+
log
(
N
/
n
)
−
1
n
frac{n+log(N/n)-1}{n}
nn+log(N/n)−1,只要打包的 LWEs 够多
n
=
Ω
(
log
N
)
n=Omega(log N)
n=Ω(logN),均摊成本仅为
O
(
1
)
O(1)
O(1)(但是打包
n
≥
2
10
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
≤
1
3
(
N
2
−
1
)
⋅
V
k
s
Var le frac{1}{3}(N^2-1) cdot V_{ks}
Var≤31(N2−1)⋅Vks
Lightweight Communication
三种转换的效率和噪声:
优势:
- 原始的 KS 过程,对于前两个参数,执行时间为
203
203
1628
1628
2
2
1.03
1.03
- 噪声仅为
O
(
log
N
)
O(log N)
b
∈
Z
q
b in mathbb Z_q
389
−
23
389-23
对于云计算场景,我们使用对称版本的 LWE 加密方案,那么多个密文的
a
j
∈
Z
q
N
a_j in mathbb Z_q^N
aj∈ZqN 完全可以被替代为随机种子,
a
j
=
P
R
F
(
s
e
e
d
,
j
)
a_j=PRF(seed,j)
aj=PRF(seed,j),这导致了 Rate 高达
1
−
o
(
1
)
1-o(1)
1−o(1) 的对称加密。在同态运算之前,需要同态解密,因为 LWE-based 是 FHE 友好的(只需要部分的同态解密,不必纠错),直接使用上述的 LWEs-to-RLWE 就可以转化为合适的 FHE 密文(这三种转换都是保护相位的,通用于任意的 FHE 方案)