董曉陽

1.清華大學(xué) 網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院, 北京 100084

2.密碼科學(xué)技術(shù)國家重點實驗室, 北京 100878

3.山東區(qū)塊鏈研究院, 濟南 250102

4.中關(guān)村實驗室, 北京 100194

1 引言

1994 年, Shor 的開創(chuàng)性工作[1]表明, 規(guī)模足夠大的量子計算機能夠在多項式時間內(nèi)對大整數(shù)進行因子分解和求解離散對數(shù)問題, 這將會破壞當(dāng)今廣泛使用的許多公鑰方案, 如RSA 和ECC 等.為了迎接未來的挑戰(zhàn), 公鑰密碼學(xué)界和標(biāo)準(zhǔn)化組織投入了大量精力進行后量子公鑰密碼方案的研究.特別地, 美國國家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology, NIST) 在2016 年啟動了后量子標(biāo)準(zhǔn)征集競賽(Post-Quantum Cryptography Standardization), 旨在征求、評估和標(biāo)準(zhǔn)化一個或多個抗量子公鑰密碼算法[2].相比之下, 關(guān)于量子計算如何改變對稱密碼的安全格局的研究似乎不太活躍.1996年, Grover 算法[3]的提出使得窮舉搜索攻擊在量子計算環(huán)境下能夠獲得二次加速(quadratic speedup),即在N個元素中找到某一特定元素, 經(jīng)典計算環(huán)境下所需的時間復(fù)雜度平均為O(N/2), 而在量子計算環(huán)境下, Grover 算法能夠在O(√N) 的時間復(fù)雜度下找到該元素.在十余年的時間里(1996–2010 年前后),密碼研究者普遍認(rèn)為, Grover 算法是對稱密碼的唯一量子計算攻擊威脅, 因此密碼研究者認(rèn)為加倍密鑰長度即可解決該問題[4].2010 年和2012 年, 隨著Kuwakado 和Morii 的初步工作, 這種觀點開始發(fā)生變化.他們證明了經(jīng)典計算環(huán)境下可證明安全的Even-Mansour 密碼和三輪Feistel 網(wǎng)絡(luò)可以在量子計算機的幫助下在多項式時間內(nèi)被破解[5,6].在2016 年美密會上, 法國密碼研究者Kaplan 等人[7]利用量子計算模型進一步在多項式時間內(nèi)破解了廣泛使用的認(rèn)證和認(rèn)證加密模式, 如CBC-MAC、PMAC、GMAC、GCM 和OCB 等.這些具有指數(shù)加速(由指數(shù)級別的時間復(fù)雜度降低至多項式級別時間復(fù)雜度) 的量子計算攻擊都是利用Simon 算法[8]來尋找依賴密鑰的隱藏周期, 過程中需要以量子疊加態(tài)訪問用量子線路實現(xiàn)的密碼算法, 這是一個比較強的攻擊條件.而以經(jīng)典的方式收集明密文對, 并利用離線的量子計算機進行密碼攻擊成為相對實際的攻擊假設(shè).另外, 在量子計算模型中, 不同于經(jīng)典隨機存儲, 量子隨機存儲被廣泛認(rèn)為是難以高效構(gòu)造的[9,10], 因此使用更少的量子隨機存儲是優(yōu)化量子攻擊的重要方向.本文綜述了分組密碼和典型結(jié)構(gòu)、認(rèn)證和認(rèn)證加密算法以及哈希函數(shù)等在不同攻擊條件下的重要量子計算分析進展,部分參考了眭晗等人2020 年的綜述論文[11]以及梁敏等人2021 年的綜述論文[12].

2 量子計算與基本算法

2.1 量子比特和運算

值得注意的是, 如果函數(shù)f能夠在經(jīng)典電路模型下快速實現(xiàn), 那么其對應(yīng)的量子酉變換Uf亦能夠在量子線路模型下快速實現(xiàn).

2.2 Grover 算法

2.3 量子振幅放大算法QAA

通俗來講, 假設(shè)要尋找集合X中被標(biāo)記的元素, 這些被標(biāo)記的元素構(gòu)成集合M ?X, 且已知?=|M|/|X|.顯然經(jīng)典搜索算法需要O(1/?) 時間復(fù)雜度.確定量子Grover 算法的復(fù)雜度, 需要確定下列兩個運算的復(fù)雜度, 即Setup 運算和Checking 運算:

量子振幅放大算法(quantum amplitude amplification, QAA) 是Brassard 等人[13]提出的.該算法可以被視為Grover 算法的一般化.簡單來說, 假設(shè)存在量子算法A來生成集合X中“好” 的元素和“壞” 的元素的量子均勻疊加態(tài), 同時, 令a是測量初始狀態(tài)A|0產(chǎn)生“好” 的元素的成功率.假設(shè)B能夠區(qū)分量子算法A的輸出是“好” 元素還是“壞” 元素, 那么量子振幅放大算法可以以下時間復(fù)雜度找到“好” 的元素:

