Page 14 - 《软件学报》2025年第10期

王洋 等: 半均匀 LWE 问题的紧致归约 4411

m
,
戏终止); 否则, 计算 A = U + E U mod q·R b = A· s+e mod q·R; 最后输出 (A, b) ∈ R m×d ×R 给 A.
q q
根据定义 1, 在 Game 2 中输出 的概率是可忽略的. 当 Game 2 正常输出 (A, b) 时, Game 2 中输出的 与
A
⊥
Game 1 中输出的 统计不可区分. 因此, 我们有 |p 1 − p 2 | ⩽ negl(λ).
A
( )
,
● Game 3 : 取样 U ←- U R m×d , E U ←- ϕ U s ←- χ 2 ; 如果 s 1 (σ coef (E U )) > η, 则输出 ⊥; 否则继续取样 e 1 ←- D R m ,γ ,
q
m
,
,
; 再计算 z = E U · s+e 1 A = U + E U mod q·R b = U · s+z+e 2 mod q·R; 最后输出 (A, b) ∈ R m×d ×R 给 A.
e 2 ←- D R m ,σ 3 q q
2
,
下面当 R = Z 时取 N = m ˜ N = d; 而当 R = R 时取 N = m·n ˜ N = n·d. 如果令 Σ 1 := γ · I N Σ 2 := σ · I N 并取
2
,
,
3
2
γ ·σ 2 γ ·σ 3 ( )
m
N
Σ 3 := 3 · I N , 则根据假设 √ ⩾ η ε (R ) = η ε Z 以及引理 2 可知, 概率分布 D R m ,γ + D R m ,σ 3 与概率分布
γ +σ 2 γ +σ 2
2
2
3 3
D √ 的统计距离不超过 2·ε. 在 Game 3 中, 我们有:
R m ,
γ 2 +σ 2 = χ 1
3
b = U · s+z+e 2 mod q·R = U · s+ E U · s+e 1 +e 2 mod q·R = (U + E U )· s+(e 1 +e 2 ) mod q·R = A· s+(e 1 +e 2 ) mod q·R.
所以, 根据上述分析, 我们可以得到 |p 2 − p 3 | ⩽ negl(λ).
( )
● Game 4 : 取样 U ←- U R m×d , E U ←- ϕ U s ←- χ 2 ; 如果 s 1 (σ coef (E U )) > η, 则输出 ⊥; 否则继续取样 e 1 ←- D R m ,γ ,
,
q
( ) −1
1 1 1
T
,
; 再计算 A = U + E U mod q·R z = E U · s+e 1 , 并取 Σ 0 := · I ˜ N + ·σ coef (E U ) ·σ coef (E U ) , c = ·Σ 0 ·
σ γ 2 γ 2
e 2 ←- D R m ,σ 3 2
2
T
σ coef (E U ) ·z; 随后取样 ˜ s ←- D R d , Σ 0 ,c , 并利用二元组 (˜ s,z) 来计算 b = U · ˜ s+z+e 2 mod q·R; 最后输出 (A, b) ∈
√
m
R m×d ×R 给 .
A
q
q
1 1
T
我们先来分析 Game 4 中所需要的分布是否可以有效地取样. 注意到 Σ 0 −1 = · I ˜ N + ·σ coef (E U ) ·σ coef (E U ),
σ 2 γ 2
2
1 η 2 1
( )
2
2
根据参数选择, 我们有 s 1 Σ −1 ⩽ + < . 所以, 可以得到 s ˜ N (Σ 0 ) > 2·σ , 进而有 Σ 0 > σ · I ˜ N 成立. 由引理 1
0
σ 2 γ 2 2·σ 2 4 4
) 4
2 ( √
以及我们选择的参数条件 σ 4 ⩾ ω logn·d 可知, 可以有效地从一个与 D R d , Σ 0 ,c 统计不可区分的分布中采样 ˜ s. 当
√
所有的分布均可以有效采样时, Game 3 与 Game 4 的区别仅仅在于用于计算 b 的 (s,z) 与 (˜ s,z) 的不同. 根据引理 3,
在我们的参数选择下, (s,z) 与 (˜ s,z) 的分布统计不可区分. 因此, 我们有 |p 3 − p 4 | ⩽ negl(λ).
( )
● Game 5 : 取样 U ←- U R m×d , E U ←- ϕ U s ←- χ 2 ; 如果 s 1 (σ coef (E U )) > η, 则输出 ⊥; 否则继续取样 e 1 ←- D R m ,γ ,
,
q
( ) −1
1 1 1
T
,
; 再计算 A = U + E U mod q·R z = E U · s+e 1 , 并取 Σ 0 := · I ˜ N + ·σ coef (E U ) ·σ coef (E U ) , c = ·Σ 0 ·
e 2 ←- D R m ,σ 3 2 2 2
σ 2 γ γ
T
σ coef (E U ) ·z; 随后取样 s 1 ←- D √ 和 并计算 ˜ s = s 1 + s 2 mod q·R; 再利用二元组 (˜ s,z) 来计算
R d , Σ 0 −σ 2 ·I ˜ N ,c s 2 ←- D R d ,σ 4
4
m
b = U · ˜ s+z+e 2 mod q·R; 最后输出 (A, b) ∈ R m×d ×R 给 A.
q q
(
)
2
2
2
我们已经知道 s ˜ N (Σ 0 ) > 2·σ , 所以 s ˜ N Σ 0 −σ · I ˜ N > σ . 根据引理 1 和我们的参数选择, 可以有效地从一个
4 4 4
1
−1
−1
−1
2
与 D √ 统计接近的分布进行采样. 如果现在取 Σ −1 = · I ˜ N Σ −1 = (Σ 0 −σ · I ˜ N ) 并令 Σ −1 = Σ +Σ , 简
,
R d , Σ 0 −σ 2 ·I ˜ N ,c 1 σ 2 2 4 3 1 2
4 4
1 2
( ) ( ) −2 √ ( )
d
d
单计算即知 s 1 Σ −1 ⩽ +s 1 Σ 2 −1 < ⩽ (η ε (R )) 成立. 由引理 1 可知, Σ 3 ⩾ η ε R . 进而根据引理 2, 分布
3
σ 2 σ 2
4 4
D √ 与分布 D R d , Σ 0 ,c 的统计距离不超过 2·ε, 即 Game 4 和 Game 5 中对应的 ˜ s 的分布统计不可区
√
R d , Σ 0 −σ 2 ·I ˜ N ,c + D R d ,σ 4
4
分. 所以, 我们可以得到 |p 4 − p 5 | ⩽ negl(λ).
( )
,
● Game 6 : 取样 U ←- U R m×d , E U ←- ϕ U s ←- χ 2 和 e 1 ←- D R m ,γ ; 如果 s 1 (σ coef (E U )) > η, 则输出 ; 否则计算
⊥
q
( ) −1
1 1 1
T
T
A = U + E U mod q·R 和 z = E U · s+e 1 ; 令 Σ 0 := · I ˜ N + ·σ coef (E U ) ·σ coef (E U ) , c = ·Σ 0 ·σ coef (E U ) ·z; 随后
σ 2 γ 2 γ 2
( ) 2
取样 s 1 ←- D √ 和 u ←- U R ; 计算 b = U · s 1 +z+u mod q·R; 最后输出 (A, b) ∈ R m×d ×R 给 .
m
m
A
R d , Σ 0 −σ 2 ·I ˜ N ,c q q q
4
( ) ( )
m
m
在 Game 6 中, 由于 u 是独立随机地取自分布 U R , 因此有 b ←- U R 成立. 根据 η -半均匀分布, A 服从的
q q
分布与 D 统计不可区分. 根据假设, 可以以 的概率解决 DLWE d ( χ 2 ;D ) 问题. 所以我们可以得到
δ
A
R,m,q,χ 1
|p 1 − p 6 | ⩾ δ−negl(λ). 综合 Game 1 – Game 5 的分析, 我们有 |p 5 − p 6 | ⩾ δ−negl(λ).
注意到在 Game 5 中,

b = U · ˜ s+z+e 2 mod q·R = U · s 1 +z+U · s 2 +e 2 mod q·R.