董炳佑, 劉 泰, 崔玉龍, 倪博煜, 秦嶺月, 董曉陽

1. 清華大學高等研究院, 北京 100084

2. 中車青島四方機車車輛股份有限公司, 青島 266111

3. 山東大學密碼技術與信息安全教育部重點實驗室, 濟南 250199

4. 山東大學網絡空間安全學院, 青島 266237

1 前言

在1994 年, Shor 算法[1]的提出, 說明一個足夠大的量子計算機可以在多項式時間內分解大整數、計算離散對數問題等, 對目前使用的許多公鑰密碼方案都帶來重大安全影響. 這激起了大家對抗量子計算機攻擊的密碼的研究興趣, 公鑰密碼學社區(qū)和標準化組織在后量子公鑰密碼學的研究上投入了大量的精力.相比之下, 人們普遍認為, 量子計算攻擊對對稱密碼安全性影響有限, 因為當攻擊者使用量子計算機攻擊對稱密碼時, 優(yōu)勢是使用Grover 算法[2]來加速密鑰的搜索, 然而將密鑰長度加倍就可以解決這個問題.直到2010 年, Kuwakado 和Morii 證明了經典可證明安全的Even-Mansour 結構密碼和三輪Feistel 結構可以在量子計算機的幫助下在多項式時間內被破解[3,4]. 接下來的幾年, 更多的對稱密碼設計結構被量子計算算法攻擊[5–13]. 幾乎所有這些指數級加速的攻擊都是通過Simon 的算法[14]來找到一個依賴于密鑰的隱藏周期, 在尋找這個隱藏周期時, 需要以量子明文疊加態(tài)訪問加密算法, 并獲得密文疊加態(tài). 這是一個相當強的要求, 敵手需要在線訪問一個用量子電路實現的加密算法. 因此, 如果不需要對密鑰原語的量子疊加預言機進行在線查詢, 那么使用更高復雜度的量子計算攻擊仍然是有意義的[7,15].

與加密算法不同, 哈希函數不需要密鑰. 因此敵手可以離線實現哈希函數的量子電路, 并利用量子疊加態(tài)訪問該量子電路, 并獲得量子疊加態(tài). 一個安全哈希函數需要具備抗碰撞攻擊、抗原象攻擊和抗第二原象攻擊等安全屬性, 本文針對AES 類哈希函數抗碰撞攻擊的安全性展開研究. AES 類哈希函數采用類似于AES 的輪函數設計, 典型AES 類哈希算法包括AES 哈希模式AES-MMO/MP、Gr?stl[16]、Whirlpool[17]等. 經典計算環(huán)境下, 反彈攻擊[18]是分析AES 類哈希函數的有效手段. 在量子計算環(huán)境下, Hosoyamada 和Sasaki[19]在2020 年歐密會上提出反彈攻擊的量子實現算法, 給出了7 輪AESMMO 和6 輪Whirlpool[17]的量子碰撞攻擊. 在2020 年亞密會上, 董曉陽等[20]提出了不使用qRAM的量子碰撞攻擊, 首次超越Chailloux 等[21]給出的一般碰撞攻擊界. 在2021 年美密會上, Hosoyamada和Sasaki[22]提出了一些列減輪SHA-2 算法的量子碰撞攻擊. 在ToSC 2020 上, Chauhan 等[23]研究了雙塊AES 壓縮函數模式的量子碰撞攻擊. 在ToSC 2021 上, 倪博煜等[24]研究了Simpira v2 哈希模式的量子碰撞攻擊. 在2021 年亞密會上, 董曉陽等[25]研究了哈希函數的自由起始的量子碰撞攻擊.

對于一個輸出為n比特摘要值的哈希函數, 在經典環(huán)境下, 需要O(2n/2) 的時間復雜度來尋找碰撞.在量子計算環(huán)境下, 根據已有的量子算法可以得到以下碰撞的一般界:

(3) CNS 算法[21]需要時間復雜度T=22n/5來找到一組碰撞, 另外需要大小為2n/5的經典內存.那么, 一個成功的量子碰撞攻擊必須優(yōu)于至少一種量子碰撞攻擊一般界.