2.4 Simon 算法

給定一個函數(shù)f:{0,1}n{0,1}n, 它在某個n比特周期a異或下保持不變, 即存在0, 使得對任意的x ∈Fn2,f(x) =f(x ⊕a).那么問題是找到這個周期a.在經(jīng)典計算環(huán)境下, 解決該問題的最優(yōu)時間復(fù)雜度約為2n/2.然而, Simon 在1997 年提出量子Simon 算法[8], 能夠以多項式時間量子復(fù)雜度找到該周期a.Simon 算法的步驟如下:

這是因為對任意的x ∈Fn2,f(x) =f(x ⊕a).因此當(dāng)測量第二個狀態(tài)的時候, 假設(shè)其坍縮到狀態(tài)t, 其一定對應(yīng)某個z, 使得f(z)=f(z+a)=t.因此第一個寄存器將坍縮成兩個狀態(tài)的疊加, 即

(4) 在上述寄存器上使用Hadamard 變換, 得到:

(5) 當(dāng)y·a=1 時,|的振幅為0.因此測量上述疊加態(tài)得到的y總滿足線性方程y·a=0.

重復(fù)上述步驟O(n) 次, 可獲得足夠多的關(guān)于a的線性方程, 求解該方程, 可獲得周期a.

3 分組密碼和及其工作模式的量子分析

2012 年, Zhandry[14]提出了兩種量子計算模型, 分別描述了不同的量子攻擊條件:

? 標(biāo)準(zhǔn)安全模型(Q1): 攻擊者可以訪問量子計算機來執(zhí)行任何離線計算, 但只允許他們以經(jīng)典方式進行在線訪問密碼算法.即, 敵手只能以經(jīng)典方式收集明密文對等數(shù)據(jù), 然后利用離線的量子計算機進行密碼分析.

? 量子安全模型(Q2): 攻擊者可以直接以輸入的量子疊加態(tài)訪問密碼算法的量子線路實現(xiàn), 并得到處于量子疊加態(tài)的輸出, 同時也具備Q1 模型的攻擊能力.

本文分別總結(jié)了兩種攻擊條件下的量子分析成果, 記為Q2 型攻擊和Q1 型攻擊.

3.1 Q2 型攻擊

Q2 型攻擊即攻擊者可以直接以輸入的量子疊加態(tài)訪問密碼算法, 并獲得處于疊加態(tài)的輸出.Kuwakado 和Morii 在2010 年和2012 年發(fā)現(xiàn)了經(jīng)典計算模型中被證明安全的密碼結(jié)構(gòu)在量子Q2 模型下存在多項式時間的量子區(qū)分攻擊[5,6], 即3 輪Feistel 結(jié)構(gòu)和Even-Mansour 結(jié)構(gòu).這些攻擊是利用密碼結(jié)構(gòu)特點構(gòu)造周期函數(shù), 而秘密信息則隱藏在秘密的周期中.利用量子Simon 算法, 這些秘密的周期能夠在量子多項式時間被恢復(fù), 從而達到攻擊密碼的目的.隨后, 在2016 年美密會上, Kaplan 等人利用量子Simon 算法攻擊攻擊了一系列認(rèn)證和認(rèn)證加密算法[7], 包括CBC-MAC、PMAC、GMAC、GCM、OCB, 以及CAESAR 競賽候選算法CLOC、AEZ、COPA、OTR、POET、OMD 和Minalpher.在2017 年亞密會上, Leander 和May 將Simon 算法和Grover 算法相結(jié)合(Grover-meet-Simon), 給出了FX 結(jié)構(gòu)的量子密鑰恢復(fù)攻擊[15].

3.1.1 Feistel 等分組密碼結(jié)構(gòu)的量子分析

在CT-RSA 2019 上, Ito 等人[16]提出了4 輪Feistel 的量子選擇密文區(qū)分攻擊(quantum chosenciphertext attack, qCCA).Dong 等人研究了Feistel 和廣義Feistel 的一系列量子多項時間區(qū)分攻擊, 并結(jié)合Grover-meet-Simon 算法給出密鑰恢復(fù)攻擊[17–19].針對Feistel 的量子分析引發(fā)了學(xué)術(shù)界對多種密碼結(jié)構(gòu)展開分析, Cui 等人研究了MISTY L/R、CAST256-like、CLEFIA-like 等典型Feistel 結(jié)構(gòu)的量子攻擊[20].Cid 等人給出了7 輪SM4 的量子區(qū)分攻擊以及相關(guān)密鑰下的量子攻擊[21].Hodz?i? 等人研究了Type-3 型廣義Feistel 和SM4 的量子攻擊[22,23].鄒劍等人將Simon 算法的周期性質(zhì)與生日攻擊思想相結(jié)合, 提出了一種新型傳統(tǒng)密鑰恢復(fù)攻擊[24].羅宜元等人研究了對MISTY L/R 和Lai-Massey 的量子分析[25].Mao 等人[26]研究了Lai-Massey 結(jié)構(gòu)的量子選擇明文和量子選擇密文區(qū)分器.Zhang 等人給出了Type-3 型廣義Feistel、帶膨脹論函數(shù)的非平衡Feistel、以及Lai-Massey 結(jié)構(gòu)的量子攻擊[27,28].Gouget 等人研究了MISTY 結(jié)構(gòu)的量子分析, 并證明了3 輪MISTY R 的抗選擇明文攻擊(chosen-plaintext attack, CPA) 的安全性[29].在2022 年美密會上, Canale 等人提出了自動化地應(yīng)用Simon 算法的工具[30], 并給出了MISTY L-FK 和Feistel-FK 分析.

