馮曉寧，吳洪宇

哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

美國(guó)物理學(xué)家費(fèi)曼在1982 年提出了量子計(jì)算的概念[1]，該技術(shù)引起了世界各國(guó)的廣泛關(guān)注。量子計(jì)算在大整數(shù)分解、離散對(duì)數(shù)計(jì)算等多個(gè)計(jì)算問(wèn)題上展現(xiàn)出了顯著優(yōu)勢(shì)。量子密碼分析學(xué)（亦稱(chēng)為量子攻擊）是量子計(jì)算與密碼分析相交叉的新學(xué)科，具有經(jīng)典密碼分析不能擁有的資源及速度優(yōu)勢(shì)。本文主要介紹了量子密碼分析學(xué)中針對(duì)于傳統(tǒng)密碼體制中對(duì)稱(chēng)密碼體制的部分，即量子（對(duì)稱(chēng)）密碼分析學(xué)。并把使用量子算法進(jìn)行密碼分析的過(guò)程稱(chēng)為量子環(huán)境設(shè)置，把未使用量子算法進(jìn)行密碼分析的過(guò)程稱(chēng)為經(jīng)典或傳統(tǒng)環(huán)境設(shè)置。

量子計(jì)算對(duì)非對(duì)稱(chēng)密碼分析學(xué)產(chǎn)生了深遠(yuǎn)影響。Shor 算法[2]和Grover 算法[3]作為兩種經(jīng)典的量子計(jì)算方法，開(kāi)啟了量子密碼分析的先河。1994 年，Shor 提出了在多項(xiàng)式時(shí)間內(nèi)分解大整數(shù)的算法[2]。大整數(shù)分解在傳統(tǒng)計(jì)算機(jī)中被視為經(jīng)典困難問(wèn)題，很多非對(duì)稱(chēng)密碼體制就是為了解決這種困難問(wèn)題而設(shè)計(jì)的，比如RSA 加密算法[4]。Shor 算法理論上對(duì)傳統(tǒng)密碼造成了巨大威脅[5]。時(shí)隔20 年，當(dāng)初提出的理論算法已變成現(xiàn)實(shí)，量子計(jì)算機(jī)已經(jīng)可以分解13 位的大整數(shù)[6]，表明量子計(jì)算在破解非對(duì)稱(chēng)密碼方面已經(jīng)取得了實(shí)質(zhì)性的突破。

在對(duì)稱(chēng)密碼體制中，量子計(jì)算的影響是有限的。Grover 算法[3]應(yīng)用于窮舉攻擊，可以產(chǎn)生二次加速的效果[7]。盡管Grover 算法在密碼分析領(lǐng)域產(chǎn)生了廣泛的影響，但除Grover 算法之外，絕大多數(shù)量子算法只能提供亞指數(shù)或多項(xiàng)式級(jí)別的加速，在對(duì)稱(chēng)密碼分析方面的實(shí)際影響尚不明顯。這也導(dǎo)致了密碼學(xué)領(lǐng)域一個(gè)長(zhǎng)期存在的共識(shí)：簡(jiǎn)單地將傳統(tǒng)對(duì)稱(chēng)密碼算法的密鑰長(zhǎng)度加倍，可確保對(duì)稱(chēng)密碼算法在量子計(jì)算模型下的安全性。

美國(guó)國(guó)家科學(xué)院關(guān)于量子計(jì)算的報(bào)告中指出：可能存在一些迄今未知但性能遠(yuǎn)超Grover算法的量子攻擊。許多密碼學(xué)家正在探索比Grover 算法更為高效的密碼分析手段。例如，量子差分密碼分析將經(jīng)典差分密碼分析的環(huán)境置為量子環(huán)境，旨在得到相比于經(jīng)典情況下二次甚至指數(shù)級(jí)別的加速[8]。密碼學(xué)家在諸多量子密碼分析方面取得了長(zhǎng)足的進(jìn)步，有些甚至能夠在多項(xiàng)式時(shí)間內(nèi)破壞許多對(duì)稱(chēng)密碼系統(tǒng)。

