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

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

with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need
for any additional non-standard assumptions. Furthermore, the dimension of the corresponding LWE problems remains unchanged, and the
reduction introduces only minimal losses in Gaussian parameters of errors.
Key words: lattice-based cryptography; reduction of lattice-based problem; LWE problems with semi-uniform seeds; Hint-LWE problem;
discrete Gaussian distribution
欧氏格 LWE (learning with errors problem) 问题 [1] 及其 (代数) 变体环/模 LWE 问题 [2,3] 是目前格密码中应用最
广泛的一类平均情形的数学困难问题, 基于欧氏格/环/模 LWE 问题及其适当形式的变体问题几乎可以设计已知
的所有密码原语. 到目前为止, 关于 LWE 问题实用化变体问题的研究可以粗略地分为 3 类 (更具体的分类讨论可
参考文献 [4]). 第 1 类是研究 LWE 问题的秘密或者误差分布为更一般的分布 (例如 {0,1} 上的二元分布, 小区间
[−α,α] 上的均匀分布, 熵 LWE 问题等) 时, 对应 LWE 问题的困难性 [5–9] ; 第 2 类是研究 LWE 问题的秘密或者误
差存在部分泄露信息时, 对应的 LWE 问题 (即 Hint-LWE 问题) 的困难性 [5,10–15] ; 第 3 类是研究 LWE 问题的公开
矩阵为非均匀分布时, 对应的 LWE 问题 (即非均匀 LWE 问题) 的困难性 [4,16–18] .
近期, Jia 等人 [4,17,18] 系统地研究了一类特殊的非均匀 LWE 问题, 即半均匀 LWE 问题, 的困难性, 给出了半均
匀 LWE 问题的形式化定义, 并采用类似证明熵 LWE 问题困难性的归约路线证明了欧氏格/理想格/模格上对应半
均匀 LWE 问题的困难性. 以欧氏格为例, 称 Z m×d 上的分布 D 为 η-半均匀分布, 如果存在 Z m×d 上的一族可以有效
q
( )
取样的分布 {ϕ U } U∈Z m×d , 使得取样过程 {U + E U : U ←- U Z m×d ,E U ←- ϕ U } 所输出的分布与 D 统计不可区分, 且以接
q
q
近于 1 的概率有 E U 的谱范数不超过 η 成立. 在本文中, 离散高斯分布一般使用 D; 当不引起歧义时, 我们使用 D
来表示对应 LWE 问题中的公开矩阵 A 服从的分布, 以突出半均匀 LWE 问题的公开矩阵. 对应地, 可以定义判定
版本的非均匀 LWE 问题 DLWE d (χ 2 ;D) 为区分如下分布.
Z,m,q,χ 1
(1) {(A,A· s+e mod qZ) : A ←- D, s ←- χ 2 ,e ←- χ 1 }.
m
(2) {(A,u) : A ←- D,u ←- U(Z )}.
q
⌊ ⌊ ⌉⌉
q p
值得注意的是, 对任意的 U ∈ Z m×d , 当选取 ϕ U 为特定的固定函数 E U = · ·U −U 时, 对应的半均匀
q p q
LWE 问题即为区分如下分布.
{(⌊ ⌊ ⌉⌉ ⌊ ⌊ ⌉⌉ ) }
q p q p ( )
(1) · · A , · · A · s+e mod qZ : A ←- U Z m×d , s ←- χ 2 ,e ←- χ 1 .
q
p q p q
{(⌊ ⌊ ⌉⌉ ) }
q p ( )
m
(2) · · A ,u : A ←- U Z m×d ,u ←- U(Z ) .
q
q
p q
⌊ ⌊ ⌉⌉
q p
值得指出的是, 由 A 可以很容易地计算 · · A . 利用这里一类特殊的半均匀 LWE 问题可以证明 NIST
p q
(National Institute of Standards and Technology) 后量子竞赛第 1 轮的候选算法 Kyber 采用的基础公钥加密方案的
IND-CPA (indistinguishability under chosen plaintext attack) 安全性 [19,20] . 也就是说, 可以证明采用 LP 框架 [21] 和压缩
公钥的方式来设计的高效公钥加密方案也是满足 IND-CPA 安全的. 早期, 由于缺乏对应非均匀 LWE 问题到标准
LWE 问题的严格归约, Kyber 设计团队从 NIST 第 2 轮竞选开始取消了方案中对公钥进行压缩的设计方式 [22–24] ,
这导致对应方案的通信带宽的增加. 在实践应用中, 这一类特殊的半均匀 LWE 问题可以结合密钥共识等技术来
设计非常高效的格密码方案 [25–29] .
虽然已知的半均匀 LWE 问题困难性的归约结果适用于一般的秘密分布 (即归约中仅要求秘密 s 的分布在特
定条件下拥有足够的熵即可, s 所服从分布的具体形式可以不定). 但是由于采用的是类似证明熵 LWE 问题困难
性的归约路线, 已知的半均匀 LWE 问题的归约在维数和高斯分布参数等方面的归约损失较大 [4,17,18] . 具体来讲, 证
˜
明 d 维的半均匀 LWE 问题的困难性要用的 d d = O(d ·logq)) 维的标准 LWE 问题的困难性. 同时, 对于一般的
˜ (
η-半均匀分布 D, 归约过程中高斯误差参数的损失与样本数目有关 (特别是样本数为 poly(λ) 时, 误差参数的膨胀

倍数较大). 另外, 在证明环中 (求解版本) 半均匀 LWE 问题的困难性时, 需要引入额外的、相对而言非标准的困
难性假设, 即某种判定版本的 NTRU 问题对应的假设.