1.1 本文貢獻

表1 針對Gr?stl 的經典與量子碰撞攻擊Table 1 Classical and quantum collision attacks on Gr?stl

2 預備知識

本節(jié)簡要介紹類AES 哈希函數、反彈攻擊、量子計算和量子隨機存儲器(quantum random access memory, qRAM), 以及一些常用的量子算法.

2.1 類AES 哈希函數

為明確起見, 首先回顧AES-128 的輪函數. 它作用在排列成矩陣的16 字節(jié)狀態(tài)上, 包括四個主要的變換: 字節(jié)替換SubBytes(SB)、行位移ShiftRows(SR)、列混合MixColumns(MC) 和密鑰加AddRoundKey(AK), 如圖1 所示. 對這些變換適當修改, 就可以改變輪函數的參數, 如矩陣的行列數量、單元的大小、變換作用的順序, 乃至交換行列排列(亦即將矩陣轉置), 進而新參數可以生成新的輪函數設計.這種在AES 輪函數上進行修改的設計可以粗略稱為類AES 輪函數. 本文假定列混合(MC) 是將狀態(tài)矩陣的每一列乘上一個MDS 矩陣的操作.

圖1 AES 輪函數Figure 1 Round function of AES

Gr?stl 算法是SHA-3 最終候選哈希函數之一, 有Gr?stl-256 和Gr?stl-512 兩個版本. 處理兩個消息分組的的結構如圖2, 其中P和Q是兩個n比特的類AES 置換. 在算法輸出哈希值之前,一個基于P的輸出變換和一個截斷函數Ω :→會作用在h2上. 更多算法設計細節(jié)讀者可以參考文獻[16].

董曉陽等[20]給出了Gr?stl-512 的4 輪、5 輪經典和量子碰撞攻擊. 圖3 展示了Gr?stl 的等價描述.令P-和Q-為去掉最后一個MixBytes(MB) 操作的類AES 置換, 有如下等價表示, 其中1≤i ≤t,

圖2 處理兩個消息分組的Gr?stl-Figure 2 Gr?stl- with two message blocks

圖3 處理兩個消息分組的Gr?stl-: 等價表示Figure 3 Alternative descriptionofGr?stl-n withtwomessage blocks

2.2 量子計算和量子隨機存儲器

一個擁有n個量子比特的系統(tǒng)狀態(tài)可以描述為 C2n空間上的一個單位向量, 可取一組正交基{|0···00〉,|0···01〉,··· ,|1···11〉}來表示, 稱為計算基(computational basis). 它是量子計算中常用的一組基, 亦可記為{|i〉: 0≤i ＜2n}. 一般來說, 量子算法的實現即是利用一系列的酉變換和測量對量子系統(tǒng)進行操控, 而所有的酉變換可以用一組單量子比特和雙量子比特變換來表示. 這種表示即是標準量子電路模型下的量子門表示, 一個量子算法的效率就可以用表示該算法需要使用的量子門數量來定量描述.

2.2.1 經典電路的疊加態(tài)預言機

給定一個經典的布爾函數:f:→F2.f的疊加態(tài)預言機定義為作用在一個(n+1)-量子比特的系統(tǒng)上的酉變換Uf, 它將基態(tài)|x,y〉變?yōu)閨x,y ⊕f(x)〉, 其中x ∈,y ∈F2. 作為一個線性算子,Uf作用在疊加態(tài)上將得到

注意到, 只要存在一個高效的經典電路可以計算f, 那么Uf就可以用量子電路模型高效實現, 而如前所述, 這只需要找到一個實現f的高效可逆電路, 再將其中的可逆門電路用量子門替代就可以了.

2.2.2 Grover 算法[2]

這里存在一個漏洞: Grover 算法的整體復雜性可能被隱藏在所調用的預言機電路的構造開銷中了.除非預言機的電路可以被高效實現, 否則算法對于搜索的加速將會沒有作用. 因此, 明確實現這樣的預言機需要怎樣的資源是十分重要的, 例如高效實現預言機可能需要一個大容量的qRAM.