3.1.2 認(rèn)證和認(rèn)證加密算法的量子分析方面

在學(xué)術(shù)界發(fā)現(xiàn)多種認(rèn)證和認(rèn)證加密算法存在量子攻擊[7,31]之后, 密碼學(xué)者開始對認(rèn)證和認(rèn)證加密算法的抗量子攻擊能力進行了更深入的研究.在SAC 2017 上, Bonnetain 給出了CAESAR 認(rèn)證加密競賽候選算法AEZ 量子密鑰恢復(fù)攻擊[32].Shi 等人發(fā)現(xiàn)了AEZ-PRF 的碰撞攻擊, 基于量子Simon 算法可以構(gòu)造該算法的偽造攻擊[33].在2021 年亞密會上, Bonnetain 等人提出了量子線性化攻擊(quantum linearization attack)[34], 該方法可以基于Simon 算法[8]、Deutsch 算法[35,36]、Bernstein-Vazirani 算法[37]、以及Shor 算法[1]等多種量子算法構(gòu)造量子攻擊.基于量子線性化攻擊, Bonnetain 等人給出了多種并行MAC 的量子攻擊, 包括LightMac、PMAC 以及多種具備超越生日安全界的MAC (beyondbirthday-bound MAC, BBB MAC), 如LightMAC+、PMAC+, 以及ZMAC、PolyMAC 等[34].在PQCrypto 2021 上, Guo 等人針對12 種BBB MAC 的抗量子攻擊安全性進行了系統(tǒng)性的研究[38].隨后, Sun 等人給出了BBB MAC 的新型量子攻擊[39].2022 年, Guo 等人針對基于公開置換的偽隨機函數(shù)給出了一些列量子攻擊[40].

3.1.3 經(jīng)典分析方法的量子化(Q2 模型)

2016 年, Kaplan 等人[7]給出了經(jīng)典滑動攻擊(slide attack)[41]的量子化版本, 并取得了指數(shù)級加速.針對高級滑動攻擊[42], Bonnetain 等人[43]和Dong 等人[44]分別獨立地提出了量子化版本, 給出了2K-/4K-Feistel 等算法的量子攻擊.針對俄羅斯標(biāo)準(zhǔn)GOST 分組密碼, 董曉陽等人提出了經(jīng)典的反射攻擊(reflection attack) 和不動點攻擊(fixed point attack) 的量子化版本[44], 給出該算法全輪的量子密鑰恢復(fù)攻擊.2019 年, Xie 和Yang 利用Bernstein–Vazirani 算法[37]研究了分組密碼的差分分析和不可能差分分析[45].Cai 等人結(jié)合量子BHT 算法[46]和滑動攻擊, 給出了1K-AES 和PRINCE 分組密碼的量子密鑰恢復(fù)攻擊[47].Chen 等人提出了搜索不可能差分和零相關(guān)區(qū)分器的量子算法[48].David 等人提出了SKINNY 和AES-192/-256 的量子不可能差分攻擊[49].Frixons 等人[50]和Zou 等人[51]研究了量子飛去來器攻擊.Hosoyamada 提出了量子多維(零相關(guān)) 線性和積分攻擊[52].隨后, Schrottenloher 在Q1 和Q2 模型下提出了基于量子傅里葉變換的量子線性攻擊[53].

3.2 Q1 型攻擊

在Q1 量子安全模型下, 攻擊者只需要通過經(jīng)典的方式收集明密文對, 然后利用離線的量子計算機對密碼進行分析.因此,相對于Q2 量子安全模型,Q1 模型對攻擊前提假設(shè)比較弱,因此攻擊更加實際.除了Q2 模型下的多項式時間量子攻擊, Kuwakado 和Morii[6]針對Even-Mansour (EM) 密碼亦提出了Q1模型下利用BHT 算法的量子攻擊, 其所需的經(jīng)典查詢、量子計算復(fù)雜度和量子比特數(shù)量均為O(2n/3).在CT-RSA 2018 上, Hosoyamada 和Sasaki[54]將EM 結(jié)構(gòu)的Q1 型攻擊所需的量子比特數(shù)目降低為多項式級別, 但是所需的經(jīng)典查詢和量子計算復(fù)雜度升高至O(23n/7).同時, 他們給出了多種MAC 算法的Q1 型攻擊, 如Chaskey、McOE-X 等.在2019 年亞密會上, Bonnetain 等人針對EM 結(jié)構(gòu)、FX 結(jié)構(gòu)等提出了離線的Simon 算法[55], 并在TCHES2022 上給出了具體的量子實現(xiàn)[56].在2022 年歐密會上,Bonnetain 等人給出第一個在僅使用經(jīng)典查詢的情況下, 相比于最佳經(jīng)典攻擊實現(xiàn)二次方加速的量子Q1型攻擊[57].

