梁 敏, 羅宜元, 劉鳳梅

1. 數(shù)據(jù)通信科學(xué)技術(shù)研究所, 北京 100191

2. 惠州學(xué)院計算機科學(xué)與工程學(xué)院, 惠州 516007

3. 河南省網(wǎng)絡(luò)密碼技術(shù)重點實驗室, 鄭州 450001

4. 電子科技大學(xué)網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點實驗室, 成都 610054

1 引言

1996 年Grover 提出著名的量子搜索算法(以下簡稱Grover 算法), 可實現(xiàn)對經(jīng)典搜索效率的二次加速[1], 從而提高密碼破譯效率, 對密碼安全性構(gòu)成潛在威脅. 對于理想的對稱密鑰密碼方案, 其安全強度將從O(2n) 次經(jīng)典計算降低至O(2n/2) 次量子計算; 對于理想的雜湊函數(shù), 其安全強度將從O(2n/2) 次經(jīng)典計算降低至O(2n/3) 次量子計算. 因此, 無論對稱密碼算法設(shè)計多么完美, 其安全強度都將受到量子攻擊的顯著影響. 此外, 對于現(xiàn)實中的密碼算法, 在量子計算攻擊下其設(shè)計弱點或潛在弱點都可能被放大,從而面臨比Grover 窮舉搜索攻擊更高效的量子攻擊. 因此, 不能單純依靠增大安全參數(shù)n來提高密碼算法的抗量子計算攻擊能力, 而是應(yīng)該將量子計算融入密碼學(xué)研究, 全方位考慮量子計算攻擊在密碼算法設(shè)計與分析中的影響.

目前, 基于量子計算的密碼分析研究大致包括三個層次的內(nèi)容: 一是量子安全模型研究, 目標(biāo)是確立量子安全標(biāo)準(zhǔn)體系, 并為量子攻擊和量子安全性證明提供根本依據(jù); 二是在量子安全模型下針對結(jié)構(gòu)和工作模式的分析和安全性證明, 目標(biāo)是判斷密碼結(jié)構(gòu)和模式在量子模型下是否符合量子安全標(biāo)準(zhǔn); 三是在量子安全模型下針對密碼算法的安全強度評估, 目標(biāo)是全面而具體地評估密碼算法的抗量子計算攻擊強度.

在量子安全模型研究方面, 針對偽隨機函數(shù)、加密、認(rèn)證、認(rèn)證加密、雜湊等密碼學(xué)原語, 分別定義了量子安全模型. 對于帶密鑰密碼原語建立的量子安全模型可分為兩大類: Q1 模型和Q2 模型, 其中Q2 模型允許攻擊者對原語執(zhí)行量子查詢而Q1 模型只允許經(jīng)典查詢. 這些量子安全模型具備不同的強弱程度,可作為衡量密碼原語的不同安全程度的基準(zhǔn).

在量子安全模型下, 許多經(jīng)典可證明安全的結(jié)構(gòu)和工作模式受到量子計算攻擊, 特別是許多結(jié)構(gòu)和工作模式在Q2 模型下完全不安全, 它們在量子疊加態(tài)查詢攻擊下受到基于Simon 量子算法的量子多項式時間攻擊[2]. 不過也有一些結(jié)構(gòu)和工作模式在量子安全模型下是可證明安全的[3–6]. 還有一些結(jié)構(gòu)或工作模式雖然不安全但是經(jīng)過改造后可達到量子可證明安全性[7].

在量子安全模型下針對密碼算法的安全強度評估, 主要包括兩類研究: 一是通用量子攻擊下的安全強度評估[8–13], 包括基于Grover 算法的量子窮舉攻擊和量子碰撞攻擊下的復(fù)雜度評估; 二是專用量子攻擊下的安全強度評估[14], 根據(jù)具體密碼算法的特征來設(shè)計專用的量子攻擊, 并評估其攻擊復(fù)雜度. 其中, 前者研究較多, 形成了成熟的評估體系; 后者更強調(diào)專用性, 與具體密碼算法是強相關(guān)的, 目前研究結(jié)果相對較少.

對稱密碼的抗量子分析研究僅有十多年的歷史, 并且直到近五年才成為熱點. 當(dāng)前這些研究還很不充分, 尚不足以全面評估對稱密碼的量子安全性, 未來還需要繼續(xù)加強量子攻擊技術(shù)和量子可證明安全研究,為抗量子對稱密碼設(shè)計和量子安全強度量化評估奠定基礎(chǔ).

本文將分別從量子算法、量子安全模型、量子安全強度量化評估、對結(jié)構(gòu)和工作模式的量子攻擊、結(jié)構(gòu)和工作模式的量子可證明安全性、抗量子對稱密碼設(shè)計等六個角度來概述抗量子對稱密碼研究進展. 在撰寫過程中部分參考了眭晗和吳文玲[15]的綜述論文.

本文第2–7 節(jié)分別從以上六個角度來介紹研究進展, 清晰呈現(xiàn)各項內(nèi)容之間的邏輯聯(lián)系, 實際上這六個方面的內(nèi)容并非完全獨立的. 第2 節(jié)介紹量子算法, 它是抗量子對稱密碼分析的基礎(chǔ)工具; 第3 節(jié)介紹量子安全模型, 它為“抗量子攻擊” 設(shè)定了基準(zhǔn), 是進行抗量子分析(攻擊/證明) 的根本依據(jù)或框架; 第4 節(jié)介紹對稱密碼算法的量子安全強度評估, 它依托各種量子攻擊技術(shù), 全面而直接地評估對稱密碼算法的量子安全強度; 第5 節(jié)介紹對結(jié)構(gòu)和工作模式的量子攻擊, 從攻擊角度闡述上層結(jié)構(gòu)或模式的抗量子攻擊能力; 第6 節(jié)介紹結(jié)構(gòu)和工作模式的量子可證明安全性, 從證明角度闡述上層結(jié)構(gòu)或模式是否達到量子安全模型所定義的安全標(biāo)準(zhǔn); 第7 節(jié)介紹抗量子對稱密碼設(shè)計的進展情況.

2 量子算法

量子算法是開展抗量子密碼分析研究的基本工具. 目前在密碼分析中最廣泛使用的量子算法是Grover 量子搜索算法及其推廣. 近年來Simon 量子算法被用于密碼結(jié)構(gòu)和工作模式的分析, 攻擊效率可實現(xiàn)指數(shù)級提升. 此外, 在某些特定情況下, 將這些量子算法組合使用, 擴大了攻擊技術(shù)適用范圍或提升了攻擊效率, 例如Grover 算法與Simon 算法組合, Grover 與幾率幅放大算法組合, Simon 算法的自我組合等. 下面具體介紹這些算法.

2.1 Grover 算法及其推廣

Grover 算法可加速無序數(shù)據(jù)集的搜索效率, 而幾率幅放大算法[16]是Grover 算法的一般性推廣. 這里先介紹幾率幅放大算法, 然后以特例形式給出Grover 算法.

總之, 幾率幅放大算法的核心是兩個量子酉變換A,Q, 其中A是一個制備初態(tài)|φinitial〉的量子變換,是必要的已知變換; 而Q的作用就是將初態(tài)中的解分量|good〉的幾率幅進行放大, 它實際上可由量子變換A和對f的量子查詢來實現(xiàn).

Grover 算法. 在上述幾率幅放大算法中, 令A(yù)為作用于k個量子比特上的Hadamard 變換, 即可獲得Grover 算法.

碰撞查找問題: 給定一個函數(shù)H:{0,1}m →{0,1}n, 尋找2 個不同的輸入值x1/=x2, 使得H(x1) =H(x2). 經(jīng)典生日碰撞算法中對隨機函數(shù)H的查詢復(fù)雜度為O(2n/2). 量子碰撞查找算法可以更快地解決碰撞查找問題. 下面具體介紹相關(guān)研究結(jié)果.

2.2 Simon 量子算法

下面簡單介紹Simon 算法的另一種用法: 并行地執(zhí)行Simon 算法, 用來判斷函數(shù)f是否為周期函數(shù),而不必具體計算出f的周期值. 若并行地運行cn個Simon 子程序, 則輸出一個量子態(tài)

然后采用量子計算對該量子態(tài)的每個疊加分量實現(xiàn)如下計算

其中Span(·) 和dim(·) 分別返回cn個輸入值所張成的空間及空間維數(shù). 若f不是周期函數(shù), 則函數(shù)t將以大概率等于0; 若f為周期函數(shù), 則函數(shù)t的計算值幾乎等于1.

2.3 組合量子算法

近幾年來, 許多研究工作都將上述量子算法進行組合使用, 在密碼分析中實現(xiàn)更高效的量子攻擊. 這里主要介紹Grover 算法和Simon 算法之間的各種嵌套用法, 它們已經(jīng)被廣泛用于密碼分析. 此外還有其它的組合量子算法, 例如Simon meets Kuperberg 和Grover meets Kuperberg 等[26].

幾率幅放大算法是Grover 算法的推廣, Albrecht 等[27]將Grover 算法與幾率幅放大算法組合使用,提出了過濾量子搜索算法(filtered quantum search), 其中外層使用幾率幅放大算法來搜索問題f的解,內(nèi)層嵌套使用Grover 算法來實現(xiàn)過濾器g. 該算法采用過濾器降低搜索問題解的開銷. 他們將這種方法用于改進格篩法中3 種NNS (near neighbour search) 算法.

Simon 算法可自我嵌套使用, 即Simon 算法內(nèi)部再嵌套一個Simon 子程序. 這種算法適用于函數(shù)f的周期本身也是關(guān)于另一個變量的周期函數(shù)的情況,即滿足f(x,y)=f(x⊕g(y),y),其中g(shù)(y)=g(y⊕s).

上述都是同類算法的嵌套組合使用. 下面介紹功能不同的兩種量子算法之間的組合使用, 即Grover算法與Simon 算法的組合, 目前有以下兩種組合形式, 它們均采用了兩層組合結(jié)構(gòu).

第一種由Leander 和May[28]提出, 適用于加密函數(shù)F(k,x) 的密鑰恢復(fù), 其中F(k,x) 滿足以下兩個條件: (1) 當(dāng)k等于真實密鑰k0時, 存在s使得F(k0,x) =F(k0,x ⊕s),?x ∈{0,1}n; (2) 當(dāng)k/=k0時,F(k,x) 以大概率不具有周期性. 將Grover 算法與Simon 算法組合使用時, 外層用Grover 算法搜索密鑰k, 內(nèi)層用并行的Simon 子程序作為Grover 迭代中的分類器: 根據(jù)密鑰k能否使F(k,x) 滿足周期性, 判斷密鑰k是否為真實密鑰k0. 這里并不需要Simon 子程序計算出周期值, 而只用于Grover 迭代中標(biāo)記待搜索的k值: 當(dāng)且僅當(dāng)k值使得F(k,x) 是關(guān)于x的周期函數(shù), 則將待搜索量子疊加分量中的|k〉執(zhí)行相位翻轉(zhuǎn)變換成為-|k〉. 而為了判斷F(k,x) 是否為關(guān)于x的周期函數(shù), 只需要并行執(zhí)行cn個Simon 子程序并檢查輸出能否張成一個n-1 維空間.

