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

P. 8

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(10):4405−4416 [doi: 10.13328/j.cnki.jos.007388] [CSTR: 32375.14.jos.007388] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
半均匀 LWE 问题的紧致归约

王洋 1,2 , 王明强 1

1
(山东大学数学学院, 山东济南 250100)
2
(密码科学技术技术全国重点实验室, 北京 100878)
通信作者: 王明强, E-mail: wangmingqiang@sdu.edu.cn

摘要: 在部分实用化的格密码协议设计和应用中, 需要用到公开矩阵服从特定分布的、非均匀的 LWE 问题的困
难性来证明相应密码体制的安全性. 近期, 有研究工作给出了半均匀 LWE 问题的具体定义, 并采用类似证明熵
LWE 问题困难性的归约路线证明了欧氏格/理想格/模格上半均匀 LWE 问题的困难性. 但是, 已知的归约方法 (在
维数和误差分布的高斯参数等方面) 会引入较大的归约损失, 同时需要引入额外的、非标准的困难性假设来证明
环上的半均匀 LWE 问题的困难性. 利用 Hint-LWE 问题困难性的归约技巧, 给出了半均匀 LWE 问题困难性更紧
致的归约. 采用的归约方法几乎不受代数结构的影响, 可以统一地应用到欧氏格/理想格/模格上定义的半均匀 LWE
问题. 可以基于标准的 LWE 假设证明对应欧氏格/理想格/模格上的半均匀 LWE 问题的困难性而无需引入任何额
外的非标准困难性假设. 归约结果保持相应 LWE 问题的维数不变, 且归约过程中对应 LWE 问题的误差高斯参数
的归约损失较小.
关键词: 基于格的密码学; 格中困难问题的归约; 半均匀 LWE 问题; Hint-LWE 问题; 离散高斯分布
中图法分类号: TP301

中文引用格式: 王洋, 王明强. 半均匀LWE问题的紧致归约. 软件学报, 2025, 36(10): 4405–4416. http://www.jos.org.cn/1000-9825/
7388.htm
英文引用格式: Wang Y, Wang MQ. Tighter Reductions of LWE Problems with Semi-uniform Seeds. Ruan Jian Xue Bao/Journal of
Software, 2025, 36(10): 4405–4416 (in Chinese). http://www.jos.org.cn/1000-9825/7388.htm
Tighter Reductions of LWE Problems with Semi-uniform Seeds
1,2
WANG Yang , WANG Ming-Qiang 1
1
(School of Mathematics, Shandong University, Jinan 250100, China)
2
(State Key Laboratory of Cryptology, Beijing 100878, China)
Abstract: In certain designs and applications of practical lattice-based cryptography, the use of a specialized variant of LWE problems,
where the public matrix is sampled from a non-uniform distribution, is required to establish the securities of corresponding cryptographic
schemes. Recently, the formal definition of LWE problems with semi-uniform seeds was introduced in some work, in which the hardness
of Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds was proved through reduction roadmaps similar to
those employed in the hardness proofs of entropic LWE problems. However, known reduction introduces significant losses in the Gaussian
parameters of errors and dimensions. Moreover, additional non-standard assumptions are required to demonstrate the hardness of LWE
problems with semi-uniform seeds over rings. In this study, a tighter reduction is proposed for LWE problems with semi-uniform seeds by
incorporating modified techniques from the hardness proofs of Hint-LWE problems. The proposed reduction is largely unaffected by the
algebraic structures of the underlying problems and can be uniformly applied to Euclidean, ideal, and module lattice-based LWE problems

* 基金项目: 国家重点研发计划 (2021YFB3100200); 保密通信全国重点实验室稳定支持计划 (2024, WD202402); 密码科学技术全国重点
实验室开放课题 (MMKFKT202207); 山东省自然科学基金 (ZR2022QF039)
本文由“抗量子密码与区块链应用”专题特约编辑翁健教授、祝烈煌教授、赵运磊教授推荐.
收稿时间: 2024-06-25; 修改时间: 2024-09-05; 采用时间: 2024-12-30; jos 在线出版时间: 2025-01-20
CNKI 网络首发时间: 2025-08-12

3 4 5 6 7 8 9 10 11 12 13