吳文玲, 王博琳

1.中國(guó)科學(xué)院 軟件研究所, 北京 100190

2.中國(guó)科學(xué)院大學(xué), 北京 100049

1 引言

數(shù)據(jù)安全與人們的生產(chǎn)生活已密不可分, 從飛機(jī)、汽車的設(shè)計(jì)制造, 到個(gè)人生活點(diǎn)滴的記錄, 數(shù)據(jù)已滲透到人類社會(huì)的各個(gè)方面.大數(shù)據(jù)時(shí)代的數(shù)據(jù)安全不僅包括傳統(tǒng)的機(jī)密性、完整性、可用性等, 也包括隱私保護(hù); 不僅包括防止數(shù)據(jù)泄露的隱私保護(hù), 也包括數(shù)據(jù)分析意義下的隱私保護(hù).數(shù)據(jù)安全問題的解決需要有可信賴的技術(shù)手段支持, 近年來, 涌現(xiàn)出一大批數(shù)據(jù)安全新技術(shù), 包括具體高效的安全多方計(jì)算技術(shù)、同態(tài)加密、函數(shù)加密、差分隱私保護(hù)技術(shù)、可驗(yàn)證計(jì)算技術(shù)、零信任技術(shù)等.

安全多方計(jì)算(secure multi-party computation, MPC) 由姚期智先生于1982 年通過提出并解答百萬富翁問題而創(chuàng)立, 能夠在不泄露任何隱私數(shù)據(jù)的情況下讓多方數(shù)據(jù)共同參與計(jì)算, 然后獲得準(zhǔn)確的結(jié)果,可以使多個(gè)非互信主體在數(shù)據(jù)相互保密的前提下進(jìn)行高效數(shù)據(jù)融合計(jì)算, 達(dá)到數(shù)據(jù)可用不可見.基于秘密分享的MPC 協(xié)議的參與方可以利用本地?fù)碛械姆蓊~進(jìn)行加法、數(shù)乘的計(jì)算, 不需要與其他參與方進(jìn)行交互和通信, 協(xié)議通信主要發(fā)生在乘法門計(jì)算, 所有運(yùn)算定義在有限域上, 也可推廣至一般環(huán)上.為了讓數(shù)據(jù)安全地進(jìn)出基于秘密分享的MPC 協(xié)議, 一種有效的解決方案是直接使用系統(tǒng)內(nèi)的對(duì)稱密碼算法進(jìn)行計(jì)算.然而, 基于AES 或SHA-3 的偽隨機(jī)函數(shù)(PRF) 在此應(yīng)用場(chǎng)景的性能不好.主要問題是數(shù)據(jù)類型不匹配, MPC 的數(shù)據(jù)通常表示為有限域Fp上的元素, 而AES 和SHA-3 的數(shù)據(jù)都表示為比特串; 雖然兩者可以轉(zhuǎn)換, 但代價(jià)昂貴; 當(dāng)?shù)讓右鎴?zhí)行算術(shù)模運(yùn)算時(shí), 數(shù)據(jù)格式轉(zhuǎn)換將極大影響MPC 的實(shí)現(xiàn)性能.因此, MPC 需要基于算術(shù)運(yùn)算的對(duì)稱密碼算法.在MPC 中使用現(xiàn)有對(duì)稱密碼算法標(biāo)準(zhǔn), 其實(shí)現(xiàn)性能和通用實(shí)現(xiàn)性能差距很大.比如, 在X86 等處理器上, AES 可以在100 個(gè)時(shí)鐘周期內(nèi)完成一次分組加密, 而在MPC 中實(shí)現(xiàn)相同的密碼運(yùn)算需要數(shù)十億個(gè)時(shí)鐘周期.主要原因在于, 在X86 等處理器上實(shí)現(xiàn)線性運(yùn)算(XOR) 和非線性運(yùn)算(AND) 的成本差別不大, 而MPC 的情況完全不同.線性運(yùn)算幾乎是免費(fèi)的, 只進(jìn)行本地計(jì)算, 不會(huì)增加太多噪聲, 而涉及對(duì)稱密碼算法和各方交互的非線性運(yùn)算會(huì)顯著增加噪聲.因此,面向安全多方計(jì)算設(shè)計(jì)對(duì)稱密碼算法時(shí), 希望算法中的非線性運(yùn)算個(gè)數(shù)盡可能少.分組密碼LowMC 是第一個(gè)適宜MPC 的對(duì)稱密碼算法.2020 年, Rechberger 等人發(fā)起了LowMC 分析挑戰(zhàn)賽, 吸引了許多密碼學(xué)者的研究興趣.隨著MPC 的發(fā)展及其應(yīng)用需求的推動(dòng), 一些適宜MPC 的新形態(tài)對(duì)稱密碼算法應(yīng)運(yùn)而生, 如MiMC 及其變體、Ciminion 和HYDRA 等.

同態(tài)加密(homomorphic encryption, HE) 方案指能夠?qū)用軘?shù)據(jù)進(jìn)行加法或乘法操作而不需要解密密鑰的加密方案.全同態(tài)加密(fully homomorphic encryption, FHE) 是指同時(shí)滿足加法同態(tài)和乘法同態(tài)性質(zhì), 可以進(jìn)行任意多次加法和乘法運(yùn)算的加密函數(shù).2009 年, Gentry 基于理想格上的困難問題構(gòu)造了第一個(gè)可行的全同態(tài)加密方案, 隨后發(fā)展出了基于不同安全假設(shè)的全同態(tài)加密方案, 比如BGV、BFV 和GSW 方案.盡管在效率方面已有較大提升, 但仍未脫離Gentry 所提出的構(gòu)造全同態(tài)加密方案的理論框架, 首先構(gòu)造一個(gè)部分同態(tài)加密方案, 之后再通過自舉來實(shí)現(xiàn)全同態(tài)加密.考慮到部分同態(tài)加密方案的安全性, 加密過程需要引入噪聲; 隨著同態(tài)運(yùn)算的進(jìn)行, 噪聲不斷地累積, 一旦噪音的尺寸超出某個(gè)閾值, 就會(huì)出現(xiàn)解密錯(cuò)誤.通常, 乘法運(yùn)算引起的噪聲大于加法的噪聲.因此, 大多數(shù)情況下全同態(tài)加密方案參數(shù)化時(shí), 需要評(píng)估所要考慮的布爾電路的乘法深度.乘法深度指的是可以在密文上執(zhí)行的連續(xù)同態(tài)乘法的最大數(shù)量, 許多全同態(tài)加密方案的噪聲隨著電路的乘法深度而快速增長(zhǎng).因此, 面向全同態(tài)加密的對(duì)稱密碼算法, 設(shè)計(jì)目標(biāo)首先是最小化乘法深度.其次, 雖然某些特定應(yīng)用程序的同態(tài)操作的成本取決于密碼的乘法深度, 但計(jì)算額外解密電路本身的代價(jià)主要取決于乘法數(shù)量.因此, 盡量減少乘法門的數(shù)量也是適宜全同態(tài)加密的對(duì)稱密碼算法的設(shè)計(jì)指標(biāo).除了噪聲問題, 全同態(tài)加密方案還存在密文擴(kuò)展問題, 嚴(yán)重影響其在帶寬、存儲(chǔ)和計(jì)算能力有限的場(chǎng)景落地應(yīng)用.許多云服務(wù)應(yīng)用框架組合使用對(duì)稱加密算法和非對(duì)稱同態(tài)加密方案, 以AES 作為對(duì)稱密碼的實(shí)例算法, AES 解密計(jì)算的乘法深度成為一個(gè)瓶頸, 因此, 亟需面向全同態(tài)加密的對(duì)稱密碼算法.近幾年推出的對(duì)稱密碼算法有: Kreyvium、FLIP、Rasta 及其變體、Pasta、Chaghri 和Rubato 等.

零知識(shí)證明(zero-knowledge proof, ZK) 是由Goldwasser 等人在20 世紀(jì)80 年代初提出的, 指的是證明者能夠在不向驗(yàn)證者提供任何有用信息的情況下, 使驗(yàn)證者相信某個(gè)論斷是正確的.零知識(shí)證明不僅作為一個(gè)基本工具為實(shí)現(xiàn)各種密碼協(xié)議分析與構(gòu)造提供強(qiáng)有力的支持, 而且其證明方法也成為一種方法論被廣泛使用.在零知識(shí)證明系統(tǒng)中, 需要將計(jì)算問題編碼為有限域上的代數(shù)約束滿足問題, 這一過程稱為算術(shù)化(arithmetization), 目前常用的算術(shù)化方法是R1CS、Plonk 和AIR 等三類.近些年使用廣泛的證明系統(tǒng)分為ZK-SNARKs 和ZK-STARKs 兩種, 它們采用不同的算術(shù)化方法進(jìn)行描述, ZK-SNARKs基于R1CS 和Plonk 兩類算術(shù)化方法, 而ZK-STARKs 基于AIR 方法, 因此證明大小和生成時(shí)間的計(jì)算方式均不同.在ZK-SNARKs 中, 證明代價(jià)與執(zhí)行的非線性操作的數(shù)量成正比; 而在ZK-STARKs 中,證明代價(jià)與必須驗(yàn)證的電路的次數(shù)和深度有關(guān).因此, 零知識(shí)證明系統(tǒng)通常需要選取針對(duì)乘法數(shù)量和乘法深度可以優(yōu)化實(shí)現(xiàn)的對(duì)稱密碼算法, 具體的優(yōu)化目標(biāo)取決于應(yīng)用場(chǎng)景的需求.此外, 在許多此類應(yīng)用中, 需要使用定義在奇特征有限域上的雜湊函數(shù), 特別是素域上的雜湊函數(shù).例如, 部署在Zcash 的零知識(shí)證明系統(tǒng).近些年陸續(xù)推出了一系列與相關(guān)應(yīng)用環(huán)境相匹配的新形態(tài)對(duì)稱密碼算法, 例如Jarvis、Friday、Vision、Rescue、POSEIDON、STARKAD 以及Reinforced Concrete.對(duì)以上算法的研究也在如火如荼地進(jìn)行著, 如2020 年發(fā)起的“STARK-Friendly Hash Challenge” 挑戰(zhàn)和2021 年以太坊基金設(shè)立的包括POSEIDON 在內(nèi)的幾種適宜零知識(shí)證明的對(duì)稱密碼算法挑戰(zhàn)賽.