在經(jīng)典分析法的量子化方面, Kaplan 等人[58]在2016 年提出了量子差分分析和量子線性分析.2018年, Hosoyamada 給出了6 輪Feistel 結(jié)構(gòu)的量子Demiric-Sel?uk (DS) 中間相遇攻擊[59].隨后, Bonnetain 等人針對AES 提出了量子Square 攻擊和DS 中間相遇攻擊[60].Naya-Plasencia 等人提出Q1模型下的飛去來器攻擊[50]和不可能差分攻擊[49].

4 哈希函數(shù)的量子分析

密碼哈希函數(shù)H可以將一個任意比特長度的消息M壓縮成n比特固定長度的摘要T.給定一個初始向量IV, 一個安全的哈希函數(shù)在經(jīng)典計算環(huán)境下應(yīng)滿足以下三個基本安全屬性:

? 抗原像攻擊屬性(preimage resistance): 對于給定的摘要T, 尋找到消息M, 使得H(IV,M)=T,所需的時間復(fù)雜度應(yīng)不低于O(2n).

? 抗碰撞攻擊屬性(collision resistance): 尋找兩個消息(M1,M2), 使得H(IV,M1)=H(IV,M2), 所需的時間復(fù)雜度應(yīng)不低于O(2n/2).

? 抗第二原像攻擊屬性(2nd-preimage resistance): 給定消息M, 尋找另外一個消息M′, 使得H(IV,M′)=H(IV,M), 所需的時間復(fù)雜度應(yīng)不低于O(2n).

在量子計算環(huán)境下, 可以利用Grover 算法[3]尋找哈希函數(shù)的原像和第二原像, 所需的時間復(fù)雜度是O(2n/2).針對碰撞攻擊, 學(xué)術(shù)界又分為以下三類:

? 標(biāo)準(zhǔn)碰撞攻擊(collision attack): 找到兩個消息(M1,M2), 滿足H(IV,M1)=H(IV,M2).

? 半自由起始碰撞攻擊(semi-free-start collision attack): 找到兩個消息(M1,M2) 和IV, 滿足H(u,M1)=H(u,M2).

? 自由起始碰撞攻擊(free-start collision attack): 找到兩個消息(M1,M2)、v和v′, 且′, 滿足H(v,M1)=H(v′,M2).

針對碰撞攻擊, 由于不同的攻擊假設(shè)或條件下, 量子碰撞攻擊所需的資源和時間復(fù)雜度不同, 需要分類討論.

4.1 通用量子碰撞攻擊

4.1.1 需要大規(guī)模量子存儲的量子碰撞攻擊算法

1998 年, Brassard、H?yer 和Tapp 提出了BHT 算法[46], 能夠在O(2n/3) 時間復(fù)雜度和O(2n/3)規(guī)模的量子存儲(quantum random access memory, qRAM) 復(fù)雜度下找到碰撞.這里量子存儲qRAM是經(jīng)典存儲RAM 的量子形態(tài), 其能夠以量子疊加態(tài)高效地被訪問.假設(shè)L= (x0,x1,···,x2m?1), 其中xi ∈Fn2(i= 0,1,···,2m ?1).那么, 存儲L的量子存儲qRAM 進行如下酉變換操作, 定于酉變換UqRAM(L) 為:

其中i ∈Fm2為訪問的地址,xi ∈Fn2為地址i上存儲的數(shù)據(jù).因此我們能夠以處于量子疊加態(tài)的地址訪問L, 并獲得相應(yīng)地址上的數(shù)據(jù)的量子疊加態(tài):

量子存儲是否存在, 取決于是否存在一個量子門線路能夠?qū)崿F(xiàn)公式(11)的酉變換.在該表L的量子存儲存在的前提假設(shè)下, BHT 算法尋找一個隨機函數(shù)f:{0,1}n {0,1}n的碰撞一共包括兩步:

(1) 任意選子集合X ?{0,1}n, 集合大小為|X| = 2n/3.對所有x ∈X, 計算f(x), 并將2n/3個對L={(x,f(x))}x∈X存儲到量子存儲qRAM 中.這一步所需時間是O(2n/3).所需的量子存儲大小是O(2n/3).

總之, 在假設(shè)存在大規(guī)模量子存儲qRAM 的前提假設(shè)下, 不考慮并行計算, BHT 算法能夠以O(shè)(2n/3) 的時間復(fù)雜度和O(2n/3) 的量子存儲找到一個碰撞.

