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

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

( )
现在, 我们可以利用敌手 A 的能力来构造敌手 以解决 DLWE d ( χ 4 ;U R m×d ) 问题. 假设敌手 B 获
B
R,m,q,χ 3 q
( ) ( )
得 的 样 本 为 (U, b) , 其 中 U ←- U R m×d , , , b = U · s 2 +e 2 mod q·R 或 者 U ←- U R m×d ,
˜
˜
q s 2 ←- D R d ,σ 4 e 2 ←- D R m ,σ 3 q
( )
˜ b ←- U R m . 则 B 进行如下操作.
q
,
(1) 取样 E U ←- ϕ U s ←- χ 2 ; 如果 s 1 (σ coef (E U )) > η, 则输出 ⊥; 否则继续取样 e 1 ←- D R m ,γ .
( ) −1
1 1 1
T
(2) 计算 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 γ 2
2
T
σ coef (E U ) ·z.
˜
(3) 取样 s 1 ←- D √ , 随后计算 b = U · s 1 +z+ b mod q·R.
R d , Σ 0 −σ 2 ·I ˜ N ,c
4
(4) 输出 (A, b) ∈ R m×d ×R 给 A.
m
q q
最后 B 输出 A 的输出即可.
显然, 根据我们的参数选择, 上述 B 的操作可以在概率多项式时间内完成. 下面来分析所构造的敌手 B 可以
( )
˜
成功解决 DLWE d ( χ 4 ;U R m×d ) 问题的概率. 易知, 当 (U, b) 来自均匀分布时, B 给 A 的样本 (A, b) 所服从的
R,m,q,χ 3 q
分布与 Game 6 的输出所服从的分布相同. 否则, B 给 A 的样本 (A, b) 所服从的分布与 Game 5 的输出所服从的分
布相同. 因此,

( )
Adv B DLWE d (χ 4 ;U(R m×d )) = |p 5 − p 6 | ⩾ δ−negl(λ).
R,m,q,χ 3 q
证毕.
( { √ √ })
注意到定理 1 中的条件 σ 1 ,σ 2 ,σ 3 ,σ 4 ,γ ⩾ ω max logm·n, logd ·n 是为了对 R 进行统一分析. 当 R = Z
( { √ √ })
时, 相应的条件可以改为 σ 1 ,σ 2 ,σ 3 ,σ 4 ,γ ⩾ ω max logm, logd . 我们对定理 1 中所选择的参数条件进行一些简
γ ·σ 3 √
m
2
单的说明. 条件 √ ⩾ η ε (R ) 和 σ 1 = γ +σ 是为了保证从 Game 2 到 Game 3 的过程中, 我们可以对 Game 2
2
γ +σ 2 3
2
3 2
1 η 1
中的原始误差 e 进行拆分; 条件 + < 是为了保证我们可以应用关键引理 3; 本质上讲, 条件 σ 1 ,σ 2 ,σ 3 ,σ 4 ,γ ⩾
σ 2 γ 2 2·σ 2
( { √ √ }) 2 4
ω max logm·n, logd ·n 保证了证明过程中对应的离散高斯分布均可以有效地取样. 同时, 此条件连同条件
1 η 2 1
+ < 也保证了从 Game 4 到 Game 5 的过渡中可以对 Game 4 中的原始误差 进行拆分. 最后得到的
s
σ 2 γ 2 2·σ 2
2 4
Game 5 (以及 Game 6 ) 即为所期望的分布形式, 非常便于我们来构造概率多项式时间的算法 (归约) 来嵌入
DLWE d ( χ 4 ;U(R m×d )) 问题的实例.
R,m,q,χ 3 q
3.2 与已知结果的对比分析
利用定理 1, 可以得到半均匀的 (欧氏格/环/模) LWE 问题的困难性结果. 在本节中, 对任意的整数 x ∈ Z, 使用
⌊ ⌋
1
符号 ⌊x⌋ 来表示不超过 x 的最大整数, 并定义 ⌊x⌉ := x+ . 相应的取整符号可以平凡的推广到向量 (多项式) 或
2
者矩阵上.
当 R = Z 时, 可以得到 d 维欧氏格对应的半均匀 LWE 问题的困难性归约.
推论 1. 假设 ε = negl(λ) 为某可忽略的函数, m,q,d 为正整数, 为 Z m×d 上的 η -半均匀分布, 正实数
D
q
√ ( { √ √ }) γ ·σ 3 √ 1 η 2 1
σ 1 ,σ 2 ,σ 3 ,σ 4 ,γ ⩾ 2·ω max logm, logd 且满足条件 √ ⩾ η ε (Z ) σ 1 = γ +σ , + < . 记
m
,
2
2
γ +σ 2 3 σ 2 2 γ 2 2·σ 2 4
2
3
, , , . 如果存在一个 (量子) 概率多项式时间的敌手 A 可以以 δ 的概率解
χ 1 = D Z m ,σ 1 χ 2 = D Z d ,σ 2 χ 3 = D Z m ,σ 3 χ 4 = D Z d ,σ 4
决 DLWE d ( χ 2 ;D ) 问题, 则存在一个 (量子) 概率多项式时间的敌手 可以以 δ−negl(λ) 的概率解决
B
Z,m,q,χ 1
( )
DLWE d ( χ 4 ;U Z m×d ) 问题.
Z,m,q,χ 3 q
√ √ 1 η 2 1 1 ( √ )
如 果 选 择 σ 2 = 2 2·σ 4 γ = 2 2·σ 4 ·η , 则 2 + = 2 < 2 . 由 引 理 1 , η ε (Z ) ⩽ ω logm . 而
,
m
γ σ 2 γ 2 4·σ 4 2·σ 4
γ ·σ 3 σ 3
√ = √ = √
γ +σ 2 3 ( γ ) 2 ( ) 2 √ ( √ ) γ ·σ 3
2
1+ 1+ σ 3 , 所以在上述参数设置下, 当 σ 3 ,γ ⩾ 2·ω logm 时, 不等式 √ 2 2 ⩾
σ 3 γ γ +σ 3