软件学报

作者：王洋，王明强

单位：王洋，山东大学 数学学院, 山东 济南 250100;密码科学技术技术全国重点实验室, 北京 10087811,王明强，山东大学 数学学院, 山东 济南 25010002

关键词：基于格的密码学;格中困难问题的归约;半均匀LWE问题;Hint-LWE 问题;离散高斯分布

基金：国家重点研发计划(2021YFB3100200); 保密通信全国重点实验室稳定支持计划(2024, WD202402); 密码科学技术全国重点实验室开放课题(MMKFKT202207); 山东省自然科学基金(ZR2022QF039)

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

来源：2025年第10期

《软件学报》期刊编辑部

查看软件学报杂志2025年第10期