4.1.2 僅需要大規(guī)模經(jīng)典存儲的量子碰撞攻擊算法

BHT 算法構(gòu)造碰撞攻擊盡管其僅需要時間復(fù)雜度O(2n/3),但它們需要O(2n/3)規(guī)模的量子存儲.目前研究人員普遍認(rèn)為制造大規(guī)模量子存儲的難度是巨大的[9,10].因此在沒有大規(guī)模量子存儲的前提下, 是否存在優(yōu)于生日攻擊(復(fù)雜度為O(2n/2)) 的量子碰撞攻擊算法成為一個公開問題.在2017 年亞密會上,法國密碼學(xué)家Chailloux 等人首次提出了不需要大規(guī)模量子存儲的量子碰撞攻擊算法[61], 其時間復(fù)雜度是O(22n/5), 同時需要O(2n/5) 的經(jīng)典存儲以及O(n) 的量子存儲, 我們記該量子算法為CNS 量子碰撞攻擊算法.首先, Chailloux 等人給出了一個如何檢測某元素是否存在于列表L={x1,x2,···,x2k}, 該列表存儲于經(jīng)典內(nèi)存中, 大小為2k.

定義1 給定列表L={x1,x2,···,x2k}, 定義一個經(jīng)典的成員檢測函數(shù)fL:fL(x) = 1 當(dāng)且僅當(dāng)x ∈L, 否則fL(x)=0.

設(shè)該經(jīng)典的成員檢測函數(shù)fL的量子實現(xiàn)(即量子成員檢測函數(shù)) 為OL:

當(dāng)L被存儲在經(jīng)典內(nèi)存中, Chailloux 等人能夠以n2k的時間復(fù)雜度和2n+1 量子比特實現(xiàn)OL.CNS量子碰撞攻擊算法可以被劃分為兩部分, 即預(yù)計算階段和匹配階段.

當(dāng)設(shè)r=2k=2n/5, 公式(15)達到最小值, 即時間復(fù)雜度最優(yōu), 為O(22n/5).所需的量子比特規(guī)模O(n),同時需要規(guī)模為2n/5經(jīng)典存儲來存L.

4.2 專用量子碰撞攻擊

在量子計算環(huán)境中尋找哈希函數(shù)的碰撞是很重要的研究方向.最近, 包括美國NIST 后量子公鑰密碼標(biāo)準(zhǔn)化競賽候選算法在內(nèi)的一些公鑰密碼方案在量子隨機預(yù)言模型(quantum random oracle model,QROM) 下被證明是安全的[2,62].量子隨機預(yù)言模型允許敵手以量子疊加態(tài)查詢公鑰系統(tǒng)中的哈希函數(shù),因此其哈希函數(shù)不應(yīng)存在任何比通用量子攻擊更有效的專用量子攻擊, 包括專用量子碰撞攻擊.

在經(jīng)典計算模型下, 對n比特輸出的理想哈希函數(shù)的最優(yōu)通用碰撞攻擊復(fù)雜度為O(2n/2).在量子計算模型下, 在不同的假設(shè)下共有三種通用碰撞攻擊:

? 第一種情況中, 假設(shè)攻擊者擁有指數(shù)量級的量子隨機存儲(qRAM), 在這種情況下的最優(yōu)攻擊為BHT 算法(見第4.1.1 節(jié)), 其時間復(fù)雜度為O(2n/3), 但它同時需要O(2n/3) 的qRAM.

? 第二種是在沒有指數(shù)級qRAM, 但是攻擊者擁有大規(guī)模經(jīng)典存儲的情況下, 最優(yōu)攻擊為Chailloux等人在2017 年亞密會上提出的方法(即第4.1.2 節(jié)的CNS 量子碰撞攻擊算法), 時間復(fù)雜度為O(22n/5), 而需要O(2n/5) 的經(jīng)典隨機存儲和O(n) 的qRAM.

在量子計算模型中的這幾個不同假設(shè)下的通用碰撞攻擊將作為評判專用量子碰撞攻擊優(yōu)劣的基準(zhǔn).2020 年歐密會上日本學(xué)者Hosoyamada 等人[65]在國際上首次給出了哈希函數(shù)的專用量子碰撞攻擊, 其在第一種和第三種情況下針對哈希模式AES-MMO 和標(biāo)準(zhǔn)哈希函數(shù)Whirlpool 給出了優(yōu)于通用攻擊的量子專用碰撞攻擊.他們將經(jīng)典計算模型下Mendel 等人提出的反彈攻擊技術(shù)[66]轉(zhuǎn)化為量子的反彈攻擊技術(shù).該工作的意義在于指出了那些在經(jīng)典計算模型下概率低于生日界從而無法使用的差分路線, 在量子計算模型下仍能利用攻擊.在擁有大規(guī)模量子隨機存儲易制備的前提下(第一種情況), Hosoyamada 等人[65]針對AES-MMO 和AES-MP 給出了優(yōu)于BHT 算法的7 輪量子碰撞攻擊.在第三種情況下, 他們給出了優(yōu)于通用攻擊的7 輪AES-MMO/-MP 和6 輪Whirlpool 等哈希算法的量子碰撞攻擊, 較經(jīng)典攻擊均提升了1 輪.但是, 在第二種情況下, 即攻擊者沒有大量qRAM, 但是具備大規(guī)模經(jīng)典存儲時,Hosoyamada 和Sasaki 未獲得攻擊復(fù)雜度優(yōu)于CNS 量子碰撞攻擊的專用攻擊方法.