綜上可知, 安全多方計(jì)算、全同態(tài)加密和零知識(shí)證明為對(duì)稱密碼算法提出了一些新的性能指標(biāo), 而AES 等現(xiàn)有標(biāo)準(zhǔn)算法不能滿足這些需求.因此, 近些年國(guó)際上推出了一批與相關(guān)應(yīng)用相匹配的新形態(tài)對(duì)稱密碼算法.不同于現(xiàn)有的對(duì)稱密碼算法標(biāo)準(zhǔn), 此類算法更強(qiáng)調(diào)算術(shù)運(yùn)算, 如環(huán)上的運(yùn)算、有限域Fp及F2n上的運(yùn)算等, 且在利用該類算法時(shí), 均需將其轉(zhuǎn)換為代數(shù)問題, 并經(jīng)歷一個(gè)算術(shù)化的過程, 這個(gè)過程在本質(zhì)上是相似的, 因此統(tǒng)稱它們?yōu)槊嫦蛩阈g(shù)化的對(duì)稱密碼算法.新形態(tài)對(duì)稱密碼算法通常關(guān)注以下三個(gè)性能指標(biāo).一是乘法復(fù)雜度(MC), 一般指電路中的乘法數(shù)量(AND 門數(shù)量); 二是每個(gè)加密比特的AND 門數(shù)量(MC/bit); 三是電路的乘法深度(ANDdepth).除了以上性能指標(biāo), 設(shè)計(jì)算法時(shí)還需要綜合考慮特殊結(jié)構(gòu)及狀態(tài)大小等因素的影響.本文根據(jù)應(yīng)用場(chǎng)景對(duì)新形態(tài)對(duì)稱密碼算法分類介紹, 但一些算法在設(shè)計(jì)時(shí)關(guān)注了多個(gè)性能指標(biāo), 因而同時(shí)適用于多種應(yīng)用場(chǎng)景, 如LowMC 同時(shí)適用于MPC 和FHE, MiMC 同時(shí)適宜MPC 和ZK.表1 總結(jié)了不同類型新形態(tài)對(duì)稱密碼算法的運(yùn)算所在有限域及適宜的應(yīng)用場(chǎng)景.

表1 新形態(tài)對(duì)稱密碼算法Table 1 New morphologic symmetric cryptographic algorithms

本文的組織結(jié)構(gòu)安排如下: 第2 節(jié)、第3 節(jié)和第4 節(jié)分別介紹了適宜MPC、FHE 及ZK 的新形態(tài)對(duì)稱密碼算法, 第5 節(jié)總結(jié)新形態(tài)對(duì)稱密碼算法的特點(diǎn)以及面臨的問題.

2 適宜MPC 的對(duì)稱密碼算法

2.1 LowMC

2015 年, Albrecht 等提出了P-SPN 結(jié)構(gòu)的分組密碼LowMC[1].P-SPN 結(jié)構(gòu)又稱為部分SPN 結(jié)構(gòu), 該結(jié)構(gòu)在算法每一輪的非線性層中只有一部分使用非線性S 盒的變換, 其余部分均為恒等變換.作為第一個(gè)新形態(tài)對(duì)稱密碼, LowMC 吸引了密碼學(xué)界的大量關(guān)注.LowMC 的輪函數(shù)包括四個(gè)操作: S 盒層、線性層、輪常量異或及輪密鑰異或.S 盒層采用3 比特S 盒, 線性層使用基于比特操作的n×n的二進(jìn)制矩陣.它的特點(diǎn)是用戶可以根據(jù)需求自主選擇參數(shù)(每輪S 盒數(shù)量、線性層、輪常量、密鑰編排函數(shù)) 來進(jìn)行實(shí)例化.LowMC 設(shè)計(jì)的亮點(diǎn)在于S 盒層減少了并行S 盒的數(shù)量, 即采用部分S 盒的設(shè)計(jì)來降低乘法復(fù)雜度, 為了在低乘法復(fù)雜度的情況下滿足安全性要求, 在線性層中使用偽隨機(jī)生成的二進(jìn)制可逆矩陣.除此之外, 輪常量及輪密鑰也是隨機(jī)生成的.Albrecht 提出了兩個(gè)具體實(shí)例.第一組采用80 比特密鑰提供“類似于PRESENT” 的安全性, 而第二組采用128 比特密鑰提供“類似于AES” 的安全性.在MPC和FHE 的實(shí)現(xiàn)方面, 當(dāng)加密大量數(shù)據(jù)時(shí), LowMC 在計(jì)算和通信復(fù)雜度方面均有不同程度的改進(jìn).在乘法復(fù)雜度和乘法深度方面, 最接近的競(jìng)爭(zhēng)對(duì)手分別是Simon 和PRINCE.

LowMC 自提出后不久, 就出現(xiàn)了對(duì)其的高階差分攻擊[27]和插值攻擊[28], 這兩種攻擊均需要很多選擇明文.為了抵抗這些攻擊, 設(shè)計(jì)者推出了LowMC v2 版本, 即使用新的公式來確定安全輪數(shù).2018 年,Rechberger 等人[29]提出了利用差分枚舉中間相遇攻擊分析LowMC v2 的多個(gè)實(shí)例, 導(dǎo)致了LowMC v3版本的出現(xiàn).2021 年, Liu 等人[30]結(jié)合差分枚舉技術(shù)和代數(shù)攻擊, 僅用2 個(gè)選擇明文和可忽略的內(nèi)存復(fù)雜度就可以對(duì)LowMC v3 的一些實(shí)例進(jìn)行分析.此外, 選擇2 個(gè)明文對(duì)LowMC 的攻擊可以擴(kuò)展到對(duì)LowMC-M 使用大量選擇明文進(jìn)行攻擊, 這些分析使得LowMC-M[31]的設(shè)計(jì)者增加了輪數(shù).之后, Liu等人進(jìn)一步改進(jìn)對(duì)LowMC 的差分枚舉攻擊, 提出了代數(shù)中間相遇攻擊[32].Rechberger 等人[29]的差分枚舉中間相遇攻擊的存儲(chǔ)復(fù)雜度是攻擊輪數(shù)的指數(shù), 雖然代數(shù)攻擊[30]可以使存儲(chǔ)復(fù)雜度忽略不計(jì), 但攻擊輪數(shù)有限.代數(shù)中間相遇攻擊不僅可以降低差分枚舉中間相遇攻擊[29]的存儲(chǔ)復(fù)雜度, 與代數(shù)攻擊[30]相比, 還可以通過使用額外的內(nèi)存來提高攻擊輪數(shù), 并且適用于各種LowMC 參數(shù)的實(shí)例.2023 年, Qiao等人[33]針對(duì)完整S 盒層的LowMC 實(shí)例, 提出了一種新的差分枚舉攻擊框架, 該方法不再考慮傳統(tǒng)的差分, 轉(zhuǎn)而考慮2-差分.利用代數(shù)方法枚舉2-差分, 并用線性化技術(shù)從恢復(fù)的2-差分跡中恢復(fù)密鑰.將攻擊應(yīng)用于分組大小分別為129、192 和255 比特的4 輪LowMC, 攻擊的數(shù)據(jù)復(fù)雜度均為3 個(gè)選擇明文.與Liu 等人的攻擊[30]相比, 在時(shí)間復(fù)雜度或成功概率方面有所改進(jìn).

LowMC 系列分組密碼的主要應(yīng)用之一是用于后量子簽名方案PICNIC 中.PICNIC 在實(shí)例化時(shí)需要一個(gè)具有較低計(jì)算開銷的函數(shù), 這種開銷在很大程度上取決于計(jì)算函數(shù)所需的非線性運(yùn)算的數(shù)量, 即乘法數(shù)量.LowMC 是一種專門針對(duì)FHE 和MPC 設(shè)計(jì)的高效分組密碼, 旨在最大限度地減少乘法數(shù)量,這使得LowMC 成為PICNIC 實(shí)例化的十分合適的選擇.令E(K,pt) 為使用密鑰K對(duì)明文pt 進(jìn)行的LowMC 加密.明文/密文對(duì)(pt,ct =E(K,pt)) 用作簽名方案的公鑰(驗(yàn)證密鑰), 加密密鑰K用作秘密密鑰(簽名密鑰).如果攻擊者可以在僅給定單個(gè)明文/密文對(duì)(pt,ct), 即簽名方案的公鑰的情況下恢復(fù)加密密鑰, 則實(shí)際上他可以計(jì)算出秘密簽名密鑰, 進(jìn)而允許他通過使用恢復(fù)的簽名密鑰來偽造簽名.因此, 在單個(gè)明文/密文對(duì)背景下對(duì)LowMC 分組密碼的密鑰恢復(fù)攻擊會(huì)直接影響PICNIC 簽名方案的安全性.2020 年5 月, 在微軟等公司的資金支持下, 知名學(xué)者Rechberger 等人發(fā)起了LowMC 算法分析挑戰(zhàn)賽[34], 尤其針對(duì)應(yīng)用于PICNIC 底層的LowMC 算法實(shí)例, 以此促進(jìn)LowMC 算法及PICNIC 方案的研究發(fā)展.有三個(gè)團(tuán)隊(duì)在這種攻擊場(chǎng)景中提出了針對(duì)LowMC 的新攻擊[35–38].根據(jù)第三輪結(jié)果的公布,中間相遇方法[36]和多項(xiàng)式方法[37]的攻擊被選為目前最好的攻擊, 但這兩種方法的一個(gè)共同特點(diǎn)是消耗大量?jī)?nèi)存.后來, Banik 等人[39]結(jié)合了文獻(xiàn)[36] 中的線性化技術(shù)和文獻(xiàn)[37] 中的方程求解方法, 分析了具有完整S 盒層的LowMC 實(shí)例, 大大降低了內(nèi)存復(fù)雜度.之后, Liu 等人[40]通過使用更好的時(shí)間存儲(chǔ)折中策略, 進(jìn)一步顯著改進(jìn)了PICNIC 背景下對(duì)LowMC 的攻擊.

2.2 MiMC 及其變體

(1) MiMC

2016 年, Albrecht 等給出了定義在有限域F2n或Fp上的以最小化乘法復(fù)雜度為目標(biāo)的對(duì)稱密碼系列MiMC[2].MiMC 包括: 分組密碼MiMC-n/n和MiMC-2n/n、雜湊函數(shù)MiMCHash.分組密碼MiMC-n/n直接通過函數(shù)F(x)=x3和輪子密鑰及輪常量實(shí)現(xiàn)加密.分組密碼MiMC-2n/n在Feistel 結(jié)構(gòu)中使用與MiMC-n/n相同的非線性置換F(x) =x3進(jìn)行加密, 記為Feistel-MiMC, 且輪數(shù)為MiMCn/n輪數(shù)的2 倍.雜湊函數(shù)MiMCHash 是在Sponge 結(jié)構(gòu)中實(shí)例化置換MiMC-n/n得到的.MiMC 作為適宜MPC 的PRF 是一個(gè)非常有競(jìng)爭(zhēng)力的候選者.與AES 相比, 測(cè)試結(jié)果表明, MiMC 在線階段的吞吐量高出10 倍以上, 在LAN 設(shè)置中的離線/預(yù)計(jì)算階段仍然快約6 倍.由于MiMC 的串行性質(zhì)和相對(duì)較高的輪數(shù), 延遲可能會(huì)相對(duì)較高, 但也優(yōu)于AES 的延遲.