2.2.3 量子振幅放大算法[31]

量子振幅放大可以視作Grover 算法的一種推廣, 后者限制A產生所有基向量的均一疊加態(tài). 類似地, 在分析量子振幅放大的復雜度時, 應當計入實現UP和A的復雜度.

2.2.4 量子隨機存儲器(qRAM)

量子隨機存儲器(qRAM) 是經典隨機存儲器(RAM) 的量子版本, 它使用n量子比特來表示任何2n個存儲單元構成的量子疊加態(tài). 給定一列經典數據L={x0,x1,··· ,x2n-1}, 其中xi ∈Fm2,L對應的qRAM 可以用一個酉變換

其中i ∈,y ∈, 且|·〉Addr和|·〉Out分別是地址和輸出存儲器. 這樣一來, 就可以訪問這些數據的任意量子疊加態(tài), 輸入對應地址的量子疊加態(tài)就能得到:

到目前為止, 如何構造一個可行的qRAM (至少說是大容量的qRAM) 仍舊未知. 盡管如此, 這一令人失望的事實并沒有阻止研究者在假定大容量qRAM 可用的模型下開展工作, 就像人們在經典或量子計算機被建造出來之前早就開始研究經典或量子算法一樣. 另一方面, 大容量qRAM 尚未出現, 而規(guī)模O(n) 的qRAM 可以用規(guī)模O(n) 的量子電路進行模擬, 因此嘗試減少甚至避免qRAM 在量子算法中的使用進行研究是相當有意義的.

2.3 反彈攻擊及其改進

反彈攻擊是由文獻[18] 首先引入的, 如圖4 所示, 它包含入站階段(Inbound) 和出站階段(Outbound). 在入站階段, 通過中間相遇降低復雜度, 從而找到滿足入站階段差分的數據對, 該數據對被稱為起點(Starting Point). 然后在出站階段, 通過大量的起點數據對分別向前和向后推算, 找到滿足出站階段差分的數據對.

圖4 反彈攻擊Figure 4 Rebound attack

為了提升入站階段的差分路徑可以覆蓋的輪數, 文獻[32,33] 分別獨立地提出了超級S 盒技術, 把連續(xù)兩輪類AES 輪函數視作一個由超級S 盒構成的整體. 后來文獻[34] 指出利用非全活躍超級S 盒的差分性質可以顯著地降低反彈攻擊所需要的空間復雜度.

下面考慮更一般的情況: 某密碼系統(tǒng)的內部狀態(tài)是一個d×d矩陣, 每個單元代表c比特數據. 參考圖5 是d=4 的情況, 對應有d=4 個超級S 盒.

2.4 全活躍超級S 盒

沿用圖5 中的記號, 利用全活躍超級S 盒的反彈攻擊的入站階段, 步驟如下:

圖5 全活躍與非全活躍超級S 盒差分路徑對比Figure 5 Differential of full-active and non-full-active super S-box

對于給定的Δin, 可以生成2d·c對起點, 需要d×2d·c的空間來儲存d個列表, 生成一對起點的平均時間復雜度為O(1).

2.5 非全活躍超級S 盒

考慮一列由d個c比特單元組成的狀態(tài)A, 經過超級S 盒SSB = SB°MC°SB 被映射為狀態(tài)D= SSB(A), 中間狀態(tài)依次為B和C, 其中SB 是d個c×c的小S 盒的并聯, 而MC : Fd2c →Fd2c是分支數為n+1 的MDS 線性變換, 那么有命題1 成立.

命題1(MDS 性質) 令MC·(X[0],X[1],··· ,X[d-1])T= (Y[0],Y[1],··· ,Y[d-1])T, 若X[0],X[1],··· ,X[d-1],Y[0],Y[1],··· ,Y[d-1] 中至少一半已知, 那么可以由等式關系推知其余未知項.

