抗量子計算對稱密碼研究進展概述*

梁 敏, 羅宜元, 劉鳳梅

1. 數據通信科學技術研究所, 北京 100191

2. 惠州學院計算機科學與工程學院, 惠州 516007

3. 河南省網絡密碼技術重點實驗室, 鄭州 450001

4. 電子科技大學網絡與數據安全四川省重點實驗室, 成都 610054

1 引言

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

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

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

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

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

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

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

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

2 量子算法

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

2.1 Grover 算法及其推廣

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

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

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

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

2.2 Simon 量子算法

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

然后采用量子計算對該量子態的每個疊加分量實現如下計算

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

2.3 組合量子算法

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

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

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

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

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

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

3 量子安全模型

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

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

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

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

3.1 加密的安全模型

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

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

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

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

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

算法1 經典不可區分實驗PrivKINDA,Π(n)Input: 參數n Output: 區分成功, 輸出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 全量子不可區分實驗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: 參數n Output: 區分成功, 輸出1; 否則輸出0

算法3 弱量子不可區分實驗PrivKwqIND A,Π (n)算法4 量子不可區分實驗PrivKqIND A,Π (n)Input: 參數n Output: 區分成功, 輸出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: 參數n Output: 區分成功, 輸出1; 否則輸出0

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

3.2 認證的安全模型

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

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

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

圖2 認證安全模型之間的關系圖Figure 2 Relationships between security models for authentication

3.3 認證加密的安全模型

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

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

3.4 雜湊的安全模型

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

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

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

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

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

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

4 量子安全強度評估

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

4.1 經典分析技術的量子增強

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

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

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

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

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

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

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

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

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

4.2 量子攻擊資源評估與優化

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

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

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

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

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

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

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

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

5 對結構和工作模式的量子攻擊

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

5.1 Q2 模型下的攻擊

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

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

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

關于廣義Feistel 結構, Ito 和Iwata[67]針對Type-1 型廣義Feistel 結構設計了3d-3 輪qCPA 區分器(即qCPA 模型下的多項式級量子區分器) 和d2-d+1 輪qCCA 區分器(即qCCA 模型下的多項式級量子區分器), 其中d為廣義Feistel 結構的分支數.

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

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

表1 Q2 模型下分組密碼迭代結構的量子區分器設計進展情況Table 1 Research progress about quantum distinguisher of iterated cryptographic construction under Q2 model

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

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

除了對分組密碼結構的量子攻擊以外, 在Q2 模型下還可對許多認證和認證加密方案進行高效的量子攻擊.

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

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

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

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

Poly1305 是由Bernstein 設計的一個MAC, 已經標準化用于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]的量子攻擊技術: 根據Poly1305 來設計兩個函數f和g, 這兩個函數都可基于對Poly1305 的量子選擇消息查詢來實現, 而且兩者存在隱藏移位r使得f(x) =g(x+r); 然后對Kuperberg 算法進行改進并用于尋找這個隱藏移位. Poly1305 的密鑰r和k都是128 比特, nonce 和輸出的tag 也是128 比特. 改進的Kuperberg 算法仍然是一個亞指數時間的量子算法, 雖然它無法達到Simon 算法那樣高效的攻擊, 但是對Poly1305 的量子攻擊復雜度為238, 在此基礎上應用Grover 加速,還可將攻擊復雜度進一步降至231. 因此, Poly1305 的安全強度無法達到Q2 模型下的安全性[26].

認證加密工作模式GCM 和OCB 等都通過嵌入一個MAC 模式來產生關聯數據的認證部分,Kaplan等[2]將上述對認證模式的量子攻擊推廣到這些帶關聯數據的認證加密模式. GCM 和OCB 都是基于nonce 的認證加密模式, 并且對關聯數據的認證都與nonce 無關. 對于這兩種模式, 當明文中只有關聯數據(消息是空值) 時, GCM 正好就等同于GMAC, OCB 正好就等同于PMAC, 因此, 對GMAC 的攻擊可直接應用于GCM, 對PMAC 的攻擊可直接應用于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 模型下對分組密碼結構的量子攻擊研究. 接下來介紹Q1 模型下的量子攻擊研究進展. 與Q2 模型相比, Q1 模型下的量子攻擊研究相對較少, 且部分結果是由Q2 模型下的攻擊轉換而來.

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

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

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

6 結構和工作模式的量子可證明安全性

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

6.1 量子證明工具

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

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

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

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

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

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

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

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

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

現有的一些結構和工作模式被證明滿足量子安全性, 即, 在量子安全模型下證明: 當底層函數滿足偽隨機性, 整體結構和工作模式也能達到偽隨機性. 在具體介紹量子可證明研究結果之前, 我們約定將Q2模型下的偽隨機函數和偽隨機置換分別記為qPRF 和qPRP, Q1 模型下的偽隨機函數和偽隨機置換分別記為sPRF 和sPRP.

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

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

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

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

6.3 雜湊的量子可證明安全

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

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

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

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

上述量子可證明安全研究主要關注Collapsing 和量子不可區別性等. 量子抗碰撞性和量子抗原像性等都是在量子模型下對傳統雜湊安全屬性的增強, 我們還應該研究雜湊結構是否滿足這些量子安全屬性.Hamlin 和Song[37]證明了由Andreeva 等提出的雜湊結構ROX[96]的量子安全性: 當底層壓縮函數f滿足量子抗碰撞性/量子抗原像性/量子抗第二原像性時, ROXf也滿足相應的量子安全屬性. Hosoyamada和Yasuda[97]證明了基于Davies-Meyer 壓縮函數的Merkle-Damgard 迭代構造滿足量子抗原像性, 這意味著該構造是一個量子可證明安全的單向函數.

7 抗量子計算對稱密碼設計

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

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

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

在量子安全的MAC 設計方面, 目前研究人員尚未開展全新設計, 而是對不安全的舊MAC 方案進行改造設計, 從而獲得量子安全的MAC. 在改造時需要考慮量子攻擊的特點給出有針對性的防護設計.Boneh 和Zhandry[7]在Q2 模型下給出了Carter-Wegman MAC 的量子多項式時間攻擊技術, 同時提出一條安全改造措施: 將原設計中的變換CWMAC(key,m) = (nonce,PRF(key,nonce)+H(m)) 改造成CWMAC(key,m) = (R(m),PRF(key,R(m))+H(m)), 其中H和R分別是從XOR-通用哈希函數族H和兩兩獨立無關函數集合R中隨機選取的. 其改造思路是將nonce 替換成一個與消息m相關的隨機值,經過改造之后, 在量子疊加態查詢時不同疊加分量之間就采用了獨立無關的隨機數R(m), 從而可有效預防Q2 模型下的量子偽造攻擊. 他們嚴格證明了該改進版是EUF-qCMA 的[7]. 對于CBC-MAC 認證模式, 雖然它在Q2 模型下存在量子多項式時間偽造攻擊[2], 但是可依據Sponge 結構的量子偽隨機性[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個比特. 經過這種填充和截斷改造后的CBC-MAC 類似于Sponge 結構, 正好等價于Sponge 結構使用帶密鑰的內部置換的情形, 從而達到Q2 模型下的量子偽隨機性. 因此改造后的方案是EUF-qCMA 的.

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

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

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

8 總結與展望

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

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

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

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

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

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

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