1 研究脈絡(luò)及分類(lèi)

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

圖1 對(duì)稱(chēng)密碼體制量子攻擊的研究脈絡(luò)Figure 1 Research context of quantum attack on symmetric cryptosystem

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

圖2 對(duì)稱(chēng)密碼體制的量子攻擊分類(lèi)圖Figure 2 Classification diagram of quantum attacks on symmetric cryptosystems

2 量子周期攻擊

2.1 Simon 算法的研究

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

對(duì)Simon 承諾條件弱化情形的研究起步較早。文獻(xiàn)[12] 說(shuō)明了Simon 函數(shù)的碰撞與測(cè)量結(jié)果之間的確切關(guān)系，證明了在大多數(shù)隨機(jī)情況下，額外的碰撞不會(huì)導(dǎo)致Simon 算法攻擊的復(fù)雜性顯著增加。Simon 函數(shù)應(yīng)避免碰撞過(guò)大，現(xiàn)在大多數(shù)基于Simon 算法的密碼分析都使用以下的沖突假設(shè)

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

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

2.2 基于周期構(gòu)建的攻擊

量子周期攻擊是利用解布爾函數(shù)周期問(wèn)題的量子算法進(jìn)行密碼分析的攻擊方法。Simon算法完成量子周期攻擊的主要思路是：在目標(biāo)密碼體制中構(gòu)建函數(shù)，該函數(shù)即為布爾隱藏周期問(wèn)題中的函數(shù)f，通過(guò)結(jié)合Simon 算法和解傳統(tǒng)方程組的方法來(lái)確定函數(shù)的周期，進(jìn)而對(duì)指定密碼體系進(jìn)行分析。

文獻(xiàn)[16] 利用Simon 算法實(shí)現(xiàn)了開(kāi)創(chuàng)性的量子密碼分析。其中展示的攻擊方法是利用量子疊加模型在O(n) 的量子時(shí)間復(fù)雜度下構(gòu)建了一個(gè)區(qū)分器。隨后，文獻(xiàn)[17] 通過(guò)構(gòu)建Even-Mansour 密碼體制上的周期函數(shù)實(shí)施了量子周期攻擊，獲取了Even-Mansour 密碼體制的密鑰，表明Even-Mansour 密碼體制是不安全的。文獻(xiàn)[15] 利用Simon 算法對(duì)固定長(zhǎng)度密碼塊鏈消息認(rèn)證碼（cipher block chaining message authentication code,CBC-MAC）進(jìn)行了偽造攻擊，能夠?yàn)橐郧拔床樵冞^(guò)的消息生成有效的標(biāo)簽。文獻(xiàn)[18] 所構(gòu)建的函數(shù)f(x)={Ex(m),Ex⊕s(m)} 周期為s，而s正好是相關(guān)密鑰攻擊模型中需要尋找的密鑰K。

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

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

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

2.3 離線計(jì)算方式的攻擊

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

在實(shí)現(xiàn)離線計(jì)算方式的算法中，主要難點(diǎn)在于正確選擇并組合g和f。文獻(xiàn)[27] 在文獻(xiàn)[25] 的基礎(chǔ)上使用離線計(jì)算方式構(gòu)造對(duì)哈希計(jì)數(shù)器的新攻擊。文獻(xiàn)[28] 給出了Simon 離線計(jì)算方式的第1 個(gè)完整實(shí)現(xiàn)，并估計(jì)了多種輕量級(jí)密碼體制的攻擊成本。文獻(xiàn)[29] 在對(duì)移動(dòng)通信網(wǎng)中的Milenage 算法集進(jìn)行量子密碼分析時(shí)，實(shí)現(xiàn)了離線Simon 算法對(duì)相關(guān)密鑰分析進(jìn)行加速。

3 Grover 算法相關(guān)攻擊的研究

