對稱密碼體制的量子攻擊

馮曉寧，吳洪宇

哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001

美國物理學家費曼在1982 年提出了量子計算的概念[1]，該技術引起了世界各國的廣泛關注。量子計算在大整數分解、離散對數計算等多個計算問題上展現出了顯著優勢。量子密碼分析學（亦稱為量子攻擊）是量子計算與密碼分析相交叉的新學科，具有經典密碼分析不能擁有的資源及速度優勢。本文主要介紹了量子密碼分析學中針對于傳統密碼體制中對稱密碼體制的部分，即量子（對稱）密碼分析學。并把使用量子算法進行密碼分析的過程稱為量子環境設置，把未使用量子算法進行密碼分析的過程稱為經典或傳統環境設置。

量子計算對非對稱密碼分析學產生了深遠影響。Shor 算法[2]和Grover 算法[3]作為兩種經典的量子計算方法，開啟了量子密碼分析的先河。1994 年，Shor 提出了在多項式時間內分解大整數的算法[2]。大整數分解在傳統計算機中被視為經典困難問題，很多非對稱密碼體制就是為了解決這種困難問題而設計的，比如RSA 加密算法[4]。Shor 算法理論上對傳統密碼造成了巨大威脅[5]。時隔20 年，當初提出的理論算法已變成現實，量子計算機已經可以分解13 位的大整數[6]，表明量子計算在破解非對稱密碼方面已經取得了實質性的突破。

在對稱密碼體制中，量子計算的影響是有限的。Grover 算法[3]應用于窮舉攻擊，可以產生二次加速的效果[7]。盡管Grover 算法在密碼分析領域產生了廣泛的影響，但除Grover 算法之外，絕大多數量子算法只能提供亞指數或多項式級別的加速，在對稱密碼分析方面的實際影響尚不明顯。這也導致了密碼學領域一個長期存在的共識：簡單地將傳統對稱密碼算法的密鑰長度加倍，可確保對稱密碼算法在量子計算模型下的安全性。

美國國家科學院關于量子計算的報告中指出：可能存在一些迄今未知但性能遠超Grover算法的量子攻擊。許多密碼學家正在探索比Grover 算法更為高效的密碼分析手段。例如，量子差分密碼分析將經典差分密碼分析的環境置為量子環境，旨在得到相比于經典情況下二次甚至指數級別的加速[8]。密碼學家在諸多量子密碼分析方面取得了長足的進步，有些甚至能夠在多項式時間內破壞許多對稱密碼系統。

1 研究脈絡及分類

近年來，涉及量子對稱密碼分析學的研究成果顯著增多，多數研究都在探索比傳統密碼分析所需資源更少的量子密碼分析方法。對稱密碼體制的量子密碼分析主流研究有兩個重要特點：1）絕大多數量子攻擊基于量子選擇明文攻擊模型（quantum chosen plaintext attack,qCPA）[9]。作為一個通用的攻擊模型，一旦實施了攻擊，則說明對稱密碼體制在量子設置下是不安全的。2）有兩種逐步上升的研究趨勢，一種是通過將經典密碼分析算法轉換為量子設置進行攻擊，另一種是以低資源量子消耗為目標設計量子密碼分析算法[10]。這兩個研究趨勢說明，在經典設置下可能無效的攻擊方法，但在量子設置下可能會有效。為了更深入地理解對稱密碼體制量子攻擊的研究歷史沿革以及各文獻之間的關系，圖1 展示本文重點文獻關系。其中箭頭表示研究的遞進關系，虛線表示同類研究，紅色表示高被引用文章，藍色表示出現的重點或有前景的攻擊方法。

圖1 對稱密碼體制量子攻擊的研究脈絡Figure 1 Research context of quantum attack on symmetric cryptosystem

根據上述研究脈絡，本文將現有對稱密碼體制的量子攻擊劃分為量子周期攻擊、Grover算法相關攻擊及量子差分攻擊，如圖2 所示。量子周期攻擊以Simon 算法為基礎，主要關注Simon 算法中的弱化條件情況。除此之外，本文介紹了基于Simon 算法的周期構建攻擊，以及Simon 算法的離線計算方式。在Grover 算法相關攻擊的研究中，主要介紹Grover meets Simon 算法、Grover 算法的窮舉攻擊以及近來基于Grover 算法中備受關注的量子中間相遇攻擊。量子差分算法是基于B-V 算法進行研究的，隨后本文分兩階段進行詳細闡述。