第二種由Bonnetain 等[29]提出, 其適用條件與前者類似, 但是在滿足以下額外條件的情況下改進了量子查詢復(fù)雜度: 函數(shù)F(k,x) 可分解成形式F(k,x)=f(k,x)⊕gk0(x), 這里f和g的值分別通過離線計算和在線查詢來實現(xiàn). 對于這種F(k,x), 若仍然采用Leander 和May[28]的組合量子算法, 則對g的量子查詢次數(shù)為指數(shù)量級; 而Bonnetain 等[29]將其降為O(n), 其關(guān)鍵點在于該特定情況下可復(fù)用g的量子查詢結(jié)果, 即, 先通過cn次對g的量子查詢產(chǎn)生g的量子數(shù)據(jù)庫|φg〉=?cn(∑x|x〉|gk0(x)〉), 然后基于|φg〉采用并行Simon 子程序檢測函數(shù)F(k,x)的周期性, 并且|φg〉被使用一輪之后還可復(fù)原用于下一輪Grover 迭代. 正是這點改進, 使得某些結(jié)構(gòu)或工作模式在Q2 模型下的攻擊被轉(zhuǎn)換成Q1 模型下的攻擊[29], 因為這個量子數(shù)據(jù)庫|φg〉是可以通過“經(jīng)典查詢+ 量子計算” 來產(chǎn)生: 以經(jīng)典方式查詢函數(shù)g在每個x處的取值{(x,gk0(x)),?x}并根據(jù)查詢值來執(zhí)行CNOT 量子運算. 顯然這里需要指數(shù)量級的經(jīng)典查詢次數(shù), 但是在一定條件下可以調(diào)節(jié)或控制經(jīng)典查詢次數(shù), 以獲得在經(jīng)典查詢復(fù)雜度方面的攻擊優(yōu)勢.

3 量子安全模型

安全模型是開展安全性證明和攻擊的根本依據(jù)和思考框架, 也是衡量密碼算法安全程度或等級的標(biāo)準(zhǔn). 安全模型的強弱需適度: 太強而不可能達到, 就失去了意義; 太弱而容易達到, 卻不能保證密碼在現(xiàn)實使用中的安全性, 這也是沒有意義的.

對于帶密鑰的密碼學(xué)原語, 例如加密、認(rèn)證、認(rèn)證加密等, 量子安全模型可根據(jù)查詢類型來分為兩大類: Q1 模型和Q2 模型, 前者允許量子攻擊者執(zhí)行經(jīng)典查詢, 而后者允許量子攻擊者執(zhí)行量子查詢. 兩類模型相比, Q1 模型相對現(xiàn)實一些; Q2 模型比Q1 模型強很多, 但在量子計算時代Q2 模型攻擊場景是可能存在的, 因此Q2 模型下的密碼證明和攻擊技術(shù)仍然具有研究價值和技術(shù)儲備意義.

對于無密鑰的密碼學(xué)原語(例如雜湊), 量子攻擊者可通過本地量子計算(不必通過查詢) 來獲得量子疊加態(tài)計算結(jié)果, 因而沒有Q1 和Q2 模型之分. 對于帶密鑰的雜湊密碼, 可參照認(rèn)證原語來開展研究, 因此這里所提雜湊是指無密鑰的.

后面將分別介紹加密、認(rèn)證、認(rèn)證加密、雜湊的量子安全模型及其研究現(xiàn)狀.

3.1 加密的安全模型

類似于經(jīng)典模型(記為Q0 模型) 下所定義的IND、IND-CPA 和IND-CCA, 研究人員定義了量子版本的攻擊類型(量子選擇明文攻擊qCPA 和量子選擇密文攻擊qCCA), 以及量子版本的安全目標(biāo)(量子不可區(qū)分性qIND 和量子語義安全性qSEM), 然后提出了一些量子版本的安全模型, 分別具備不同級別的量子安全程度. 這些量子安全模型主要包括IND-qCPA、IND-qCCA、qIND 和qIND-qCPA 等加密安全模型. 具體定義可參考相關(guān)文獻[30—33] 中的研究. 圖1 給出了它們之間的強弱關(guān)系總結(jié), Q0 代表經(jīng)典模型, Q1 和Q2 代表兩種不同的量子模型. 在Q0 模型中, 敵手可執(zhí)行經(jīng)典計算和經(jīng)典查詢; 在Q1 模型中, 敵手可執(zhí)行量子計算和經(jīng)典查詢; 在Q2 模型中, 敵手可執(zhí)行量子計算和量子查詢. 箭頭表示兩者之間的單向推導(dǎo)關(guān)系(若密碼滿足一個安全模型, 則必定滿足另一安全模型), 帶短斜線的箭頭表示不存在該推導(dǎo)關(guān)系, 帶“?” 的箭頭表示暫時沒有定論.

圖1 加密量子安全模型之間的關(guān)系圖Figure 1 Relationships between quantum security models for encryption

Chevalier 等[34]定義了qIND-qCCA2, 該成果曾在QCrypt2020 會議上作口頭報告, 但是目前還沒有正式發(fā)表, 所以未體現(xiàn)在圖1 中. 對于量子版的IND, Boneh 和Zhandry[30]曾定義了全量子不可區(qū)分性fqIND, 并證明fqIND 因太強而不可能達到, 因此也未在圖中體現(xiàn). 對于Q1 模型下的IND 定義(即pqIND), 除了允許攻擊者使用量子計算機以外, 它與經(jīng)典安全模型下的IND 定義相同. Q2 模型下可定義三種不可區(qū)分性: IND、wqIND 和qIND, 其中qIND 最強, wqIND 稍弱, 但是目前還不明確wqIND 是否嚴(yán)格弱于qIND, 因此圖中箭頭上添加了“？”.

圖中涉及4 種程度的不可區(qū)分性. 若對稱密鑰加密方案Π = (Gen,Enc,Dec) 滿足其中某種不可區(qū)分性IND/fqIND/wqIND/qIND, 則對于所有的多項式時間攻擊算法或敵手A, 存在一個可忽略函數(shù)negl使得

其中概率來源于A的內(nèi)部隨機性以及實驗PrivK 中的隨機性(選擇密鑰、隨機比特b, 以及在加密過程中使用到的任何隨機性). 這里的實驗PrivKI(n) 分別用算法1–4 實驗來描述, 其中IND 實驗中的A具備概率多項式時間計算能力, 而其它3 種實驗中的A都具備量子多項式時間計算能力. 符號φb表示量子態(tài), Dsc(.) 表示以量子態(tài)作為輸入來產(chǎn)生該量子態(tài)的經(jīng)典描述, Qbuild(.) 表示以經(jīng)典描述作為輸入來制備量子態(tài).

算法1 經(jīng)典不可區(qū)分實驗PrivKINDA,Π(n)Input: 參數(shù)n Output: 區(qū)分成功, 輸出1; 否則輸出0 1 k ←Gen(1n);2 m0,m1 ←A(1n);3 b←${0,1};45 c b′ ←←EAn(cck)(;b,m0,m1);6 if b′ = b then 7output 1;8 else 9output 0;10 end

算法2 全量子不可區(qū)分實驗PrivKfqIND A,Π (n)1 k ←Gen(1n);2 φ0,φ1 ←A(1n);3 b←${0,1};4 5 φ b′←←|AE(nφck);〉(b,φ0,φ1);6 if b′ = b then 7output 1;8 else 9output 0;10 end Input: 參數(shù)n Output: 區(qū)分成功, 輸出1; 否則輸出0

算法3 弱量子不可區(qū)分實驗PrivKwqIND A,Π (n)算法4 量子不可區(qū)分實驗PrivKqIND A,Π (n)Input: 參數(shù)n Output: 區(qū)分成功, 輸出1; 否則輸出0 1 k ←Gen(1n);1 k ←Gen(1n);2 Dsc(φ0),Dsc(φ1) ←A(1n);2 φ0,φ1 ←A(1n);3 b←${0,1};3 b←${0,1};4 φb ←Qbuild(Dsc(φb));4 φ ←|Enck〉(b,φ0,φ1);56 φ b′ ←←|AE(nφck);〉(φb);5 6 tbr′ a←c e A ou(tφ φ);1-b;7 if b′ = b then7 if b′ = b then 8output 1;8output 1;9 else9 else 10output 0;10output 0;11 end11 end Input: 參數(shù)n Output: 區(qū)分成功, 輸出1; 否則輸出0

圖1 中CCA1 與CCA2 (或qCCA1 與qCCA2) 的差別在于: 前者的選擇密文查詢發(fā)生在挑戰(zhàn)查詢之前,而后者的選擇密文查詢不受此限制.

3.2 認(rèn)證的安全模型

在經(jīng)典模型下的認(rèn)證安全模型有: 選擇消息攻擊下的弱不可偽造性(WUF-CMA) 和選擇消息攻擊下的存在不可偽造性(EUF-CMA), 其中前者比后者弱一些. 在WUF-CMA 的定義中, 安全目標(biāo)通常設(shè)定為:q次查詢后不能在多項式時間內(nèi)產(chǎn)生一個新消息msg 的標(biāo)記tag, 但不排除產(chǎn)生“舊消息” (被查詢過的消息) 的新標(biāo)記的可能. 更強的安全模型EUF-CMA 的安全目標(biāo)為:q次查詢后不能有效產(chǎn)生一對新的“消息-標(biāo)記(msg, tag)”. 在Q1 模型下, 關(guān)于認(rèn)證安全模型沒有明確的公開研究結(jié)論, 從當(dāng)前的研究情況來看, Q1 模型下有類似于Q0 模型的等價關(guān)系, 而且兩類模型之間的差距至多是多項式量級.

