量子计算与密码分析专栏序言(中英文)

高 飞, 孙思维

1. 北京邮电大学网络与交换技术国家重点实验室, 北京 100876

2. 中国科学院大学密码学院, 北京 100049

相较经典计算理论, 量子计算是一种全新的计算模式, 是一项可能对传统技术体系产生冲击、进行重构的重大颠覆性技术创新. 量子计算在大整数分解、离散对数计算、密钥穷搜索等多个计算问题上展现出了显著优势, 一旦成规模的通用量子计算机问世, 将对一些密码体制构成严重的威胁. 这使得在量子计算模型下研究密码体制的安全性成为学术界、工业界、标准化组织和各国政府机构高度关注的重要领域. 实际上, 美国国家技术与标准研究院(NIST) 早在2016 年就正式发布了征集抗量子攻击公钥密码的公开邀请, 为向后量子密码迁移做出准备. 在我国, 量子科技也已上升为国家战略. “十四五” 期间, 我国将在量子信息领域实施一批科技重大项目.

在这一背景下, 为促进量子计算和密码分析的交叉研究和探索,《密码学报》组织了“量子计算与密码分析” 专栏, 展示了我国学者在基于量子计算的对称密码和公钥密码分析、量子电路的综合与优化以及量子攻击资源评估等方面的部分研究成果, 并综合介绍了国际国内抗量子计算对称密码研究的总体情况. 本专栏共收录6 篇论文, 其中包括1 篇综述, 分别简介如下:

综述论文《抗量子计算对称密码研究进展概述》, 针对抗量子计算对称密码研究的总体情况, 介绍了量子算法、量子安全模型、量子安全评估和抗量子对称密码设计等方面的研究进展, 归纳总结了各项成果之间的关联, 分析了当前研究中存在的问题, 并讨论了未来有待加强的发展方向.

论文《NTRU 公钥密码的量子算法攻击研究》, 提出了一种变体的Claw-Finding 算法, 并基于该算法给出了针对后量子公钥密码NTRU 在私钥搜索方面具有平方加速的量子攻击. 与Scott 在2015 年提出的基于Grover 算法的攻击相比, 本文的方法避免了强量子Oracle 的假设, 且在攻击中不需要维护指数大的列表.

论文《若干广义非平衡Feistel 结构的量子分析研究》, 研究了针对5 种广义非平衡Feistel 结构的量子攻击, 对n-cell 结构构造了n+1 轮量子区分器; 对New Structure I/III/IV 结构分别构造了6 轮/9轮/5 轮量子区分器; 对FBC-like 结构构造了3 轮量子区分器, 并利用Simon 算法对这5 种分组密码结构进行了量子区分攻击. 进一步, 将Simon 算法和Grover 算法相结合对n-cell 结构、New Structure I/III/IV 结构和FBC-like 结构进行了量子密钥恢复攻击, 并分析了攻击的时间复杂度.

论文《改进的五轮Grøstl-512 的量子碰撞攻击》, 通过以一般振幅放大算法替代Grover 算法, 改进了2020 年亚密会上由董晓阳等提出的针对5 轮Grøstl-512 哈希函数的量子碰撞攻击. 改进攻击的时间复杂度较原攻击降低了224倍, 并与原攻击一样不需要大量的量子随机存储(quantum random access memory, qRAM).

论文《MIBS 算法量子密码分析》, 在可以访问分组密码MIBS 的量子Oracle 的前提下, 利用MIBS轮函数和线性变换的性质, 对MIBS 进行了7 轮量子密钥恢复攻击. 这是Leander 和May 提出的Grover-meet-Simon 方法的又一个应用.

论文《SM4 算法的量子实现》, 基于对表面码特性及容错量子计算的综合考虑, 以量子比特数、量子电路深度和深度宽度乘积为指标, 提出了我国商密标准SM4 算法量子电路的综合与优化方法, 并基于Grover 算法设计了对SM4 进行穷举攻击的量子电路, 评估了该攻击所需的量子资源.

希望本专栏能够引起更多国内学者关注量子计算与密码分析的交叉研究, 并促进相关领域学者的合作交流.