(2) GMiMC

2019 年, Albrecht 進(jìn)一步推廣MiMC 中使用的設(shè)計(jì)方法, 他們使用兩個(gè)非平衡的Feistel 結(jié)構(gòu)和一個(gè)新的平衡Feistel 結(jié)構(gòu)來構(gòu)造一個(gè)新的分組密碼系列—GMiMC[3], 包括GMiMCcrf、GMiMCerf和GMiMCmrf, 并用它來在Sponge 結(jié)構(gòu)中構(gòu)造雜湊函數(shù)GMiMCHash.在MPC 中, GMiMC 的吞吐量與MiMC 相比提高了4 倍以上, 同時(shí)預(yù)處理工作減少了80% 以上, 盡管以更高的延遲為代價(jià).在SNARK應(yīng)用程序中, GMiMCerf在三種結(jié)構(gòu)中的性能最好.對(duì)于N ≈1024 比特分組大小的GMiMCerf, 當(dāng)t=8時(shí), 觀察到其比MiMC-1025 有所改進(jìn).對(duì)于單個(gè)消息分組, GMiMCHash-256 比MiMCHash-256 快1.2倍以上.與MiMCHash 相比, GMiMCerfHash 的主要優(yōu)勢(shì)是它可以使用超過256 位或更小的素域.在最近提出的基于ZK 的后量子密碼簽名方案領(lǐng)域, LowMC 被認(rèn)為是小簽名和運(yùn)行時(shí)間的最佳選擇.由于可以靈活選擇分支數(shù), GMiMC 與LowMC 相比具有一定的競(jìng)爭(zhēng)力, 并且比MiMC 效率高得多, 其簽名大小約為MiMC 的三十分之一.

(3) HADESMiMC

2020 年, Grassi 等提出了將經(jīng)典SPN 結(jié)構(gòu)與P-SPN 結(jié)構(gòu)相結(jié)合的HADES 結(jié)構(gòu)[4].該結(jié)構(gòu)將整體輪數(shù)分為三部分: 中間部分為P-SPN 結(jié)構(gòu), 兩邊為相同輪數(shù)的SPN 結(jié)構(gòu).一方面, 為了確保算法針對(duì)差分和線性密碼分析的安全性, 在開始和最后使用SPN 結(jié)構(gòu).另一方面, 為了盡可能減少非線性操作的總數(shù), 在中間部分使用P-SPN 結(jié)構(gòu)(通常情況下非線性層使用一個(gè)S 盒), 這樣不僅可以達(dá)到較高的代數(shù)次數(shù), 還可以盡可能地滿足低乘法復(fù)雜度的要求.最后, 通過選擇完整S 盒層和部分S 盒層的輪數(shù)之間的最佳比例, 可以同時(shí)實(shí)現(xiàn)安全性和性能要求.由以上方法得到的HADES 結(jié)構(gòu)不僅可以直接使用寬軌跡策略進(jìn)行分析, 還可以針對(duì)代數(shù)攻擊給出安全性聲明.

分組密碼HADESMiMC 是Grassi 等基于HADES 結(jié)構(gòu)給出的在素域Fp上設(shè)計(jì)的面向MPC 的一個(gè)實(shí)例.輪函數(shù)由三部分組成: S 盒層、線性層和輪密鑰加, 其中S 盒采用的是冪函數(shù)S-Box(x)=x3.線性層使用基于字操作的MDS 矩陣, 密鑰編排函數(shù)是線性的.在使用安全多方計(jì)算保護(hù)分布式數(shù)據(jù)庫的數(shù)據(jù)傳輸中, 與目前最快的MiMC 相比, HADESMiMC 的在線帶寬要求和吞吐量顯著提高, 并減少了預(yù)處理工作, 同時(shí)具有相當(dāng)?shù)脑诰€延遲.

2019 年, Li 和Preneel[41]提出了對(duì)MiMC 的插值攻擊, 這是對(duì)MiMC 的第一個(gè)第三方分析.與MiMC 設(shè)計(jì)文檔里給出的經(jīng)典插值攻擊相比, 攻擊只需要常數(shù)大小的存儲(chǔ)或數(shù)據(jù)復(fù)雜度.對(duì)于具有82 輪的MiMC-129/129, 可以破解38 輪, 數(shù)據(jù)和時(shí)間復(fù)雜度分別為265.5和260.2, 存儲(chǔ)復(fù)雜度可忽略.對(duì)于具有較大密鑰的MiMC 變體, 該攻擊的復(fù)雜度更低.除此之外, 作者還提出了對(duì)具有簡(jiǎn)單密鑰編排的分組密碼的通用插值攻擊.2020 年, Eichlseder 等人[42]給出了定義在F2n上的接近全輪MiMC 的高階差分區(qū)分器和接近MiMC 兩倍輪數(shù)的已知密鑰零和區(qū)分器, 以及F2n上全輪MiMC 的密鑰恢復(fù)攻擊和具有低次數(shù)輪函數(shù)的密鑰交替密碼的代數(shù)次數(shù)增長(zhǎng)的新上界.

2020 年, Roy 等人[43]將文獻(xiàn)[41] 的低內(nèi)存插值攻擊擴(kuò)展到具有低次數(shù)函數(shù)的非平衡Feistel 結(jié)構(gòu), 并將其應(yīng)用于GMiMC.之后他們給出了針對(duì)具有擴(kuò)展輪函數(shù)的GMiMC 的有效密鑰恢復(fù)技術(shù), 并表明最終的密鑰恢復(fù)步驟不僅可以簡(jiǎn)化為GCD 問題, 還可以簡(jiǎn)化為求根問題.Beyne 等人[44]給出了GMiMCerf和HADESMiMC 置換的低復(fù)雜度積分區(qū)分器和零和區(qū)分器.在ZK-STARKs 中時(shí), 針對(duì)實(shí)際使用的Sponge 結(jié)構(gòu)的具體設(shè)置, 給出了GMiMC 置換的縮減輪的實(shí)際碰撞攻擊.除此之外, 他們還將這幾種密碼技術(shù)推廣到了奇特征的有限域.2022 年, Beyne 等人[45]利用截?cái)嗖罘置艽a分析, 得到了對(duì)收縮型Feistel 結(jié)構(gòu)密碼的改進(jìn)通用攻擊.當(dāng)應(yīng)用于GMiMCcrf時(shí), 上述攻擊對(duì)于某些實(shí)例可以得到全輪區(qū)分器和密鑰恢復(fù)攻擊.然而, 這些攻擊的實(shí)際意義可能相對(duì)有限, 因?yàn)镚MiMCcrf的大多數(shù)應(yīng)用程序使用的分支數(shù)量t相對(duì)較小, 但選取的有限域很大.Cui 等人[46]將二元域上的可分性質(zhì)推廣到有限域F2n上, 給出了一種對(duì)基于算術(shù)運(yùn)算的密碼代數(shù)次數(shù)進(jìn)行檢測(cè)的通用方法.主要思想是評(píng)估分組密碼的多項(xiàng)式表示是否包含某些特定的單項(xiàng)式.在深入研究基于域運(yùn)算的算法特征的基礎(chǔ)上, 引入了基于域運(yùn)算的單項(xiàng)式傳播規(guī)則, 并利用SMT 的比特向量理論對(duì)其進(jìn)行了有效建模.利用代數(shù)次數(shù)與單項(xiàng)式指數(shù)之間的關(guān)系,構(gòu)造了一種新的次數(shù)估計(jì)搜索工具.之后, 將上述方法應(yīng)用于Feistel-MiMC、GMiMC 和MiMC.對(duì)于Feistel-MiMC, 結(jié)果表明代數(shù)次數(shù)的增長(zhǎng)明顯低于指數(shù)界, 并首次提出了一種高達(dá)124 輪的秘密密鑰高階差分區(qū)分器, 比Beyne 等人[44]對(duì)Feistel-MiMC 置換給出的83 輪區(qū)分器要多41 輪.此外, 還給出了一個(gè)已知密鑰條件下的全輪零和區(qū)分器, 數(shù)據(jù)復(fù)雜度為2251.將以上方法擴(kuò)展到更多的分支, 成功地找到了目前最長(zhǎng)的秘密密鑰高階差分區(qū)分器, 可用于分組密碼GMiMCerf的實(shí)際實(shí)例, 最長(zhǎng)可達(dá)50 輪, 比之前的最優(yōu)區(qū)分器[44]長(zhǎng)10 輪.對(duì)于MiMC, 得到的結(jié)果與Bouvier 等人[47]所證明的精確代數(shù)次數(shù)相一致.

2.3 Ciminion 和HYDRA

流密碼算法Ciminion 的設(shè)計(jì)目標(biāo)是最大限度地減少有限域F2n或Fp上的域乘法次數(shù)[5].在MiMC、GMiMC 和HADESMiMC 中, 非線性層均采用的是冪函數(shù)來對(duì)獨(dú)立的域元素進(jìn)行操作.而Ciminion 提供了一種不同的設(shè)計(jì)方法, 它的設(shè)計(jì)基于Toffoli 門[48]和一個(gè)簡(jiǎn)單的非線性雙射, 將三元組(a,b,c) 轉(zhuǎn)換為三元組(a,b,ab+c).同時(shí), 為了進(jìn)一步地優(yōu)化實(shí)現(xiàn)性能, Ciminion 使用非常輕量級(jí)的線性層.由于作者最終的設(shè)計(jì)目標(biāo)不是構(gòu)造一個(gè)低乘法復(fù)雜度的密碼, 而是提供一個(gè)低乘法復(fù)雜度的加密函數(shù).因此, 他們通過采用Farfalle 結(jié)構(gòu)[49]的修改版本來實(shí)現(xiàn), 從而可以執(zhí)行流加密.Farfalle 是一個(gè)有效的并行置換結(jié)構(gòu), 具有可變輸入和輸出長(zhǎng)度的偽隨機(jī)函數(shù).采用Farfalle 結(jié)構(gòu)的優(yōu)點(diǎn)是可以盡量減少密碼的輪數(shù), 從而最大程度地減少域乘法的數(shù)量.設(shè)計(jì)者根據(jù)數(shù)據(jù)量限制條件分別定義了Ciminion 算法的標(biāo)準(zhǔn)實(shí)例、MPC應(yīng)用實(shí)例及保守實(shí)例.為了促進(jìn)對(duì)Ciminion 算法的進(jìn)一步分析, 設(shè)計(jì)者還提出了Ciminion 算法的簡(jiǎn)化版本, 稱為Aiminion 算法[6].