在Q2 模型下, 由于允許執(zhí)行量子疊加態(tài)查詢, 攻擊者可并行地查詢所有消息的認(rèn)證標(biāo)記, 因此在定義未被查詢過的“新消息msg” 或者“新消息標(biāo)記對(msg, tag)” 時遇到困難. 研究人員先后提出了兩種方式來定義認(rèn)證安全模型. 第一種是Boneh 和Zhandry[7]定義的PO (plus one) 方式. 對應(yīng)的安全模型稱為PO 安全性, 其中要求攻擊者經(jīng)過q次查詢后不能有效產(chǎn)生q+1 個消息標(biāo)記對(msg, tag), 且這q+1 對中的msg 不重復(fù)出現(xiàn). 其加強版sPO 的定義中只要求這q+1 個消息標(biāo)記對中不出現(xiàn)重復(fù)的(msg, tag), 但允許重復(fù)出現(xiàn)同一個消息msg. 第二種是Alagic 等[35]定義的的BU (blind unforgeable)方式. 對應(yīng)的安全模型稱為BU 安全性, 該模型要求在消息空間中隨機分割出一塊大小可忽略的盲區(qū), 只允許攻擊者查詢該盲區(qū)以外的消息但要求攻擊者去偽造該盲區(qū)元素的合法標(biāo)記tag. 其加強版sBU 的定義中要求在消息標(biāo)記對(msg, tag) 的空間中隨機設(shè)置盲區(qū), 不允許攻擊者查詢但要求偽造產(chǎn)生該盲區(qū)的元素(msg, tag).

通常廣泛使用的EUF-qCMA 是指Boneh 和Zhandry[7]所定義的PO 方式, 即圖2 中的EUFqCMA(PO), 后文直接寫作EUF-qCMA. 而采用BU 方式定義的EUF-qCMA(BU) 值得繼續(xù)開展研究.事實上, Q0 模型下的認(rèn)證安全模型也可按PO 或BU 方式來定義, 但是WUF-CMA 等價于采取PO 和BU 方式的定義, 而EUF-CMA 也等價于采取sPO 和sBU 方式的定義. 圖2 中總結(jié)了這些安全模型之間的強弱或等價關(guān)系, 前兩行都是Q0 模型下的經(jīng)典安全模型, 最后一行是Q2 模型下的量子安全模型. Q1模型位于Q0 模型和Q2 模型之間, 且與Q0 模型有類似的關(guān)系描述, 故圖中未體現(xiàn).

圖2 認(rèn)證安全模型之間的關(guān)系圖Figure 2 Relationships between security models for authentication

3.3 認(rèn)證加密的安全模型

認(rèn)證加密方案可以同時提供私密性和完整性保護功能. 在研究其量子安全模型時, 應(yīng)該兼顧私密性和完整性的量子安全定義. 私密性的定義可沿用加密安全模型(如IND-qCPA), 然而完整性的定義不能直接采用認(rèn)證安全模型(如EUF-qCMA).

經(jīng)典安全模型下的完整性定義有明文完整性INT-PTXT 和密文完整性INT-CTXT 兩種. Q1 模型下也可類似地定義. 然而Q2 模型允許量子疊加態(tài)查詢, 攻擊者可并行地查詢每個消息的密文, 因此在定義安全目標(biāo)時應(yīng)該特別注意. Soukharev 等[36]在Q2 模型下定義了認(rèn)證加密的量子安全模型: INTqCTXT (量子攻擊下的密文完整性) 和INT-qPTXT (量子攻擊下的明文完整性). 但是, 他們在定義INT-qCTXT 時直接將IND-qCCA 的敵手能力和EUF-qCMA 的安全目標(biāo)進行簡單組合(若按通行記法應(yīng)該記為EUF-qCCA), 顯然不適合作為密文完整性的定義.

3.4 雜湊的安全模型

對于雜湊密碼, 傳統(tǒng)研究中采用的安全模型主要有抗碰撞性(collision resistance)、抗原像性(preimage resistance)、抗第二原像性(second-preimage resistance) 和不可區(qū)別性(indifferentiability), 分別記為Coll、Pre、Sec、Indiff.

由于hash 函數(shù)是無密鑰的密碼原語, 量子攻擊者不必通過在線量子查詢, 只需執(zhí)行離線本地量子計算, 就可獲得量子疊加態(tài)的雜湊值計算結(jié)果. 因此, 對hash 函數(shù)的在線量子查詢并不會為量子攻擊者帶來攻擊能力上的根本提升, 其量子安全模型也不再細分為Q1 和Q2 兩類模型.

Hash 函數(shù)的量子安全性定義有兩類, 一類是直接由經(jīng)典安全模型的推廣[37], 即在量子計算模型下定義的抗碰撞性CollQ、抗原像性PreQ、抗第二原像性SecQ、不可區(qū)別性IndiffQ. 另一類是量子計算情況下獨有的, 目前包括Collapsing hash 和Bernoulli-preserving hash.

Collapsing hash 是由Unruh[38]在2016 年提出來的, 他發(fā)現(xiàn)在量子背景下, 特別是在研究抗量子密碼協(xié)議時[39], 滿足CollQ 的hash 函數(shù)不足以提供強的安全屬性, 所以提出用Collapsing 替代CollQ. 一個hash 函數(shù)H是Collapsing, 若滿足如下條件: 如果某個量子多項式時間算法產(chǎn)生了一個y值和一個量子寄存器X, 其中X處于由{|x〉|H(x)=y}中的基態(tài)組成的量子疊加態(tài); 給定這個量子寄存器X(它可能已被測量或未被測量), 任何量子多項式時間算法均無法有效地區(qū)分X是否被測量過, 即其區(qū)分概率是可忽略的.

Bernoulli-preserving hash 是Alagic 等[35]在2020 年提出來的. 他們發(fā)現(xiàn)抗碰撞的hash 不足以證明MAC 構(gòu)造方式“Hash-and-MAC” 滿足Blind-Unforgeability, 從而提出更強的hash 量子安全定義——Bernoulli-preserving hash. 有效可計算的函數(shù)族H:X →Y是Bernoulli-preserving hash,若滿足如下條件: 將Y中元素按Bernoulli 過程采樣獲得集合Y′, 則Y′關(guān)于函數(shù)h ←H的原像集{x ∈X|h(x)∈Y′}(以可忽略的差異) 等同于一個從X中Bernoulli 采樣所得集合. Bernoulli-preserving hash 退化回到經(jīng)典模型下就與經(jīng)典的抗碰撞性等價了.

關(guān)于不同hash 安全屬性之間關(guān)系的研究結(jié)果, 總結(jié)如下: (1) 一個函數(shù)H是隨機預(yù)言機或者Q2 模型下的偽隨機函數(shù)(即qPRF),則它也是Bernoulli-preserving hash;(2)一個函數(shù)是Bernoulli-preserving hash, 則它也是Collapsing hash; (3) 一個函數(shù)是Collapsing hash, 則它也是CollQ 的.

4 量子安全強度評估

本節(jié)將從兩個角度來闡述量子安全強度評估的現(xiàn)狀: 首先介紹一些經(jīng)典分析技術(shù)的量子增強版, 然后總結(jié)敘述在這些量子分析技術(shù)下開展對稱密碼算法的量子攻擊資源評估與優(yōu)化研究的進展情況.

4.1 經(jīng)典分析技術(shù)的量子增強

通過將密碼算法的經(jīng)典攻擊方式進行量子化改造, 一些量子增強的密碼分析技術(shù)相繼被提出, 包括量子窮舉攻擊、量子碰撞攻擊、量子中間相遇攻擊、量子相關(guān)密鑰攻擊、量子滑動攻擊、量子差分分析、量子線性分析、量子不可能差分攻擊、量子平方攻擊等. 與經(jīng)典攻擊方式相比, 它們的量子版本具有更好的攻擊性能. 具體研究情況介紹如下.

量子窮舉攻擊和量子碰撞攻擊分別是基于Grover 搜索算法對經(jīng)典窮舉攻擊和碰撞攻擊的量子增強.它們都是通用的量子攻擊技術(shù), 即使密碼算法設(shè)計得非常理想, 仍然可以使用, 目前已被廣泛用于評估密碼算法的量子安全強度, 特別是對AES 和SHA 算法的量子安全強度量化評估[8,13]. 此外, 在NIST 抗量子公鑰密碼標(biāo)準(zhǔn)征集中, 所設(shè)定的五個安全級別正是分別對標(biāo)AES128/192/256 和SHA256/384 的通用量子攻擊復(fù)雜度[40].

量子中間相遇攻擊是對經(jīng)典中間相遇攻擊的量子增強, 最早是Zhong 和Bao[41]在分析3DES 時提出的. Hosoyamada 和Sasaki[42]將該量子攻擊技術(shù)進一步應(yīng)用于攻擊可調(diào)分組結(jié)構(gòu)TDR、認(rèn)證模式Chaskey、認(rèn)證加密McOE-X、認(rèn)證模式H2-MAC 和keyed-sponge、FX 結(jié)構(gòu)等. 他們后來又提出量子版的Demiric-Selcuk 中間相遇(DS-MITM) 攻擊[43], 用于分析6 輪Feistel 結(jié)構(gòu). 本質(zhì)上, 這些量子中間相遇攻擊都是用Grover 算法替換了經(jīng)典中間相遇攻擊中的搜索部分, 從而增強攻擊性能; 差異在于, 這些工作需要根據(jù)具體密碼的結(jié)構(gòu)特點來提出有針對性的攻擊方案設(shè)計.

Kaplan 等[44]提出了量子線性分析, Bonnetain 等[48]提出了量子平方攻擊(或積分攻擊), 這兩種量子攻擊技術(shù)分別是在經(jīng)典線性分析和經(jīng)典平方攻擊的基礎(chǔ)上, 將搜索部分用量子算法來完成, 從而實現(xiàn)攻擊加速.

Chen 和Gao[49]基于HHL 量子算法(即線性方程組量子求解算法[50]) 提出了量子代數(shù)攻擊方法,將AES、Trivium 和SHA3 等密碼算法的量子安全強度與布爾方程組的條件數(shù)建立了直接關(guān)聯(lián), 從而將密碼算法的安全分析轉(zhuǎn)換成對條件數(shù)的分析.

上述量子攻擊技術(shù)一般都可在Q1 模型下使用, 此時其攻擊效率只能達到多項式量級的加速. 接下來介紹可實現(xiàn)指數(shù)級加速的量子攻擊技術(shù), 它們已經(jīng)被用于Q2 模型下的攻擊.