圖2 對稱密碼體制的量子攻擊分類圖Figure 2 Classification diagram of quantum attacks on symmetric cryptosystems

2 量子周期攻擊

2.1 Simon 算法的研究

目前，Simon 算法[11]已經成為一種基礎性的量子密碼分析算法。為獲取布爾函數的周期，經典算法需要指數式查詢復雜度。使用Simon 算法獲得布爾函數周期的步驟如下：首先通過多次使用Simon 算法獲得n-1 個線性獨立的變量，然后使用經典算法（如高斯消除算法）解個數為n-1 的二值線性方程組。使用Simon 算法的主要優勢在于它能夠在多項式查詢復雜度下獲得函數f(x) 的周期。

對Simon 承諾條件弱化情形的研究起步較早。文獻[12] 說明了Simon 函數的碰撞與測量結果之間的確切關系，證明了在大多數隨機情況下，額外的碰撞不會導致Simon 算法攻擊的復雜性顯著增加。Simon 函數應避免碰撞過大，現在大多數基于Simon 算法的密碼分析都使用以下的沖突假設

式中：max 為取最大值函數；Px為概率；ε(f,s) 為量化函數f(x) 距離Simon 承諾遠近的參數。ε(f,s) 與Simon 算法的失效概率有著緊密聯系。ε(f,s) 越接近1，則函數發生沖突的概率越大，Simon 算法的失效概率越大；ε(f,s) 越接近0，函數越接近一個完美的周期函數，Simon算法的失效概率越低。給出ε(f,s)≤1/2 的假設意味著使用Simon 函數可以在O(n) 次的查詢后找到周期s。文獻[12] 的進一步結論是，經過cn次查詢后，可返回計算周期s的概率為1-2n×(0.645 4)cn。特殊地，當取c=4，n=8 時，得到周期s的概率約為0.998。即Simon算法作為子程序（重復地執行4n次）將保證成功概率接近1。

文獻[13] 對上述的結論進行了泛化：定義了4 個擴展的布爾隱藏周期問題，利用函數的周期個數以及是否具有額外碰撞這兩個屬性進行劃分，擴展了4 種弱化的Simon 算法的承諾條件，經證明這4 種弱化的承諾條件均可以使用Simon 算法進行多項式求解。弱化承諾下Simon 算法仍有很多其他相關的重要性質，文獻[14] 發現在弱化承諾下Simon 算法具有以下重要性質：若一個函數存在周期，則該函數只存在唯一周期的概率接近1。文獻[15] 指出只需要前向蘊含的承諾x=y⊕s?f(x)=f(y) 就能夠利用Simon 算法獲得獨立向量。弱化承諾下Simon 算法在對稱密碼分析中具有很強的實用性，促使量子周期攻擊快速發展。

2.2 基于周期構建的攻擊

量子周期攻擊是利用解布爾函數周期問題的量子算法進行密碼分析的攻擊方法。Simon算法完成量子周期攻擊的主要思路是：在目標密碼體制中構建函數，該函數即為布爾隱藏周期問題中的函數f，通過結合Simon 算法和解傳統方程組的方法來確定函數的周期，進而對指定密碼體系進行分析。

文獻[16] 利用Simon 算法實現了開創性的量子密碼分析。其中展示的攻擊方法是利用量子疊加模型在O(n) 的量子時間復雜度下構建了一個區分器。隨后，文獻[17] 通過構建Even-Mansour 密碼體制上的周期函數實施了量子周期攻擊，獲取了Even-Mansour 密碼體制的密鑰，表明Even-Mansour 密碼體制是不安全的。文獻[15] 利用Simon 算法對固定長度密碼塊鏈消息認證碼（cipher block chaining message authentication code,CBC-MAC）進行了偽造攻擊，能夠為以前未查詢過的消息生成有效的標簽。文獻[18] 所構建的函數f(x)={Ex(m),Ex⊕s(m)} 周期為s，而s正好是相關密鑰攻擊模型中需要尋找的密鑰K。

使用Simon 周期構建可形成量子滑動攻擊。文獻[19] 針對替換-置換網絡（substitutionpermutation network,SPN）和Feistel 密鑰簇，在經典滑動攻擊的基礎上，根據不同的滑動類型（如扭曲滑動，互補滑動和鏡像滑動），提出了較為完整的量子滑動攻擊。這種量子滑動攻擊的主要思路是：使用經典滑動攻擊滿足的滑動屬性構建Simon 函數，構建的周期s中包含所尋找的密鑰值K。文獻[20] 使用量子滑動攻擊對2/4K-Feistel 和2/4K-DES 進行密碼分析，相比經典的滑動攻擊，該方法在時間復雜度上獲得了指數級的加速。

文獻[21] 給出了一種在旋轉密碼塊結構上構建周期函數的新方法。對于可調整分組密碼，固定t0t1，構建函數f(x)=Ek(x⊕h(t0))⊕h(t0)⊕Ek(x⊕h(t1))⊕h(t1)，此函數的周期為s=h(t0)⊕h(t1)。文獻[22] 提出了一種自動搜索周期函數的方法，其主要思想是將計算復雜度中的電路理論引入自動測試中。這種方法涉及使用一系列電路來表示對應密碼體制中的合理函數，然后測試所有可能的電路配置來確定這些函數的周期性特征。通過這種自動化方法結合Simon 算法，實施了有效密鑰恢復攻擊。

在2017 年的歐洲密碼學會議上，文獻[23] 介紹了一種新策略來對抗文獻[21] 中描述的攻擊方法。這種策略建議用更復雜的運算方法替換傳統的異或運算，以增強安全性。鑒于效率和實現方案的均衡，常見的替換方案是模加運算。文獻[23] 說明此改進可以抵抗量子選擇明文攻擊。文獻[24] 對Kuperberg 算法進行了改進，顯著降低了針對Poly1305（使用模加運算的加密算法）的攻擊成本。相較于通用攻擊的復雜度為，這種改進將復雜度降至，顯著提高了效率。

2.3 離線計算方式的攻擊

在特定的攻擊場景中，假設敵方只能通過傳統（經典）方式訪問加密體系，這種假設被稱為離線計算方式。文獻[25] 對Grover meets Simon 算法進行了改進，并提出了離線Simon 算法。這種算法是Q1 模型下的一種Simon 算法，適用于在有限條件下進行加密分析。算法的主要思路是利用目標密碼體制g以及密碼體制中的公開函數f構造函數g★f，在目標體制密碼g上做經典查詢得到量子態|g〉。通過對f的量子疊加查詢得到g★f，在g★f上應用并行化的Simon 算法判定g★f是否具有周期性：如果g★f顯示出周期性，則表明找到了正確的密鑰。在這種情況下，可以利用Grover 算法搜索正確密鑰。文獻[26] 對離線Simon 算法進行了更廣泛的推廣，指出g與f的結合方式不必局限于異或的方式。同時，g也不需要僅限于排列函數。上述離線計算方式以高概率尋找到正確密鑰和周期值，具有如下定理：當攻擊者具有對g的經典查詢權限時，離線Simon 算法對g進行了O(2n) 次經典查詢，時間復雜度為O((n3+nTf)2m/2)，其中Tf表示量子查詢一次f的時間，m是Grover meets Simon 算法中的常數。

在實現離線計算方式的算法中，主要難點在于正確選擇并組合g和f。文獻[27] 在文獻[25] 的基礎上使用離線計算方式構造對哈希計數器的新攻擊。文獻[28] 給出了Simon 離線計算方式的第1 個完整實現，并估計了多種輕量級密碼體制的攻擊成本。文獻[29] 在對移動通信網中的Milenage 算法集進行量子密碼分析時，實現了離線Simon 算法對相關密鑰分析進行加速。

3 Grover 算法相關攻擊的研究

Grover 算法是典型的量子搜索算法，可解決無序搜索問題。Grover 算法作為一種高性能量子搜索算法，實現了對經典搜索算法的二次加速，在密碼分析領域中備受矚目。

3.1 Grover meets X 算法

Grover 算法能夠與其他量子算法進行結合并作用在量子對稱密碼分析中，這一類算法被稱為Grover meets X 算法，其中X 指結合的量子算法。將Grover 算法整合到密碼分析算法中被視為一種臃腫的操作。許多研究者應用了與Grover 算法具有等效的放大器定理：設A是在量子比特上無測量的量子算法，量子算法B:{0,1}q→{0,1} 是量子算法A的分類器，將A作用的結果分成0 和1，分類器B判定態A|0〉為1 的成功概率為p，定義k=，sin2(θ)=p，酉矩陣Q=Q(A,B)=-AS0A-1SB，S0僅在|0〉態上起作用，那么經過k次迭代QkA|0〉，測量為1 的概率至少為max{1-p,p}。其中酉矩陣SB定義為

