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

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

在实用中, 一般采用的秘密/误差分布为离散高斯分布的 LWE 问题来进行密码协议的设计或者困难问题的归
约讨论. 一个自然的问题是针对特定的离散高斯分布的情形, 能否给出非均匀 LWE 问题的更紧致的归约. 这也是
本研究的主要出发点和研究动机所在.
在本文中, 我们推广了 Hint-LWE 问题困难性研究中用到的技巧并将其应用于半均匀 LWE 问题困难性的研
究中, 给出了半均匀 LWE 问题困难性更紧致的归约方法. 本文采用的归约方法基本不受代数结构的限制, 可以统
一地应用于欧氏格/理想格/模格上定义的半均匀 LWE 问题. 具体来讲, 本文的归约方式具有以下优势.
(1) 归约结果是保持维数的: 即 d 维的半均匀 LWE 问题的困难性仅需要用到 d 维的标准 LWE 问题的困难性
来保证.
(2) 归约过程中的高斯参数损失较少, 且对于一般的 η-半均匀分布 D, 归约中的高斯参数与样本数无关: 即高

斯参数为 σ 的 d 维的半均匀 LWE 问题的困难性可以由高斯参数为 O(η·σ) 的 d 维的标准 LWE 问题的困难性来
保证.
本文第 1 节介绍非均匀 LWE 问题的简单研究现状. 第 2 节介绍本文所需的基础知识, 包括欧氏格/理想格/模
格、高斯分布、 LWE 问题/半均匀 LWE 问题的定义和一些有用的引理等. 第 3 节介绍本文的主要归约, 并将我们
的归约结果与已知结果做简单比较. 最后, 在第 4 节总结全文.

1 非均匀 LWE 问题的相关工作
( )
在初始 LWE 问题的样本中, 公开矩阵一般选自随机均匀分布, 即 A ←- U Z m×d . 在已知的部分 LWE 问题的
q
变体问题研究中, 经常需要将 A 换成所谓的 Lossy 形式 (即 A = B·C + E, 使用多秘密的 LWE 样本来替换均匀矩
阵) 来进行讨论 [6–8] . 一般而言, A = B·C + E 对应的分布不是与均匀分布统计不可区分的. 但是在对应 LWE 问题
困难这个计算假设下, 可以证明对应的“非均匀” LWE 问题也是困难的. 在本文中, 非均匀 LWE 问题指的是公开
( )
矩阵 A 服从的分布 D 与 U Z m×d 不是统计或者计算不可区分的情况下对应的 LWE 问题.
q
据我们所知, 在不考虑某些 A 为特定的循环矩阵的情况下对应的 LWE 问题 (此类问题对应 A 的系数在某些
环上均匀选择) [30] 时, Boneh 等人 [16] 首次讨论了非均匀 LWE 问题的困难性, 并证明了当公开矩阵 A 服从的分布为
k
d
d
(1) Z 上适当参数的离散高斯分布; (2) k 足够大时对应的 {0,1} 上的均匀分布; (3) Z 的某些足够大的线性子空
间上的均匀分布时, 对应的非均匀 LWE 问题的困难性可以由标准 LWE 问题的困难性来保证. 此外, Bruna
等人 [31] 提出的连续 LWE 问题 (continuous LWE problem) 对应的公开矩阵 A 服从适当的连续高斯分布, Gupte 等
人 [32] 也证明了适当参数条件下, 此类问题的困难性可以由标准的 LWE 问题来保证.
但是, 上述几类非均匀 LWE 问题不适用于某些格密码应用 (例如压缩公钥的方式来设计的加密/密钥封装方
案 [25–29] ). 近期, Jia 等人 [4,17,18] 形式化定义了半均匀 LWE 问题, 并采用类似证明熵 LWE 问题困难性的归约路线, 结
合 Renyi 散度、格中正则性结论 (leftover hash lemma) 等工具证明了欧氏格/理想格/模格中适当参数的半均匀
LWE 问题是困难的.

2 基础知识

在本节中, 我们将给出符号说明, 并介绍在本文讨论过程中要经常用到的概念、定义和部分引理.
使用符号 Z, Q, R 来依次表示全体整数/有理数/实数组成的集合. 对于给定的正整数 q ∈ Z, 定义符号
[ ]
Z q := Z/q·Z 并使用符号 q 来表示集合 {1,2,...,q}. 如无特殊说明, 我们默认 Z q 中陪集的代表元取自集合
[ q q )
− , ∩Z. 本文使用粗体小写字母 x 来表示向量, 使用斜体大写字母 A 来表示矩阵或者集合. 如无特殊说明, 在
2 2
T
本文中默认使用列向量, 并使用符号 A 来表示矩阵 A 的转置 (向量亦看为特殊的矩阵); 符号 表示 d ×d 的单
I d
d ∑ d ∑
T
2
d
位矩阵. 对于向量 x = (x 1 ,..., x d ) ∈ R , 定义 || x|| := x , || x|| 1 := |x i | || x|| ∞ := max|x i | . 对于矩阵 A ∈ R d×d ,
,
i
i∈[d]
i=1 i=1
A
d
使用符号 s k (A),k ∈ [d] 来表示矩阵 的 个不同的奇异值. 我们默认对奇异值按照大小排序为 s d (A) ⩽ ...