Kaplan 等[2]提出了在Q2 模型下使用的量子滑動攻擊技術(shù), 主要利用了Simon 量子算法來增強滑動攻擊效率, 從而實現(xiàn)指數(shù)級加速(量子查詢復(fù)雜度從O(2n/2) 降至O(n)). 這種攻擊適用于迭代Even-Mansour 結(jié)構(gòu)中所有輪密鑰都相同的情形. Dong 等[51,52]針對2/4K-Feistel 提出了量子版的高級滑動攻擊, 該技術(shù)適用于Feistel 結(jié)構(gòu)的2 (或4) 個輪密鑰以周期2 (或4) 交替地重復(fù)使用的情形(例如, 交替使用2 個輪密鑰時, 迭代的每一輪所用密鑰依次為k1,k2,k1,k2,k1,k2,···), 其攻擊復(fù)雜度為量子多項式時間, 從而實現(xiàn)了指數(shù)級攻擊加速. Bonnetain 等[53]以SPN 和Feistel 結(jié)構(gòu)為分析對象, 深入研究了各種量子滑動攻擊, 將“模加” 運算、自相似、圈等因素都考慮進來, 其攻擊加速效果因結(jié)構(gòu)的具體特點而差異巨大, 例如, Feistel 結(jié)構(gòu)分別采用“⊕” 和“模加” 情況時, 在該量子攻擊下的復(fù)雜度相差指數(shù)量級.

Rotteler 和Steinwandt[54]基于Simon 量子算法提出一種量子相關(guān)密鑰攻擊模型. 在此模型下, 攻擊者不僅可對消息空間進行量子疊加態(tài)查詢, 還可對密鑰空間做疊加查詢. 由于該模型賦予攻擊者過于強大的能力, 任何分組加密方案都不可能抵抗此種量子相關(guān)密鑰攻擊. 因此, 這是一種不現(xiàn)實的量子攻擊模型. Hosoyamada 和Aoki[55]提出另一種量子相關(guān)密鑰攻擊, 僅針對迭代Even-Mansour 結(jié)構(gòu)可在多項式時間內(nèi)恢復(fù)密鑰. 事實上, 這種量子相關(guān)密鑰攻擊是對Kaplan 等所提出的量子滑動攻擊[2]的一種推廣, 從而適用于迭代Even-Mansour 結(jié)構(gòu)中所有輪密鑰都獨立選擇的情形.

總體來看, Q2 模型下的量子攻擊技術(shù)通常以Simon 量子算法為核心, 從而實現(xiàn)非常高效的量子攻擊;而Q1 模型下的量子攻擊技術(shù)大多以Grover 搜索算法為核心, 攻擊加速的效果有限, 但是相對Q2 模型來說是更具現(xiàn)實意義的. Bonnetain 等[29]提出了離線“Grover+Simon” 算法, 在特定的情況下可將Q2模型下量子攻擊技術(shù)(包括Rotteler 和Steinwandt[54]的量子相關(guān)密鑰攻擊和量子滑動攻擊) 轉(zhuǎn)換到Q1模型下使用.

4.2 量子攻擊資源評估與優(yōu)化

在評估密碼算法在量子攻擊下的量子資源需求時, 首先需要選取一個或多個指標(biāo)作為量化評估標(biāo)準(zhǔn).量化評估指標(biāo)的選取通常都要結(jié)合量子計算機物理實現(xiàn)進展水平. 量子線路模型是量子計算研究廣泛采用的模型, 目前研究人員主要選取量子線路的各種復(fù)雜度指標(biāo), 如Toffoli 門與T 門的數(shù)量和深度、線路總深度、量子比特數(shù)等. 部分研究還將MAXDEPTH(最大線路深度)約束作為量化評估的一個限制因素,即在量子線路所允許的最大深度限制下量化評估量子攻擊資源[10,13].

在量子窮舉密鑰攻擊下, 加密算法安全強度的粗略估計是O(2n/2) 次量子計算, 與經(jīng)典安全強度O(2n) 相比正好是平方加速, 其中n是密鑰長度. 實際上這里O(2n/2) 是該攻擊運行中執(zhí)行Grover迭代的輪數(shù), 由于每一輪Grover 迭代的主體部分都是以量子方式執(zhí)行至少兩次該密碼算法, 通常也將O(2n/2) 視為量子查詢復(fù)雜度. 為了量化評估加密算法的量子安全強度, 必須分析每一輪Grover 迭代(或密碼算法) 的量子實現(xiàn)復(fù)雜度. 因此, 為了準(zhǔn)確評估加密算法在量子窮舉密鑰攻擊下的安全強度, 應(yīng)盡可能準(zhǔn)確地評估加密算法的量子實現(xiàn)復(fù)雜度. Grassl 等[8]最早開展了AES 的量子線路設(shè)計工作, 給出了AES-128/192/256 的量子線路實現(xiàn)中T 門數(shù)量和深度、Clifford 門數(shù)量、線路的深度和量子比特數(shù), 在此基礎(chǔ)上估計了量子窮舉攻擊所需量子資源: 對于AES-128, 需要2953 個量子比特, 1.19×286個T 門,1.55×286個Clifford 門, 線路深度為1.16×281(遠大于粗略的估計值264). Kim 等[13]、Almazrooie等[56]、Jaques 等[57]和Zou 等[58]通過改進量子線路設(shè)計, 優(yōu)化量子線路實現(xiàn)的各項復(fù)雜度指標(biāo), 盡可能逼近真實的量子攻擊資源需求. 目前公開的最優(yōu)設(shè)計是Zou 等給出的結(jié)果: AES-128/192/256 的量子線路實現(xiàn)分別需要512, 640 和768 個量子比特[58].

除了AES 以外, 研究人員還在量子窮舉攻擊下對其它(輕量級) 分組密碼和序列密碼開展了量子攻擊資源量化評估和優(yōu)化研究, 包括GIFT、SKINNY、SATURNIN[11]和基于ARX 的SPECK[12]和LowMC[57],還有基于反饋移位寄存器的序列密碼Grain-128-AEAD、TinyJAMBU、LIZARD 和Grainv1 等[10].

對于雜湊算法, 為了評估其量子抗碰撞性, 一般使用量子碰撞攻擊技術(shù)來量化評估其安全強度, 而為了評估其量子抗原像攻擊性, 一般采用量子原像查找攻擊(實際上就是對原像的量子窮舉攻擊). 無論從哪個角度來評估量子攻擊資源, 都需要盡可能準(zhǔn)確地評估雜湊算法的量子實現(xiàn)復(fù)雜度. Amy 等[9]在量子原像攻擊下評估雜湊算法SHA2 和SHA3 的安全強度. 類似于對AES 的量子窮舉攻擊, 他們設(shè)計量子線路實現(xiàn)SHA-256 和SHA3-256, 然后評估了該攻擊所需量子資源, 包括在采用表面碼(surface code) 實現(xiàn)量子糾錯的情況下的線路深度和量子比特數(shù). Kim 等[13]從Toffoli 門深度和量子比特數(shù)角度改進了對SHA2 的量子原像攻擊資源評估, 其中Toffoli 門深度可降至大約2141, 而量子比特數(shù)量可改進到802.

量子碰撞攻擊技術(shù)的核心是量子碰撞查找算法. 早期的BHT 碰撞查找算法的查詢復(fù)雜度為O(2n/3)(其中n為雜湊函數(shù)的輸出長度), 優(yōu)于經(jīng)典碰撞攻擊的復(fù)雜度O(2n/2); 但是該算法需要O(2n/3) 規(guī)模的量子隨機可訪問的經(jīng)典存儲(QRACM), 目前這個QRACM 需要用量子存儲來完成. 在當(dāng)前的量子計算機體系架構(gòu)下, 用于存儲數(shù)據(jù)的量子位就是量子計算機的核心, 相當(dāng)于傳統(tǒng)計算機的中央處理單元. 因此, 應(yīng)該將這些量子存儲納入量化評估體系, 采用時間-存儲折衷(time-memory tradeoff, TMT) 來評估算法復(fù)雜度. 在這種情況下, BHT 碰撞查找算法的TMT 值為O(22n/3), 與經(jīng)典生日碰撞攻擊的復(fù)雜度O(2n/2) 相比就失去了優(yōu)勢. Chailloux 等[59]重新發(fā)掘了量子碰撞查找算法的優(yōu)勢, 通過改進算法設(shè)計,新算法(簡記為CNS 量子算法) 的時間復(fù)雜度為O(22n/5), 量子存儲規(guī)模為O(n). 基于CNS 量子算法, Kim 等[13]對SHA2 在量子碰撞攻擊下所需量子資源進行了量化評估, 給出的Toffoli 門深度估計為2117, 而量子比特數(shù)量為939.

除了量子窮舉攻擊和碰撞攻擊這兩類通用量子攻擊以外, 采用其它攻擊技術(shù)的量子攻擊資源評估還存在很多研究空白. 研究人員在這方面也開展了一些工作, 針對具體密碼方案的內(nèi)部構(gòu)造細節(jié)或特點, 設(shè)計專用的量子攻擊算法, 開展量子安全強度評估. 具體介紹如下.

Bonnetain 和 Jaques[14]在 Q1 模型下采用離線 Simon 算法開展攻擊研究, 給出了 Chasky、PRINCE、Elephant 等的量子攻擊資源量化評估. 研究結(jié)果表明其攻擊性能明顯優(yōu)于通用量子攻擊.

這些研究進展表明, 專用的量子碰撞攻擊能夠顯著改進碰撞查找效率, 已經(jīng)成為了一種重要的量子攻擊技術(shù). 其潛力還可進一步發(fā)掘并應(yīng)用于更多的密碼方案.

5 對結(jié)構(gòu)和工作模式的量子攻擊

量子計算對對稱密碼安全性的重要影響之一是對結(jié)構(gòu)和工作模式的威脅. 目前對結(jié)構(gòu)和工作模式的量子攻擊研究主要可分為兩大類: (1) 在Q2 模型下的量子攻擊, 這種情況下可以充分利用Simon 量子算法等黑盒算法取得指數(shù)級攻擊加速; (2) 在Q1 模型下的量子攻擊, 這方面的研究相對較少, 且不易取得顯著的攻擊加速效果. 由于這兩類模型下的量子攻擊技術(shù)和研究方法均存在較大差異, 下面將分別進行介紹.

5.1 Q2 模型下的攻擊

在Q2 模型下攻擊分組密碼結(jié)構(gòu)和工作模式的常用方法是先根據(jù)密碼結(jié)構(gòu)或模式的具體特點來設(shè)計具有周期性結(jié)構(gòu)的數(shù)學(xué)函數(shù), 然后用Simon 量子算法來查找該函數(shù)的周期(該周期值通常是某種關(guān)鍵信息, 例如密鑰或者與密鑰有關(guān)的值), 再根據(jù)攻擊目標(biāo)來設(shè)計后續(xù)的量子偽造攻擊或量子區(qū)分攻擊等. 理論上Q2 模型下還可使用其它黑盒量子算法作為區(qū)分器設(shè)計的基本工具.

