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

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

( ⌊ ⌉)
p
并返回公钥 pk = A, · b 和私钥 sk = s.
q
( ⌊ ⌉) ⌊ ⌊ ⌉⌉
p q p
˜
n
● Enc(pk,m): 假设 pk = A, · b , 要加密消息 σ coef (m) ∈ {0,1} , 加密算法先计算 b = · · b . 随后, 采样
q p q
T
, , , 并计算 c 1 = A · r+e 1 和 c 2 = b · r+e 2 . 最后返回密文 ct = (c 1 ,c 2 ).
˜ T
r ←- D R d ,σ 2 e 1 ←- D R d ,σ 2 e 2 ←- D R,σ 1
⌊ ⌉
2
T
,
● Dec(sk,ct): 假设 ct = (c 1 ,c 2 ) sk = s. 解密算法计算并返回 m = ·(c 2 − s · c 1 ) .
q
简单计算可知, 对于适当选择的参数, 上述方案可以正确解密. 为证明方案的 IND-CPA 安全性, 需要用到两次
相应判定版本的 LWE 假设. 第 1 次是将 (A, b) 替换为均匀随机的 (A,u), 用到的假设是 DLWE d R,d,q,D R d ,σ 1 ( D R d ,σ 2 ;
d×d ) ) 问 题 是 困 难 的 ; 第 2 次 是 将 密 文 替 换 为 随 机 均 匀 的 元 素 , 其 中 替 换 密 文 c 1 用 到 的 假 设 仍 是
U(R q
DLWE d ( D R d ,σ 2 ;U(R d×d )) 问题是困难的. 但是, 替换密文 需要用到的困难性假设是 DLWE d ( D R d ,σ 2 ;
c 2
R,d,q,D R d ,σ 1 q R,1,q,D R,σ 1 ⌉
⌊ ⌊ ⌉⌉ ⌊
( ) q p √ q
d
D p,q,1,d ). 这里, D p,q,1,d 对应的分布为: 取样 u ←- U R , 输出 · ·u . 注意到分布 D p,q,1,d 是 n· d · -半均匀
q p q 2p
d
分布, 采用本文的归约结果可知, DLWE d ( D R d ,σ 2 ;D p,q,1,d ) 问题的困难性可以由 DLWE d ( D R d ,σ ;U(R ))
R,1,q,D R,σ q
R,1,q,D R,σ 1 (
⌊ ⌉ )
√ q
问题的困难性来保证. 对应的参数关系是 σ 1 = O n· d · ·σ , σ 2 = O(σ). 为兼顾解密错误率和安全强度, 参
2p
数 p,q 相差的比特数一般为 O(1). 采用文献 [27] 的经验估计, 非对称 LWE 问题的困难性与误差参数约为
√
σ 1 ·σ 2 = O(n 1/2 ·d )·σ 的对称 LWE 问题的困难性相当. 因此, 当将本文的归约结果应用于 Kyber 类采用压缩公
1/2
1/4
钥的设计方式来设计的公钥加密方案时, 对应的理论归约损失约为 O(n 1/2 ·d ). 值得指出的是, 本文的归约方式对
( )
于参数 d (和 q) 的限制很小. 可以选择 d = O(1), 此时对应的理论归约损失约为 O n 1/2 .
我们采用文献 [4] 第 5.2 节的定理来估计采用上述设计方式的公钥加密方案 IND-CPA 安全性的理论归约损
k
失. 此时, DLWE d ( D R d ,σ 2 ;D p,q,1,d ) 问题的困难性可以由 DLWE k ( U(R );U(R ) ) 问题的困难性和
k
R,1,q,D R,σ 1 R,1,q,D R,σ q q
( ⌊ ⌉ )
√ q
d
2
d
DLWE d ( U(R );U(R )) 问题的困难性来保证. 这里, σ 1 = O n· d · ·σ+σ . 如果我们也选择 σ 2 = O(σ)
R,1,q,D R,σ 1 q q 2p
的话, 根据离散高斯的性质大致估计文献 [4] 中的熵不等式条件可以得到对应模 LWE 问题的秩至少应该满足
( )
d ⩾ O(k ·logq+logn+ω logλ ) (注意到即使是将 D R d ,σ 2 替换为随机均匀分布, 这个条件也应该满足). 因此严格来
讲, 文献 [4] 的归约结果不适用于 d = O(1) 的情形. 此外, 文献 [4] 的归约结果对于参数 q 以及秘密分布也有额外
的限制. 例如要求 q 为分裂性质良好的素数, 且要求秘密的分布模 qR 的每一个素理想均具有足够大的熵. 如果加
上这些限制, 文献 [4] 的归约结果将更加受限.
4 总 结
在本文中, 我们将 Hint-LWE 相关问题研究中的方法进行改进并应用到半均匀 LWE 问题的研究之中, 给出了
非均匀 LWE 问题更简单、更紧致的困难性归约. 具体来讲, 本文的归约方法几乎不受代数结构的影响, 可以一致
地应用到对应的欧氏格/环/模上的半均匀 LWE 问题的归约. 相比于已知的半均匀 LWE 问题的归约结果, 本文给
出的归约是保持对应 LWE 问题的维数的, 归约损失小且归约损失 (对应的 LWE 问题的误差所服从的离散高斯参
数) 与样本数等条件无关. 当将本文的归约应用到环 LWE 问题时, 对应的归约方法可以基于标准的环 LWE 问题
给出非均匀环 LWE 问题的困难性证明, 归约结论无需用到 DSPR 等额外的 (相对而言非标准的) 困难性假设.
References:
[1] Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proc. of the 37th Annual ACM SIGACT Symp. on
Theory of Computing. Baltimore: ACM, 2005. 84–93. [doi: 10.1145/1060590.1060603]
[2] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Gilbert H, ed. Proc. of the 29th Annual Int’l
Conf. on the Theory and Applications of Cryptographic Techniques. French: Springer, 2010. 1–23. [doi: 10.1007/978-3-642-13190-5_1]
[3] Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015, 75(3):
565–599. [doi: 10.1007/s10623-014-9938-4]
[4] Jia WJ, Zhang J, Xiang BW, Wang BC. Hardness of (M)LWE with semi-uniform seeds. Theoretical Computer Science, 2024, 994: