格上困难问题量子求解算法综述
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP309

基金项目:

国家自然科学基金 (62472438, 62172433, 62172435); 国家重点研发计划 (2022YFB3102900); 河南省自然科学基金 (242300421414)


Survey on Quantum Algorithms for Solving Hard Problems in Lattice
Author:
Affiliation:

Fund Project:

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

    随着基于格的后量子密码体制快速发展, 格上困难问题求解算法已成为评估后量子密码方案安全性的关键技术. 当前, 经典计算模型下已存在枚举、筛法、格基约化等格上困难问题求解算法, 同时量子筛法、量子枚举等格上困难问题量子求解算法正逐步引起关注. 围绕后量子密码研究中涉及的格上困难问题, 对格上困难问题量子求解算法给出综述. 首先, 分类整了格上困难问题量子求解算法研究现状. 其次, 梳理各类格上困难问题量子求解算法的设计思路和应用的量子计算技术, 并总结各类格上困难问题量子求解算法的复杂度. 最后, 展望格上困难问题量子求解算法的未来发展趋势.

    Abstract:

    With the rapid development of Lattice-based post-quantum cryptography, algorithms for hard problems in Lattices have become an essential tool for evaluating the security of post-quantum cryptographic schemes. Algorithms such as enumeration, sieve, and Lattice basis reduction have been developed under the classical computing model, while quantum algorithms for solving hard problems in Lattices, such as quantum sieve and quantum enumeration, are gradually attracting attention. Although Lattice problems possess post-quantum properties, techniques such as quantum search can accelerate a range of Lattice algorithms. Given the challenges involved in solving hard problems in Lattices, this study first summarizes and analyzes the research status of quantum algorithms for such problems and organizes their design principles. Then, the quantum computing techniques applied in these algorithms are introduced, followed by an analysis and comparison of their computational complexities. Finally, potential future developments and research directions for quantum algorithms addressing Lattice-based hard problems are discussed.

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

曹金政,罗向阳,陈晓峰,程庆丰.格上困难问题量子求解算法综述.软件学报,2026,37(1):398-424

复制
相关视频

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

京公网安备 11040202500063号