Kuwakado 和Morii[64]在Q2 模型下研究了Even-Mansour 結(jié)構(gòu)(即Ek1,k2(x)=P(x ⊕k1)⊕k2,其中P是一個公開置換,k1,k2為密鑰) 的量子偽隨機性, 基于Simon 量子算法構(gòu)造了qCPA 下的高效區(qū)分器: 經(jīng)過O(n) 次量子查詢, 可有效地區(qū)分Even-Mansour 結(jié)構(gòu)和真隨機函數(shù). Kaplan 等[2]推廣了這種量子區(qū)分器構(gòu)造方法, 將其應(yīng)用到可調(diào)分組密碼結(jié)構(gòu)LRW : ?Et,k(x) =Ek(x ⊕h(t))⊕h(t), 其中h是一個(almost) universal hash function. 他們構(gòu)造了qCPA 下的高效區(qū)分器: 經(jīng)過O(n) 次量子查詢就可區(qū)分LRW 結(jié)構(gòu)和理想的可調(diào)分組密碼. 作為LRW 結(jié)構(gòu)的實例化, XEX 或XE 也存在這種量子區(qū)分器.

關(guān)于Feistel 結(jié)構(gòu), 有qCPA 和qCCA 下的量子分析研究結(jié)果. Kuwakado 和Morii[65]構(gòu)造了3 輪Feistel 結(jié)構(gòu)的qCPA 區(qū)分器. Ito 等[66]構(gòu)造了4 輪Feistel 結(jié)構(gòu)的qCCA 區(qū)分器, 即4 輪Feistel 結(jié)構(gòu)不是量子強偽隨機的(實際上4 輪Feistel 結(jié)構(gòu)是量子偽隨機的[4]). 關(guān)于Feistel 結(jié)構(gòu)的這些量子區(qū)分器構(gòu)造中, 均假定對結(jié)構(gòu)的量子查詢Oracle 進行了截斷輸出, 但是并沒有提出截斷Oracle 的實現(xiàn)方法, 直到Hosoyamada 和Sasaki[43]給出一個簡單的解決方案: 將存放輸出結(jié)果的量子寄存器中需要截斷的部分量子位都初始化為量子態(tài)|+〉.

關(guān)于廣義Feistel 結(jié)構(gòu), Ito 和Iwata[67]針對Type-1 型廣義Feistel 結(jié)構(gòu)設(shè)計了3d-3 輪qCPA 區(qū)分器(即qCPA 模型下的多項式級量子區(qū)分器) 和d2-d+1 輪qCCA 區(qū)分器(即qCCA 模型下的多項式級量子區(qū)分器), 其中d為廣義Feistel 結(jié)構(gòu)的分支數(shù).

Wang 和Ma[68]構(gòu)造了3 輪和4 輪非平衡Feistel 結(jié)構(gòu)的量子區(qū)分器; Dong 等[69]針對d分支Type-1 型GFN 設(shè)計了2d-1 輪量子區(qū)分器, 針對2d分支Type-2 型GFN 設(shè)計了2d+1 輪量子區(qū)分器. 針對4 分支Type-2 型GFN 的5 輪量子區(qū)分器, 羅宜元等[70]指出了其中的錯誤并作出修正. 由于4 分支Type-2 型GFN 需要迭代至少10 輪才能達到經(jīng)典偽隨機性, 因此僅僅構(gòu)造5 輪量子區(qū)分器是沒有價值的, 那么能否構(gòu)造10 輪結(jié)構(gòu)的量子區(qū)分器？該問題仍然有待研究. Ni 和Dong[71]繼續(xù)對Type-1型GFN 的量子區(qū)分器做出改進, 分別在qCPA 和qCCA 情況下設(shè)計了3d-3 輪區(qū)分器. 羅宜元等[70]證明在qCPA 下基于Simon 算法的量子攻擊技術(shù)可有效攻擊3 輪MISTY-L 與MISTY-R 結(jié)構(gòu), 但不能攻擊3 輪Lai-Massey 結(jié)構(gòu). 該結(jié)果由Gouget 等改進, 給出了4 輪MISTY-L 結(jié)構(gòu)的qCPA 區(qū)分器[72].對于SM4 型Feistel 結(jié)構(gòu), Cid 等[73]和我們分別獨立給出了7 輪結(jié)構(gòu)的qCPA 區(qū)分器, 此外, 我們還設(shè)計了8 輪結(jié)構(gòu)的qCCA 區(qū)分器.

對這些迭代結(jié)構(gòu)的量子區(qū)分器設(shè)計進展情況如表1 所示. 易見, 在qCCA 模型下的研究尚不充分, 還存在許多未知項.

表1 Q2 模型下分組密碼迭代結(jié)構(gòu)的量子區(qū)分器設(shè)計進展情況Table 1 Research progress about quantum distinguisher of iterated cryptographic construction under Q2 model

以分組密碼結(jié)構(gòu)的量子區(qū)分器為基礎(chǔ), 研究人員開展了量子密鑰恢復(fù)攻擊技術(shù)研究. Leander 和May[28]提出組合使用Grover 算法和Simon 算法的量子攻擊技術(shù)框架(簡稱為“Grover+Simon” 量子攻擊框架), 可用于執(zhí)行量子密鑰恢復(fù)攻擊, 并成功應(yīng)用于對FX 結(jié)構(gòu)的分析. 這里的FX 結(jié)構(gòu)可描述為FXk0,k1,k2(x)=Ek0(x ⊕k1)⊕k2, 其中密鑰長度|k0|=m,|k1|=|k2|=n. 在密碼學(xué)研究中, FX 結(jié)構(gòu)被用于擴展給定分組密碼的密鑰長度, 以獲得更高的經(jīng)典安全強度, 例如DESX、PRINCE 和PRIDE 的設(shè)計中均采用FX 結(jié)構(gòu). Leander 和May[28]以Even-Mansour 結(jié)構(gòu)的量子區(qū)分器為基礎(chǔ), 采用Grover 算法來搜索給定分組密碼的密鑰(k0,k1,k2), 只需要O(m+n)2m/2次量子查詢. 因此在Q2 模型下, 相對于原分組密碼Ek0, 采用FX 結(jié)構(gòu)進行擴展后并沒有顯著提升量子安全強度.

采用Leander 和May[28]提出的“Grover+Simon” 量子攻擊框架, Hosoyamada 和Sasaki[43], 以及Dong 和Wang[51]分別研究了Feistel 結(jié)構(gòu)的量子密鑰恢復(fù)攻擊技術(shù). 前者針對6 輪Feistel 結(jié)構(gòu)分析了恢復(fù)全部密鑰的攻擊復(fù)雜度, 其查詢復(fù)雜度為O((m+n2)2n), 計算復(fù)雜度為O(n32n/2), 且只需要使用O(m+n2) 個qubits 的存儲(不需要經(jīng)典存儲). 后者針對r輪Feistel 結(jié)構(gòu)設(shè)計了量子密鑰恢復(fù)攻擊, 其量子查詢次數(shù)為O(n2(r-3)n/4), 攻擊所需量子比特數(shù)為O(n2).

除了對分組密碼結(jié)構(gòu)的量子攻擊以外, 在Q2 模型下還可對許多認(rèn)證和認(rèn)證加密方案進行高效的量子攻擊.

在認(rèn)證方案的量子攻擊方面, Boneh 和Zhandry[7]最早設(shè)計了一個量子算法, 可在量子多項式時間內(nèi)攻擊Carter-Wegman MAC. 即, 他們證明了該MAC 方案不是EUF-qCMA 安全的: 攻擊者經(jīng)過一次量子選擇消息查詢就能以高概率獲得關(guān)鍵信息, 足以偽造任意消息的合法標(biāo)記.

該量子攻擊技術(shù)未能推廣到對其它MAC 的攻擊, 而基于Simon 量子算法的攻擊技術(shù)后來被廣泛使用, 其中影響較廣的研究是Kaplan 等[2]提出的針對CBC-MAC、PMAC、GMAC 等認(rèn)證模式的量子偽造攻擊. 下面分別進行介紹.

CBC-MAC 是一種確定性的MAC, 它有多個變化版本. Kaplan 等[2]給出的量子攻擊是針對Encrypted-CBC-MAC 的偽造攻擊, 其中使用了兩個密鑰:k和k′. 但這里的攻擊方法容易修改后用于其它版本, 包括CMAC. 對各版本的量子攻擊都利用了它們的一個共性: 在對所輸入消息塊m1‖m2產(chǎn)生認(rèn)證標(biāo)記時都執(zhí)行了形如m2⊕Ek(m1) 的計算, 從而容易設(shè)計得到周期函數(shù), 以達到使用Simon 算法的前提條件.

GMAC 是一種隨機性的MAC, 增加了一個nonce, 每次都選擇一個不同的nonce 值. GMAC 的結(jié)構(gòu)與CBC-MAC 類似, 可采用類似的基于Simon 量子算法的攻擊方式, 即使每次查詢都更換一個新的nonce, 基于GMAC 查詢所構(gòu)造的周期函數(shù)(該函數(shù)值必然與nonce 有關(guān)) 仍然保持一個與nonce 無關(guān)的周期值. 因此, nonce 在GMAC 中的使用方式并不能抵抗這種量子攻擊.

Poly1305 是由Bernstein 設(shè)計的一個MAC, 已經(jīng)標(biāo)準(zhǔn)化用于TLS1.2. 對于兩分組長度的消息M=m1‖m2, Poly1305 定義為:c1= (m2+ 2128)rmod(2130- 5),c2= (m1+ 2128)r2mod(2130- 5),Poly1305(N,M) =c1+c2+Ek(N), 其中r,k為密鑰,N為nonce. 該工作模式中采用“模加” 運算而不是bitwise XOR 運算. 基于Simon 算法的量子攻擊無法使用, 但是Bonnetain 和Naya-Plasencia[26]提出基于Kuperberg 算法[75]的量子攻擊技術(shù): 根據(jù)Poly1305 來設(shè)計兩個函數(shù)f和g, 這兩個函數(shù)都可基于對Poly1305 的量子選擇消息查詢來實現(xiàn), 而且兩者存在隱藏移位r使得f(x) =g(x+r); 然后對Kuperberg 算法進行改進并用于尋找這個隱藏移位. Poly1305 的密鑰r和k都是128 比特, nonce 和輸出的tag 也是128 比特. 改進的Kuperberg 算法仍然是一個亞指數(shù)時間的量子算法, 雖然它無法達到Simon 算法那樣高效的攻擊, 但是對Poly1305 的量子攻擊復(fù)雜度為238, 在此基礎(chǔ)上應(yīng)用Grover 加速,還可將攻擊復(fù)雜度進一步降至231. 因此, Poly1305 的安全強度無法達到Q2 模型下的安全性[26].