假設一個差分輸入超級S 盒, 使得其中有s個c×c的S 盒不活躍, 那么活躍的S 盒有2d-s個. 而S 盒不會改變作用前后狀態(tài)中各單元的差分, 所以(A,D) 和(B,C) 都各有s個單元不活躍. 為了生成一對數據, 使其滿足給定的輸入輸出差分(ΔA,ΔD), 進行以下操作:

(1) 猜測(A,D) 的活躍單元中的d-s個單元.

(2) 由(A,D) 猜測的d-s個單元計算(B,C) 中對應的d-s個單元, 并計算差分(ΔB,ΔC).

(3) 結合(ΔB,ΔC) 中s個不活躍的單元差分, 共有d單元被MC 作用的輸入輸出差分已知. 根據命題1, 可以求得這一截斷差分路徑中的所有差分.

(4) 現在(B,C) 中d-s個單元已被確定, 另需確定s個單元才能通過MC 完全確定(B,C) 的全部單元. 通過查詢DDTs次來獲得這s個單元, 引入s比特輔助變量β來區(qū)分2s種可能的選擇.

(5) 結合步驟(2) 獲得(B,C) 的d-s個單元和由DDT 獲得的s個單元, 根據命題1 可以確定余下的d個單元.

(6) 至此, 剩余未用的活躍S 盒數目為

可以當做一個(d-s)c比特的篩選器, 滿足差分的過篩概率為2-(d-s)c. 這樣就得到了滿足給定SSB 差分的完整數據對(A,D) 和(A′,D′).

上述操作的復雜度包含s次DDT 查詢和4(d-s) 次S 盒計算. 平均意義上, 成功找到一對數據需要重復操作2(d-s)c×2s次以遍歷初始猜測和s比特輔助變量β, 對應大約2(d-s)c+s×s次DDT 查詢和2(d-s)c+s×4(d-s) 次S 盒計算. 假設一次DDT 查詢相當于一次S 盒計算, 那么經典設定下的整體時間復雜度為:

而在量子設定下, 利用Grover 算法得到加速后的時間復雜度(包括逆運算) 為:

同時需要216大小的qRAM 來存儲DDT. 詳細定義及實現參見文獻[20].

根據式公式(1) 與(2), 復雜度主項為2(d-s)c(在本文中c=8), 因此最大化s可以降低復雜度.

3 董曉陽等的5 輪Gr?stl-512 的碰撞攻擊[20]

3.1 5 輪經典碰撞攻擊

(1) 隨機選取240對消息分組(m0,m′0), 計算差分Δv1=v1⊕v′1, 使得藍色字節(jié)對應的差分滿足初始條件, 平均而言可以得到一組滿足條件的(m0,m′0) 和Δv1.

(2) 針對消息分組m1進行反彈攻擊. 注意到輸入差分Δin由Δv1唯一確定, 而輸出差分Δout有8個活躍字節(jié), 因此利用全活躍超級S 盒技術, 可以找到264個m1滿足對應的入站階段的差分路徑. 而對于出站階段的差分路徑, 后向的截斷差分路徑(128→64→8→1→8→8) 成立的概率為2-56, 而前向的差分傳播經過一次前饋8 字節(jié)異或, 差分抵消的概率為2-64. 因此可以以概率264×2-56×2-64=2-56確定滿足要求的差分路徑和中間狀態(tài)v2, 對應的時間復雜度為264.如果沒有求得所需差分, 那么用下一個消息分組和之前產生的中間狀態(tài)來重復同樣的攻擊. 平均而言, 在對256個消息分組進行計算之后會成功消去差分, 得到正確的路徑.

(3) 重復步驟(2), 不斷逐列消去中間狀態(tài)包含的活躍差分, 直到剩余兩列活躍差分.

(4) 可以利用步驟(2) 的技巧同時消去最后兩列活躍差分, 但反彈攻擊的成功概率有所不同. 因為入站階段的差分的輸出狀態(tài)中有16 個活躍字節(jié), 可以利用全活躍超級S 盒技術得到216×8= 2128個起點, 對應的時間復雜度為2128. 接著考慮出站階段的差分, 相應的截斷差分路徑(88→96→16→2→16→16) 成立的概率為2-112, 而兩列之間的相互消去發(fā)生的概率為2-128. 因此在步驟(4) 之內, 有2128×2-112×2-128=2-112的概率得到滿足要求的碰撞, 對應的時間復雜度為2128. 同樣地, 在平均意義上用2112個消息分組重復步驟(4) 就能得到碰撞.