與MiMC、HADESMiMC 和Rescue 等相比,Ciminion 在MPC 中實(shí)現(xiàn)了最佳性能.然而,Ciminion的安全性高度依賴于其子密鑰的獨(dú)立性,這是通過使用復(fù)雜的密鑰編排來實(shí)現(xiàn)的.由于許多涉及對(duì)稱PRF的MPC 用例依賴于秘密共享的對(duì)稱密鑰, 復(fù)雜的密鑰編排也必須在MPC 中計(jì)算.因此, Ciminion 在這些用例中的性能顯著降低.2023 年, Grassi 等解決了這個(gè)問題[7], 他們按照Ciminion 設(shè)計(jì)者介紹的方法提出了Farfalle 的修改版本—Megafono 設(shè)計(jì), 旨在實(shí)現(xiàn)較小的乘法復(fù)雜度, 而無需任何密鑰編排.按照這種策略, 進(jìn)一步提出了PRF HYDRA, 它同時(shí)利用了Lai-Massey 結(jié)構(gòu)和在其非線性層中命名為Amaryllises 的新型結(jié)構(gòu).Amaryllises 可以看作是Lai-Massey 的變體, 它允許進(jìn)一步降低HYDRA 的乘法復(fù)雜度.由于Ciminion 的密鑰編排乘法深度較大, 且參與方之間的通信量較大, 因此, Ciminion 只有在不需要計(jì)算密鑰編排時(shí)才具有競(jìng)爭(zhēng)力.總的來說, HYDRA 在低乘法復(fù)雜度、小通信、良好的普適性能以及合理的深度之間取得了很好的平衡, 使其成為大多數(shù)網(wǎng)絡(luò)環(huán)境中MPC 的首選PRF.

在Ciminion 的設(shè)計(jì)文檔中, Dobraunig 等對(duì)其進(jìn)行了全面的安全分析, 研究了Ciminion 對(duì)線性密碼分析、差分密碼分析、高階差分密碼分析、插值攻擊和Gr?bner 基攻擊的安全性.由于Ciminion 的結(jié)構(gòu)新穎, 傳統(tǒng)分析方法對(duì)其安全性分析效果并不好.除此之外, 對(duì)于Gr?bner 基攻擊, 他們研究的是Ciminion的一個(gè)弱化版本.2022 年, Bariant 等人[50]針對(duì)實(shí)際的Ciminion 來建立方程組, 且給出的Gr?bner 基攻擊的漸近復(fù)雜度為O(24rω), 而設(shè)計(jì)者給出的攻擊復(fù)雜度為O(26rω), 其中r為輪數(shù),ω為矩陣乘法的指數(shù).Zhang 等人[51]提出了F2n上Ciminion 的高階差分區(qū)分器及Fp上Ciminion 的積分區(qū)分器.通過對(duì)Ciminion 輪函數(shù)的研究, 給出了輪函數(shù)的弱隨機(jī)數(shù)條件, 并在弱隨機(jī)數(shù)條件下, 提出了對(duì)Aiminion 的子密鑰恢復(fù)攻擊.

3 適宜FHE 的對(duì)稱密碼算法

3.1 Kreyvium

流密碼Kreyvium[8]具有與Trivium 相同的內(nèi)部結(jié)構(gòu), 但允許更大的密鑰比特(128 比特).與Trivium 唯一不同的是, Kreyvium 在288 比特的內(nèi)部狀態(tài)中增加了兩個(gè)128 比特的寄存器, 分別與密鑰和IV相對(duì)應(yīng), 目的是使過濾和轉(zhuǎn)換函數(shù)都依賴于密鑰和IV.Kreyvium 相對(duì)于Trivium 的主要優(yōu)勢(shì)在于, 它在與Trivium 具有相同的乘法深度情況下提供了128 比特的安全性(而不是80 比特), 并繼承了相同的安全性參數(shù).除了更高的安全級(jí)別, Kreyvium 的另一個(gè)優(yōu)點(diǎn)是可能的IV 數(shù)量, 以及在同一密鑰下可以加密的最大數(shù)據(jù)長(zhǎng)度.在HE 方案的具體實(shí)現(xiàn)中, 與LowMC 相比, Trivium 和Kreyvium 具有出色的性能.

2017 年, Liu[52]提出了對(duì)基于非線性反饋移位寄存器(NFSR) 的密碼系統(tǒng)的代數(shù)次數(shù)迭代估計(jì)的一般框架.在此基礎(chǔ)上, 進(jìn)一步提出了一種求代數(shù)次數(shù)上界的有效算法, 算法具有線性時(shí)間復(fù)雜度, 需要的內(nèi)存可以忽略不計(jì).之后, 將以上算法應(yīng)用于Kreyvium, 并通過設(shè)置不同的輸入變量來分析代數(shù)次數(shù)的各種上界.Kreyvium 的初始化輪數(shù)為1152, 當(dāng)Kreyvium 以所有密鑰和IV 比特作為輸入變量時(shí), 使生成的密鑰流比特達(dá)到最大代數(shù)次數(shù)的初始化輪數(shù)至少為982.當(dāng)以所有IV 比特作為輸入變量時(shí), 初始化輪數(shù)至少是862.通過該算法, 可以在立方測(cè)試器中使用任意大小的立方.該算法為Kreyvium 找到的最好的立方大小為61, 利用該立方可以得到Kreyvium 的872 輪零和區(qū)分器.

在文獻(xiàn)[53] 中, Wang 等人利用超級(jí)多項(xiàng)式(superpoly) 的各種代數(shù)性質(zhì)來改進(jìn)基于可分性質(zhì)的立方攻擊.基于大小為102 的立方, 作者提出了891 輪Kreyvium 的密鑰恢復(fù)攻擊.2018 年, 一種利用線性化技術(shù)在立方攻擊中測(cè)試非線性超級(jí)多項(xiàng)式的一般框架被提出[54].對(duì)于Kreyvium, 結(jié)果表明, 使用新框架找到二次超級(jí)多項(xiàng)式的概率是找到線性超級(jí)多項(xiàng)式的兩倍.2020 年, Kesarwani 等人[55]將Liu[52]的代數(shù)次數(shù)估計(jì)方法與文獻(xiàn)[56] 中的貪心算法結(jié)合起來, 提出了一種新的立方生成算法, 得到了Kreyvium 大小為56 的立方, 并給出了875 輪的零和區(qū)分器.

2018 年, Watanabe 等人[57]給出了Kreyvium 的條件差分密碼分析.他們分別利用20 階和25 階的高階條件差分特征獲得了Kreyvium 的730 輪和899 輪區(qū)分器.之后, 作者又根據(jù)20 階的高階條件差分特征得到了Kreyvium 的736 輪密鑰恢復(fù)攻擊.在文獻(xiàn)[58] 中, Roy 等人利用差分故障攻擊(DFA)技術(shù), 提出了對(duì)Kreyvium 的密鑰恢復(fù)攻擊.通過注入3 個(gè)錯(cuò)誤和考慮450 多個(gè)密鑰流比特, 可以恢復(fù)Kreyvium 的完整密鑰.

3.2 FLIP 和FiLIP

2016 年, Méaux 等人介紹了一種新的流密碼結(jié)構(gòu)—濾波置換器(filter permutator, FP)[9].主要設(shè)計(jì)原則是將布爾函數(shù)應(yīng)用于常量密鑰寄存器的公共比特置換, 從而使流密碼輸出的布爾復(fù)雜度是恒定的.更準(zhǔn)確地說, 在每個(gè)周期, 密鑰寄存器被偽隨機(jī)生成的置換打亂, 然后對(duì)打亂的密鑰寄存器的輸出應(yīng)用非線性濾波函數(shù).這種結(jié)構(gòu)的主要優(yōu)點(diǎn)是總是直接對(duì)密鑰比特應(yīng)用非線性濾波函數(shù), 從而使得輸出的噪聲水平是恒定的.之后, 作者研究了濾波置換器中各組件的優(yōu)化, 基于梳狀結(jié)構(gòu)設(shè)計(jì)了一個(gè)濾波函數(shù), 并指定了一系列濾波置換器, 稱為FLIP.除此之外, 還給出了流密碼FLIP 的幾個(gè)實(shí)例, 用于80 和128 比特安全性, 該算法的特點(diǎn)是密鑰長(zhǎng)度遠(yuǎn)大于安全界.與LowMC、Trivium 和Kreyvium 相比, FLIP 設(shè)計(jì)具有非常低的乘法深度, 這使得它們也適用于第二代FHE 方案.在HElib 的實(shí)現(xiàn)中, FLIP 實(shí)例在延遲和吞吐量的性能方面綜合表現(xiàn)良好.

Duval 等人[59]利用FLIP 的結(jié)構(gòu)弱點(diǎn)對(duì)FLIP 的安全性進(jìn)行了分析.他們采用的是猜測(cè)確定攻擊的一種變體技術(shù): 猜測(cè)一些空密鑰比特的位置, 而不是對(duì)密鑰或內(nèi)部狀態(tài)比特的值進(jìn)行假設(shè).FLIP 流密碼系列的兩個(gè)特征表明使用猜測(cè)確定攻擊可能是有效的: 首先是其固定的內(nèi)部狀態(tài), 其次是其濾波函數(shù)的定義.更準(zhǔn)確地說, 寄存器不進(jìn)行更新意味著在任何時(shí)候猜測(cè)一個(gè)密鑰或內(nèi)部狀態(tài)比特, 都會(huì)給出一個(gè)比特的信息.攻擊的主要思想是: 首先猜測(cè)空密鑰比特的位置, 由于濾波函數(shù)F高階的單項(xiàng)式數(shù)量很少, 在有很多空密鑰比特的情況下, 高階單項(xiàng)式有很大的概率被抵消.然后, 收集關(guān)于未知密鑰比特的低階方程, 選取那些空密鑰比特可以將次數(shù)大于等于3 的單項(xiàng)式消去的方程.最后, 使用線性化技術(shù)求解方程系統(tǒng).將以上攻擊應(yīng)用于FLIP 的兩個(gè)實(shí)例進(jìn)行密鑰恢復(fù), 針對(duì)80 和128 比特的安全級(jí)別, 時(shí)間復(fù)雜度分別為254和268個(gè)基本操作.FLIP 系列流密碼的最大問題在于其濾波函數(shù), 一個(gè)可能的改進(jìn)方向是使用含有更多高階單項(xiàng)式的濾波函數(shù).在文獻(xiàn)[58] 中, Roy 等人提出了對(duì)FLIP 的密鑰恢復(fù)攻擊.如果密碼的狀態(tài)中有1 比特錯(cuò)誤, 那么從9000 個(gè)正常和錯(cuò)誤的密鑰流比特中就可以恢復(fù)密鑰.對(duì)于單比特故障, 需要為每530個(gè)可能的故障位置求解方程組, 以恢復(fù)正確的FLIP 密鑰.

