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

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

m
η ε (Z ) 恒成立.
√
2
2
注意到 σ 1 = γ +σ , 因此当选取参数 σ 3 = σ 4 =: σ 时, 可以将标准 (即秘密与误差服从相同参数的离散高斯
3
( ( ))
分布) 的 DLWE d D Z d ,σ ;U Z m×d 问题归约到公开矩阵服从任意 η -半均匀分布 D 的半均匀 DLWE d (χ 2 ;D)
Z,m,q,D Z m ,σ q Z,m,q,χ 1
问题. 其中, , ; , σ 2 = O(σ).
χ 1 = D Z m ,σ 1 σ 1 = O(η·σ) χ 2 = D Z d ,σ 2
值得指出的是, 在不计多项式规模样本数的情况下, 误差 e 所服从的高斯分布的参数大小决定了对应 LWE
问题的困难程度 (例如, 采用文献 [36] 的方法可以将秘密取自均匀分布的 LWE 问题归约到秘密取自与误差相同
参数的离散高斯分布的 LWE 问题, 即所谓的标准形式 (normal form) 的 LWE 问题; 而秘密取自均匀分布的 LWE
问题是同等条件下最难的一类问题). 因此, 我们在这里仅举例说明 σ 3 = σ 4 的情形.
与文献 [4] 的归约结果相比, 本文的归约结果是保持格的维数 d 的, 但是文献 [4] 中的归约结果需要依赖于相
应的低维 LWE 问题的困难性. 同时, 在我们的归约结果中, 在渐进意义下两个问题的误差参数大小的归约损失为
η, 与样本数目无关. 但是文献 [4] 中的归约结果在渐进意义下两个问题的误差参数大小的归约损失与样本数相关
( √ )
(约为 σ 1 = ˜ O m·σ+η ). 不过值得注意的是, 本文的归约结果仅仅局限于秘密/误差服从离散高斯分布的情形, 且
仅适用于判定版本 LWE 问题的归约. 而文献 [4] 的归约同时适用于求解和判定版本问题的归约, 但是对于判定版
本的对应问题, 需要额外限制 q 为素数或者要求秘密 s 取自 {0,1} 上的、特定条件下熵足够大的二元分布.
⌊ ⌊ ⌉⌉
q p
假设 0 < p ⩽ q 为正整数, 对任意的矩阵 U ∈ Z m×d , 可以定义固定函数 E U = · ·U −U . 对任意的 x ∈
q
⌊ ⌊ ⌉⌉ ⌊ ⌉ ⌊ ⌉ p q
√
q p q q
Z q , 简单计算知 x− · · x ⩽ . 因此, 我们有 s 1 (E U ) ⩽ m·d · . 定义分布 D p,q,m,d 为: 取样 U ∈ Z m×d ,

p q 2p 2p q
⌊ ⌊ ⌉⌉ ⌊ ⌉
q p √ q
输出 · ·U , 则 D p,q,m,d 为特殊的 m·d · -半均匀分布. 上述讨论的结论可以自然地应用到 D p,q,m,d 对应
p q 2p
的半均匀 LWE 问题.
当 R = R 时, 可以得到对应的判定版本的环/模半均匀 LWE 问题的困难性归约.
推论 2. 假设 ε = negl(λ) 为某可忽略的函数, m, q, d 为正整数, 为 R m×d 上的 η -半均匀分布, 正实数
D
q
√ ( { √ √ }) √ 1 η 2
σ 1 , σ 2 , σ 3 , σ 4 , γ ⩾ 2·ω max logm·n, logd ·n 且 满 足 条 件 √ γ ·σ 3 ⩾ η ε (R ) σ 1 = γ +σ , + <
,
m
2
2
γ +σ 2 3 3 σ 2 2 γ 2
2
1
. 记 χ 1 = D R m ,σ 1 , χ 2 = D R d ,σ 2 , χ 3 = D R m ,σ 3 , χ 4 = D R d ,σ 4 . 如果存在一个 (量子) 概率多项式时间的敌手 A 可以以
2·σ 2
4
δ 的概率解决 DLWE d ( χ 2 ;D) 问题, 则存在一个 (量子) 概率多项式时间的敌手 B 可以以 δ−negl(λ) 的概率解
R,m,q,χ 1
( )
决 DLWE d ( χ 4 ;U R m×d ) 问题.
R,m,q,χ 3 q
类似于欧氏格中的半均匀 LWE 问题的参数分析, 可以推出以下结论. 当选取参数 σ 3 = σ 4 =: σ 时, 可以将标准
( )
的 DLWE d ( D R d ,σ ;U R m×d ) 问题归约到公开矩阵服从任意 η -半均匀分布 D 的半均匀 DLWE d ( χ 2 ;D)
R,m,q,D R m ,σ q R,m,q,χ 1
问题. 其中, χ 1 = D R m ,σ 1 , σ 1 = O(η·σ) χ 2 = D R d ,σ 2 , σ 2 = O(σ).
;
注意到当 d = 1 时, 上述结果即为对应的环上的半均匀 LWE 问题的困难性归约结果. 与文献 [17] 的结论相
比, 我们可以将标准的环 LWE 问题归约到对应的半均匀环 LWE 问题, 而不需要使用额外的困难性假设 (例如某
些特定形式的 DSPR (decisional small polynomial ratio) 假设, 即对应为判定版本的 NTRU 假设). 当 d ⩾ 2 时, 与文
献 [4] 的结果相比, 在渐近的意义下, 我们的误差参数的归约损失仅为 η, 与其余参数无关. 特别地, 我们的归约也
是保持格的维数的, 不需要像文献 [4,17,18] 那样基于低维度 (更确切地说, 低秩数) 的模 LWE 问题的困难性.
⌊ ⌊ ⌉⌉ ⌊ ⌉
q p √ q
当定义分布 D p,q,m,d 为: 取样 U ∈ R m×d , 输出 · ·U 时, 简单计算易知, D p,q,m,d 为特殊的 n· m·d · -
q p q 2p
半均匀分布. 利用分布 D p,q,m,d 对应的半均匀模 LWE 问题可以证明, 当采用类似 NIST 第 1 轮候选算法 Kyber 那
种压缩公钥的设计方式时, 对应的底层加密方案也满足 IND-CPA 安全性. 具体方案的构造如下. 由于相关方案的
IND-CPA 安全性的证明是标准的, 我们仅给出大概解释, 证明的具体细节可以参考文献 [4,25–29].
( )
( )
● KeyGen 1 : 给定安全参数 λ, 密钥生成算法采样 A ←- U R d×d , s ←- D R d ,σ 2 , e ←- D R d ,σ 1 . 计算 b = A· s+e,
λ
q