| 摘要: |
| 在部分实用化的格密码协议设计和应用中, 需要用到公开矩阵服从特定分布的、非均匀的LWE问题的困难性来证明相应密码体制的安全性. 近期, 有研究工作给出了半均匀LWE问题的具体定义, 并采用类似证明熵LWE问题困难性的归约路线证明了欧氏格/理想格/模格上半均匀LWE问题的困难性. 但是, 已知的归约方法(在维数和误差分布的高斯参数等方面) 会引入较大的归约损失, 同时需要引入额外的、非标准的困难性假设来证明环上的半均匀LWE问题的困难性. 利用Hint-LWE问题困难性的归约技巧, 给出了半均匀LWE问题困难性更紧致的归约. 采用的归约方法几乎不受代数结构的影响, 可以统一地应用到欧氏格/理想格/模格上定义的半均匀LWE问题. 可以基于标准的LWE假设证明对应欧氏格/理想格/模格上的半均匀LWE问题的困难性而无需引入任何额外的非标准困难性假设. 归约结果保持相应LWE问题的维数不变, 且归约过程中对应LWE问题的误差高斯参数的归约损失较小. |
| 关键词: 基于格的密码学 格中困难问题的归约 半均匀LWE问题 Hint-LWE 问题 离散高斯分布 |
| DOI：10.13328/j.cnki.jos.007388 |
| 分类号:TP301 |
| 基金项目:国家重点研发计划(2021YFB3100200); 保密通信全国重点实验室稳定支持计划(2024, WD202402); 密码科学技术全国重点实验室开放课题(MMKFKT202207); 山东省自然科学基金(ZR2022QF039) |
|
| Tighter Reductions of LWE Problems with Semi-uniform Seeds |
|
WANG Yang1,2, WANG Ming-Qiang1
|
|
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 with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need for any additional non-standard assumptions. Furthermore, the dimension of the corresponding LWE problems remains unchanged, and the reduction introduces only minimal losses in Gaussian parameters of errors. |
| Key words: lattice-based cryptography reduction of lattice-based problem LWE problems with semi-uniform seeds Hint-LWE problem discrete Gaussian distribution |