認(rèn)證加密工作模式GCM 和OCB 等都通過嵌入一個MAC 模式來產(chǎn)生關(guān)聯(lián)數(shù)據(jù)的認(rèn)證部分,Kaplan等[2]將上述對認(rèn)證模式的量子攻擊推廣到這些帶關(guān)聯(lián)數(shù)據(jù)的認(rèn)證加密模式. GCM 和OCB 都是基于nonce 的認(rèn)證加密模式, 并且對關(guān)聯(lián)數(shù)據(jù)的認(rèn)證都與nonce 無關(guān). 對于這兩種模式, 當(dāng)明文中只有關(guān)聯(lián)數(shù)據(jù)(消息是空值) 時, GCM 正好就等同于GMAC, OCB 正好就等同于PMAC, 因此, 對GMAC 的攻擊可直接應(yīng)用于GCM, 對PMAC 的攻擊可直接應(yīng)用于OCB. 類似地, 還可以把對CBC-MAC 的攻擊推廣到CLOC,把對PMAC 的攻擊推廣到AEZ、COPA、OTR、POET 等CAESAR 候選方案. 另外, OMD、Minalpher 也是PMAC 的不同版本, 因此對它們也能采用量子攻擊. 對于CAESAR 候選方案AEZ 的其它版本AEZv4、AEZv5 和AEZ10, Bonnetain[76]提出了基于Simon 算法的量子攻擊方案, 至此AEZ的所有版本在Q2 模型下都可被完全攻破.

5.2 Q1 模型下的攻擊

前面介紹了Q2 模型下對分組密碼結(jié)構(gòu)的量子攻擊研究. 接下來介紹Q1 模型下的量子攻擊研究進展. 與Q2 模型相比, Q1 模型下的量子攻擊研究相對較少, 且部分結(jié)果是由Q2 模型下的攻擊轉(zhuǎn)換而來.

對于Even-Mansour 結(jié)構(gòu), Kuwakado 和Morii[64]基于量子claw finding 算法, 提出了一種量子密鑰恢復(fù)攻擊方法, 只需要O(2n/3) 次經(jīng)典查詢和O(2n/3) 時間的量子計算.

Hosoyamada 和Sasaki 提出了兩類量子中間相遇(MITM) 攻擊技術(shù). 第一類是量子Demiric-Selcuk中間相遇攻擊(量子DS-MITM)[43], 用于攻擊6 輪Feistel 結(jié)構(gòu); 在經(jīng)典DS-MITM 攻擊下的數(shù)據(jù)復(fù)雜度、時間復(fù)雜度和存儲復(fù)雜度分別為O(23n/4),O(23n/4) 和O(2n/2)[77], 而Q1 模型下DS-MITM 攻擊給出的各項復(fù)雜度指標(biāo)均降低至O(2n/2). 第二類被用于攻擊一些超生日界安全的MAC 模式Chaskey、可調(diào)分組密碼TDR、McOE-X、H2-MAC、keyed-sponge, 還可以用于FX 結(jié)構(gòu)獲得新的TMT:D·T6=23(n+m)(D ≤min{2n,23(n+m)/7})[42].

Bonnetain 等[29]提出一種全新的思路: 不是將經(jīng)典模型下的攻擊方法向Q1 模型推廣, 而是利用離線“Grover+Simon” 算法, 將Q2 模型下量子區(qū)分器進行了“部分去量子化” 轉(zhuǎn)換, 設(shè)計Q1 模型下的量子攻擊. 基于這種思路, 他們設(shè)計或改進了針對許多密碼結(jié)構(gòu)和模式的量子攻擊, 包括Even-Mansour 結(jié)構(gòu)、FX 結(jié)構(gòu)、迭代的FX 結(jié)構(gòu)、輕量級密碼Chaskey、Beetle 和SATURNIN 等. 其中, 針對Even-Mansour 結(jié)構(gòu)改進了量子攻擊, 只需要多項式規(guī)模的經(jīng)典和量子存儲, 針對FX 結(jié)構(gòu)改進了量子攻擊的TMT:D·T2=2n+m(D ≤2n).

6 結(jié)構(gòu)和工作模式的量子可證明安全性

結(jié)構(gòu)和工作模式的量子可證明安全性是當(dāng)前抗量子對稱密碼研究的重要方向. Q1 模型和Q2 模型所允許的查詢方式不同, 導(dǎo)致其安全性證明方面存在很大差異. Q1 模型只允許量子攻擊者執(zhí)行經(jīng)典查詢, 此時的證明方式更接近于經(jīng)典可證明安全. 然而當(dāng)允許攻擊者執(zhí)行量子疊加態(tài)查詢時, 一次查詢即可并行地完成對定義域全體元素的查詢, 因此量子證明中需要新工具新技術(shù). 下面分別從量子證明工具、帶密鑰密碼原語的量子可證明安全、雜湊密碼的量子可證明安全等方面來介紹.

6.1 量子證明工具

目前廣泛使用的量子證明工具包括One-way-to-hiding Lemma (O2H 引理[78]) 和壓縮預(yù)言機技術(shù)(compressed oracle technique[20]).

O2H 引理最早由Unruh[78]提出, 后來發(fā)展了多個改進版本[79–81], 成為量子安全性證明的主要工具之一. “games-playing” 方式被廣泛用于密碼安全性證明(特別是一些復(fù)雜的構(gòu)造). 在設(shè)計一系列的games 的過程中, 非常關(guān)鍵的技術(shù)就是將game 進行隨機化: 例如將一個計算值H(x) 替換成一個隨機值y(將(x,H(x)) 替換成(x,y)); 如果攻擊者可對H執(zhí)行量子疊加態(tài)查詢, 那么“如何估計隨機化前后兩個games 之間的差異” 就成為一個關(guān)鍵問題, 而O2H 引理正好解決了這個問題. 目前O2H 引理已經(jīng)成為公鑰密碼在量子隨機預(yù)言機模型下的安全性證明的重要工具[81–83], 并且它還被用于Q2 模型下的對稱密碼工作模式的安全性證明, 包括加密工作模式CBC 和CFB 的IND-qCPA 安全性證明[5].

壓縮預(yù)言機技術(shù)用于動態(tài)地記錄對隨機函數(shù)的量子查詢, 從而有效地模擬量子模型下的隨機函數(shù)(事實上也可視為lazy-sampling 的量子版). 在經(jīng)典安全性證明中經(jīng)常需要記錄對隨機函數(shù)的查詢輸入/輸出值. 但是將這些安全性證明向量子模型遷移的過程中將遇到困難, 因為在量子查詢情況下, 實際上對所有疊加分量(即隨機函數(shù)的定義域全體元素) 都并行地做了查詢, 而這些查詢的輸入輸出值無法全部直接記錄下來. Zhandry[20]提出壓縮預(yù)言機技術(shù), 有效地解決了這個問題.

壓縮預(yù)言機技術(shù)是記錄量子查詢的重要技術(shù), 但是Zhandry[20]的壓縮預(yù)言機技術(shù)是有局限的, 只適用于記錄對隨機函數(shù)的量子查詢. 當(dāng)要記錄隨機置換的量子查詢時, 量子數(shù)據(jù)庫中任何兩條記錄(x,u) 和(x′,u′) 是存在關(guān)聯(lián)的(即x/=x′時u/=u′), 此時Zhandry 的壓縮預(yù)言機技術(shù)就不能直接使用了. 該局限性已由Unruh[84]解決. Czajkowski 等[85]將壓縮預(yù)言機技術(shù)推廣到更一般的情況, 構(gòu)造非均勻分布隨機函數(shù)(non-uniformly distributed random functions) 的壓縮預(yù)言機.

壓縮預(yù)言機技術(shù)是一種重要的量子安全性證明技術(shù), 它被成功地應(yīng)用于量子疊加態(tài)查詢情況下結(jié)構(gòu)和模式的安全性證明. 此外, 在量子算法的查詢復(fù)雜度下界的證明方面, 它也發(fā)揮了重要作用, 例如碰撞查找問題[19]、k碰撞查找問題[24], 以及k-xor 問題[86]等的量子求解算法的查詢復(fù)雜度下界證明.

在經(jīng)典可證明安全研究中, 偽隨機函數(shù)-偽隨機置換轉(zhuǎn)換引理(PRF-PRP Switching Lemma) 是被廣泛應(yīng)用的工具之一. 利用壓縮預(yù)言機技術(shù)可以證明得到一個量子版本的PRF-PRP 轉(zhuǎn)換引理, 從而作為量子可證明安全的一個基本工具.

除了上述量子證明工具以外, 還有一些證明工具在密碼協(xié)議的量子安全性研究中發(fā)揮了重要作用. 一般地, 在證明協(xié)議安全性時, 模擬器需將協(xié)議參與方回倒(rewinding) 至以前的狀態(tài), 而在協(xié)議方是量子參與者的情況下,常規(guī)的方式無法做到這一點. Watrous[87]和Unruh[88]各自提出了“quantum rewinding”技術(shù), 分別應(yīng)用于Goldreich–Micali–Wigderson 圖同構(gòu)零知識證明協(xié)議和Σ 協(xié)議的量子安全性證明. 現(xiàn)有的“quantum rewinding” 技術(shù)都局限于特定情形下的證明, Ambainis 等[89]發(fā)展了新的量子證明工具“pick-one trick”, 它是指從給定子空間中搜索滿足一定條件的值的搜索技術(shù). 該技術(shù)可用于證明協(xié)議在量子情況下的安全性或不安全性. “quantum rewinding” 和“pick-one trick” 技術(shù)能否用于對稱密碼的量子可證明安全？目前還有待探索.

與經(jīng)典安全性證明相比, 通常在量子情況下的安全性證明過程都相當(dāng)復(fù)雜, 對量子態(tài)和量子運算的推導(dǎo)也非常容易出錯. 如果能夠采用計算機輔助證明, 則可提高證明的可靠性. Unruh[90]提出了quantum relational hoare logic (qRHL), 適用于計算機輔助執(zhí)行對密碼算法(包括量子密碼和抗量子密碼) 的量子安全性形式化分析, 但是目前該工具還不夠完善.

6.2 帶密鑰原語的量子可證明安全

現(xiàn)有的一些結(jié)構(gòu)和工作模式被證明滿足量子安全性, 即, 在量子安全模型下證明: 當(dāng)?shù)讓雍瘮?shù)滿足偽隨機性, 整體結(jié)構(gòu)和工作模式也能達到偽隨機性. 在具體介紹量子可證明研究結(jié)果之前, 我們約定將Q2模型下的偽隨機函數(shù)和偽隨機置換分別記為qPRF 和qPRP, Q1 模型下的偽隨機函數(shù)和偽隨機置換分別記為sPRF 和sPRP.

