半均匀LWE问题的紧致归约
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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


Tighter Reductions of LWE Problems with Semi-uniform Seeds
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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 seedss 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.

    参考文献
    相似文献
    引证文献
引用本文

王洋,王明强.半均匀LWE问题的紧致归约.软件学报,2025,36(10):4405-4416

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2024-06-25
  • 最后修改日期:2024-09-05
  • 录用日期:
  • 在线发布日期: 2025-01-20
  • 出版日期: 2025-10-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号