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

4410 软件学报 2025 年第 36 卷第 10 期

˜ n
˜ m
出 (˜ s,z) ∈ Z ×Z .
˜ n
证明: 记输出的第 1 个随机变量为 x, 第 2 个随机变量为 y. 注意到对任意的 (v,w)∈ Z ×Z :
˜ m

[
]
Pr x = v∧ y = w = Pr[y = w]·Pr[x = v|y = w].
]
[
同时, 在两个取样过程中, Pr y = w = Pr[z = F · s+e = w] 相同. 因此, 为了证明这两个取样过程最后输出的分
布相同, 只需证明在取样过程 (1) 中, 在已知 F · s+e 的情况下, s 服从的条件分布为 D Z ˜n , Σ 0 ,c 即可.
√
˜ n
˜ m
为此, 任取 (v,w)∈ Z ×Z . 在取样过程 (1) 中, 我们有:

[ ]
Pr x = v∧ y = w = Pr[s = v∧ F · s+e = w] = Pr[s = v∧e = w− F ·v]
1 ( 1 1 T ) 1 ( T 1 )
0
= ·e −π σ 1 2 ·v T ·v+ σ 2 2 ·(w−F·v) ·(w−F·v) = ·e −π (v−c) ·Σ −1 ·(v−c)−c T ·Σ −1 ·c+ σ 2 2 w T ·w .
0
˜ n ˜ m ˜ n ˜ m
ρ σ 1 (Z )·ρ σ 2 (Z ) ρ σ 1 (Z )·ρ σ 2 (Z )
−T
这里, 我们用到了条件 Σ −1 = Σ . 注意到:
0 0

∑ 1 ∑ ||a|| 2 ||w−F·a|| 2
[ ] −π· −π·
Pr y = w = Pr[z = w] = Pr[s = a]·Pr[e = w− F · s|s = a] = · e σ 2 1 ·e σ 2 2 ,
˜ n (Z )
˜ m
a∈Z ˜n ρ σ 1 (Z )·ρ σ 2 a∈Z ˜n
我们可以得到:

( )
−π −c T ·Σ −1 ·c+ 1 2 w T ·w
Pr[s = v∧z = w] e 0 σ 2
[ ] T
Pr x = v|y = w = Pr[s = v|z = w] = = ·e −π·(v−c) ·Σ −1 ·(v−c) .
0
Pr[z = w] ∑ −π· ||a|| 2 −π· ||w−F·a|| 2
e σ 2 1 ·e σ 2 2
a∈Z ˜n
( )
1
−π −c T ·Σ −1 ·c+ 2 w T ·w ∑
e 0 σ 2
因为公式 与 v 无关, 且有概率等式 Pr[s = v|z = w] = 1 成立, 所以我们有:
∑ ||a|| 2 ||w−F·a|| 2
−π· −π· v∈Z ˜n
e σ 2 1 ·e σ 2 2 ( )
−π −c T ·Σ −1 ·c+ 1 2 w T ·w   −1
a∈Z ˜n e 0 σ 2 ∑ T   1

 e −π·(v−c) ·Σ −1 ·(v−c)  = .
=   0 
˜ n
√
∑ ||a|| 2 ||w−F·a|| 2   ρ Σ 0 ,c (Z )
−π· σ 2 −π· σ 2
e 1 ·e 2 v∈Z ˜n
a∈Z ˜n
因此,

1 T
Pr[s = v|z = w] = ·e −π·(v−c) ·Σ −1 ·(v−c) .
0
ρ Σ 0 ,c (Z )
˜ n
√
也就是说, 在已知 z = F · s+e = w 的情况下, s 服从的条件分布为 D Z ˜n , Σ 0 ,c . 证毕.
√
3.1 半均匀 LWE 问题的归约
本文的主要定理如下.
定理 1. 假设 ε = negl(λ) 为某可忽略的函数, m,q,d 为正整数, 为 R m×d 上的 η-半均匀分布, 正实数
D
q
( }) 1 η 2 1
{ √
√ γ ·σ 3 √
m
2
2
,
σ 1 ,σ 2 ,σ 3 ,σ 4 ,γ ⩾ ω max logm·n, logd ·n 且满足条件 √ ⩾ η ε (R ) σ 1 = γ +σ , 2 + < 2 . 记
3
γ +σ 2 σ 2 γ 2 2·σ 4
2
3
, , , . 如果存在一个 (量子) 概率多项式时间的敌手 A 可以以 δ 的概率解
χ 1 = D R m ,σ 1 χ 2 = D R d ,σ 2 χ 3 = D R m ,σ 3 χ 4 = D R d ,σ 4
决 DLWE d ( χ 2 ;D ) 问题, 则存在一个 (量子) 概率多项式时间的敌手 可以以 δ−negl(λ) 的概率解决
B
R,m,q,χ 1
( )
DLWE d ( χ 4 ;U R m×d ) 问题.
R,m,q,χ 3 q
证明: 根据假设, D 为 R m×d 上的 η -半均匀分布. 由定义 1, 存在 R m×d 上的一族可以有效取样的概率分布
q
( )
,
{ϕ U } U∈R m×d 使得对任意随机取样的 A ←- D U ←- U R m×d 和 E U ←- ϕ U , 随机变量 A 与 U + E U mod q·R 统计不可
q
]
区分. 同时, 有 Pr [ s 1 (σ coef (E U )) ⩽ η ⩾ 1−negl(λ) 成立.
q )
U←-U( R m×d ,E U ←-ϕ U
对任意 (量子) 概率多项式时间的敌手 A, 我们定义一系列区分游戏 Game i , 并定义 p i := Pr Game i [A(A, b) = 1].
m
这里, i ∈ [6] (A, b) ∈ R m×d ×R .
,
q q
m
● Game 1 : 取样 A ←- D s ←- χ 2 e ←- χ 1 ; 计算 b = A· s+e mod q·R; 最后输出 (A, b) ∈ R m×d ×R 给 A.
,
,
q q
注意到 Game 1 中输出的样本 (A, b) 即为 DLWE d ( χ 2 ;D) 问题的原始分布.
R,m,q,χ 1
( )
,
● Game 2 : 取样 U ←- U R m×d , E U ←- ϕ U s ←- χ 2 e ←- χ 1 ; 如果 s 1 (σ coef (E U )) > η, 则输出 ⊥ (代表采样出错, 游
,
q