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

高 飛, 孫思維

1. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100876

2. 中國(guó)科學(xué)院大學(xué)密碼學(xué)院, 北京 100049

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

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

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

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

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

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

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

論文《SM4 算法的量子實(shí)現(xiàn)》, 基于對(duì)表面碼特性及容錯(cuò)量子計(jì)算的綜合考慮, 以量子比特?cái)?shù)、量子電路深度和深度寬度乘積為指標(biāo), 提出了我國(guó)商密標(biāo)準(zhǔn)SM4 算法量子電路的綜合與優(yōu)化方法, 并基于Grover 算法設(shè)計(jì)了對(duì)SM4 進(jìn)行窮舉攻擊的量子電路, 評(píng)估了該攻擊所需的量子資源.

希望本專欄能夠引起更多國(guó)內(nèi)學(xué)者關(guān)注量子計(jì)算與密碼分析的交叉研究, 并促進(jìn)相關(guān)領(lǐng)域?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.