對于加密工作模式, Anand 等[5]證明了CBC、CFB、OFB 和CTR 模式在Q2 模型下的量子可證明安全性: 將CBC、CFB、OFB、CTR 等模式的IND-qCPA 安全性歸約到底層分組加密函數(shù)在Q2模型下的偽隨機性, 即, 這四種模式中任何一個都可將定長定義域上的qPRF 擴展得到一個變長定義域上的qPRF. 他們還研究發(fā)現(xiàn), 工作模式要達到Q2 模型下的量子安全性并不一定要求底層分組加密函數(shù)是qPRF 或qPRP. 例如, 對于OFB 和CTR, 僅要求底層函數(shù)達到sPRF 的安全要求, 它們就能滿足Q2模型下的IND-qCPA 安全性; 而對于CBC 和CFB, 如果底層函數(shù)是一個sPRF 但不是qPRF, 則它們也只能達到Q1 模型下的安全性.

對于認(rèn)證工作模式, Song 和Yun[6]在Q2 模型下證明了NMAC、HMAC、AMAC 和定長輸入的Cascade 構(gòu)造都是量子偽隨機的. 因此,它們都可作為由qPRP 構(gòu)造qPRF 的變換. 由于qPRF 直接作為MAC 使用時就可以滿足EUF-qCMA 安全性[7], 因此這4 種構(gòu)造都是Q2 模型下量子安全的認(rèn)證模式.他們的證明所確定的NMAC(或HMAC)的量子安全性界為O(2n/5)(或O(2n/8))次量子查詢,其中n為輸出長度. Hosoyamada 和Iwata[91]給出了更緊的量子安全界: 在量子隨機預(yù)言機模型下, 區(qū)分HMAC(或NMAC) 和隨機函數(shù)所需量子查詢次數(shù)至少為Ω(2n/3). 由于通用量子碰撞攻擊下需要O(2n/3) 次量子查詢, 我們獲得量子安全界Θ(2n/3).

對于Feistel 結(jié)構(gòu),3 輪迭代即可達到經(jīng)典偽隨機性,但是不滿足Q2 模型下的偽隨機性. Hosoyamada和Iwata[4]證明了4 輪Feistel 結(jié)構(gòu)可達到Q2 模型下的偽隨機性: 若f1,f2,f3,f4是獨立的qPRF, 則4 輪迭代函數(shù)Feistel4(f1,f2,f3,f4) 就是一個qPRP. 在經(jīng)典模型下, 4 輪Feistel 迭代結(jié)構(gòu)能夠達到強偽隨機性, 然而在Q2 模型下需要迭代多少輪才能達到量子強偽隨機性？這個問題還有待研究.

Czajkowski 等[3]證明當(dāng)內(nèi)部函數(shù)是帶密鑰的函數(shù)或置換時, Sponge 結(jié)構(gòu)可達到Q2 模型下的偽隨機性: 若內(nèi)部函數(shù)f是qPRF 或qPRP, 則根據(jù)Sponge 結(jié)構(gòu)進行擴展所得函數(shù)SPONGEf是一個qPRF.因此, Sponge 結(jié)構(gòu)可用于Q2 模型下的抗量子對稱密碼設(shè)計.

6.3 雜湊的量子可證明安全

這里的雜湊函數(shù)都是指無密鑰的函數(shù), 而帶密鑰的雜湊函數(shù)可視為一種認(rèn)證來研究. 目前, 雜湊結(jié)構(gòu)的量子可證明安全研究主要涉及量子抗碰撞性、Collapsing 以及量子不可區(qū)別性(quantum indifferentiability) 等安全屬性.

Sponge 結(jié)構(gòu)是一種被廣泛應(yīng)用的雜湊結(jié)構(gòu), 對它的量子安全性研究也是最多的. Czajkowski 等[92]證明了Sponge 結(jié)構(gòu)的量子抗碰撞性, 該結(jié)論要求內(nèi)部函數(shù)f滿足以下條件: 截斷f輸出的左半或右半部分時均滿足抗碰撞性, 且截斷f輸出的左半部分時難以找到0 對應(yīng)的原像. 他們還證明了Sponge 結(jié)構(gòu)滿足Collapsing 屬性: 當(dāng)內(nèi)部函數(shù)f是隨機函數(shù)或隨機置換時, Sponge 結(jié)構(gòu)滿足Collapsing 安全屬性(這里要求隨機置換f不可有效求逆). 該結(jié)果存在局限性, 不能應(yīng)用于SHA3 的量子安全性證明, 因為SHA3使用了一個有效可逆的置換作為f. Unruh[38]證明了Merkle-Damgaard 結(jié)構(gòu)滿足Collapsing 安全屬性,即,當(dāng)?shù)讓訅嚎s函數(shù)f是Collapsing,則MDf也是Collapsing. 針對雜湊結(jié)構(gòu)的Collapsing 證明,Fehr[93]提出一套證明框架, 允許我們以純經(jīng)典(不涉及任何量子推理) 的方式來證明雜湊結(jié)構(gòu)的Collapsing 安全性. 基于這套證明框架, 他們重新證明了MD 結(jié)構(gòu)和Sponge 結(jié)構(gòu)是Collapsing, 并且新證明了HAIFA結(jié)構(gòu)也滿足Collapsing. Gunsing 和Mennink[94]將該框架應(yīng)用到tree hash 的Collapsing 證明.

與量子抗碰撞性和 Collapsing 等安全屬性的證明相比, 量子不可區(qū)別性的證明難度要大很多.Zhandry 提出的壓縮預(yù)言機技術(shù)發(fā)揮了關(guān)鍵作用, 他證明了(在prefix-free encoding 情況下) Merkle-Damgaard 結(jié)構(gòu)滿足量子不可區(qū)別性. Czajkowski 等[85]改進Zhandry 的壓縮預(yù)言機, 證明了: 當(dāng)內(nèi)部函數(shù)是隨機函數(shù)或隨機置換時, Sponge 結(jié)構(gòu)是量子不可區(qū)別的, 并證明由量子不可區(qū)別性可推導(dǎo)出Collapsing, 因此Sponge 結(jié)構(gòu)也滿足Collapsing. 注意, 這里的Collapsing 證明不要求Sponge 結(jié)構(gòu)的內(nèi)部函數(shù)f不可有效求逆, 從而克服了他們早期證明結(jié)果[92]中的局限性.

Carstens 等[95]給出一個否定性的證明: Sponge 結(jié)構(gòu)不滿足完美的量子不可區(qū)別性. 注意這與Sponge 結(jié)構(gòu)的量子不可區(qū)別性證明并不矛盾, 因為一般所說的量子不可區(qū)別性證明并不要求零區(qū)分優(yōu)勢.

上述量子可證明安全研究主要關(guān)注Collapsing 和量子不可區(qū)別性等. 量子抗碰撞性和量子抗原像性等都是在量子模型下對傳統(tǒng)雜湊安全屬性的增強, 我們還應(yīng)該研究雜湊結(jié)構(gòu)是否滿足這些量子安全屬性.Hamlin 和Song[37]證明了由Andreeva 等提出的雜湊結(jié)構(gòu)ROX[96]的量子安全性: 當(dāng)?shù)讓訅嚎s函數(shù)f滿足量子抗碰撞性/量子抗原像性/量子抗第二原像性時, ROXf也滿足相應(yīng)的量子安全屬性. Hosoyamada和Yasuda[97]證明了基于Davies-Meyer 壓縮函數(shù)的Merkle-Damgard 迭代構(gòu)造滿足量子抗原像性, 這意味著該構(gòu)造是一個量子可證明安全的單向函數(shù).

7 抗量子計算對稱密碼設(shè)計

與傳統(tǒng)對稱密碼相比, 抗量子對稱密碼在設(shè)計方面尚未發(fā)現(xiàn)本質(zhì)差異. 雖然一些對稱密碼方案遭受了不同程度的量子計算攻擊, 但是仍然有很多傳統(tǒng)對稱密碼方案是量子安全的; 并且對于遭受量子計算攻擊的方案, 經(jīng)過改造仍然可能達到量子安全性. 接下來具體介紹相關(guān)研究進展情況.

量子偽隨機函數(shù)是抗量子對稱密碼研究中基本的密碼學(xué)原語. 最早是在2012 年Zhandry[98]給出了Q2 模型下的3 種偽隨機函數(shù)的設(shè)計方法: (1) 基于Q1 模型下的偽隨機發(fā)生器, 采用Goldreich、Goldwasser 和Micali[99]的偽隨機函數(shù)(即GGM-PRF) 的構(gòu)造方法, 可獲得Q2 模型下的偽隨機函數(shù)(即qPRF);(2)基于Q1 模型下的偽隨機合成器,采用Naor 和Reingold[100]的偽隨機函數(shù)(即NR-PRF)的構(gòu)造方法, 也可獲得qPRF; (3) Banerjee、Peikert 和Rosen[101]基于LWE 困難問題構(gòu)造的偽隨機函數(shù)(即BPR-PRF) 也是一種qPRF. 與前兩種不同, 后者是一種直接構(gòu)造且其安全性基于標(biāo)準(zhǔn)的困難性假設(shè). Mennink 和Szepieniec[102]提出一種XOR 設(shè)計方法:F(k1,k2,··· ,kr,x)=⊕Eki(x), 當(dāng)E是Q1 模型下的偽隨機置換(sPRP) 時,F就是Q1 模型下的偽隨機函數(shù)(sPRF). 他們并沒有考慮XOR 設(shè)計在Q2 模型下的安全性. Dottling 等[103]研究在Q2 模型下采用新的XOR 方式來設(shè)計qPRF: 給定一個小定義域(多項式規(guī)模) 上的PRF, 如果它滿足Q1 模型下的偽隨機性, 則根據(jù)他們的XOR 構(gòu)造方法,可獲得一個大定義域(指數(shù)規(guī)模) 上的qPRF. 由于Czajkowski 等[3]在Q2 模型下證明了Sponge 結(jié)構(gòu)(使用帶密鑰的內(nèi)部函數(shù)時) 的量子偽隨機性, 理論上采用Sponge 結(jié)構(gòu)也可構(gòu)造qPRF, 例如后面將會介紹的對CBC-MAC 的“類Sponge” 改造也可視為一種qPRF 設(shè)計.