目前情況下, 無論是制備大規(guī)模量子比特或者qRAM 都是非常困難的, 能否制造出大的qRAM 即使在量子計算學(xué)界也是一個頗有爭議的問題[10,67].因此, 如何在只使用小規(guī)模量子計算機, 且使用少量qRAM 或不使用qRAM 的情況下超越Chailloux 等人提出的方法, 便成為一個重要的且較為實際的問題.在2020 年亞密會上, Dong 等人提出了利用非飽和超級S 盒降低qRAM 使用的反彈攻擊方法, 并結(jié)合量子計算, 提出了一個低qRAM 復(fù)雜的量子碰撞攻擊方法[68].該工作還指出, 利用Bonnetain 等人給出的一個專用的量子電路在線計算滿足一定S 盒輸入輸出差分的數(shù)據(jù)對[60], 可以完全避免qRAM 的使用.該工作的意義在于, 其首次給出了在不使用qRAM 的情況下, 超越Chailloux 等人方法的專用量子碰撞攻擊.同時, 該工作還給出了一個基于混合整數(shù)規(guī)劃(MILP) 技術(shù), 自動化搜索用于量子碰撞攻擊最優(yōu)差分路線的方法.

在2021 年亞密會上,Dong 等人利用相關(guān)密鑰差分路線構(gòu)造基于反彈技術(shù)的經(jīng)典和量子碰撞攻擊[69],并構(gòu)造了基于混合整數(shù)線性規(guī)劃的自動化搜索模型, 搜索適用于構(gòu)造經(jīng)典和量子碰撞攻擊的差分特征.該攻擊的想法是利用密鑰自由度, 提高差分路線的概率.在自動化模型建立過程中, 有效地解決了某些哈希函數(shù)存在相關(guān)密鑰差分路線多輪不兼容的情形, 自動化地搜索出有效的攻擊路線.基于上述想法, 他們首次給出ISO 標(biāo)準(zhǔn)哈希函數(shù)Whirlpool 的9 輪自由起始量子碰撞攻擊(free-start quantum collision).

在軍事題材的影視作品中，常常出現(xiàn)指戰(zhàn)員們站在一個巨大的沙盤前討論戰(zhàn)爭形勢的情形。傳統(tǒng)意義上的沙盤作為地圖的補充，彌補了傳統(tǒng)軍事地圖無法形象表現(xiàn)出戰(zhàn)場地勢地形的缺陷，為廣大指戰(zhàn)員提供了在和平時期進行戰(zhàn)爭推演的平臺。而全息數(shù)字沙盤，在具備傳統(tǒng)沙盤的功能的同時，還摒棄了傳統(tǒng)沙盤搭建時間長、精度差、重復(fù)使用率低的缺陷。并且模塊化的硬件使得沙盤可以多次使用，數(shù)字影像又實現(xiàn)了在使用時，可以全方位多角度地觀察戰(zhàn)場。并且其易于儲存方便攜帶的特點，也使得隨行保障更加便捷。

在2021 年美密會上, Hosoyamada 等人首次研究了針對SHA-256 和SHA-512 的專用量子碰撞攻擊[70], 攻擊分別達到38 步和39 步, 顯著改進了31 步和27 步的經(jīng)典碰撞攻擊.攻擊采用的框架是將許多半自由起始碰撞(semi-free-start quantum collision) 攻擊轉(zhuǎn)換為兩消息塊碰撞攻擊.在第三種情況(時空權(quán)衡) 下, 能夠比并行rho 算法更加高效.Hosoyamada 等人觀察到在量子計算條件下, 利用Grover 算法可以顯著減少所需的半自由啟動碰撞次數(shù), 這使其能夠?qū)⒅敖?jīng)典的38 步和39 步半自由起始碰撞攻擊轉(zhuǎn)換為量子碰撞攻擊.該攻擊背后的想法很簡單, 也將適用于其他密碼哈希函數(shù)的量子碰撞攻擊.