上述攻擊的時間復雜度主項是步驟(4), 可以估計為2112×2128=2240. 存儲超級S 盒需要空間復雜度264. 最終, 獲得一組碰撞使用了2112個消息分組計算.

3.2 5 輪Gr?stl-512 量子碰撞攻擊

董曉陽等[20]中基于上述5 輪經典碰撞攻擊, 利用量子算法可以得到加速后的5 輪量子碰撞攻擊, 即用Grover 算法替代經典攻擊中的窮舉搜索.

圖6 5 輪Grostl-512 的碰撞攻擊Figure 6 Collision attacks on 5-round Grostl-512

(1) 利用Grover 算法,找到符合藍色字節(jié)的初始條件的第一輪輸入一對消息分組和對應輸出差分,所對應的復雜度約是經典情況的一半規(guī)模, 即220.

(2) 逐列消去中間狀態(tài)差分的多輪反彈攻擊, 每一輪都需要檢查264對起點(Δin,Δout) 是否能推導出8 個活躍字節(jié)的消除. 這里整個狀態(tài)空間大小為264, SB 操作涉及16 個獨立聯合作用的超級S 盒, 利用2.5 節(jié)的技術, 需要增加15 比特的輔助變量α, 因而搜索空間擴大到264×215=279.

(3) 最后一輪反彈攻擊同時消去兩列差分, 與步驟(2) 相似, 也需要15 比特的輔助變量α, 搜索空間相應地擴大到2128×215輪Gr?stl-512 中有5×2×128 = 1280 次S 盒計算, 這里與文獻[20] 中用4 輪Gr?stl-512 來估計不同., 這一部分是復雜性的主項.

相當于226.67/1280≈216.35次5 輪Gr?stl-512 運算. 類似的,s=4 的SSB 有6 個, 每個對應的時間復雜度約為212.65次5 輪Gr?stl-512 運算, 而s ≥5 的SSB 對應的時間復雜度可以忽略不計. 綜上, 步驟(3) 的時間復雜度為

圖7 五輪Gr?stl-512 的碰撞攻擊中的最后一輪反彈攻擊差分路徑示意圖[20]Figure 7 Inbound phase of last step of collision attack on Gr?stl-512 [20]

平均意義上, 成功找到一組碰撞需要運行14 輪步驟(2), 每輪重復256次, 還需要將步驟(3) 重復運行2112次, 前者相對后者可以忽略不計. 因此量子碰撞攻擊的時間復雜度為288.05×2112≈2200.05, 同時需要216大小的qRAM 來儲存DDT.

類似地, 為了成功找到一組碰撞平均需要將步驟(3) 重復運行2112次, 因此不需要qRAM 的量子碰撞攻擊總的時間復雜度為289.00×2112≈2201.0.

因為使用5 輪Gr?stl-512 (1280 個S 盒) 而非4 輪Gr?stl-512 (1024 個S 盒) 來估計時間復雜度,這里給出的復雜度結論與文獻[20] 中略有不同, 總體上少了大約1280/1024≈20.32.

4 改進的5 輪Gr?stl-512 量子碰撞攻擊

4.1 基本算法實現細節(jié)

為了明確使用振幅放大算法進行碰撞攻擊的細節(jié), 首先推導文獻[20] 中Gr?stl-512 碰撞攻擊的實現細節(jié), 這部分在文獻[20] 作為利用非全活躍超級S 盒的AES-MMO 碰撞攻擊的推廣沒有明確給出.

首先, 需要預先計算DDT 的輸入輸出差分, 存儲在表中以便查詢, 即文獻[20] 中的算法1.