在量子偽隨機置換設(shè)計方面, Zhandry[104]最早于2016 年提出了基于qPRF 構(gòu)造qPRP 的設(shè)計框架,即函數(shù)-置換轉(zhuǎn)換器(FPC):給定一個qPRF,就可用FPC 產(chǎn)生一個qPRP,未直接設(shè)計qPRP.雖然他提到了基于Feistel 結(jié)構(gòu)來作為FPC 的想法, 但是缺乏量子證明工具而未能證明. 直到2018 年Zhandry提出壓縮預(yù)言機技術(shù)(后正式發(fā)表于文獻[20]) 之后, Hosoyamada 和Iwata[4]于2019 年利用該技術(shù)證明了4 輪Feistel 結(jié)構(gòu)與隨機置換是Q2 模型下量子不可區(qū)分的. 根據(jù)該結(jié)論, 4 輪Feistel 結(jié)構(gòu)可作為由qPRF 向qPRP 轉(zhuǎn)換的FPC.

在量子安全的MAC 設(shè)計方面, 目前研究人員尚未開展全新設(shè)計, 而是對不安全的舊MAC 方案進行改造設(shè)計, 從而獲得量子安全的MAC. 在改造時需要考慮量子攻擊的特點給出有針對性的防護設(shè)計.Boneh 和Zhandry[7]在Q2 模型下給出了Carter-Wegman MAC 的量子多項式時間攻擊技術(shù), 同時提出一條安全改造措施: 將原設(shè)計中的變換CWMAC(key,m) = (nonce,PRF(key,nonce)+H(m)) 改造成CWMAC(key,m) = (R(m),PRF(key,R(m))+H(m)), 其中H和R分別是從XOR-通用哈希函數(shù)族H和兩兩獨立無關(guān)函數(shù)集合R中隨機選取的. 其改造思路是將nonce 替換成一個與消息m相關(guān)的隨機值,經(jīng)過改造之后, 在量子疊加態(tài)查詢時不同疊加分量之間就采用了獨立無關(guān)的隨機數(shù)R(m), 從而可有效預(yù)防Q2 模型下的量子偽造攻擊. 他們嚴(yán)格證明了該改進版是EUF-qCMA 的[7]. 對于CBC-MAC 認(rèn)證模式, 雖然它在Q2 模型下存在量子多項式時間偽造攻擊[2], 但是可依據(jù)Sponge 結(jié)構(gòu)的量子偽隨機性[3],按以下“類Sponge” 的方式來安全改造CBC-MAC: (1) 將CBC-MAC 的輸入消息分成r比特消息塊mi ∈{0,1}r,i=1,2,··· ,N; (2) 每個消息塊填充0c, 即mi →mi ‖0c, 以r+c比特塊作為CBC-MAC的輸入分組; (3) 將CBC-MAC 的輸出截斷為前r個比特. 經(jīng)過這種填充和截斷改造后的CBC-MAC 類似于Sponge 結(jié)構(gòu), 正好等價于Sponge 結(jié)構(gòu)使用帶密鑰的內(nèi)部置換的情形, 從而達到Q2 模型下的量子偽隨機性. 因此改造后的方案是EUF-qCMA 的.

其它方面還有對可調(diào)分組密碼結(jié)構(gòu)和認(rèn)證加密模式的安全改造設(shè)計. Hosoyamada 和Iwata[105]改造了可調(diào)分組密碼結(jié)構(gòu) LRW, 改造后的版本記為 LRWQ, 簡單描述為:(m) =Ek3(Ek1(m)⊕Ek2(tweak)), 他們在Q2 模型下利用壓縮預(yù)言機技術(shù)證明結(jié)論: 若E是qPRP, 則LRWQ是可調(diào)的qPRP. Bhaumik 等[106]對認(rèn)證加密模式OCB 進行改造, 設(shè)計了新的認(rèn)證加密模式QCB, 并證明了該模式在Q2 模型下的量子可證明安全性.

為了應(yīng)對基于Simon 量子算法的攻擊技術(shù), Alagic 和Russell[107]從底層運算改造的思路出發(fā), 提出將分組密碼結(jié)構(gòu)或模式中普遍使用的XOR 運算替換成“模2n加” 運算, 從而抵抗基于Simon 算法的量子攻擊, 但隨后被Bonnetain 和Naya-Plasenci[26]指出這種改造未必有效, 因為它們還有可能受到改進的Kuperberg 算法的亞指數(shù)時間攻擊, 例如Poly1305 認(rèn)證模式在這種攻擊下的量子安全強度可降低至231.

目前的抗量子設(shè)計研究主要關(guān)注密碼結(jié)構(gòu)或工作模式在量子安全模型下的整體安全設(shè)計, 然而在實例化的抗量子設(shè)計方面仍然缺乏研究. 如何進行實例化的密碼算法設(shè)計以獲得相對更高的量子安全強度？這是當(dāng)前研究中的一個難點. 從對稱密碼算法設(shè)計角度來看, 抗量子設(shè)計與傳統(tǒng)設(shè)計相比并沒有本質(zhì)區(qū)別,兩者都要通過設(shè)計迭代結(jié)構(gòu)和輪函數(shù)以及算法參數(shù)等來完成算法設(shè)計, 然而所設(shè)計對稱密碼算法能否抗量子計算攻擊, 仍然需要通過量子安全性分析. 因此, 抗量子設(shè)計深度依賴于量子安全性分析成果, 通過開展量子安全性分析研究, 積累量子攻擊技術(shù)和量子證明成果, 同時提煉抗量子設(shè)計準(zhǔn)則, 保證算法設(shè)計中所用密碼結(jié)構(gòu)和密碼部件都具有相對更高的量子攻擊復(fù)雜度.

8 總結(jié)與展望

從目前的研究來看, 在量子計算攻擊背景下, 對稱密碼設(shè)計技術(shù)所受影響相對較小, 原有的很多結(jié)構(gòu)或模式被證明滿足量子可證明安全性, 具體密碼算法如AES 的安全強度雖然受到削弱, 但可通過增大算法參數(shù)來彌補. 但這并不意味著不必繼續(xù)研究抗量子對稱密碼. 從密碼學(xué)的發(fā)展歷史來看, 密碼設(shè)計與分析技術(shù)始終隨著計算技術(shù)的進步而不斷發(fā)展, 而量子計算是一種高效的物理可實現(xiàn)的全新計算技術(shù), 因此量子計算融入密碼學(xué)研究必然成為未來的發(fā)展趨勢.

在抗量子對稱密碼研究中, 在量子計算攻擊技術(shù)、量子安全性證明、量子安全強度量化評估、抗量子對稱密碼設(shè)計等方面亟需進一步加強研究, 具體可從以下幾個角度進行探索.

(1) 面向密碼分析研究領(lǐng)域的量子算法探索. 量子計算為數(shù)學(xué)問題求解提供了一些強大的算法, 但是目前尚未充分挖掘這些量子算法在密碼分析中的潛力. 密碼學(xué)者可將Grover 搜索算法、Simon 量子算法、Kuperberg 算法、HHL 算法等量子算法應(yīng)用于更多密碼算法的量子安全性分析; 還要繼續(xù)發(fā)掘現(xiàn)有的其它量子算法, 研究能否應(yīng)用于密碼算法分析, 從而提供更多的量子安全性分析工具; 針對具體密碼學(xué)相關(guān)數(shù)學(xué)問題設(shè)計新的量子算法, 應(yīng)用于特定的對稱密碼方案的量子安全性分析.

(2) 抗量子計算安全強度及資源消耗量化評估. 目前的量子安全強度量化評估大多還停留在研究基于Grover 窮舉搜索和量子碰撞查找等通用量子攻擊下的安全強度量化評估, 而很少考慮專用的量子攻擊技術(shù), 因此不能全面地反映對稱密碼算法的量子安全強度. 此外, 還有必要結(jié)合量子計算機物理架構(gòu)和發(fā)展程度, 綜合選取適當(dāng)?shù)脑u價指標(biāo)作為量子安全及資源量化評估標(biāo)準(zhǔn), 從而優(yōu)化對密碼算法抗量子計算攻擊的分析.

(3) 抗量子計算密碼結(jié)構(gòu)的可證明安全分析. 對稱密碼的量子安全性證明比經(jīng)典模型下要復(fù)雜得多,遇到的困難也非常多. 由于密碼結(jié)構(gòu)的量子安全性證明過程通常都過于繁瑣, 一方面需要開展量子證明工具研究從而簡化證明; 另一方面還要開展計算機輔助證明技術(shù)研究, 特別是形式化證明技術(shù). 此外, 還有一個重要的方向是開展具有一定普適性的抗量子安全機理研究, 建立從Q1 模型向Q2 模型的安全性提升變換框架, 在該框架下可將Q1 模型下的量子安全性證明提升到Q2 模型.

(4) 抗量子對稱密碼設(shè)計. 目前的研究成果集中于抗量子分析方面, 而抗量子對稱密碼設(shè)計相對較少.可以深入分析這些量子攻擊和量子證明的共性機理, 歸納總結(jié)量子安全設(shè)計規(guī)范, 在此基礎(chǔ)上改造舊方案獲得量子安全的新設(shè)計. 此外, 在設(shè)計具體的密碼算法實例時, 一般認(rèn)為應(yīng)該將密鑰長度增加大約一倍以抵抗量子計算攻擊. 然而密鑰長度的增加將大大提高密碼算法的設(shè)計難度和實現(xiàn)開銷. 是否存在其它途徑, 將密鑰長度少量增加甚至不增加, 仍然能夠達到預(yù)期的量子安全強度.

(5) 真實量子環(huán)境下的對稱密碼算法安全性. 還有一類非常重要但長期被忽視的問題: 密碼算法在未來的真實量子計算機下的安全性. 對密碼算法的量子攻擊最終是要在真實的量子計算機上實施的, 然而目前的主流研究都在理想化的量子計算模型(即純數(shù)學(xué)描述的量子計算框架) 下評估密碼算法的量子安全強度. 在現(xiàn)實情況下, 量子比特都是一個個微觀的量子物理系統(tǒng), 利用它們執(zhí)行計算時, 操控這些量子比特或者相互之間傳遞狀態(tài)信息都將受到物理定律的限制, 那么現(xiàn)實的量子計算模型下密碼算法的量子安全強度如何去評估？物理定律是否會限制量子計算的邏輯門深度或者量子比特數(shù)量的理論極限？楊理等[108,109]初步探索了離子阱量子計算機在物理定律限制下所容許的邏輯門深度, 然而解決上述這些難題還需要更多的努力. 此外, 對于n比特密鑰的對稱加密算法, 經(jīng)典窮舉攻擊需要O(2n) 次經(jīng)典計算, 而量子窮舉攻擊需要O(2n/2) 次量子計算; 那么考慮真實的量子計算時,O(2n/2) 次量子計算從物理實現(xiàn)角度是否具有現(xiàn)實可行性？即使可行, 那么實際的時間復(fù)雜度與O(2n) 次經(jīng)典計算相比還有多少優(yōu)勢？目前這些問題仍然有待探索.