Grover 算法是典型的量子搜索算法，可解決無(wú)序搜索問(wèn)題。Grover 算法作為一種高性能量子搜索算法，實(shí)現(xiàn)了對(duì)經(jīng)典搜索算法的二次加速，在密碼分析領(lǐng)域中備受矚目。

3.1 Grover meets X 算法

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

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

Grover meets Simon 算法對(duì)后續(xù)研究者產(chǎn)生了深遠(yuǎn)的影響。文獻(xiàn)[32] 利用Grover meets Simon 算法實(shí)施對(duì)埃文-曼蘇爾之和（sum of Even-Mansour,SoME）的密鑰恢復(fù)攻擊。針對(duì)文獻(xiàn)[32] 中提出的攻擊方法，攻擊效果在某些SoME 變體中不夠明顯的問(wèn)題，文獻(xiàn)[33] 進(jìn)一步討論了SoME 密碼體制變體攻擊的情況。文獻(xiàn)[34] 應(yīng)用了Grover meets Simon 算法，對(duì)廣義Feistel 結(jié)構(gòu)進(jìn)行了密鑰恢復(fù)攻擊。文獻(xiàn)[35] 提出了一個(gè)針對(duì)Feistel 結(jié)構(gòu)中子密鑰恢復(fù)的通用攻擊方法。在R輪的Feistel 結(jié)構(gòu)中，對(duì)后R-3 輪子密鑰進(jìn)行Grover 算法窮舉，在前3 輪中構(gòu)造了一個(gè)具有后面輪次密鑰參數(shù)的Simon 函數(shù)。當(dāng)后R-3 輪子密鑰猜測(cè)正確時(shí)，定義的函數(shù)擁有一個(gè)周期。

文獻(xiàn)[36]提出了一種結(jié)合Bernstein-Vazirani 算法和Grover 算法的新算法，用于對(duì)Feistel結(jié)構(gòu)實(shí)施量子密鑰恢復(fù)攻擊。Grover 算法也可以與一些經(jīng)典量子算法如Deutsch-Jozsa 算法進(jìn)行meets 類(lèi)的結(jié)合，但此類(lèi)方法對(duì)于對(duì)稱(chēng)密碼分析的作用尚未可知。

3.2 Grover on X 算法

使用Grover 算法進(jìn)行密鑰恢復(fù)攻擊涉及兩個(gè)主要環(huán)節(jié)：首先，將已公開(kāi)的經(jīng)典算法轉(zhuǎn)換成相應(yīng)的量子版本；然后，在這個(gè)量子版本上實(shí)施Grover 算法模塊。對(duì)于對(duì)稱(chēng)密碼體制，采用這種攻擊方法在本小節(jié)中被稱(chēng)為“Grover on X 算法”，其中“X”代表特定的密碼體制。這種命名方式旨在強(qiáng)調(diào)Grover 算法在特定密碼體制上的應(yīng)用。

美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所在后量子公鑰密碼學(xué)領(lǐng)域提出所需的期望安全級(jí)別[37]。這些安全級(jí)別有助于理解使用Grover 算法進(jìn)行攻擊的難度。Grover on X 算法的攻擊難度取決于公開(kāi)算法的量子實(shí)現(xiàn)和Grover 算法模塊。由于Grover 算法模塊一般是固定的（但是這并不意味著Grover 算法模塊的消耗是固定的），許多密碼分析者通過(guò)優(yōu)化經(jīng)典對(duì)稱(chēng)密碼體制的量子實(shí)現(xiàn)算法來(lái)降低Grover 算法量子攻擊的復(fù)雜度。Grover on X 算法的比較如表1 所示。

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