式中：B為量子算法的分類器；|x〉為酉矩陣SB作用的量子態。文獻[30] 證明了白化密鑰不會增加qCPA 下的安全性，提出一種Grover 和Simon 融合的量子算法，稱此算法為Grover meets Simon 算法。此算法依賴延遲測量法則[31]和并行化Simon 算法的技術，形成一種邏輯上的等價：當Grover 算法猜測正確的密鑰值時，所定義的函數擁有一個周期s，且這個周期就是白化密鑰的一部分。將融合算法應用于具有白化密鑰的分組密碼時，僅使用Grover 算法進行給定分組密碼的密鑰恢復攻擊，其復雜度等同于使用Grover meets Simon 算法對白化密鑰分組密碼進行密鑰恢復攻擊的復雜度。Grover meets Simon 算法對F進行O((n+m)2m/2)次量子查詢，時間復雜度為O((n+m)32m/2)，以常數概率發現正確密鑰和周期值。

Grover meets Simon 算法對后續研究者產生了深遠的影響。文獻[32] 利用Grover meets Simon 算法實施對埃文-曼蘇爾之和（sum of Even-Mansour,SoME）的密鑰恢復攻擊。針對文獻[32] 中提出的攻擊方法，攻擊效果在某些SoME 變體中不夠明顯的問題，文獻[33] 進一步討論了SoME 密碼體制變體攻擊的情況。文獻[34] 應用了Grover meets Simon 算法，對廣義Feistel 結構進行了密鑰恢復攻擊。文獻[35] 提出了一個針對Feistel 結構中子密鑰恢復的通用攻擊方法。在R輪的Feistel 結構中，對后R-3 輪子密鑰進行Grover 算法窮舉，在前3 輪中構造了一個具有后面輪次密鑰參數的Simon 函數。當后R-3 輪子密鑰猜測正確時，定義的函數擁有一個周期。

文獻[36]提出了一種結合Bernstein-Vazirani 算法和Grover 算法的新算法，用于對Feistel結構實施量子密鑰恢復攻擊。Grover 算法也可以與一些經典量子算法如Deutsch-Jozsa 算法進行meets 類的結合，但此類方法對于對稱密碼分析的作用尚未可知。

3.2 Grover on X 算法

使用Grover 算法進行密鑰恢復攻擊涉及兩個主要環節：首先，將已公開的經典算法轉換成相應的量子版本；然后，在這個量子版本上實施Grover 算法模塊。對于對稱密碼體制，采用這種攻擊方法在本小節中被稱為“Grover on X 算法”，其中“X”代表特定的密碼體制。這種命名方式旨在強調Grover 算法在特定密碼體制上的應用。

美國國家標準與技術研究所在后量子公鑰密碼學領域提出所需的期望安全級別[37]。這些安全級別有助于理解使用Grover 算法進行攻擊的難度。Grover on X 算法的攻擊難度取決于公開算法的量子實現和Grover 算法模塊。由于Grover 算法模塊一般是固定的（但是這并不意味著Grover 算法模塊的消耗是固定的），許多密碼分析者通過優化經典對稱密碼體制的量子實現算法來降低Grover 算法量子攻擊的復雜度。Grover on X 算法的比較如表1 所示。

表1 Grover on X 算法的比較Table 1 Comparison of Grover on X algorithms

文獻[38] 首次提出了一種量子窮舉方法，該方法采用Grover 算法搜索高級加密標準（advanced encryption standard,AES）的密鑰值。從量子電路大小、量子比特數量、量子電路深度等方面分析了該窮舉攻擊的量子資源開銷，其中量子電路的大小與整體量子電路消耗的通用量子邏輯門有關。文獻[39] 提出了一種簡化AES 算法的量子化版本，該電路采用zig-zag 結構以節約量子比特。文獻[40] 使用基于塔域分解的S 盒，設計了AES 的量子優化實現電路。文獻[41] 引入逆替代盒運算以減少zig-zag 結構所需要的量子位，提出了一種減少AES 密鑰表中量子位數的方法，使實現AES 所需的量子比特大幅減少。