Compared with the theory of classical computation, quantum computation is a brand-new computing paradigm, which brings a major influential technological innovation that may have an impact on and reconstruct the traditional computing technology. Quantum computing has shown significant advantages in many computation problems such as large integer factorization, discrete logarithm, and exhaustive key search. Once a large-scale general-purpose quantum computer is made available, it will pose a serious of security threats to certain cryptosystems. This makes studying the security of cryptosystems under the quantum computing model an important area, and would attact much attention from academia, industry, standardization organizations, and government agencies. In fact, as early as 2016, the National Institute of Standards and Technology (NIST) officially issued a public call for proposals of public-key post-quantum cryptographic algorithms, preparing for the transition to the post-quantum era. In China, quantum technology has also become a national strategy. During the period of “14th Five-Year Plan” , China will support a number of major scientific and technological projects in the field of quantum information.

In this context,in order to promote the interdisciplinary research and exploration of quantum computing and cryptanalysis, the Journal of Cryptologic Research organized the special column “Quantum Computing and Cryptoanalysis”, demonstrating some achievements of Chinese scholars in the cryptanalysis of symmetric-key and public-key primitives based on quantum computing, synthesis and optimization of quantum circuits, and evaluation of quantum attack resources. This special column includes six papers, which are briefly introduced as follows.

The paper titled“A Survey on Quantum-Secure Symmetric Cryptography”introduces the research development of quantum algorithms, quantum security models, quantum security evaluation, and the design of quantum-resistant symmetric-key primitives, in view of the overall status of the research on post-quantum symmetric-key cryptology. It summarizes the relations among various results, points out some existing problems to be solved, and discusses the development directions that need to be strengthened in the future.

The paper titled “Research on Quantum Algorithm Attack of NTRU Public Key Cryptography”proposes a variant of the Claw-Finding algorithm, based on which a quantum attack on the postquantum public-key cryptographic scheme NTRU with quadratic speedup in searching the private key is given. Compared with the attack proposed by Scott in 2015 that relies on Grover’s algorithm, the new method avoids the assumption of strong quantum oracle and does not need to maintain a table in exponential size.

The paper titled “Quantum Cryptanalysis on Some Generalized Unbalanced Feistel Networks”studies quantum attacks on five types of generalized Feistel networks. For then-cell network, an(n+ 1)-round quantum distinguisher is constructed; for the New Structure I/III/IV, 6/9/5-round quantum distinguishers are constructed; for FBC-like structure,a 3-round distinguisher is constructed.With Simon’s algorithm, quantum distinguishing attacks are performed targeting these five types of structures. Moreover, key-recovery attacks are performed on then-cell structure, the New Structure I/III/IV, and the FBC-like network respectively, and the time complexities are analyzed.

The paper titled “Improved Quantum Collision Attack on 5-Round Grøstl-512” improves the quantum collision attack on the 5-round Grøstl-512 proposed by Dong et al. at ASIACRYPT 2020.The improvement is made by substituting Grover’s algorithm with the generic quantum amplitude amplification algorithm. The improved attack reduces the time complexity by a factor of 224and does not require a large amount of quantum random access memories as required in the original attack.

The paper titled “Quantum Cryptanalysis of MIBS” gives a quantum key-recovery attack on the 7-round MIBS by exploiting the properties of the round function and the linear transformation of MIBS with the assumption that the attack has access to the on-line quantum oracle of MIBS. This is another application of the Grover-meet-Simon technique proposed by Leander and May.

The paper titled “Quantum Implementation of SM4” proposes techniques of synthesis and optimization of the quantum circuit of SM4 with respect to the number of qubits, the circuit depth, and the depth-times-width metric, where the characteristics of surface code and fault tolerance are taken into account. Moreover, the quantum circuit for conducting an exhaustive key search attack on SM4 is constructed based on Grover’s algorithm and the quantum resources for carrying out such an attack are evaluated.

Hope that this special column will attract more scholars to pay attention to the research of quantum computing and cryptanalysis, and promote collaboration and discussion among researchers in related fields.