2019 年, Méaux 等利用FP 并根據(jù)FLIP 的最新進(jìn)展提出了改進(jìn)的濾波置換器(improved filter permutator, IFP)[10], 主要從兩個(gè)方向進(jìn)行改進(jìn).首先, IFP 利用擴(kuò)展密鑰寄存器, 因此密鑰大小大于作為濾波器的布爾函數(shù)的輸入, 這使得濾波器的輸入隨著密鑰大小的增加而越來越接近均勻分布, 而對(duì)于FP 情況則不同.其次, IFP 使用了一個(gè)白化階段.也就是說, 在發(fā)送到濾波器之前, 經(jīng)過置換的密鑰比特先和一個(gè)隨機(jī)的公共值進(jìn)行異或操作.之后, 作者給出了具體的實(shí)例FiLIPDSM, 與現(xiàn)有的FLIP 實(shí)例相比, 它們進(jìn)一步降低了乘法復(fù)雜度.在HElib 的實(shí)現(xiàn)中, 對(duì)于80 比特安全級(jí)別, FLIP、FiLIPDSM、Rasta 和Agrasta 的噪聲是大致相同的, FiLIPDSM在延遲方面的表現(xiàn)最佳.對(duì)于128 比特安全級(jí)別,FiLIP-1280 的密文噪聲略微小于Agrasta 和FLIP, FiLIP-1216 的延遲優(yōu)于FLIP.

3.3 Rasta 及其變體

(1) Rasta

Rasta 是由Dobraunig 等人提出的面向全同態(tài)加密的流密碼[11].與基于線性反饋移位寄存器(LFSR) 的流密碼完全不同, Rasta 更像一種分組密碼.它的設(shè)計(jì)同時(shí)考慮如下兩個(gè)度量標(biāo)準(zhǔn): 每個(gè)加密比特的與門數(shù)量和電路的乘法深度.該算法采用類ASASA 結(jié)構(gòu)來生成密鑰流, 其中替換層是公開且固定的, 采用的是Keccak 中的χ變換.仿射層包括一個(gè)二進(jìn)制矩陣操作和輪常量異或的置換, 均是由nonce 和計(jì)數(shù)器通過可擴(kuò)展輸出函數(shù)(extendable-output function, XOF) 派生的.因此, 允許在分析過程中將矩陣和輪常量看作隨機(jī)生成的進(jìn)行處理, 但限制條件是相同的nonce 和計(jì)數(shù)器總是會(huì)得到相同的矩陣和輪常量.敵手在Rasta 中永遠(yuǎn)無法在同一密鑰下訪問相同的類ASASA 置換, 這種設(shè)計(jì)方法的優(yōu)點(diǎn)如下: 一是可以防止文獻(xiàn)[60–62] 中提出的攻擊, 二是由于XOF 不使用秘密信息, 其不會(huì)影響FHE 應(yīng)用中與AND 門相關(guān)的評(píng)估.基于線性密碼分析、差分密碼分析等經(jīng)典攻擊方法及代數(shù)攻擊的結(jié)果, 作者建議Rasta 的輪數(shù)選取為4–6 輪, 并且給出了80、128 及256 比特安全級(jí)別下的分組大小.除此之外, 從理論的角度來看, 更低輪數(shù)的Rasta 實(shí)例也很有趣, 因此, 還增加了2 輪和3 輪的參數(shù).與Kreyvium 和LowMC 對(duì)比, 它們?cè)试S密鑰大小與安全級(jí)別一樣, 而Rasta 和FLIP 一樣, 需要更長(zhǎng)的密鑰.Dobraunig等人證明了即使Rasta 的乘法深度很小時(shí), 如在2–6 之間選取, 某些攻擊也可能不存在.傳統(tǒng)上, 線性操作的成本與非線性操作相比幾乎可以忽略不計(jì), 但在某些環(huán)境中, 異或操作的數(shù)量過多, 不可以被忽略.與LowMC 類似, Rasta 需要的異或操作遠(yuǎn)遠(yuǎn)多于FLIP 和Kreyvium, 因此在FHE 應(yīng)用場(chǎng)景中的計(jì)算代價(jià)不可忽略.根據(jù)實(shí)現(xiàn)的性能比較, Rasta 的乘法深度選取4 到6 在實(shí)際中是更有用的.

Rasta 的密鑰大小主要由得到的單項(xiàng)式最大數(shù)量的界和存在好的線性逼近的概率界決定.然而, 在對(duì)Rasta 的分析中, 實(shí)際的攻擊遠(yuǎn)小于以上界.因此, 作者進(jìn)一步提出了密鑰大小與安全級(jí)別匹配的一種Rasta 變體Agrasta, 其密鑰大小等于安全級(jí)別大小加一.因此, Agrasta 在80、128 及256 比特安全級(jí)別下的分組大小分別為81、129 和257, 輪數(shù)分別為4、4 和5 輪.

(2) Dasta

由于Rasta 依賴于一個(gè)偽隨機(jī)函數(shù)來生成仿射層中的矩陣, 導(dǎo)致在Rasta 中生成每次加密的仿射層非常耗時(shí).因此, Hebborn 和Leander 提出了Dasta[12], Rasta 中的線性層被可變比特置換和確定性線性變換所取代.這種方法有如下優(yōu)點(diǎn), 首先, 由于線性層是固定的, 因此可以優(yōu)化它們的實(shí)現(xiàn).其次, 更重要的是, 可以將Rasta 的基于隨機(jī)的安全參數(shù)提升到固定線性層情況下的參數(shù).除線性層的生成外,Dasta 在密鑰大小和輪數(shù)的參數(shù)選取方面和Rasta 相同.在離線密鑰流的生成時(shí)間方面, Dasta 比Rasta快200–400 倍.在HElib[63]中實(shí)現(xiàn)的FHE 環(huán)境下, 與Rasta 相比, Dasta 的運(yùn)行時(shí)間減少了大約15%–20%.

(3) Masta

盡管Rasta 在FHE 的成本度量方面提供了良好的結(jié)果, 但有兩個(gè)缺點(diǎn)限制了它的實(shí)際應(yīng)用.一是Rasta 在二進(jìn)制明文空間上操作, 而大多數(shù)HE 方案都是在特定類別的環(huán)上運(yùn)行.二是Rasta 的仿射層需要生成大量的偽隨機(jī)比特, 導(dǎo)致在客戶端需要大量的計(jì)算成本.因此, Rasta 的又一變體算法Masta 被提出[13].與Rasta 類似, Masta 將密鑰和一個(gè)nonce 作為輸入, 并為每個(gè)計(jì)數(shù)器生成一個(gè)密鑰流.Masta的結(jié)構(gòu)和Rasta 很相似, Masta 通過交替應(yīng)用仿射層和χ變換來計(jì)算其密鑰流分組.但Masta 與Rasta相比有兩個(gè)主要區(qū)別: Masta 在非二進(jìn)制明文空間上使用模運(yùn)算, 并且它通過有限域乘法定義仿射層, 使得仿射層使用較少的隨機(jī)比特.通過這種方式, Masta 在BGV/BFV 下的HE 方案的傳輸框架中優(yōu)于Rasta.實(shí)現(xiàn)表明, 在客戶端吞吐量方面, Masta 比Rasta 快505–592 倍, 在服務(wù)器端要快4792–6986 倍.

(4) Fasta

2022 年, Cid 等提出了用于實(shí)現(xiàn)更快同態(tài)加密的流密碼—Fasta[14].Fasta 可以被認(rèn)為是Rasta 的變體, 同樣在二進(jìn)制明文空間上操作.它采用6 輪類ASASA 結(jié)構(gòu)的輪函數(shù)來生成密鑰流, 其中非線性層為χ變換, 仿射層是基于移位操作構(gòu)造的, 其中參數(shù)是隨機(jī)生成的.Fasta 使用特定選擇的參數(shù)和線性層使得其在BGV 方案中能有效地實(shí)現(xiàn), 特別是在HElib 中的實(shí)現(xiàn).并且所選取的參數(shù)利用BGV 提供的并行性, 使得密文中的槽被打包以在評(píng)估非線性層時(shí)可以實(shí)現(xiàn)完全并行.Fasta 實(shí)例的參數(shù)選擇保證了128比特安全性, 其不僅可以作為獨(dú)立的對(duì)稱密碼, 也可以與它所應(yīng)用的BGV 方案的特定實(shí)例串聯(lián)使用.在Rasta 中, 線性層是由隨機(jī)矩陣生成的, 導(dǎo)致填充效率很低.因此, 在進(jìn)行同態(tài)計(jì)算時(shí), Fasta 比相應(yīng)的(修改過的) Rasta 實(shí)例快6 倍以上, 比原始Rasta 版本快25 倍.

在文獻(xiàn)[64] 中, Dobraunig 等利用相關(guān)密鑰高階差分區(qū)分器在單個(gè)明文/密文對(duì)條件下對(duì)1、2、3、4輪的Agrasta 進(jìn)行了密鑰恢復(fù)攻擊.結(jié)果表明, 1、2、3 輪Agrasta 的密鑰恢復(fù)攻擊快于蠻力攻擊.2021年, Liu 等人[65]指出, Rasta 和Dasta 的設(shè)計(jì)者忽略了χ變換的一個(gè)重要性質(zhì).結(jié)合Rasta 和Dasta 的特殊結(jié)構(gòu), 這一性質(zhì)直接導(dǎo)致了代數(shù)攻擊的顯著改進(jìn).特別是, 他們?cè)诶碚撋夏軌蚍治? 個(gè)完整Agrasta實(shí)例中的2 個(gè).主要策略是構(gòu)建由χn表示的n位χ操作的可利用方程, 并且這些方程都是通過首先研究較小n的χn得到的.之后, Liu 等人[66]又證明如果χn的逆χ?1n的顯式公式已知, 則所有這些可利用的方程都將是顯式的, 并且在設(shè)計(jì)時(shí)可以避免類似Rasta 密碼的弱點(diǎn).他們給出了一個(gè)非常簡(jiǎn)單的χ?1n公式, 并以嚴(yán)格的方式證明了它的正確性.基于此公式, 可以很容易地推導(dǎo)出類Rasta 密碼的可利用方程的公式, 從而找到更多可利用的方程.

3.4 Pasta