研究者提出更多對稱密碼體制的Grover 算法窮舉攻擊電路的實現方法。文獻[42] 提供了SIMON 所有變體（SIMON 指的是一種對稱密碼體制，而Simon 指的是一種量子算法）的量子化版本。該文獻不僅詳細列出了對SIMON 密碼體制進行Grover 算法密鑰恢復攻擊所需的各種量子資源，如NOT 門、CNOT 門和Toffoli 門，還提供了實施該攻擊所需的量子位數以及T-深度和總深度的具體信息。同時，描述了一種在IBM 量子模擬器上實現的縮小版SIMON 變體。在這個IBM 模擬器上，可以一定程度地恢復縮小版SIMON 密碼的密鑰值。在文獻[42] 的研究基礎上，文獻[43] 對SIMON 變體的量子化版本進行了改進，減少了實現SIMON 所需的資源消耗（具體體現于T-深度和全深度上）。

3.3 量子中間相遇攻擊

中間相遇攻擊是一種常用于對稱密碼體制的攻擊方法。在中間相遇攻擊中，內部狀態分別沿著兩個獨立路徑（前向路徑和后向路徑）計算，最終通過匹配這兩個路徑，生成完整的路徑解。量子中間相遇攻擊可看作經典中間相遇攻擊的變體，大部分的量子中間相遇攻擊是基于Grover 算法構建的。

文獻[44] 發現，量子計算模型下可以顯著加速由Demiric 和Selcuk 提出的中間相遇攻擊（meet-in-the-middle attack designed by Demiric and Selcuk,DS-MITM），其中包含窮舉差分技術。該研究將尋找Claw 對問題的量子算法嵌入到區分器匹配和查詢數據過程。在經典設置下，DS-MITM 方法攻擊6 輪Feistel 過程時，需要的數據復雜度、時間復雜度以及內存復雜度均為O(23n/4)。在Q1 模型下，量子DS-MITM 方法攻擊需要O(2n/q) 的時間復雜度（其中q表示量子比特數）和O(2n/2) 次經典查詢復雜度，最佳平衡點是O(2n/2)。在Q2模型下，最佳平衡點是O(23n/4)。該研究說明Q1 模型對經典情況是一個有效的提升；Q2 模型下是否對該攻擊有較好的提升，是一個開放性的問題。文獻[45] 在文獻[44] 的基礎上，針對超過7 輪的Feistel 結構，提出了Q1 模型下的量子中間相遇攻擊，這在一定程度上降低了時間復雜度。文獻[46] 使用文獻[44] 的方法攻擊AES-128，從而降低了攻擊的時間復雜度。

最為經典的時空-折中攻擊是Hellman 時空-折中攻擊(包含常見的彩虹表技術)。經典情況下，Hellman 時空-折中攻擊需要的時空權衡為TM2D2=N2，T≥D2；文獻[47] 給出了量子設置下Hellman 時空-折中攻擊的時空權衡為T4/3M2D2=N2，T≥D3/2。

在中間相遇攻擊的密鑰恢復階段，一種通用的量子加速思路是使用量子嵌套搜索算法達到二次加速的效果。文獻[48] 利用嵌套的量子搜索算法和Ambainis 算法構建了飛去來器和混合飛去來器（一種融合了截斷攻擊的飛去來器）的量子版本，達到了近似二次加速的效果。矩形攻擊是飛去來器攻擊的進階版本，近年來，基于矩形攻擊的密鑰恢復攻擊技術發展迅猛。具有非線性關系的密鑰之間更適合矩形攻擊。文獻[49] 提出在進行矩形攻擊之前先對關鍵單元進行猜測，并將這種猜測策略應用于量子環境中，從而實現加速。然而，這一領域的研究尚未受到足夠的重視。

文獻[50] 研究了量子不可能差分算法，并實現了早夭技術的量子化。主要思路是將早夭技術通用地表示為嵌套搜索問題，此嵌套搜索問題的復雜度為|K1|(T1+|K2|(T2+···+|Kl-1|(Tl-1+|Kl|Tl)···))，其中Ki為搜索的密鑰空間，Ti為每一級需要搜索的表空間。在嵌套搜索問題中多次利用放大器定理（目的在于降低迭代次數），使嵌套搜索問題的復雜度降低為，從而實現二次加速。