算法1 S 盒S(x) 的輸入輸出差分分布表[20]Output: T 1 Let T be an empty dictionary;2 for δin ∈F82 do 3for x ∈F82 do 4 x′ ←x ⊕δin, y ←S(x), y′ ←S(x′), δout ←y ⊕y′;5 if x ≤x′ then 6 Insert (x,x′,y,y′) into T[(δin,δout)];end 8end 9 end 10 return T;7

接下來著重分析反彈攻擊最后一輪中用到的非全活躍超級S 盒的差分路徑, 因為這一輪是整個碰撞攻擊過程中復雜性的主項. 以圖7 中紅框標出的一個超級S 盒為例, 其不活躍字節(jié)數s=7, 截斷差分路徑如圖8. 從這個例子出發(fā), 整個攻擊中涉及的其他超級S 盒的差分路徑可以結合2.5 節(jié)的結論進行類推.

圖8 Gr?stl-512 最后一輪反彈攻擊中一個非全活躍超級S 盒的截斷差分路徑Figure 8 Differential of one non-full-active super S-box in last round rebound attack of Gr?stl-512

根據2.5 節(jié)的一般化討論, 取Gr?stl-512 對應的參數為d=8,c=8, 則可利用命題1 生成滿足該SSB的差分路徑的數據對, 具體步驟如算法2 所示. 這需要先猜測d-s= 1 個(A,D) 中的活躍字節(jié)(不妨設為A[0]), 作為輸入傳遞給算法2 最終輸出所需數據對. 算法2 的成功概率為2-7×2-8=2-15, 因此在平均意義下遍歷15 比特輸入(A[0],β) 后可以輸出1 對滿足SSB 輸入輸出差分的數據對. 算法2 運行一次需要執(zhí)行s= 7 次DDT 訪問(步驟3 到9) 和4 次S 盒計算(步驟1 和25), 因此輸出所需數據對的平均復雜度為215×11, 這符合將d=8,c=8,s=7 代入公式(1)的結果.

算法2 生成非全活躍超級S 盒的輸入輸出數據對Input: (ΔA,ΔD), A[0], β = (β0,··· ,β7)Output: 數據A 滿足SSB(A)⊕SSB(A ⊕ΔA) = ΔD 1 B[0] = S(A[0]), B′[0] = S(A[0]⊕ΔA[0]), ΔB[0] = B[0]⊕B′[0]/* 算上(ΔB,ΔC) 中7 個非活躍字節(jié), 總計2 利用命題1, 計算ΔB[1],ΔB[2],ΔB[5],ΔB[7] 和ΔC[1],ΔC[3],ΔC[5],ΔC[7]/* 查詢DDT 獲取對應輸入輸出差分的數據,3 (A[2],A′[2],B[2],B′[2]) ←T[(ΔA[2],ΔB[2])]4 for i ∈{3,5,7} do 5(A[i],A′[i],B[i],B′[i]) ←T[(ΔA[i],ΔB[i])]6(C[i],C′[i],D[i],D′[i]) ←T[(ΔC[i],ΔD[i])]7 end/* 按β 的值選取(A[2],A[3],A[5],A[7],C[3],C[5],C[7]) 的組合: 若β0 = 0 則取β0 = 1 則取β0 ·ΔA[2] = ΔA[2] */8 A[2] = A[2]⊕β0 ·ΔA[2], A′[2] = A[2]⊕ΔA[2];9 B[2] = B[2]⊕β0 ·ΔB[2], B′[2] = B[2]⊕ΔB[2];10 for (i,j) ∈{(3,1),(5,2),(7,3)} do 11A[i] = A[i]⊕βj ·ΔA[i], A′[i] = A[i]⊕ΔA[i];12B[i] = B[i]⊕βj ·ΔB[i], B′[i] = B[i]⊕ΔB[i];13C[i] = C[i]⊕βj ·ΔC[i], C′[i] = C[i]⊕ΔC[i];14D[i] = D[i]⊕βj ·ΔD[i], D′[i] = D[i]⊕ΔD[i];15 end/* 加上步驟1 得到的B[0], (B,C) 有16 利用命題1, 求出B 和C 的所有值/* 在所有活躍的S 盒中, 只剩下(ΔC[1],ΔD[1]) 尚未考慮, 可17 if S(C[1])⊕S(C[1]⊕ΔC[1]) = ΔD[1]18 then 19return A ←SB-1(B) and A ⊕ΔA 20 end有8 字節(jié)差分已知*/成功的概率為2-7 */β0 ·ΔA[2] = 0, 若8 個字節(jié)已經確定*/以視作一個過濾器*//* 成功概率2-8 */