在2022 年美密會上, Dong 等人進一步利用哈希函數(shù)消息自由度延長反彈攻擊路線[71].一般情況下,反彈攻擊包括一個Inbound 階段和兩個Outbound 階段.如何拉長反彈攻擊的輪數(shù)是一個重要的密碼分析難題.相關(guān)研究包括Gilbert 和Peyrin 在FSE 2010 上提出的超級S 盒技術(shù)[72], 以及Sasaki 等人在2010 年亞密會上提出的非滿活躍盒的超級S 盒技術(shù)[73].然而這些技術(shù)僅能將Inbound 階段擴展至2 輪.在上述工作基礎(chǔ)上, 文獻[71] 提出了名為對角化反彈攻擊(triangulating rebound attack) 的新型方法.該方法利用壓縮函數(shù)中的消息自由度鏈接多輪Inbound 階段, 顯著延長了反彈攻擊的輪數(shù).鏈接過程需要建立并求解一組關(guān)于消息的非線性方程組, 作者利用類似高斯消元(triangulation algorithm, 對角化) 方法[74], 通過合理消耗消息自由度, 高效地求解非線性方程組, 從而成功構(gòu)造多Inbound 階段的反彈攻擊.該攻擊僅需要少量的內(nèi)存, 這使得其也能夠用于構(gòu)造低量子隨機存儲的量子碰撞攻擊.同時, 作者還提出了基于可滿足性問題(constrained programming)建立自動化搜索模型,高效地搜索多輪Inbound 的反彈攻擊路線.基于該方法, 作者首次將AES-MMO 的碰撞攻擊突破至8 輪.另外, 還給出了Saturnin-Hash、Gr?stl-512、SKINNY-128-384-MMO/MP 等哈希函數(shù)的多個減輪的經(jīng)典和量子碰撞攻擊.

除了上述分析外, Flórez-Gutiérrez 等人[75]給出了Gimli-Hash 的自由起始量子碰撞攻擊.Kumar等人研究了基于Hirose 雙分組哈希模型下的AES-256 (記為HCF-AES-256, 全輪14 輪) 的量子碰撞攻擊[76].Ni 等人研究了Simpira v2 置換函數(shù)在Davies-Meyer 哈希模式下的量子碰撞攻擊[77].Guo 等人給出了SHA-3 哈希函數(shù)減輪的量子碰撞攻擊[78].這些攻擊意味著在量子計算模型下, 可以用于攻擊的密碼特征范圍被大大擴展了.因此, 如何搜索這些特征并利用它們進行基于量子計算的密碼分析會成為對稱密碼分析和設(shè)計領(lǐng)域的一個重要問題.

4.3 哈希函數(shù)的量子原象攻擊

給定一個n比特摘要, 利用Grover 算法可以在2n/2的時間復(fù)雜度下搜索出原象.在專用量子原象攻擊方面, Schrottenloher 和Stevens 在2022 年美密會上提出了量子中間相遇攻擊(quantum Meet-inthe-Middle, quantum MitM) 求解原象[79].該算法的核心是找到兩個列表中相等的元素, 被稱為雙列表融合量子算法(quantum two-list merging algorithm).假設(shè)在中間相遇過程中, 需要遍歷一個全局猜測空間Fg2, 對于每一個猜測G ∈Fg2, 攻擊者可以構(gòu)造兩個列表L1和L2, 并判斷是否存在x ∈L1和y ∈L2,使得x=y.令Omerge是如下的酉變換:

Schrottenloher 和Stevens 給出量子中間相遇的如下引理:

引理1[79](量子中間相遇攻擊) 實現(xiàn)Omerge的時間復(fù)雜度是

其中Lmerge是一個融合后的列表.實現(xiàn)Omerge所需的量子隨機存儲大小為min(|L1|,|L2|).因此, 量子中間相遇攻擊的復(fù)雜度為:

此外, Wang 等人[80]結(jié)合旋轉(zhuǎn)攻擊給出了Keccak-224 的4 輪量子原像攻擊.Chen 等人[81]提出了一個求解布爾方程的量子算法, 并應(yīng)用到了哈希函數(shù)的原像攻擊中.

4.4 哈希函數(shù)的多目標(biāo)原象攻擊(Multi-target preimage attack)

定義 2 (多目標(biāo)原象攻擊) 給定一個隨機函數(shù)H:{0,1}n {0,1}n以及一個摘要集合T={y1,y2,···,y2t}, 找到一個集合T中某一個元素yi的原象, 即找到i ∈{1,2,···,l}和x ∈{0,1}n,滿足H(x)=yi.

在經(jīng)典計算模型中, 上述多目標(biāo)原象攻擊的復(fù)雜度約為O(2n?t).在SAC 2017 上, Banegas 和Bernstein 介紹了并行的量子多目標(biāo)原象攻擊[82].假設(shè)量子隨機存儲跟經(jīng)典隨機存儲一樣能夠簡單制備,那么將T存儲于量子隨機存儲中, 可以利用Grover 算法搜索x, 使得H(x) 在T中.這種情況下, 量子多目標(biāo)原象攻擊的時間復(fù)雜度約為O(2(n?t)/2), 所需量子隨機存儲的大小是2t.