反彈技術是中間相遇攻擊用來降低預計算時間復雜度的技巧。文獻[51] 首次對反彈技術進行了量子化，稱為量子反彈技術。量子反彈技術效果顯著，在攻擊AES-MMO 時，量子反彈技術能夠增加一個加密輪次；在攻擊5 輪Whirlpool 時，量子反彈技術的速度是經典攻擊的兩倍。為減少文獻[51] 對量子隨機存儲器模型（quantum random access memory,qRAM）的依賴，文獻[52] 結合非全活躍超級S 盒技術以降低qRAM 的使用。

其他一些經典中間相遇攻擊的量子化設置也逐漸變得流行。文獻[53] 對經典的在線-離線中間相遇攻擊進行了量子Q1 模型的轉換。文獻[54] 將兩量子表合并算法與中間相遇攻擊相結合，使得量子中間相遇攻擊的時間和存儲復雜度由列表大小決定。文獻[55] 對解剖攻擊（經典中間相遇攻擊的一種）進行了量子化改進，專門針對二次迭代加密的密鑰恢復攻擊，將尋找Claw 對問題的量子算法融入到該攻擊策略中。在四次迭代加密的密鑰恢復攻擊環境下，這種二次迭代加密的密鑰恢復方法被作為一個關鍵子程序加以應用。此外，該研究結合量子游走算法來搜索有效的中間值。最終，提供了比經典解剖攻擊更為顯著的增益效果。

4 量子差分攻擊

4.1 Bernstein-Vazirani 算法的研究

Bernstein-Vazirani 算法（B-V 算法）是基于Deutsch-Jozsa 算法發展出的一種變體算法[56]。分別稱布爾函數f:{0,1}n→{0,1} 和布爾函數f:{0,1}n→{0,1}n為一位輸出布爾函數和多位輸出布爾函數?；贐-V 算法對布爾函數線性結構的研究拉開了量子差分攻擊的序幕。文獻[57] 提出了適用于多位輸出布爾函數的廣義B-V 算法，與經典算法相比，該算法可以提供多項式級別的加速。廣義B-V 算法與密碼屬性測試方法關系密切，在基于廣義B-V 算法的密碼屬性測試方法中，non-junta 測試表現出色。為確定布爾函數的概率分布，在文獻[57] 的基礎之上，文獻[58] 重新對“距離”進行了定義，用以反映布爾函數概率分布與均勻分布的偏差。研究利用“距離”與沃爾什譜的關系，獲得了學習彈性程度的量子算法。

相比于經典算法，B-V 算法具有指數級別的加速效果，但其先驗假設是當f=a·x時，函數f與沃爾什譜建立聯系。此限制是明顯的，因為擁有這類表達形式的布爾函數無法涵蓋所有可能的布爾函數族。更為嚴格的先驗假設是一種非部分線性結構的承諾[59]，這意味著需要所有點x∈{0,1}n均需要滿足線性結構的要求。

Simon 算法與B-V 算法具有緊密聯系[52]。Simon 算法計算函數周期的一個正交向量，n個正交向量可計算出函數的周期值；B-V 算法計算函數線性結構的沃爾什系數，n個沃爾什系數可計算出函數的線性結構。使用Simon 算法進行攻擊的思路是尋找使等式F(x)=F(x⊕a)成立的a，即周期值。使用B-V 算法進行攻擊的思路是尋找等式F(x)=F(x⊕a)=b成立的a值，即線性結構。相比于Simon 算法，使用B-V 算法，擴充了攻擊范圍，即在b=0 的情況下，線性結構變為了周期值。兩者都可以用于量子周期攻擊中，但B-V 算法原理和Simon 算法原理顯然不同。兩者在查找周期的過程以及獲得每個向量的概率上存在差異，這意味著兩者的成功率可能存在某種關聯，但還未有此類文獻討論兩者具體聯系的情況。

4.2 兩階段的量子差分攻擊研究

差分密碼分析在經典密碼分析中是一種典型的選擇明文攻擊。與經典差分密碼分析[60]相似，量子差分密碼分析的過程分為兩個主要階段：量子差分攻擊的第I 階段是識別出一些具有較高概率的差分特性；第II 階段則是根據這些發現的差分特性，測試潛在的子密鑰候選項以恢復加密系統的主密鑰。根據各個攻擊階段，將量子差分攻擊進行分類與比較?？偨Y表如表2 所示。

表2 量子差分攻擊方法分類Table 2 Classification of quantum differential attack methods

4.2.1 量子差分攻擊第I 階段