2021 年, Dobraunig 等人提出了面向混合同態(tài)加密(hybrid homomorphic encryption, HHE) 優(yōu)化的流密碼Pasta[15].與Rasta 相比, Pasta 同樣采用類ASASA 結(jié)構(gòu)的輪函數(shù)來生成密鑰流, 但其使用兩種不同的S 盒層, 這樣做的目的是盡可能減少輪數(shù).前r ?1 輪采用的S 盒設(shè)計(jì)靈感來自χ變換, 最后一輪采用冪函數(shù)構(gòu)造的S 盒S(x) =x3.此外, Rasta 中的前饋操作被截?cái)嗖僮魉〈? 這允許以更有效的方式防止中間相遇攻擊, 但代價(jià)是使用更大的狀態(tài).Pasta 的線性層生成也比Rasta 簡(jiǎn)單得多, 其并不直接生成隨機(jī)可逆矩陣, 而是通過選取隨機(jī)元素來構(gòu)造兩個(gè)序列矩陣, 然后通過混合操作將這兩個(gè)矩陣組合成一個(gè)隨機(jī)可逆矩陣.

Pasta 對(duì)定義在Fp上的明文進(jìn)行操作, 與之前提出的大多數(shù)定義在F2上的對(duì)稱密碼相比, 大大提高了性能.此外, Pasta 利用最先進(jìn)的整數(shù)HE 密碼系統(tǒng)(BFV 和BGV) 的結(jié)構(gòu)來最小化HHE 中的解壓縮延遲, 同時(shí)仍然保持較少的輪數(shù)和乘法深度.作者評(píng)估了Pasta 在SEAL 和HElib 中的性能, 并和LowMC、Rasta、Dasta、Agrasta、Kreyvium、FLIP 和Masta 等對(duì)稱密碼算法進(jìn)行了比較.結(jié)果表明,在同態(tài)計(jì)算時(shí)間和噪聲量方面, Pasta 在HHE 中優(yōu)于其競(jìng)爭(zhēng)對(duì)手.具體來說, 當(dāng)應(yīng)用于HElib 中的一個(gè)小用例時(shí), Pasta 的速度是Agrasta 的82 倍, 后者是目前FHE 中最快的算法.而當(dāng)應(yīng)用于SEAL 中的一個(gè)更大用例時(shí), Pasta 的速度是Masta 的6 倍.

3.5 Chaghri

分組密碼Chaghri 以Vision 的設(shè)計(jì)為起點(diǎn)[16], 采用SPN 結(jié)構(gòu), 狀態(tài)向量為解密輪數(shù)為8 輪, 每輪包括相同的兩步, 每步由S 盒層、線性層和輪密鑰加組成.其中S 盒層包括一個(gè)冪映射G(x)=x232+1和一個(gè)仿射變換B(x)=c1x23+c2,c1,c2為常量.線性層是一個(gè)3×3 的MDS 矩陣.密鑰編排實(shí)際上是迭代地應(yīng)用解密輪函數(shù).在HElib 的實(shí)現(xiàn)中, Chaghri 實(shí)現(xiàn)了0.28 秒/比特的吞吐量, 在相同設(shè)置下比AES 快63%.

在Chaghri 被提出后不久, 其安全性就遭受到了攻擊.2023 年, Liu 等人[67]提出了一種稱為系數(shù)分組的方法來評(píng)估Chaghri 的代數(shù)次數(shù), 結(jié)果發(fā)現(xiàn)其代數(shù)次數(shù)增長(zhǎng)是線性的而非指數(shù)的.核心思想是通過用一個(gè)整數(shù)向量來描述每一個(gè)指數(shù)集合, 從而將研究指數(shù)的傳播簡(jiǎn)化為研究向量的傳播, 這種方法的效率來自于如下事實(shí): 向量的傳播是確定的, 可以在線性時(shí)間內(nèi)計(jì)算, 且與輪數(shù)無關(guān).利用MILP 解決了將整數(shù)向量轉(zhuǎn)化為代數(shù)次數(shù)的問題.作者又利用上述方法對(duì)Chaghri 構(gòu)造了一個(gè)時(shí)間和數(shù)據(jù)復(fù)雜度均為263的13 輪區(qū)分器, 并進(jìn)行了13.5 輪密鑰恢復(fù)攻擊.特別是對(duì)8 輪Chaghri 進(jìn)行了高階差分攻擊, 時(shí)間和數(shù)據(jù)復(fù)雜度為238.因此, 以上分析結(jié)果表明8 輪的Chaghri 是遠(yuǎn)遠(yuǎn)不夠安全的.Chaghri 的漏洞在于其使用了稀疏仿射變換B(x), Liu 等人進(jìn)一步給出了新的仿射變換B′(x) =c′1x+c′2x22+c′3x28+c′4來替換B(x), 可以實(shí)現(xiàn)幾乎指數(shù)級(jí)的代數(shù)次數(shù)增長(zhǎng).

3.6 HERA 和Rubato

2021 年, Cho 等人提出了一種支持對(duì)加密數(shù)據(jù)進(jìn)行近似計(jì)算的同態(tài)加密框架, 稱為RtF 框架, 可以在沒有顯著的密文擴(kuò)展或客戶端計(jì)算過載的情況下對(duì)實(shí)數(shù)進(jìn)行加密[17].作為框架中流密碼的一個(gè)實(shí)例, 他們提出了流密碼HERA.HERA 的主要特點(diǎn)是在生成密鑰流的輪函數(shù)中, 它使用一個(gè)十分簡(jiǎn)單的隨機(jī)密鑰編排, 即將主密鑰直接與XOF 的輸出隨機(jī)值進(jìn)行乘積操作.HERA 的輪函數(shù)與AES 類似, 對(duì)4×4 的狀態(tài)矩陣進(jìn)行操作, 除最后一輪外, 其輪函數(shù)包括列混淆、行混淆、S 盒層及輪密鑰異或操作.與使用隨機(jī)線性層的FLIP 和Rasta 等密碼相比, HERA 需要更少的隨機(jī)比特?cái)?shù).在HElib 的實(shí)現(xiàn)中, 與LowMC、FLIP、Rasta、Dasta 和Masta 相比, HERA 在客戶端和服務(wù)端的延遲和吞吐量表現(xiàn)均是最優(yōu)的.

2022 年,Ha 等提出了一個(gè)帶噪聲的流密碼系列,稱為Rubato[18].作為近似同態(tài)加密框架中LWE 加密和傳統(tǒng)對(duì)稱加密的結(jié)合, 該算法采用一種新穎的設(shè)計(jì)策略將噪聲引入到一個(gè)低代數(shù)次數(shù)的對(duì)稱密碼中,Rubato 不適合對(duì)精確數(shù)據(jù)進(jìn)行加密, 因?yàn)榉?wù)器在加密后可能會(huì)丟失原始消息的一些信息.Rubato 采用和HERA 一樣的隨機(jī)密鑰編排, 輪函數(shù)也類似.與現(xiàn)有的適宜HE 的密碼相比, 這種策略可以使得密碼的乘法復(fù)雜度顯著降低, 但不會(huì)降低整體安全性.更準(zhǔn)確地說, 給定一個(gè)中等大小的分組(16–64), Rubato具有較低的乘法深度(2–5) 和每個(gè)加密字的少量乘法數(shù)量(2.1–6.25), 代價(jià)是密文擴(kuò)展略大(1.26–1.31).與RtF 框架內(nèi)的HERA 相比, Rubato 在客戶端和服務(wù)端的吞吐量分別提高了22.9% 和32.2%, 代價(jià)是密文擴(kuò)展僅增加了1.6%.

3.7 Elisabeth

2022 年, Cosseron 等將FLIP 和FiLIP 使用的濾波置換器的設(shè)計(jì)方法推廣到任意群上, 提出了面向混合同態(tài)加密的流密碼族Elisabeth[19], 并給出了一個(gè)實(shí)例: Elisabeth-4.在TFHE 實(shí)現(xiàn)中, 與FiLIP 相比, Elisabeth-4 的數(shù)據(jù)開銷顯著減少, 每比特的速度提高了5–27.5 倍.

4 適宜ZK 的對(duì)稱密碼算法

4.1 Jarvis 和Friday

2018 年, Ashur 和Dhooghe 提出了分組密碼Jarvis 及其衍生雜湊函數(shù)Friday[20], 均在有限域F2n上運(yùn)算.Jarvis 和Friday 的設(shè)計(jì)理念是提高在ZK-STARKs 中使用時(shí)的時(shí)間、存儲(chǔ)和通信成本的效率.Jarvis 的設(shè)計(jì)靈感來自Rijndael, 通過構(gòu)造一個(gè)具有與Rijndael 相似性質(zhì)的密碼, 使用寬軌跡策略來證明其對(duì)差分和線性密碼分析的安全性.但與Rijndael 在輪函數(shù)中使用多個(gè)S 盒不同, Jarvis 對(duì)整個(gè)狀態(tài)應(yīng)用單個(gè)非線性變換, 其本質(zhì)上是使用一個(gè)大的n比特S 盒S(x) =x?1.在Jarvis 中, 通過組合單個(gè)可逆S 盒、仿射置換多項(xiàng)式和密鑰異或來獲得輪函數(shù).Jarvis 的密鑰編排與其輪函數(shù)類似, 主要的區(qū)別在于省略了仿射變換.作者給出了Jarvis 的四個(gè)實(shí)例, 安全級(jí)別分別為128、160、192 及256, 且等于密鑰大小(分組大小).Friday 是一個(gè)基于Merkel-Damg?rd 結(jié)構(gòu)的雜湊函數(shù).在STARK 證明生成時(shí)間方面,Friday 據(jù)稱比Pedersen 雜湊函數(shù)具有20 倍的優(yōu)勢(shì), 比基于MiMC 的雜湊函數(shù)具有2.5 倍的優(yōu)勢(shì)[68].

在Jarvis 和Friday 提出后不久, Albrecht 等人[69]就提出了對(duì)Jarvis 和Friday 的Gr?bner 基攻擊, 即對(duì)Jarvis 的密鑰恢復(fù)攻擊和對(duì)Friday 的原像攻擊.盡管Jarvis 仿射多項(xiàng)式的高次數(shù)可以防止一些代數(shù)攻擊, 但輪函數(shù)的特定代數(shù)性質(zhì)使得Jarvis 和Friday 都容易受到Gr?bner 基攻擊.結(jié)果表明, Jarvis和Friday 輪數(shù)的選擇不足以提供足夠的安全性.

4.2 Vision 和Rescue