在CNS 量子碰撞攻擊的論文中, 作者亦給出了在量子隨機存儲非常昂貴的情況下, 用經(jīng)典隨機存儲構(gòu)造量子多目標(biāo)原象攻擊的方法[61].其所需的時間復(fù)雜度是2n/2?t/6+min{2t,23n/7}, 所需的量子隨機存儲為O(n), 所需的經(jīng)典隨機存儲是min{2t/3,2n/7}.當(dāng)t= 23n/7時, 整體復(fù)雜度達到最優(yōu), 即時間是23n/7, 經(jīng)典隨機存儲是2n/7.

4.5 多碰撞問題(Multi-collisions)

4.6 廣義生日攻擊的量子解法

廣義生日攻擊問題的經(jīng)典模型最優(yōu)解法是Wagner 提出的[87], 其所需經(jīng)典時間復(fù)雜度和存儲均為O(2n/(t+1)), 其中k=2t.在2018 年亞密會上, Grassi 等人[88]在攻擊者具有多項式規(guī)模量子存儲、指數(shù)規(guī)模量子存儲兩種假設(shè)下給出了多種廣義生日攻擊的量子解法.在2020 年歐密會上, Naya-Plasencia 等人在不需要量子存儲的假設(shè)下, 給出了廣義生日攻擊的最優(yōu)量子算法[89], 同時給出了在不需要查詢量子預(yù)言機的假設(shè)下的量子求解算法.在SAC 2021 上, Schrottenloher 針對僅具有唯一解的廣義生日攻擊問題, 提出了一般性量子算法[90].

4.7 預(yù)言者攻擊(Nostradamus attack)

在2022 年亞密會和NSS 上, Benedikt 等人[94]和Bao 等人[95]分別獨立研究了量子計算模型下的預(yù)言者攻擊, 其所需的量子時間復(fù)雜度是O(20.43n) 且需要O(20.43n) 規(guī)模的量子存儲.在亞密會文章中作者還提出了如何在不使用量子存儲的情況下設(shè)計量子攻擊算法的公開問題.隨后, 在ToSC 2023 上,Zhang 等人利用中間相遇攻擊給出了AES 類哈希函數(shù)的專用量子和經(jīng)典的預(yù)言者攻擊[96].在2023 年亞密會上, Dong 等人[97]解決了2022 年亞密會上Benedikt 等人提出的公開問題, 提出了不使用量子存儲的新型量子預(yù)言者攻擊, 其攻擊的時間復(fù)雜度相較于Benedikt 等人的攻擊僅由O(20.43n) 略微上升至O(20.46n).該文章還提出了其他一些哈希結(jié)構(gòu)(如, 哈希異或組合H1⊕H2、哈希級聯(lián)組合H12、兩次哈希、Zipper 哈希等) 的量子原像、量子碰撞、量子預(yù)言者攻擊等.在ToSC 2024 上, Dong 等人[98]利用其提出的不使用量子存儲的量子預(yù)言者攻擊, 結(jié)合中間相遇攻擊方法, 改進了AES 類哈希函數(shù)的專用量子和經(jīng)典的預(yù)言者攻擊.

5 總結(jié)和展望

對稱密碼的量子分析研究是自2010 年之后才開始蓬勃發(fā)展的研究方向, 十余年來所取得的重要進展表明量子計算模型能夠顯著提升對稱密碼的攻擊效果, 甚至在某些量子攻擊假設(shè)下, 某些經(jīng)典密碼算法可以被量子多項式時間破解.另一方面, 在密碼分析過程中, 研究者設(shè)計了新的量子算法, 這些算法反過來又促進了量子計算的進步.在后續(xù)研究中, 以下幾個研究方面值得進一步探索:

量子算法設(shè)計與創(chuàng)新: 針對RSA 公鑰密碼的大整數(shù)分解問題, Peter Shor 設(shè)計了Shor 算法.因此,針對密碼基于的數(shù)學(xué)問題設(shè)計高效的量子求解算法是密碼分析的重要研究方向.同時, 挖掘和應(yīng)用已知的量子算法進行密碼分析也是重要研究內(nèi)容.目前密碼學(xué)者已將多種量子算法應(yīng)用于密碼分析, 包括Grover算法、Simon 算法、Kuperberg 算法等.甚至, 密碼學(xué)者可以將多種量子算法加以結(jié)合, 設(shè)計出針對具體密碼算法的新型量子分析方法, 如Grover 和Simon 的結(jié)合使用、Grover 和Kuperberg 的結(jié)合使用等.

經(jīng)典計算模型下的密碼分析技術(shù)的量子化: 對稱密碼的經(jīng)典分析方法已經(jīng)發(fā)展了四十余年, 期間積累了眾多經(jīng)典分析方法,包括中間相遇攻擊、差分分析、線性分析、不可能差分分析、零相關(guān)密碼分析、代數(shù)攻擊、反彈攻擊等.如何利用量子算法將這些經(jīng)典分析方法量子化,并提升分析效果,是一個重要的研究方向.