文獻[69] 基于B-V 算法，提出了一個多項式時間的量子算法，用于求解一位輸出布爾函數f:{0,1}n→{0,1} 的線性結構。記Uf為布爾函數f的線性結構；布爾函數的沃爾什譜為；對于沃爾什系數集合，有。這個量子算法主要利用布爾函數的沃爾什譜來尋找線性結構。具體來說，當子集W足夠大后，就可以通過解線性方程{x·w=i|w∈W} 來獲取函數f的線性結構。在經典情況下，獲得子集W的復雜度為O(n2n)，這意味著實際執行這種計算是不切實際的。通過多項式次數運行B-V 算法，可以確定子集W，并在多項式時間內求出一位輸出布爾函數的線性結構。

多位輸出布爾函數的線性結構在量子差分攻擊第I 階段使用廣泛。在差分攻擊（差分特征為F(x)⊕F(x⊕Δin)=Δout）中，獲取多位輸出布爾函數的線性結構等同于識別出高概率的差分特征。對于加密塊E:{0,1}n×{0,1}m→{0,1}n，將加密塊E分解為n個更小的組件函數E1,E2,···,En。這里，每個Ej(1≤j≤n) 的輸入是加密塊E的輸入，而輸出則是加密塊E的第j位輸出，使用n+m+1 個量子比特的n個B-V 算法作用于每個Ej函數上。在這個設置中，前n個量子比特被用于表示n位的明文，接下來的m個量子比特用于存儲m位的密鑰，而最后一個量子比特專門用于記錄生成的密文的第j位。B-V 算法在每個Ej，1≤j≤n函數上重復執行O(p(n)) 次。經過O(p(n)) 次循環后，算法通過構建一組線性布爾方程{a·w=i,i=0,1} 來確定函數的線性結構a。因此，整個過程共需要O(np(n)) 次循環來完成。最終，通過尋找每個Ej函數的共同解，可以確定具有高概率的差分特征。文獻[64] 提出了一種標簽技術，有效解決了在計算公共解時遇到的指數次運算問題。

在經典方法中尋找差分特征時并不考慮輸入的具體密鑰，所尋找的差分特征與密鑰無關。然而，在上述方法中，需要確保密鑰以量子態的形式存在，并將這個密鑰態作為輸入，與回合制密碼結合，形成一個新的函數。在非相關密鑰模型下保持密鑰態的一致性，即保證密鑰差分為0。在這種情況下，所尋找的差分特征并不是完全與密鑰無關的。

文獻[61] 介紹了兩種利用B-V 算法尋找差分特征的方法。第1 種方法是在每個S-Box 上單獨應用量子算法。而第2 種方法則將整個加密塊作為一個單一實體，在整個過程中應用量子算法。相較于傳統的差分分析，第2 種方法有著明顯的優勢：它將目標密碼的所有差分回合視作一個整體，僅關注輸入和輸出之間的差異，而非特定的差分特性。這種方法在一定程度上減輕了傳統差分密碼分析當輪數增加時在尋找差分特征上遇到的困難。

文獻[62] 介紹了3 種量子算法：第1 種是通用的量子差分密碼分析；第2 種是應用中間未命中技術的量子不可能差分密碼分析，這一方法在文獻[59] 中得到了詳細分析；第3 種則是一種新型的量子小概率差分分析。此外，文獻[63] 提出了一種新的方法來查找塊密碼的截斷差分特征，并對該算法的復雜性進行了嚴格分析。文獻[64] 將B-V 算法應用于相關密鑰模型。在這一研究中，對攻擊的有效性進行了嚴格分析，并提出了算法有效工作的兩個具體條件。

4.2.2 量子差分攻擊第II 階段

研究人員專注于基于計數的經典差分密碼分析。這種方法的工作原理是統計每個候選子密鑰值ki滿足條件=Δout（也稱為密鑰公式）的次數，其中次數最多的候選子密鑰值ki就是經典差分密碼分析得出的正確密鑰值。在量子版本的實現中，采用了修改后的量子計數算法[70]（該算法在量子查找最大值或最小值的框架[71]下運行），以獲得正確密鑰值。具體而言，實現密鑰公式的量子電路被整合到量子計數算法中，從而能夠計算出每個潛在候選子密鑰值ki滿足密鑰公式的次數。首先設定一個門限值，代表某個可能的候選子密鑰值ki滿足密鑰公式的次數。然后利用量子計數算法得到的計數值來更新這個門限值，并不斷重復這一過程。在每次迭代過程中，通過對量子加密預言機進行疊加查詢，標記出候選子密鑰。這些被標記的候選密鑰值，其密鑰公式的統計次數超出了前一輪設定的門限值。使用Grover 算法對門限值和候選子密鑰進行搜索。最終，與門限值相對應的候選子密鑰值ki被識別為正確的密鑰值。