2020 年, Aly 和Ashur 等人作為對(duì)Jarvis 和Friday 的安全性遭受破壞[69]的回應(yīng), 首先系統(tǒng)地給出了針對(duì)提高STARK 效率的Marvellous 設(shè)計(jì)策略的一般結(jié)構(gòu)及設(shè)計(jì)原則, 旨在提供一種通用的框架可用于在采用算術(shù)運(yùn)算的應(yīng)用環(huán)境中設(shè)計(jì)安全高效的密碼算法.本質(zhì)上, Marvellous 設(shè)計(jì)是一個(gè)由(q,m,π,m,v,s) 參數(shù)化的SPN 結(jié)構(gòu),q,m,π,m,v,s分別代表有限域的階、向量空間維數(shù)、S 盒、MDS矩陣、常量及安全級(jí)別.之后, Aly 等人基于Marvellous 設(shè)計(jì)提出了一個(gè)新的SNARK/STARK 友好雜湊函數(shù)系列, 為Vision 和Rescue[21].Vision 在有限域F2n上進(jìn)行運(yùn)算, 每一輪輪函數(shù)包括兩步: 第一步包括S 盒S(x) =x?1, F2上線性化的4 次仿射多項(xiàng)式B, MDS 矩陣M和輪常量加, 第二步非常相似,但將B替換為B?1.Rescue 在素域Fp上進(jìn)行運(yùn)算, 輪函數(shù)和Vision 一樣包括兩步, 第一步包括S 盒S(x)?1=x1/α, MDS 矩陣M和輪常量加, 第二步中將S(x)?1替換為S(x)=xα,α=3 或5.分別在采用AIR 和R1CS 的ZK-STARKs 零知識(shí)證明系統(tǒng)和MPC 這三個(gè)不同應(yīng)用場(chǎng)景中分析Vision 和Rescue的效率, 結(jié)果顯示, Rescue 在AIR 系統(tǒng)中比Vision、POSEIDON、STARKAD 和GMiMCerf更有效.在R1CS 系統(tǒng)中, 大多數(shù)情況下POSEIDON 的表現(xiàn)優(yōu)于其他算法.這一結(jié)果主要是由于安全界的差異導(dǎo)致的.在MPC 中, Rescue 的在線通信輪數(shù)總是優(yōu)于其他算法, Vision 和POSEIDON 在乘法數(shù)量方面有競(jìng)爭(zhēng)力, 出現(xiàn)以上結(jié)果的原因一方面在于安全界的不同, 另一方面是由于不同的優(yōu)化策略.STARKAD 和POSEIDON 的優(yōu)化策略是最小化乘法數(shù)量, 而Vision 和Rescue 的優(yōu)化策略是最小化通信輪數(shù)(即電路深度).

高級(jí)密碼協(xié)議幾乎普遍偏愛素域, 因此, Rescue 得到了比Vision 更多的關(guān)注.除設(shè)計(jì)者外, 2020 年,Beyne 等人[70]研究了Rescue 針對(duì)線性密碼分析、差分密碼分析、乘法子群的傳播及反彈攻擊的安全性.結(jié)果表明, 并未發(fā)現(xiàn)任何對(duì)Rescue 的直接威脅.在文獻(xiàn)[71] 中, Szepieniec 等人以優(yōu)化實(shí)現(xiàn)性能為目標(biāo), 基于原始的Rescue 設(shè)計(jì)進(jìn)行簡(jiǎn)化, 提出了雜湊函數(shù)Rescue-Prime.改動(dòng)包括三部分: 簡(jiǎn)化輪常量的生成方式—采用隨機(jī)輪常量; 將安全余量從100% 降低到50%; 顛倒每輪兩步中S 盒的順序.2021 年,以太坊基金專門發(fā)起了針對(duì)Rescue-Prime、Feistel-MiMC、POSEIDON 和Reinforced Concrete 這幾種適宜ZK 的對(duì)稱密碼算法挑戰(zhàn)賽[72].2022 年, Bariant 等人[50]提出了一種通用方法在代數(shù)攻擊中可以刪除描述SPN 結(jié)構(gòu)中前兩輪的所有方程, 前提是第一個(gè)操作是S 盒層而不是線性層, 并且S 盒是一個(gè)單項(xiàng)式.將以上通用方法與多變量根求解算法結(jié)合起來, 針對(duì)挑戰(zhàn)賽中使用t= 2 和t= 3 (字的個(gè)數(shù)) 的Rescue-Prime, 成功進(jìn)行了縮減輪的攻擊.

4.3 POSEIDON 和STARKAD

Grassi 等人提出了雜湊函數(shù)POSEIDON[22]和STARKAD[23].POSEIDON 是在Fp上運(yùn)算的雜湊函數(shù)族, 其采用Sponge 結(jié)構(gòu)進(jìn)行實(shí)例化, 且內(nèi)部置換是基于HADES 結(jié)構(gòu)設(shè)計(jì)的, 被稱為POSEIDONπ.在具有部分S 盒層的輪函數(shù)中,非線性部分僅使用一個(gè)S 盒,目的是降低R1CS 或AET 的代價(jià).S 盒采用冪映射xα,α可選取?1、3 或5,且設(shè)計(jì)者聲稱x5更適用于ZK 應(yīng)用中最流行的兩個(gè)素域.POSEIDONπ的線性層是由柯西矩陣生成的MDS 矩陣, 生成之后需要利用文獻(xiàn)[73] 中的方法判斷矩陣是否存在無限長(zhǎng)不變/迭代子空間跡.雜湊函數(shù)STARKAD 和POSEIDON 的結(jié)構(gòu)一樣, 但STARKAD 的設(shè)計(jì)基于有限域F2n, 且S 盒僅使用x3.

2020 年, Beyne 等人[44]給出了POSEIDON 和STARKAD 內(nèi)部置換的零和區(qū)分器及作為雜湊函數(shù)時(shí)的原像攻擊.在2021 年的歐密會(huì)上, Keller 等人[74]顯著提高了POSEIDON 的差分和線性密碼分析的活躍S 盒數(shù)量的下界.之后對(duì)STARKAD 算法給出了一個(gè)不變子空間攻擊.證明對(duì)于任何t(即每輪中字的數(shù)量) 可被4 整除的STARKAD 算法實(shí)例, 該算法允許一個(gè)維數(shù)較大的不變子空間通過任意數(shù)量的P-SPN 輪而不激活任何S 盒.除此之外, 對(duì)于STARKAD 算法各種參數(shù)的選擇, 這個(gè)不變子空間可以用于對(duì)雜湊函數(shù)進(jìn)行原像攻擊, 破壞了其安全性聲明, 因此, 后來作者只保留了POSEIDON.在以太坊基金針對(duì)POSEIDON[72]發(fā)起的挑戰(zhàn)賽中, POSEIDON 的S 盒為3且字的個(gè)數(shù)為3.2022 年,Bariant 等人[50]將可以刪除描述SPN 結(jié)構(gòu)中前兩輪的所有方程的通用方法與單變量根求解算法結(jié)合起來, 針對(duì)挑戰(zhàn)賽中的POSEIDON 成功進(jìn)行了代數(shù)攻擊.

4.4 Reinforced Concrete

2022 年, 為支持查找表的證明系統(tǒng), Barbara 等人提出了一種新的面向零知識(shí)證明和可驗(yàn)證計(jì)算的雜湊函數(shù)Reinforced Concrete (RC)[24], 且使用的是基于KZG 承諾或FRI 的Plookup 協(xié)議[75].Reinforced Concrete 的設(shè)計(jì)目標(biāo)如下: 一是最小化ZK 電路中門的數(shù)量, 從而最小化證明創(chuàng)建時(shí)間, 二是最小化普通計(jì)算的時(shí)間和電路約束的數(shù)量.它有兩個(gè)突出的優(yōu)點(diǎn): (1) 使用查找表比模塊化歸約在ZK 和普通計(jì)算中的速度都更快, 從而使基于遞歸證明的可驗(yàn)證計(jì)算協(xié)議更高效; (2) 安全性不再僅僅基于(高) 代數(shù)次數(shù),而是基于更傳統(tǒng)的類似AES 部件.RC 采用Sponge 結(jié)構(gòu),其內(nèi)部置換的設(shè)計(jì)思路基于POSEIDON設(shè)計(jì)策略, 即由兩種不同的輪函數(shù)組成: 用于防止統(tǒng)計(jì)攻擊的外部輪數(shù)和用于防止代數(shù)攻擊的內(nèi)部輪數(shù).RC 置換的輪函數(shù)采用7 輪的SP 結(jié)構(gòu),在素域Fp上進(jìn)行運(yùn)算且字的個(gè)數(shù)為3.S 盒為低次數(shù)的Bricks 和高次數(shù)的Bars, Bricks 是F3p上的一個(gè)5 次非線性置換, Bars 是F3p上三個(gè)函數(shù)復(fù)合定義的一個(gè)置換.線性層由3×3 的MDS 矩陣和輪常量異或組成.在普通實(shí)現(xiàn)中, 與POSEIDON、Rescue 和Rescue-Prime相比, RC 的速度更快, 同時(shí)電路門數(shù)量更少.具體性能表現(xiàn)取決于素域的選擇, 當(dāng)使用通用的素域時(shí), 如在BLS12-381 或BN254 橢圓曲線的標(biāo)量域中, RC 比POSEIDON 快5 倍, 比Rescue 快125 倍, 比Rescue-Prime 快110 倍.與作為基準(zhǔn)測(cè)試的最快的傳統(tǒng)雜湊函數(shù)Blake2s 比, RC 只比其慢了80%, 但所需門的數(shù)量不到其七分之一.雖然RC 算法在計(jì)算速度上更優(yōu), 但其通用性和可拓展性不如其他算法.由于其S 盒設(shè)計(jì)非常復(fù)雜, 因此利用查表實(shí)現(xiàn)S 盒, 這也要求零知識(shí)證明系統(tǒng)支持查表運(yùn)算.

4.5 Anemoi

Anemoi 是由Bouvier 等提出的定義在F2n或Fp上的雜湊函數(shù)[25], 與其他適宜ZK 的雜湊函數(shù)相比, Anemoi 的主要特征如下: (1) 它的設(shè)計(jì)目標(biāo)是在多個(gè)證明系統(tǒng)(例如Groth16、Plonk 等) 中均是高效的; (2) 它包含針對(duì)特定應(yīng)用優(yōu)化的專用功能; (3) 在性能方面具有競(jìng)爭(zhēng)力.在設(shè)計(jì)方面, Anemoi 內(nèi)部置換的設(shè)計(jì)利用了CCZ 等價(jià)和算術(shù)運(yùn)算之間的關(guān)系, 輪函數(shù)的操作類似于SPN 結(jié)構(gòu), 作者提出了兩種新的組件, 一種是名為Flystel 的新型S 盒, 基于蝴蝶結(jié)構(gòu)(butterfly structure)[76]進(jìn)行設(shè)計(jì).另一種是壓縮函數(shù)Jive, 用于構(gòu)造高效的Merkle 樹.Flystel 置換分為開-Flystel 置換和閉-Flystel 置換.對(duì)于狀態(tài)大小為偶數(shù)的Anemoi, 其S 盒采用開-Flystel 置換, 且第一輪的前兩個(gè)輪常量由定義給出, 其余輪常量由閉-Flystel 置換得到.線性層可以分為兩個(gè)子層, 其劃分依據(jù)是零知識(shí)證明協(xié)議的不同.具體來說, 當(dāng)零知識(shí)證明系統(tǒng)基于Plonk 時(shí), 應(yīng)當(dāng)盡可能地減少加法運(yùn)算的次數(shù), 此時(shí)應(yīng)采用Duval 和Leurent 提出的最低加法個(gè)數(shù)的矩陣[77].若采用ZK-STARKs 系統(tǒng), 則應(yīng)使用MDS 矩陣.線性層的第二層是偽Hadamard變換, 主要用于抵抗代數(shù)攻擊.在R1CS 系統(tǒng)中, Anemoi 比POSEIDON 和Rescue-Prime 的效率高約2倍.在Plonk 約束下, 比POSEIDON 實(shí)現(xiàn)提高了10%–28%.