文獻(xiàn)[38] 首次提出了一種量子窮舉方法，該方法采用Grover 算法搜索高級(jí)加密標(biāo)準(zhǔn)（advanced encryption standard,AES）的密鑰值。從量子電路大小、量子比特?cái)?shù)量、量子電路深度等方面分析了該窮舉攻擊的量子資源開(kāi)銷(xiāo)，其中量子電路的大小與整體量子電路消耗的通用量子邏輯門(mén)有關(guān)。文獻(xiàn)[39] 提出了一種簡(jiǎn)化AES 算法的量子化版本，該電路采用zig-zag 結(jié)構(gòu)以節(jié)約量子比特。文獻(xiàn)[40] 使用基于塔域分解的S 盒，設(shè)計(jì)了AES 的量子優(yōu)化實(shí)現(xiàn)電路。文獻(xiàn)[41] 引入逆替代盒運(yùn)算以減少zig-zag 結(jié)構(gòu)所需要的量子位，提出了一種減少AES 密鑰表中量子位數(shù)的方法，使實(shí)現(xiàn)AES 所需的量子比特大幅減少。

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

3.3 量子中間相遇攻擊

中間相遇攻擊是一種常用于對(duì)稱(chēng)密碼體制的攻擊方法。在中間相遇攻擊中，內(nèi)部狀態(tài)分別沿著兩個(gè)獨(dú)立路徑（前向路徑和后向路徑）計(jì)算，最終通過(guò)匹配這兩個(gè)路徑，生成完整的路徑解。量子中間相遇攻擊可看作經(jīng)典中間相遇攻擊的變體，大部分的量子中間相遇攻擊是基于Grover 算法構(gòu)建的。

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

最為經(jīng)典的時(shí)空-折中攻擊是Hellman 時(shí)空-折中攻擊(包含常見(jiàn)的彩虹表技術(shù))。經(jīng)典情況下，Hellman 時(shí)空-折中攻擊需要的時(shí)空權(quán)衡為T(mén)M2D2=N2，T≥D2；文獻(xiàn)[47] 給出了量子設(shè)置下Hellman 時(shí)空-折中攻擊的時(shí)空權(quán)衡為T(mén)4/3M2D2=N2，T≥D3/2。

在中間相遇攻擊的密鑰恢復(fù)階段，一種通用的量子加速思路是使用量子嵌套搜索算法達(dá)到二次加速的效果。文獻(xiàn)[48] 利用嵌套的量子搜索算法和Ambainis 算法構(gòu)建了飛去來(lái)器和混合飛去來(lái)器（一種融合了截?cái)喙舻娘w去來(lái)器）的量子版本，達(dá)到了近似二次加速的效果。矩形攻擊是飛去來(lái)器攻擊的進(jìn)階版本，近年來(lái)，基于矩形攻擊的密鑰恢復(fù)攻擊技術(shù)發(fā)展迅猛。具有非線性關(guān)系的密鑰之間更適合矩形攻擊。文獻(xiàn)[49] 提出在進(jìn)行矩形攻擊之前先對(duì)關(guān)鍵單元進(jìn)行猜測(cè)，并將這種猜測(cè)策略應(yīng)用于量子環(huán)境中，從而實(shí)現(xiàn)加速。然而，這一領(lǐng)域的研究尚未受到足夠的重視。

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

反彈技術(shù)是中間相遇攻擊用來(lái)降低預(yù)計(jì)算時(shí)間復(fù)雜度的技巧。文獻(xiàn)[51] 首次對(duì)反彈技術(shù)進(jìn)行了量子化，稱(chēng)為量子反彈技術(shù)。量子反彈技術(shù)效果顯著，在攻擊AES-MMO 時(shí)，量子反彈技術(shù)能夠增加一個(gè)加密輪次；在攻擊5 輪Whirlpool 時(shí)，量子反彈技術(shù)的速度是經(jīng)典攻擊的兩倍。為減少文獻(xiàn)[51] 對(duì)量子隨機(jī)存儲(chǔ)器模型（quantum random access memory,qRAM）的依賴(lài)，文獻(xiàn)[52] 結(jié)合非全活躍超級(jí)S 盒技術(shù)以降低qRAM 的使用。

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

4 量子差分攻擊

4.1 Bernstein-Vazirani 算法的研究

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

