| 摘要: |
| 量子计算的快速发展对现有经典密码体制的安全性造成了严峻的威胁。尤其是在Shor算法的推动下，现有的基于大数分解和离散对数难题构建的公钥密码体制面临显著威胁；与此同时，Grover算法、Simon算法、Bernstein-Vazirani算法等一系列量子算法则为攻击对称密码体制提供全新的技术路径。目前量子密码分析领域的研究取得了显著进展，各种改进的量子算法被开发并有效地应用于密码分析领域，在降低查询复杂度、最小化存储复杂度、优化量子资源利用以及在其它实际应用等方面表现出显著的潜力。本文从理论逻辑层面概述了该领域近年来量子算法的发展、其资源的优化及其在密码分析的应用。然而，尽管取得了这些理论性突破，但量子计算仍受物理定律和当前技术的限制，其物理实现仍然面临着巨大挑战。目前，离子阱量子计算机和超导量子计算机被认为是最具潜力的量子计算实现方案。本文聚焦最具工程化潜力的离子阱量子计算机，介绍了存在的固有物理局限性如何限制量子计算并影响其整体能力。该领域的研究尚未形成完整的体系，本文对现有的研究成果进行总结，并基于此从新的视角提出一种评估框架，从实际运行时间下限的角度评估量子算法在离子阱量子计算机中对经典密码体制的攻击能力。该框架可为设计具备实际量子安全性的密码算法提供关键时间裕度参数和理论支持。最后，总结了该快速发展领域中一些亟待解决的问题以及未来的发展方向。 |
| 关键词: 量子计算 经典密码体制 离子阱量子计算机 量子算法 攻击能力 量子安全 |
| DOI： |
| 投稿时间：2025-05-19修订日期：2025-08-11 |
| 基金项目: |
|
| Quantum Attack Capability Assessment Against Classical Cryptosystems: From Theory to Ion-Trap Implementation |
|
xiaqiqing, gaoneng, yangli
|
| (Institute of Information Engineering, Chinese Academy of Sciences) |
| Abstract: |
| The rapid development of quantum computing poses a serious threat to the security of existing classical cryptosystems. In particular, driven by Shor's algorithm, existing public-key cryptosystems based on the hardness of large prime factorization and discrete logarithm problems face significant threats. Meanwhile, a series of quantum algorithms, such as Grover's algorithm, Simon's algorithm, Bernstein-Vazirani algorithm, and so on, provide new technical avenues for attacking symmetric cryptosystems. At present, research in the field of quantum cryptanalysis has achieved significant advancements. A variety of improved quantum algorithms have been developed and effectively applied to the cryptanalysis field, demonstrating notable capabilities in reducing query complexity, minimizing storage complexity, and optimizing the use of quantum resources, among other improvements in practical applications. This paper provides a comprehensive overview of recent advances in quantum algorithms, resource optimization, and their application in cryptanalysis from a theoretical logic level. However, despite these theoretical breakthroughs, quantum computing is constrained by the laws of physics and current technology, and its physical implementation still faces significant challenges. Ion-trap quantum computers and superconducting quantum computers are the most promising quantum computing implementation schemes. This paper focuses on the ion-trap quantum computer, which has the greatest engineering potential, and introduces how existing inherent physical limitations constrain quantum computing and influence its overall capabilities. Research in this field has not yet formed a complete system. This paper summarizes these existing research results and proposes an assessment framework from a novel perspective to assess the attack capability of quantum algorithms against classical cryptosystems via ion-trap quantum computers from the perspective of the lower bound of actual running time. This framework can provide key time margin parameters and theoretical support for the design of cryptographic algorithms with quantum security. Finally, several urgent problems and potential directions for future research in this rapidly evolving field are summarized. |
| Key words: quantum computing classical cryptosystem ion-trap quantum computer quantum algorithm attack capability quantum security |
