吳文玲, 王博琳

1.中國科學院 軟件研究所, 北京 100190

2.中國科學院大學, 北京 100049

1 引言

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

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

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

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

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

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

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

2 適宜MPC 的對稱密碼算法

2.1 LowMC

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

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

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

2.2 MiMC 及其變體

(1) MiMC

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

(2) GMiMC

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

(3) HADESMiMC

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

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

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

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

2.3 Ciminion 和HYDRA

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

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

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

3 適宜FHE 的對稱密碼算法

3.1 Kreyvium

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

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

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

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

3.2 FLIP 和FiLIP

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

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

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

3.3 Rasta 及其變體

(1) Rasta

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

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

(2) Dasta

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

(3) Masta

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

(4) Fasta

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

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

3.4 Pasta

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

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

3.5 Chaghri

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

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

3.6 HERA 和Rubato

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

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

3.7 Elisabeth

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

4 適宜ZK 的對稱密碼算法

4.1 Jarvis 和Friday

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

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

4.2 Vision 和Rescue

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

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

4.3 POSEIDON 和STARKAD

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

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

4.4 Reinforced Concrete

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

4.5 Anemoi

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

4.6 GRIFFIN

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

5 總結與展望

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

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

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