相比于經(jīng)典算法，B-V 算法具有指數(shù)級(jí)別的加速效果，但其先驗(yàn)假設(shè)是當(dāng)f=a·x時(shí)，函數(shù)f與沃爾什譜建立聯(lián)系。此限制是明顯的，因?yàn)閾碛羞@類(lèi)表達(dá)形式的布爾函數(shù)無(wú)法涵蓋所有可能的布爾函數(shù)族。更為嚴(yán)格的先驗(yàn)假設(shè)是一種非部分線性結(jié)構(gòu)的承諾[59]，這意味著需要所有點(diǎn)x∈{0,1}n均需要滿足線性結(jié)構(gòu)的要求。

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

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

差分密碼分析在經(jīng)典密碼分析中是一種典型的選擇明文攻擊。與經(jīng)典差分密碼分析[60]相似，量子差分密碼分析的過(guò)程分為兩個(gè)主要階段：量子差分攻擊的第I 階段是識(shí)別出一些具有較高概率的差分特性；第II 階段則是根據(jù)這些發(fā)現(xiàn)的差分特性，測(cè)試潛在的子密鑰候選項(xiàng)以恢復(fù)加密系統(tǒng)的主密鑰。根據(jù)各個(gè)攻擊階段，將量子差分攻擊進(jìn)行分類(lèi)與比較?？偨Y(jié)表如表2 所示。

表2 量子差分攻擊方法分類(lèi)Table 2 Classification of quantum differential attack methods

4.2.1 量子差分攻擊第I 階段

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

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

在經(jīng)典方法中尋找差分特征時(shí)并不考慮輸入的具體密鑰，所尋找的差分特征與密鑰無(wú)關(guān)。然而，在上述方法中，需要確保密鑰以量子態(tài)的形式存在，并將這個(gè)密鑰態(tài)作為輸入，與回合制密碼結(jié)合，形成一個(gè)新的函數(shù)。在非相關(guān)密鑰模型下保持密鑰態(tài)的一致性，即保證密鑰差分為0。在這種情況下，所尋找的差分特征并不是完全與密鑰無(wú)關(guān)的。

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

文獻(xiàn)[62] 介紹了3 種量子算法：第1 種是通用的量子差分密碼分析；第2 種是應(yīng)用中間未命中技術(shù)的量子不可能差分密碼分析，這一方法在文獻(xiàn)[59] 中得到了詳細(xì)分析；第3 種則是一種新型的量子小概率差分分析。此外，文獻(xiàn)[63] 提出了一種新的方法來(lái)查找塊密碼的截?cái)嗖罘痔卣鳎?duì)該算法的復(fù)雜性進(jìn)行了嚴(yán)格分析。文獻(xiàn)[64] 將B-V 算法應(yīng)用于相關(guān)密鑰模型。在這一研究中，對(duì)攻擊的有效性進(jìn)行了嚴(yán)格分析，并提出了算法有效工作的兩個(gè)具體條件。

4.2.2 量子差分攻擊第II 階段

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

文獻(xiàn)[66] 利用上述方法設(shè)計(jì)了一種基于計(jì)數(shù)的量子電路，用于量子差分密碼分析。利用量子并行化技術(shù)可以使量子差分密碼分析的時(shí)間復(fù)雜度變?yōu)?。相較于經(jīng)典密碼分析所需的時(shí)間復(fù)雜度O(N)+O(K)，量子設(shè)置達(dá)到了二次加速效果。在文獻(xiàn)[66] 的基礎(chǔ)上，文獻(xiàn)[67] 將量子部分搜索算法應(yīng)用于搜索過(guò)程，以減少查詢次數(shù)。

