量子計算與密碼分析專欄序言(中英文)

高 飛, 孫思維

1. 北京郵電大學網(wǎng)絡與交換技術國家重點實驗室, 北京 100876

2. 中國科學院大學密碼學院, 北京 100049

相較經(jīng)典計算理論, 量子計算是一種全新的計算模式, 是一項可能對傳統(tǒng)技術體系產(chǎn)生沖擊、進行重構的重大顛覆性技術創(chuàng)新. 量子計算在大整數(shù)分解、離散對數(shù)計算、密鑰窮搜索等多個計算問題上展現(xiàn)出了顯著優(yōu)勢, 一旦成規(guī)模的通用量子計算機問世, 將對一些密碼體制構成嚴重的威脅. 這使得在量子計算模型下研究密碼體制的安全性成為學術界、工業(yè)界、標準化組織和各國政府機構高度關注的重要領域. 實際上, 美國國家技術與標準研究院(NIST) 早在2016 年就正式發(fā)布了征集抗量子攻擊公鑰密碼的公開邀請, 為向后量子密碼遷移做出準備. 在我國, 量子科技也已上升為國家戰(zhàn)略. “十四五” 期間, 我國將在量子信息領域?qū)嵤┮慌萍贾卮箜椖?

在這一背景下, 為促進量子計算和密碼分析的交叉研究和探索,《密碼學報》組織了“量子計算與密碼分析” 專欄, 展示了我國學者在基于量子計算的對稱密碼和公鑰密碼分析、量子電路的綜合與優(yōu)化以及量子攻擊資源評估等方面的部分研究成果, 并綜合介紹了國際國內(nèi)抗量子計算對稱密碼研究的總體情況. 本專欄共收錄6 篇論文, 其中包括1 篇綜述, 分別簡介如下:

綜述論文《抗量子計算對稱密碼研究進展概述》, 針對抗量子計算對稱密碼研究的總體情況, 介紹了量子算法、量子安全模型、量子安全評估和抗量子對稱密碼設計等方面的研究進展, 歸納總結了各項成果之間的關聯(lián), 分析了當前研究中存在的問題, 并討論了未來有待加強的發(fā)展方向.

論文《NTRU 公鑰密碼的量子算法攻擊研究》, 提出了一種變體的Claw-Finding 算法, 并基于該算法給出了針對后量子公鑰密碼NTRU 在私鑰搜索方面具有平方加速的量子攻擊. 與Scott 在2015 年提出的基于Grover 算法的攻擊相比, 本文的方法避免了強量子Oracle 的假設, 且在攻擊中不需要維護指數(shù)大的列表.

論文《若干廣義非平衡Feistel 結構的量子分析研究》, 研究了針對5 種廣義非平衡Feistel 結構的量子攻擊, 對n-cell 結構構造了n+1 輪量子區(qū)分器; 對New Structure I/III/IV 結構分別構造了6 輪/9輪/5 輪量子區(qū)分器; 對FBC-like 結構構造了3 輪量子區(qū)分器, 并利用Simon 算法對這5 種分組密碼結構進行了量子區(qū)分攻擊. 進一步, 將Simon 算法和Grover 算法相結合對n-cell 結構、New Structure I/III/IV 結構和FBC-like 結構進行了量子密鑰恢復攻擊, 并分析了攻擊的時間復雜度.

論文《改進的五輪Gr?stl-512 的量子碰撞攻擊》, 通過以一般振幅放大算法替代Grover 算法, 改進了2020 年亞密會上由董曉陽等提出的針對5 輪Gr?stl-512 哈希函數(shù)的量子碰撞攻擊. 改進攻擊的時間復雜度較原攻擊降低了224倍, 并與原攻擊一樣不需要大量的量子隨機存儲(quantum random access memory, qRAM).

論文《MIBS 算法量子密碼分析》, 在可以訪問分組密碼MIBS 的量子Oracle 的前提下, 利用MIBS輪函數(shù)和線性變換的性質(zhì), 對MIBS 進行了7 輪量子密鑰恢復攻擊. 這是Leander 和May 提出的Grover-meet-Simon 方法的又一個應用.

論文《SM4 算法的量子實現(xiàn)》, 基于對表面碼特性及容錯量子計算的綜合考慮, 以量子比特數(shù)、量子電路深度和深度寬度乘積為指標, 提出了我國商密標準SM4 算法量子電路的綜合與優(yōu)化方法, 并基于Grover 算法設計了對SM4 進行窮舉攻擊的量子電路, 評估了該攻擊所需的量子資源.

希望本專欄能夠引起更多國內(nèi)學者關注量子計算與密碼分析的交叉研究, 并促進相關領域?qū)W者的合作交流.

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.