2注意到給定(Δvj,mj,Δuj) 推導16 個超級S 盒的輸入輸出差分時, 若對每個超級S 盒都存在一對滿足條件的輸入輸出, 那么由此可以組合出216/2 = 215 種不同的起點, 因此需要引入15 比特的指標αj 來指示如何選擇起點.

算法4 UFj 的實現Input: |mj,Δvj,Δuj;α〉|y〉, α = (α0,··· ,α14) ∈F152 Output: |mj,Δvj,Δuj;α〉|y ⊕Fj(mj,Δvj,Δuj;α)〉1 for k ∈{0,·,14} do 2ΔA(k)j ←Δvj; ΔD(k)j ←Δuj;3對函數G(k)j (mj,ΔA(k)j ,ΔD(k)j ;·) 運行Grover 搜索, 輸出A(k)j [0] ∈F82 和β(k) ∈F7 2 j ←P(i)(mj,ΔA(k)j ,ΔD(k)j ,A(k)j {d-s},β(k),αj)5 end 6 ΔA(15)4A(k)j←Δvj; ΔD(15)j←Δuj;7 對函數G(15)j (mj,ΔA(15)j ,ΔD(15)j ;·) 運行Grover 搜索, 輸出A(15)j {d-s} ∈F82 和β(15) ∈F7 2 8 A(15)j←P(i)(mj,ΔA(15)j ,ΔD(15)j ,A(15)j {d-s},β(15))/* 從|mj,Δvj,Δuj;α〉 生成反彈攻擊起點*/9 A ←(A(0)j ,··· ,A(15)j )10 A′ ←(A(0)j ⊕ΔA(0)j ,··· ,A(15)j⊕ΔA(15)j )11 if (A,A′)滿足出站差分路徑then 12return |mj,Δvj,Δuj;α〉|y ⊕1〉13 else 14return |mj,Δvj,Δuj;α〉|y〉15 end

4.2 振幅放大算法實現

在3.2 節(jié)中,通過重復運行步驟(2)和步驟(3)來提高算法的成功概率,也即反復運行對UFj的Grover搜索. 注意到在量子環(huán)境下, 還可以利用振幅放大算法來改進提高成功概率的過程. 這就是說, 把步驟(1)和(2) 聯合起來不進行重復運行, 整體可以看做一個過程, 它不需要給定輸入而是進行一系列隨機數據選取和操作, 最后(隨機) 輸出一對消息分組m0,m′0和一系列中間值, 使得得到反彈攻擊最后一輪前只剩兩列差分沒有消去的狀態(tài)vi-1, 而vi-1滿足最后一輪88→96→16→2→16→16 的差分路線并最終得到一組碰撞的概率是2-112. 根據5 輪經典攻擊的描述, 在經典環(huán)境下, 上述過程需要2128時間復雜度;而根據3.2 節(jié), 在量子環(huán)境下, 上述過程需要288.05時間復雜度.

4.3 不使用qRAM 的改進量子碰撞算法

5 總結

我們利用振幅放大算法改進了文獻[20] 中針對Gr?stl-512 的5 輪量子碰撞攻擊, 主要是優(yōu)化了這一隨機算法提高成功概率的流程,復雜度降低為原來的.可以看到,在構造與本文攻擊類似地,基于反彈攻擊的量子碰撞攻擊時, 振幅放大算法的使用應當納入考慮之中,它可以有效優(yōu)化算法流程、提高運行效率. 振幅放大算法在這一方面仍有更大的應用空間, 值得進一步研究.