文獻[66] 利用上述方法設計了一種基于計數的量子電路，用于量子差分密碼分析。利用量子并行化技術可以使量子差分密碼分析的時間復雜度變為。相較于經典密碼分析所需的時間復雜度O(N)+O(K)，量子設置達到了二次加速效果。在文獻[66] 的基礎上，文獻[67] 將量子部分搜索算法應用于搜索過程，以減少查詢次數。

文獻[68] 詳細描述了實現密鑰公式的量子電路，同時指出了先前在復雜度評估中的錯誤，并提供了實現Grover 迭代的正確量子電路。之前的誤解源于Grover 算法迭代中量子電路將量子計數算法作為子程序，這實際上消除了量子并行性所帶來的計算加速效果?；谶@一發現，得出了更準確的復雜度估計，。

文獻[65] 將傳統基于表的經典差分密碼分析進行量子化。結合Grover 算法和Ambainis算法設計了一種量子差分分析方法。這項研究提出了兩個主要結論：首先，在Q2 模型下，量子差分攻擊比傳統方法實現了顯著的二次量子加速，但是要注意的是，量子截斷差分攻擊并不能獲得這樣的加速；其次，在Q1 模型中，特別是當密鑰長度大于塊長度時，量子差分攻擊展現出了更加顯著的增益效果。在該研究中，量子設置的核心理念在于將傳統的差分攻擊轉化為查找兩個聯合表的問題，并利用Grover 算法來加快查找過程。

5 結語

分析上述文獻可以得到對稱密碼體制的量子攻擊領域可能會出現的熱門研究方向。

首先，關于Q2 模型攻擊轉換問題。Q2 模型能夠以攻擊者的高能力產生許多低成本的攻擊，導致大多數研究集中在Q2 模型的變體上。本文提到的離線計算方式攻擊是一個有效的基于Simon 算法的Q1 模型攻擊示例。然而，實際上可能還有許多潛在Q1 模型下的攻擊未被發掘，例如量子中間相遇攻擊的多個Q2 版本。于是第1 個問題是：除了基于Simon 算法的離線計算方式，是否還存在僅使用經典查詢的其他離線變體？

其次，關于削減qRAM 資源消耗問題。qRAM 作為一個在多個領域廣泛使用的量子計算模型，其應用范圍遠遠超出量子密碼分析。使用qRAM 模型的研究者指出，qRAM 的實現難度高于普通的量子電路模型。于是第2 個問題是：對于依賴qRAM 模型的攻擊方法，是否存在一種轉換策略，用以減少或完全消除對qRAM 模型的依賴？

再次，關于Grover 算法的并行性。Grover 算法的并行性較差。將原有的個條目分布在個獨立的小型量子處理器上進行處理，Grover 算法所需的時間復雜度將降低到。這種并行化技術使Grover 算法的時間復雜度僅提升了倍，且查詢復雜度反而會增加為。于是第3 個問題是：是否可以利用量子算法的并行特性，以實現比單核量子處理器更高效的量子攻擊方式？

最后，關于新型攻擊方式。相比于量子密碼分析這一新型領域，經典密碼分析技術的發展源遠流長。新型攻擊方式主要有兩種構建方式：可以考慮一類新的通用問題解法并將其應用于量子（對稱）密碼分析領域，這種方法可能發展出與任何已知經典攻擊無關的新型量子攻擊；可以將傳統的密碼分析算法進行量子化設置。這兩種思路已經成為密碼分析領域的主要攻擊構建策略。

本文對現有對稱密碼體制下的量子攻擊進行了總結。全文概述了對稱密碼體制量子攻擊的研究脈絡，將近幾年的研究分為量子周期攻擊、Grover 相關攻擊的研究、量子差分攻擊3類，并進行了攻擊簡述與相應評注?？梢钥闯?，對稱密碼體制中Feistel 結構和類AES 結構受到了廣泛研究，而涉及序列密碼與流密碼的篇幅相對較少。新型的對稱密碼體制，如本文提到的AE 體制類密碼，設計之初應著重考慮在量子計算模型下的安全性。