文獻(xiàn)[68] 詳細(xì)描述了實(shí)現(xiàn)密鑰公式的量子電路，同時(shí)指出了先前在復(fù)雜度評(píng)估中的錯(cuò)誤，并提供了實(shí)現(xiàn)Grover 迭代的正確量子電路。之前的誤解源于Grover 算法迭代中量子電路將量子計(jì)數(shù)算法作為子程序，這實(shí)際上消除了量子并行性所帶來(lái)的計(jì)算加速效果?；谶@一發(fā)現(xiàn)，得出了更準(zhǔn)確的復(fù)雜度估計(jì)，。

文獻(xiàn)[65] 將傳統(tǒng)基于表的經(jīng)典差分密碼分析進(jìn)行量子化。結(jié)合Grover 算法和Ambainis算法設(shè)計(jì)了一種量子差分分析方法。這項(xiàng)研究提出了兩個(gè)主要結(jié)論：首先，在Q2 模型下，量子差分攻擊比傳統(tǒng)方法實(shí)現(xiàn)了顯著的二次量子加速，但是要注意的是，量子截?cái)嗖罘止舨⒉荒塬@得這樣的加速；其次，在Q1 模型中，特別是當(dāng)密鑰長(zhǎng)度大于塊長(zhǎng)度時(shí)，量子差分攻擊展現(xiàn)出了更加顯著的增益效果。在該研究中，量子設(shè)置的核心理念在于將傳統(tǒng)的差分攻擊轉(zhuǎn)化為查找兩個(gè)聯(lián)合表的問(wèn)題，并利用Grover 算法來(lái)加快查找過(guò)程。

5 結(jié)語(yǔ)

分析上述文獻(xiàn)可以得到對(duì)稱(chēng)密碼體制的量子攻擊領(lǐng)域可能會(huì)出現(xiàn)的熱門(mén)研究方向。

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

其次，關(guān)于削減qRAM 資源消耗問(wèn)題。qRAM 作為一個(gè)在多個(gè)領(lǐng)域廣泛使用的量子計(jì)算模型，其應(yīng)用范圍遠(yuǎn)遠(yuǎn)超出量子密碼分析。使用qRAM 模型的研究者指出，qRAM 的實(shí)現(xiàn)難度高于普通的量子電路模型。于是第2 個(gè)問(wèn)題是：對(duì)于依賴(lài)qRAM 模型的攻擊方法，是否存在一種轉(zhuǎn)換策略，用以減少或完全消除對(duì)qRAM 模型的依賴(lài)？

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

最后，關(guān)于新型攻擊方式。相比于量子密碼分析這一新型領(lǐng)域，經(jīng)典密碼分析技術(shù)的發(fā)展源遠(yuǎn)流長(zhǎng)。新型攻擊方式主要有兩種構(gòu)建方式：可以考慮一類(lèi)新的通用問(wèn)題解法并將其應(yīng)用于量子（對(duì)稱(chēng)）密碼分析領(lǐng)域，這種方法可能發(fā)展出與任何已知經(jīng)典攻擊無(wú)關(guān)的新型量子攻擊；可以將傳統(tǒng)的密碼分析算法進(jìn)行量子化設(shè)置。這兩種思路已經(jīng)成為密碼分析領(lǐng)域的主要攻擊構(gòu)建策略。

本文對(duì)現(xiàn)有對(duì)稱(chēng)密碼體制下的量子攻擊進(jìn)行了總結(jié)。全文概述了對(duì)稱(chēng)密碼體制量子攻擊的研究脈絡(luò)，將近幾年的研究分為量子周期攻擊、Grover 相關(guān)攻擊的研究、量子差分攻擊3類(lèi)，并進(jìn)行了攻擊簡(jiǎn)述與相應(yīng)評(píng)注。可以看出，對(duì)稱(chēng)密碼體制中Feistel 結(jié)構(gòu)和類(lèi)AES 結(jié)構(gòu)受到了廣泛研究，而涉及序列密碼與流密碼的篇幅相對(duì)較少。新型的對(duì)稱(chēng)密碼體制，如本文提到的AE 體制類(lèi)密碼，設(shè)計(jì)之初應(yīng)著重考慮在量子計(jì)算模型下的安全性。