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

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

2
Σ
T
Σ > r · B· B 的实对称正定矩阵 , 存在利用 B 的多项式时间的取样算法从一个与分布 D Λ, Σ,c 统计接近的分布中
√
抽取样本.
( √ )
n
n·d
注意到在 σ coef 的作用下, R 对应 Z . 根据引理 1, 对任意的向量 c ∈ R 和满足条件 Σ > ω logn·d 的实对
称正定矩阵 Σ, 我们可以有效地从一个与 D R d , Σ,c 统计不可区分的分布中进行抽样.
√
( )
1 √ ( )
引理 2. 假设实数 ε ∈ 0, , Σ 1 ,Σ 2 为实对称正定矩阵, Σ −1 := Σ +Σ 且满足条件 Σ 3 ⩾ η ε Z . 则对任意的
d
−1
−1
2 3 2 2
d
向量 c ∈ R , 分布 {x 1 + x 2 : x 1 ←- D Z d , Σ 1 , x 2 ←- D Z d , Σ 2 ,c } 与 D Z d , Σ 1 +Σ 2 ,c 的统计距离不超过 2·ε.
√
√
√
利用引理 2, 我们可以将某个离散高斯分布拆分为某两个适当参数的离散高斯分布的和.
2.2 LWE 问题
[1]
LWE 问题最早由 Regev 提出, 是目前格密码设计中应用最广泛的一类平均情形的格中困难问题.
本文用符号 R 来表示环 Z 或者 R, 并定义 R q := R/q·R. 在系数嵌入 σ coef 的作用下, R 中元素的加法和乘法
可以使用 Z 中向量的加法, 以及对应矩阵和向量的乘法来表示. 注意到 σ coef 可以平凡地扩展到以 R 中的元素为
n
元素的向量或者矩阵上. 为了讨论方便, 定义 Z 上的 σ coef 作用为恒等映射. 这样, σ coef 可以视为 R 上的 Z -模同
态, 或者视为 R q 上的 Z q -模同态.
d
m
,
对于正整数 m,d,q 以及 R 上的概率分布 χ 1 R 上的概率分布 χ 2 R m×d 上的概率分布 D, 定义环 R 相关的
,
q
判定版本的 LWE 问题 (记为 DLWE d ( χ 2 ;D)) 为如下问题: 区分分布 (A,A· s+e mod q·R) 与分布 (A,u). 这里,
R,m,q,χ 1
( )
m
,
,
,
A ←- D s ←- χ 2 e ←- χ 1 u ←- U R . 注意到在上述定义中, 参数 m 对应的是 LWE 问题的样本数; D 即为 LWE
q
问题公开矩阵服从的分布; χ 1 和 χ 2 分别为 LWE 问题的误差向量和秘密向量服从的分布. 为了下文讨论方便, 当
样本形式为 (A,A· s+e mod q·R) 时, 我们称对应的样本取自 DLWE d ( χ 2 ;D) 问题的分布. 对于任意的 (量子)
R,m,q,χ 1
概率多项式时间的敌手 A, 定义其解决 DLWE d ( χ 2 ;D) 问题的优势为:

R,m,q,χ 1
( )
Adv A DLWE d (χ 2 ;D) := |Pr[A(A,A· s+e mod q·R) = 1]−Pr[A(A,u) = 1]|.
R,m,q,χ 1
当 R = Z 时, 上述判定版本 LWE 问题对应欧氏格上的 LWE 问题. 此时, 参数 d 为对应的 (格的) 维数. 而当
R = R 时, 上述判定版本 LWE 问题对应现实中最常用的、扩张次数为 2 的幂次的分圆域上定义的相应 LWE 问
题. 此时, 对应的 (格的) 维数为 n·d. 当 d = 1 时对应环 LWE 问题, 而当 d ⩾ 2 时对应模 LWE 问题.
( ) ( )
一般而言,LWE 问题的公开矩阵的分布为 D = U R m×d . 当 D , U R m×d 时, 我们称对应的 LWE 问题为非均
q
q
匀 LWE 问题. 本文关心的是非均匀 LWE 问题中的一类特殊的半均匀 LWE 问题, 即 D 为下面定义的 η -半均匀分
布 [4,17,18] .
定义 1. 假设 m,d 为正整数. 对于任意的正实数 η > 0, 我们称分布 为 R m×d 上的 η -半均匀分布, 如果存在
D
q
( )
R m×d 上的一族可以有效取样的概率分布 {ϕ U } U∈R m×d 使得对任意随机取样的 A ←- D,U ←- U R m×d 和 E U ←- ϕ U ,
q
下面两个条件成立:
(1) 随机变量 A 与 U + E U mod q·R 统计不可区分.
[ ]
(2) Pr s 1 (σ coef (E U )) ⩽ η ⩾ 1−negl(λ).
q )
U←-U( R m×d ,E U ←-ϕ U
3 半均匀 LWE 问题的困难性研究
本节将给出半均匀 LWE 问题相关的更紧的归约方法. 在给出具体的归约之前, 我们需要用到下面这个关键
引理. 引理 3 的证明所采用到的方法与文献 [10] 中的方法类似.
( ) −1
1 1
引理 3. 假设 σ 1 ,σ 2 为正实数, ˜ m, ˜n 为正整数, F ∈ Z ˜ mטn 为任意一个使得矩阵 Σ 0 := · I ˜n + · F · F 存在
T
2 2
σ 1 σ 2
的矩阵. 则以下两个取样过程输出的分布相同.
(1) 先取样 s ←- D Z ˜n ,σ 1 和 e ←- D Z ˜m ,σ 2 , 再计算 z = F · s+e, 最后输出 (s,z) ∈ Z ×Z .
˜ n
˜ m
1
T
(2) 先取样 和 , 再计算 z = F · s+e 和 c = ·Σ 0 · F ·z; 随后采样 ˜ s ←- D Z ˜n , Σ 0 ,c ; 最后输
√
2
e ←- D Z ˜m ,σ 2
s ←- D Z ˜n ,σ 1
σ 2