4.6 GRIFFIN

2022 年, Grassi 等提出了一種新的結(jié)構(gòu)—Horst 結(jié)構(gòu)[26].Horst 結(jié)構(gòu)是將Feistel 結(jié)構(gòu)中加法操作替換為乘法操作, 且保留原有的加法操作, 破壞了Feistel 結(jié)構(gòu)原有的可逆性, 因此需要特殊函數(shù)G來保持Horst 結(jié)構(gòu)的可逆性, 即(x,y)(y+F(x),x) 變?yōu)?x,y(y×G(x)+F(x),x).之后, 作者基于Horst 結(jié)構(gòu)設(shè)計(jì)了一個(gè)新的雜湊函數(shù)族, 稱為GRIFFIN, 其內(nèi)部置換為定義在Fp上的GRIFFIN-π.GRIFFIN-π的輪函數(shù)采用SPN 結(jié)構(gòu), 但其非線性層和線性層與之前的設(shè)計(jì)不同.非線性層利用了Horst 結(jié)構(gòu), 并不采用獨(dú)立S 盒的級(jí)聯(lián), 而是由三個(gè)不同的非線性函數(shù)定義的兩個(gè)非線性子層組成的.根據(jù)狀態(tài)大小可將線性層分為兩種.當(dāng)狀態(tài)大小t= 3,4 時(shí), 選擇MDS 矩陣作為線性層.當(dāng)狀態(tài)大小t= 4t′≥8 時(shí), 線性層可以定義為兩個(gè)矩陣的乘積, 不僅可以在1 輪后就達(dá)到全擴(kuò)散, 并且通過少量加法就可以實(shí)現(xiàn).在實(shí)現(xiàn)方面, 主要與POSEIDON、Rescue-Prime 和GMiMCerf進(jìn)行比較.在普通實(shí)現(xiàn)中, 當(dāng)字的個(gè)數(shù)小于等于16時(shí), GMiMCerf速度最快, GRIFFIN 的速度快于Rescue-Prime, 當(dāng)字的個(gè)數(shù)大于16 時(shí), GRIFFIN 的速度最快.在R1CS 系統(tǒng)中, GRIFFIN 需要最小數(shù)量的R1CS 約束, 且具有最快的證明時(shí)間.

5 總結(jié)與展望

云計(jì)算、大數(shù)據(jù)、物聯(lián)網(wǎng)等新型應(yīng)用的安全需求, 促進(jìn)了安全多方計(jì)算、全同態(tài)加密和零知識(shí)證明等安全協(xié)議的發(fā)展和應(yīng)用, 帶動(dòng)了新形態(tài)對(duì)稱密碼算法的設(shè)計(jì)與分析.自LowMC 被提出以后, 短短幾年時(shí)間, 國(guó)際上公開發(fā)布了30 多個(gè)與相關(guān)應(yīng)用相匹配的新形態(tài)對(duì)稱密碼算法, 發(fā)表了幾十篇新形態(tài)對(duì)稱密碼算法的設(shè)計(jì)與分析論文.

新形態(tài)對(duì)稱密碼算法類型包括分組密碼、流密碼和雜湊函數(shù).6 個(gè)分組密碼算法中, LowMC 采用P-SPN 結(jié)構(gòu), HADESMiMC 采用HADES 結(jié)構(gòu), Chaghri 和Jarvis 采用SPN 結(jié)構(gòu), MiMC 的兩種參數(shù)分別使用了SP 結(jié)構(gòu)和Feistel 結(jié)構(gòu), GMiMC 使用了Feistel 類結(jié)構(gòu).除了LowMC, 其他5 個(gè)算法的非線性層均使用有限域上的冪函數(shù), 其中MiMC、GMiMC 和HADESMiMC 都使用了立方函數(shù).Jarvis 的輪變換由可逆函數(shù)、仿射置換多項(xiàng)式和密鑰異或組成.雖然設(shè)計(jì)者聲稱設(shè)計(jì)靈感來源于AES, 但是整個(gè)狀態(tài)用一個(gè)S 盒, 和寬軌跡策略沒有關(guān)系, 該算法設(shè)計(jì)的重點(diǎn)是仿射置換多項(xiàng)式, 一方面為了安全性, 仿射置換多項(xiàng)式的次數(shù)要高, 項(xiàng)數(shù)要稠密, 保障輪函數(shù)的多項(xiàng)式表達(dá)式足夠復(fù)雜.另一方面, 為了適宜STARK實(shí)現(xiàn), 仿射置換多項(xiàng)式的次數(shù)或者其逆多項(xiàng)式的次數(shù)要盡可能小.LowMC 的設(shè)計(jì)亮點(diǎn)在于結(jié)構(gòu)P-SPN,同時(shí)為了安全性要求, 線性層使用偽隨機(jī)生成的二元可逆矩陣.15 個(gè)流密碼算法中, Ciminion、Aiminion和HYDRA 都采用了Farfalle 類結(jié)構(gòu), FLIP、FiLIP 和Elisabeth 采用了濾波置換器, Rasta 以及變體采用類ASASA 結(jié)構(gòu), Kreyvium 具有和Trivium 類似的結(jié)構(gòu), HERA 和Rubato 都是針對(duì)RtF 框架設(shè)計(jì)的適宜FHE 加密的流密碼算法.非線性層多使用二次或三次等低次函數(shù), 同時(shí)希望非線性層的逆函數(shù)具有高代數(shù)次數(shù).線性層多采用隨機(jī)生成的線性變換或者隨機(jī)數(shù), 因此, 一般需要一個(gè)隨機(jī)數(shù)生成器或者XOF 函數(shù).比如FLIP 采用基于AES-128 的一種隨機(jī)數(shù)生成器, 產(chǎn)生每一拍的隨機(jī)置換.Rasta 及其變體、HERA 和Rubato 都利用基于雜湊函數(shù)的XOF 函數(shù)生成隨機(jī)數(shù)或者隨機(jī)線性變換.10 個(gè)雜湊函數(shù),MiMCHash、GMiMCHash、POSEIDON、STARKAD、Reinforced Concrete、Anemoi 和GRIFFIN 算法都采用了Sponge 結(jié)構(gòu), Vision 和Rescue 采用參數(shù)化的SP 結(jié)構(gòu), Friday 采用MD 結(jié)構(gòu).MiMCHash和GMiMCHash 的內(nèi)部置換來源于分組密碼MiMC 和GMiMC, POSEIDON 和STARKAD 的內(nèi)部置換采用HADES 結(jié)構(gòu), POSEIDON 面向素域, S 盒采用5 次冪函數(shù), STARKAD 面向二元擴(kuò)域, S 盒采用3 次冪函數(shù).GRIFFIN 的內(nèi)部置換結(jié)合了Fluid-SPN 和擴(kuò)展Horst 結(jié)構(gòu), Horst 結(jié)構(gòu)是GRIFFIN 的亮點(diǎn).Anemoi 內(nèi)部置換的非線性部件采用Flystel 結(jié)構(gòu)設(shè)計(jì), 其中用到了平方和立方等冪函數(shù).Vision 和Rescue 分別面向二元擴(kuò)域和素域, S 盒采用逆函數(shù)和冪函數(shù).Friday 是基于Jarvis 分組密碼的HASH 函數(shù), 壓縮函數(shù)采用Miyaguchi-Preneel 結(jié)構(gòu).

總的來說, 新形態(tài)對(duì)稱密碼算法還處于起步階段.許多算法的非線性層設(shè)計(jì)相對(duì)簡(jiǎn)單, 采用低次數(shù)的冪函數(shù), 導(dǎo)致算法加密過程中的中間狀態(tài)可能存在線性或低次的多項(xiàng)式關(guān)系, 從而更易受到代數(shù)類分析方法的攻擊.比如針對(duì)Jarvis 的Gr?bner 攻擊、LowMC 的代數(shù)中間相遇攻擊、Chaghri 的代數(shù)次數(shù)的分析.算法結(jié)構(gòu)方面, 推出了P-SPN、HADES、FP、Farfalle 和Horst 結(jié)構(gòu)等, 對(duì)于這些結(jié)構(gòu)缺乏系統(tǒng)的安全性研究, 設(shè)計(jì)思路、構(gòu)造方式、參數(shù)選取等不同層次上均缺乏全面的理論基礎(chǔ).不同于傳統(tǒng)對(duì)稱密碼算法, 多數(shù)新形態(tài)對(duì)稱密碼算法定義在素域、整數(shù)環(huán)或者二元擴(kuò)域上, 而且運(yùn)算規(guī)模比較大; 其次, 由于非線性層相對(duì)簡(jiǎn)單, 新形態(tài)對(duì)稱密碼算法的線性層一般比較復(fù)雜, 而且部分算法采用了隨機(jī)生成的線性層;另外, 新形態(tài)對(duì)稱密碼算法的應(yīng)用場(chǎng)景比較特殊, 對(duì)于安全性分析的數(shù)據(jù)復(fù)雜度等有較強(qiáng)的限制.因此, 傳統(tǒng)的密碼分析技術(shù)難以應(yīng)用, 目前還沒有針對(duì)這類算法的系統(tǒng)分析方法.雖然統(tǒng)計(jì)類分析方法和代數(shù)攻擊等方式在對(duì)一些算法的分析中發(fā)揮了作用, 但可以注意到, 當(dāng)推出新算法時(shí), 很難對(duì)所有類型的攻擊做出令人信服的安全論證.因此, 研究如何將現(xiàn)有分析技術(shù)應(yīng)用到此類算法, 以及如何根據(jù)算法獨(dú)特的設(shè)計(jì)方式和結(jié)構(gòu)特點(diǎn)提出新的分析方法, 都是目前亟需解決的問題.本文介紹了新形態(tài)對(duì)稱密碼算法的發(fā)展歷程、設(shè)計(jì)目標(biāo)和理念、算法特點(diǎn)及最新的安全性評(píng)估成果, 致力于吸引國(guó)內(nèi)更多的學(xué)者參與其中, 推動(dòng)我國(guó)在相關(guān)領(lǐng)域的研究發(fā)展.