何詩洋, 李 暉, 李鳳華,3

1. 大數(shù)據(jù)安全教育部工程研究中心, 西安 710126

2. 西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院, 西安 710126

3. 中國科學(xué)院信息工程研究所, 北京 100093

1 引言

隨著人類計算能力的迅速提升, 特別是量子計算機的不斷突破(如中國科技大學(xué)潘建偉科研團隊構(gòu)建量子計算原型機“九章”[1]等), 基于大質(zhì)因數(shù)分解、離散對數(shù)困難問題的傳統(tǒng)密碼體制, 如公鑰加密、數(shù)字簽名、密鑰交換等方案的安全性都將面臨巨大威脅和挑戰(zhàn)[2]. 這種威脅和挑戰(zhàn)一方面體現(xiàn)在計算能力增強導(dǎo)致暴力破解成功率提升, 另一方面, 量子計算機和量子算法[3,4]能夠在多項式時間內(nèi)解決傳統(tǒng)密碼體制依賴的困難問題.

面對這一嚴(yán)峻形勢, 研究后量子密碼(post-quantum cryptography, PQC) 顯得極為緊迫和重要. 目前, 能夠抵抗量子攻擊的主流密碼體制有[5]: 基于編碼的密碼體制(code-base cryptography)、基于哈希函數(shù)的密碼體制(hash-based cryptography)、基于格的密碼體制(lattice-based cryptography)、多變量密碼體制(multivariate cryptography) 等.

相較于其他后量子密碼體制, 基于格的密碼體制具有明顯優(yōu)勢. 主要體現(xiàn)在: 第一, Ajtai 等人[6,7]證明了格中某些平均情況下的困難問題與NP 困難問題的難度等價, 具有較強的安全性[8]. 第二, 基于格的密碼體制不僅能夠應(yīng)用于傳統(tǒng)的安全場景如哈希函數(shù)[9]、公鑰加密[10]、數(shù)字簽名[11]、密鑰交換[12]等, 而且還具有良好的同態(tài)特性[13–15]. 第三, 基于格的密碼體制主要涉及矩陣向量之間的運算, 易于計算和實現(xiàn). 第四, 基于格的密碼體制與硬件實現(xiàn)相結(jié)合, 可部署場景廣泛, 既可應(yīng)用于資源豐富的平臺, 如云平臺、服務(wù)器平臺; 也可應(yīng)用于資源受限的平臺, 如穿戴醫(yī)療、移動設(shè)備等, 為它們提供強力的安全保障[16,17].

美國國家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology, NIST) 自2016 年12月開始面向全球公開征集并制定后量子密碼算法[18], 包括公鑰密碼(密鑰交換) 算法、數(shù)字簽名等. 截止2017 年12 月, 共收到76 份提交的后量子密碼算法申請, 經(jīng)過第一輪篩選, 共有69 個后量子密碼算法晉級下一輪候選[19]. 2019 年1 月, NIST 進一步精選了26 個后量子密碼算法進入第二輪候選[20]. 在前兩輪中, 基于格理論的后量子密碼算法占比約38% 和46%. 2020 年7 月, NIST 經(jīng)過綜合對比篩選了包括CLASSIC MCELIECE、CRYSTALS-KYBER、NTRU、SABER 等4 個公鑰密碼(密鑰交換) 算法與CRYSTALS-DILITHIUM、FALCON、RAINBOW 等3 個數(shù)字簽名算法進入第三輪[21]. 在這4 個公鑰密碼(密鑰交換) 算法中, CRYSTALS-KYBER、NTRU、SABER 等3 個算法都是基于格理論的密碼算法, 而在數(shù)字簽名的3 個算法中, CRYSTALS-DILITHIUM、FALCON 等2 個算法是基于格理論的密碼算法. 在所有候選算法中, 基于格理論的后量子密碼算法在數(shù)量上占優(yōu).

基于格理論的后量子密碼體制易于硬件高效實現(xiàn), 主要原因如下: 第一, 基于理想格構(gòu)造的格基密碼體制涉及大量多項式計算, 在硬件上多項式運算可以使用高效快速算法, 如快速傅里葉變換(fast Fourier transform, FFT) 和數(shù)論變換(number theoretic transform, NTT) 算法, 在硬件上實現(xiàn)快速算法能夠極大提高格基密碼方案的吞吐量. 在文獻[22] 中, 同樣使用硬件, 實現(xiàn)格基數(shù)字簽名不但比實現(xiàn)RSA 簽名速度更快而且資源消耗更少. 在文獻[23] 中, 在同等安全等級下, 硬件實現(xiàn)格基公鑰加密速度比ECC、RSA 快一個數(shù)量級, 而且資源消耗更少. 第二, 與軟件相比, 硬件具有高效并行處理這一獨特優(yōu)勢, 能夠快速處理密碼算法中的復(fù)雜計算, 吞吐量高. 在文獻[9] 中, 采用全并行架構(gòu)實現(xiàn)基于格的哈希函數(shù)算法, 吞吐量能夠達到0.6 GB/s, 約是軟件實現(xiàn)的16 倍. 第三, 出色的權(quán)衡性能. 硬件實現(xiàn)可以根據(jù)使用場景的不同, 在性能、資源消耗、功耗等方面進行權(quán)衡, 使格基密碼方案既可以部署在資源豐富的平臺如服務(wù)器平臺、云平臺等; 也可以部署在資源受限的平臺如物聯(lián)網(wǎng)平臺、穿戴醫(yī)療平臺、移動設(shè)備平臺等.

目前, 面向格基密碼體制的高效硬件實現(xiàn)是當(dāng)前研究的熱點, 有大量的研究成果和文獻, 但是缺乏系統(tǒng)性的總結(jié)和比較. 本文簡要介紹了格的基本概念以及格上的困難問題; 探討了格基密碼體制的主要優(yōu)勢以及其在公鑰加密、數(shù)字簽名、密鑰交換等方面的應(yīng)用價值; 在硬件實現(xiàn)格基密碼的模塊設(shè)計架構(gòu)中, 本文針對離散高斯采樣器、多項式乘法器這兩大主要模塊的主流優(yōu)化技術(shù)和實現(xiàn)方法進行了調(diào)研、總結(jié)和比較; 在硬件實現(xiàn)格基密碼的整體架構(gòu)中, 本文圍繞格基密碼在不同場景下的應(yīng)用、不同的硬件優(yōu)化目的(面向性能/面向資源) 等方面, 詳細(xì)分析和對比了當(dāng)前先進的設(shè)計理念和優(yōu)化技術(shù); 最后, 本文從安全性、靈活性、資源消耗、吞吐量等角度, 將格基密碼體制在硬件上的實現(xiàn)情況與其它實現(xiàn)方法進行對比分析, 充分展現(xiàn)其在實際應(yīng)用中的高效性和實用性, 為后量子密碼體制標(biāo)準(zhǔn)的制定以及后續(xù)格基密碼體制在實踐、應(yīng)用等方面的優(yōu)化和改進提供重要參考.

本文的剩余部分結(jié)構(gòu)如下, 第2 節(jié)重點介紹格的基礎(chǔ)知識, 格上的困難問題以及基于格的公鑰加密、數(shù)字簽名、密鑰交換方案在硬件中實現(xiàn)現(xiàn)狀; 第3 節(jié)重點介紹格基密碼方案硬件實現(xiàn)中的重要組成模塊離散高斯采樣器, 歸納和對比拒絕采樣算法、Ziggurat 采樣算法、積累分布表(cumulative distribution table, CDT) 采樣算法、伯努利采樣算法、Knuth-Yao 采樣算法、二項采樣算法等在硬件應(yīng)用中的特點和優(yōu)劣; 第4 節(jié)重點介紹格基密碼方案硬件實現(xiàn)中的重要組成模塊多項式乘法器, 討論了Schoolbook multiplication 算法和NTT 算法在不同應(yīng)用場景和優(yōu)化模式下的性能和資源消耗情況; 第5 節(jié)重點介紹了基于格的公鑰加密、數(shù)字簽名、密鑰交換方案在不同優(yōu)化模式、應(yīng)用場景下的架構(gòu)設(shè)計, 并分析它們的性能表現(xiàn)、資源消耗等; 第6 節(jié)對全文進行了簡要總結(jié).

2 基礎(chǔ)知識

本節(jié)主要介紹格上的相關(guān)定義、困難問題以及硬件實現(xiàn)格基密碼體制的現(xiàn)狀, 以下是本文用到的主要符號定義.

2.1 格的定義

設(shè)ν1,ν2,··· ,νn ∈Rm為一組線性無關(guān)向量, 格L是由向量ν1,ν2,··· ,νn的線性組合構(gòu)成的向量集合, 即:L={a1ν1+a2ν2+···+anνn:a1,a2,··· ,an ∈Z}. 任意一組可以生成格的線性無關(guān)向量稱為格的基, 基中的向量個數(shù)稱為格的維數(shù).

2.2 循環(huán)格

向量v=(ν1,ν2,··· ,νn)T的一次循環(huán)記為rot(v)=(νn,ν1,··· ,νn-1)T, 若對格L和?v ∈L, 都有rot(v)∈L, 則格L是循環(huán)格. 2002 年, Micciancio[24]首次提出了循環(huán)格的概念, 主要目的是用于緩解格基密碼體制中密鑰尺寸過大、運算效率較低等問題.

2.3 理想格

理想格是所有格向量的集合構(gòu)成某種環(huán)的一個理想. 設(shè)環(huán)R=Zq[X]/f(X), 其中f(X) =Xn+fn-1Xn-1+···+f0∈Z[X], 且f(X) 是n階首一不可約多項式. 相較于循環(huán)格, 理想格可以通過選擇適當(dāng)?shù)膄(X) 來控制格向量的長度, 在格基密碼體制中常用的f(X) 為:Xn+1, 其中n為2 的冪.在環(huán)Zq[X]/(Xn+1) 上構(gòu)造的理想格是目前實現(xiàn)硬件快速算法的最佳選擇. 2006 年, Lyubashevsky 和Micciancio[25]首次提出理想格的概念, 理想格能夠有效降低格基密碼中密鑰的空間占用, 利于構(gòu)造基于格的密碼方案; 同時理想格對內(nèi)具有乘法封閉性, 對外具有乘法吸收性, 這種優(yōu)勢還有利于構(gòu)造全同態(tài)加密方案.

2.4 格上的困難問題

格上困難問題的主要形式是找出滿足某種最小特征的格向量,最經(jīng)典的格難題是最短向量問題(SVP)和最近向量問題(CVP)[27]. Ajtai 等人[6,7]證明了最短向量問題(SVP) 在隨機歸約下是NP 困難問題,隨后CVP 問題也被證明是NP 困難問題. 如表1 所示,圍繞這兩個格上的經(jīng)典難題,學(xué)者進行了充分研究,通過問題規(guī)約等方法提出了一些新的格上的近似困難問題(更加利于密碼方案的構(gòu)造),如LWE(RLWE)、SIS (RSIS) 問題等. 目前, 大多數(shù)格基密碼體制的安全保障都是基于LWE (RLWE)、SIS (RSIS) 困難問題[25,28,29].

表1 格上的困難問題Table 1 Lattice problem

2.5 硬件實現(xiàn)格基密碼體制現(xiàn)狀

2005 年,Regev 等人[30]提出LWE 問題,并將解決該問題的困難程度規(guī)約到最壞情況下的格難題,同時給出了基于LWE 問題的公鑰加密方案. 以此為基礎(chǔ), 隨后很多學(xué)者相繼提出了該方案的改進型[31,32],進一步提升了格基公鑰加密方案的效率和安全性. 由于基于LWE 問題設(shè)計的密碼方案產(chǎn)生的密鑰和密文膨脹開銷過大(達到兆字節(jié)級), 計算效率低, 很難在實際中應(yīng)用. Lindner 和Peikert[33]基于理想格的思想, 提出了環(huán)上的LWE 問題, 并給出了基于RLWE 問題的格基公鑰加密方案, 該方案的密鑰和密文尺寸與基于LWE 問題的方案相比, 下降為原來的1/n, 在硬件實現(xiàn)中極大降低了內(nèi)存資源占用. 不僅如此, 在理想格結(jié)構(gòu)上, 硬件實現(xiàn)還可以部署快速算法如FFT、NTT 等, 進一步提高運算效率.

在格基數(shù)字簽名方面. 早期的格基數(shù)字簽名基于公鑰密碼方案修正而來, 缺乏安全證明, 比如NTRU數(shù)字簽名[34,35]提出不久后, 就被Nguyen 和Regev[36]破解. 直到2008 年, 第一個可證明安全的格基數(shù)字簽名由Gentry 等人[37]提出, 但是該方案產(chǎn)生的密鑰尺寸過大, 達到兆字節(jié)級, 效率很低. 隨后,Lyubashevsky[38,39]基于RSIS 問題構(gòu)造了一個較為成熟的簽名方案, 降低了密鑰和簽名尺寸. 以此為基礎(chǔ), Güneysu 等人[22]、P?ppelmann 等人[11]結(jié)合硬件特點, 構(gòu)造了新的格基簽名方案, 進一步降低密鑰和簽名尺寸, 提升了簽名效率.

在格基密鑰交換方面. 格基密鑰交換主要是基于協(xié)商或加密兩種方法實現(xiàn)[40]. Ding 等人[41]提出了第一個基于協(xié)商的格基密鑰交換方案, 隨后, 大量的基于協(xié)商的格基密鑰交換方案被學(xué)者提出,如Frodo[42]、BCNS[43]、NewHope[12]、Kyber[44]等. 基于加密的格基密鑰交換方案有NewHope-Simple[12], 與前者相比基于加密的方案比基于協(xié)商的方案占用更多帶寬[45].

3 格基密碼在硬件實現(xiàn)中的采樣器模塊

采樣在格基密碼方案中扮演著重要角色, 它不僅關(guān)系到整個格密碼方案的安全性, 而且它的運行效率直接影響整個密碼方案的性能. 在格基密碼方案中, 采樣通常來自均勻分布或離散高斯分布. 其中離散高斯采樣在格基密碼方案中應(yīng)用最為廣泛且具有眾多優(yōu)勢, 主要體現(xiàn)在, 利用離散高斯采樣能夠有效減小格基密碼方案中密文、簽名的尺寸, 通過在明文上加減離散高斯采樣噪聲來隱藏或恢復(fù)明文. 同樣離散高斯采樣也是硬件實現(xiàn)中的難點[46], 它的實現(xiàn)較為復(fù)雜, 主要體現(xiàn)在高精度的計算要求、大量隨機數(shù)和大尺寸查找表的需求以及高質(zhì)量統(tǒng)計距離的要求等, 迄今為止沒有任何計算可以獲得完美的離散高斯分布, 因此采樣器在設(shè)計的過程中要兼顧安全性、效率、資源消耗等因素, 使實際采樣精度與離散高斯分布盡可能相近. 除此之外, 在離散高斯采樣器實現(xiàn)的過程中還要考慮到時鐘循環(huán)信息泄漏的情況, 敵手會利用時鐘循環(huán)泄漏的信息對采樣器進行攻擊, 從而影響整個格基密碼方案的安全性[47]. NIST 在公開征求加密和簽名的方案中明確強調(diào), 方案中所采用的離散高斯采樣器必須能夠抵抗邊信道攻擊(side-channel analysis,SCA)[48]. 通常我們使用具有固定時鐘循環(huán)消耗的采樣器和隨機洗牌采樣器[49]應(yīng)對邊信道攻擊.

3.1 拒絕采樣

拒絕采樣算法首先從x ∈{-τσ,··· ,τσ}中均勻隨機采樣, 隨后采樣值x以概率exp(-x2/2σ2) 被接收. 拒絕采樣算法簡單直觀, 不需要預(yù)計算積累分布存儲表, 它是第一個被提出用于格基密碼方案的離散高斯采樣算法[37]. 由于拒絕采樣算法需要消耗大量硬件資源去計算e 的冪函數(shù), 同時還涉及浮點數(shù)的運算, 而且拒絕率高, 采樣成功率低, 所以拒絕采樣在格基密碼的硬件實現(xiàn)中很少直接使用. 在軟件實現(xiàn)中, Norman 等人[10]采用了文獻[37] 中的拒絕采樣算法, 采樣成功率僅有20%. 作者還利用了Devroye等人[52]提出的優(yōu)化拒絕采樣算法, 使采樣成功接收率提高至85.2%, 每產(chǎn)生108個采樣所消耗的時間由75 秒降至19 秒.

3.2 Ziggurat 采樣

Ziggurat 采樣一開始主要用于連續(xù)型高斯采樣[53], Buchman 等人[54]對該采樣進行了改進, 并應(yīng)用于離散高斯采樣中. Ziggurat 采樣首先生成多個自上而下面積相等的相鄰矩形, 以y軸為矩形的左邊, 矩形的右下角在高斯分布函數(shù)上, 并將該矩形右下角的坐標(biāo)(xi,yi) 存入數(shù)據(jù)表中. 采樣時, 在多個矩形中均勻隨機采樣, 隨后在被采樣的矩形中繼續(xù)隨機均勻采樣得到采樣值x, 如果x的值小于等于相鄰上方矩形右下角橫坐標(biāo)的值, 直接接收, 否則計算e 的冪函數(shù)決定是否接收(與拒絕采樣原理類似). 由于絕大部分采樣值小于上方相鄰矩陣的橫坐標(biāo), 無需計算e 的冪函數(shù)進行比較, 可以直接接收, 相比于普通的拒絕采樣算法, 極大地提高了采樣接收率, 進而提升了采樣效率. 在硬件實現(xiàn)方面, 與其他采樣算法相比,Ziggurat 采樣算法資源消耗大, 采樣速度低, 產(chǎn)生合適的矩形采樣需要大量乘法迭代等復(fù)雜運算[55], 在面向硬件實現(xiàn)的實際應(yīng)用中并不常見.

3.3 積累分布表采樣

積累分布表采樣由Peikert[56]首次提出, 該采樣算法需要提前計算離散高斯分布Pz ∈Pr(x≤z;x ←Dσ), 并將計算好的Pz存入積累分布表中, 由于該分布關(guān)于y軸對稱, 取z ∈[0,τδ], 可節(jié)省一半存儲空間, 一般需要的存儲空間約為τσλbits. 采樣時, 以λbits 的精度從y ∈[0,1) 中均勻隨機采樣(在硬件實現(xiàn)中,y使用小數(shù)的二進制表示), 從b ∈{0,1}中均勻隨機采樣, 得到采樣y,b后, 使用比較器, 在積累分布表中查找y ∈[Pz-1,Pz], 取出對應(yīng)的z, 輸出采樣值(-1)bz完成采樣. 積累分布表采樣算法避免了e 的冪函數(shù)和浮點數(shù)運算, 提高了計算效率, 但是由于引入了積累分布表, 需要耗費大量存儲空間進行存儲.

3.4 伯努利采樣

3.5 Knuth-Yao 采樣

Knuth-Yao 采樣算法[59]基于離散分布生成樹(discrete distribution generating, DDG), 在概率矩陣中采用二叉樹隨機游走的方式完成采樣. 其中概率矩陣是由分布概率P1,P2,··· ,Pn和精度系數(shù)λ組成的二進制矩陣. 離散分布生成樹根據(jù)概率矩陣生成, 它包含2 種節(jié)點, 分別是內(nèi)部節(jié)點(internal node)和末端節(jié)點(terminal node), 內(nèi)部節(jié)點下有2 個子節(jié)點, 末端節(jié)點下沒有子節(jié)點. 在概率矩陣中, 每一列的非零元素個數(shù)等于末端節(jié)點數(shù), 零元素個數(shù)等于內(nèi)部節(jié)點數(shù). 進行采樣時, 從離散分布生成樹樹頂部開始隨機向下面2 個子節(jié)點游走, 當(dāng)走到內(nèi)部節(jié)點時繼續(xù)隨機游走, 當(dāng)走到末端節(jié)點時停止游走, 并輸出采樣結(jié)果. 從信息論角度分析, 該方案近乎完美, 它需要的隨機輸入bits 只比分布的熵大2, 可以用較少的隨機bits 輸入完成離散高斯采樣, 該方案適用于高精度采樣. Roy 等人[60]首次利用硬件構(gòu)造Knuth-Yao采樣器, 作者針對離散分布生成樹的結(jié)構(gòu)進行了優(yōu)化, 在采樣前, 并不存儲整個離散分布生成樹, 而是在采樣過程中, 利用觀察節(jié)點和最右邊內(nèi)部節(jié)點的距離d實時構(gòu)建當(dāng)前層的樹結(jié)構(gòu), 這樣做可以節(jié)省計算資源和存儲開銷. 在概率矩陣存儲方面, 概率矩陣按列存儲, 且只存儲每一列中不同的元素, 通過優(yōu)化存取算法降低內(nèi)存消耗. 針對概率矩陣讀取掃描, 作者提出了兩種優(yōu)化方案, 分別是基于省略跳過的掃描方法和基于窗口的掃描方法, 兩者都可以提升掃描效率, 前者需要增加額外的存儲空間和移位器, 后者需要增加額外的乘法器. 該方案在Virtex-5 上實現(xiàn), 每完成一次采樣平均需要約5 個隨機bits 和17 個時鐘循環(huán).隨后Roy 等人[49]進一步優(yōu)化了Knuth-Yao 采樣器, 在面向資源節(jié)約型的硬件設(shè)計中, 作者通過約減只讀存儲器(read only memory, ROM) 的位寬和掃描寄存器來降低資源消耗, 與文獻[60] 相比減少17 個SLICEs 消耗; 在面向性能提升的硬件設(shè)計中, 作者利用專用的查找表存儲隨機bits 的初始位與采樣點的映射關(guān)系, 將采樣所需的時鐘循環(huán)次數(shù)由平均17 次降低為平均約2.5 次, 大幅度提升采樣性能; 在面向采樣器安全性的硬件設(shè)計中, 由于Knuth-Yao 算法在隨機游走時, 時鐘循環(huán)消耗不固定, 容易受到邊信道攻擊, 作者采用隨機洗牌法去除采樣中的時鐘循環(huán)信息, 保證采樣器安全.

3.6 二項采樣

二項采樣算法的硬件實現(xiàn)相對簡單, 首先從均勻分布中隨機獲取兩個k-bits 的向量, 隨后計算兩個向量的漢明距離并做差, 所獲得的采樣值即服從二項分布. 在一些格基密碼方案中, 如NewHope 等, 已經(jīng)開始使用二項分布(k= 2σ2) 替代離散高斯分布(exp(-x2/2σ2)). 文獻[12] 指出, 這樣的采樣分布替代不僅不會嚴(yán)重影響密碼系統(tǒng)的安全性, 使用二項分布采樣還具有避免e 冪函數(shù)的計算、不需要存儲表避免內(nèi)存占用、時鐘循環(huán)消耗固定能夠抵抗邊信道攻擊等優(yōu)勢. 由于k= 2σ2, 二項采樣不適用于對標(biāo)準(zhǔn)差要求較大的格基密碼方案, 例如數(shù)字簽名方案等. Oder 等人[61]在設(shè)計的二項采樣器硬件架構(gòu)中使用Trivium PRNG[11]隨機數(shù)生成器, 每個時鐘循環(huán)可獲得1 個隨機bit, 當(dāng)二項分布k= 16 時, 完成一次采樣需要33 個時鐘循環(huán).

普通拒絕采樣器原理簡單直觀, 易于實現(xiàn), 由于涉及到復(fù)雜運算(e 的冪函數(shù)), 且拒絕率高等劣勢, 在硬件實現(xiàn)中很少直接使用. Ziggurat 采樣器在拒絕采樣的基礎(chǔ)上進行了優(yōu)化, 大幅度減少了e 的冪函數(shù)計算(但并沒有消除), 提高了采樣成功率, 但是該算法資源消耗大, 采樣速率低, 在硬件實現(xiàn)中也并不多見. 根據(jù)表2 不難看出, 積累分布表采樣器能有效避免e 冪函數(shù)復(fù)雜計算, 采樣速度快, 但是由于引入了積累分布表, 增加了隨機存取存儲器(random access memory, RAM) 消耗. 在面向窄帶離散高斯分布采樣中, P?ppelmann[23]、Du 等人[57]對積累分布表采樣器進行優(yōu)化, 綜合考慮性能和資源消耗, 與其他采樣器相比, 積累分布表采樣器性能突出. 在面向大標(biāo)準(zhǔn)差離散高斯分布采樣中, P?ppelmann 等人[11]利用Peikert[56]卷積定理和Kullback-Leibler 散度定理, 對采樣器進行優(yōu)化, 在格基BLISS 數(shù)字簽名方案中,與伯努利采樣器相比, 積累分布表采樣器在吞吐量/資源消耗方面比伯努利采樣器性能更好. 伯努利采樣器通過按位采樣避免了e 的冪函數(shù)復(fù)雜運算,降低了資源消耗,結(jié)合二進制高斯分布,伯努利采樣器同樣可以用于大標(biāo)準(zhǔn)差離散高斯分布采樣, 在眾多采樣器中, 該采樣器需要的積累分布表尺寸最小. Knuth-Yao采樣器硬件資源消耗小, 采樣效率高, 采樣所需的隨機bits 輸入數(shù)量接近于分布的熵, 與其他采樣器相比需要的隨機bits 數(shù)最少, 但是該采樣器只適合用于面向窄帶離散高斯分布采樣, 不適合用于對離散高斯分布標(biāo)準(zhǔn)差要求較大的數(shù)字簽名方案.

4 格基密碼在硬件實現(xiàn)中的多項式乘法模塊

正如上文所述, 在眾多格基密碼方案中, 基于標(biāo)準(zhǔn)格的密碼方案由于涉及大量的復(fù)雜矩陣向量乘法、密鑰尺寸過大等問題, 資源消耗巨大, 并不適合硬件實現(xiàn). 而基于理想格的格基密碼方案, 在保證安全性的同時, 兼顧了計算效率和密鑰尺寸, 易于硬件實現(xiàn). 在理想格上, 格基密碼方案的計算主要是基于多項式環(huán)Rq=Zq[X]/(Xn+1)(通常情況下n是2 的冪,q是素數(shù)) 開展, 主要涉及多項式環(huán)Rq上的加/減法、乘法、模約減等, 其中加/減法的計算復(fù)雜度是O(n), 樸素乘法的計算復(fù)雜度為O(n2), 隨著多項式階n的不斷增大, 多項式乘法運算會變得非常復(fù)雜. 在硬件實現(xiàn)格基密碼方案的整個架構(gòu)中, 多項式乘法部分是最耗時、最耗資源的模塊. 基于理想格的格基密碼方案中最常用的多項式乘法算法是Schoolbook multiplication 算法和數(shù)論變換(NTT) 算法.

4.1 Schoolbook multiplication 算法

Schoolbook multiplication 算法在硬件實現(xiàn)中主要分為2 種, 第一種是橫向乘法, 先固定多項式a的一個系數(shù)與多項式b的所有系數(shù)相乘, 隨后再固定多項式a的另一個系數(shù)與多項式b的所有系數(shù)相乘, 順序進行, 直到全部乘法計算結(jié)束后再進行累加操作, 進而得出結(jié)果; 第二種是縱向乘法, 即兩個多項式相乘,固定多項式X的次冪, 依次計算X0,X1,··· ,Xn-1次冪的乘法結(jié)果. 在多項式環(huán)Rq上, 兩個多項式相乘, 采用Schoolbook multiplication 算法需要n2次模乘法運算和(n-1)2次模加/減法運算.

Güneysu 等人[22]在格基數(shù)字簽名方案的多項式乘法器模塊設(shè)計中采用Schoolbook multiplication算法, 模q約減電路利用Solinas[63]的思想, 采用輕量化設(shè)計. 雖然Schoolbook multiplication 算法的計算復(fù)雜度與其他(Karatsuba, NTT) 算法[64]相比較高, 但是它結(jié)構(gòu)規(guī)則, 資源占用少, 運行頻率高, 非常適合應(yīng)用在資源受限的設(shè)備上. 該多項式乘法器模塊在Spartan-6 上實現(xiàn), 消耗204 個SLICEs, 3 個BRAMs, 4 個DSP, 運行頻率可達300 MHz, 每秒能夠完成約1130 次多項式乘法計算.

Brakerski 等人[65]發(fā)現(xiàn), 在格基密碼方案中, 模約減q不一定必須是素數(shù), 如果q的值能取2 的冪次, 那么在硬件實現(xiàn)的模約減模塊中, 電路結(jié)構(gòu)將會變得簡單而高效. 在此發(fā)現(xiàn)的基礎(chǔ)上, P?ppelmann等人[58]在輕量化硬件格基公鑰加密方案中使用(n= 256,q= 4096,s= 8.35) 這一組高效參數(shù), 基于Schoolbook multiplication 算法設(shè)計多項式乘法器模塊. 模塊采用橫向乘法模式, 由2 個計數(shù)器和1 個模乘法內(nèi)核組成, 并將采樣過程融入到多項式計算中, 節(jié)省BUFFER, 降低資源消耗. 在Spartan-6 上整個加密模塊共消耗95 個SLICEs, 2 個BRAMs, 1 個DSP, 資源消耗下降明顯.

Liu 等人[62]針對Schoolbook multiplication 算法進行了進一步優(yōu)化. 作者發(fā)現(xiàn), 在σ= 4.51,q=7681 時,對于無符號的離散高斯采樣值需要使用13 bits 表示,而采用有符號的表示方法僅需要6 bits(1 bit 表示符號位, 5 bits 表示數(shù)據(jù)位). 利用這一發(fā)現(xiàn)可以有效降低對乘法器位寬的需求, 由26 bits (13 bits×13 bits) 降為17 bits (13 bits×5 bits). 在Xilinx7 系列芯片中, 由于DSP 支持25 bits×18 bits 位寬的乘法, 可以將2 個(13 bits×5 bits) 的乘法運算打包在一個DSP 中完成, 完成2 個乘法運算只需消耗一個時鐘循環(huán), 整體性能提升約2.2 倍.

根據(jù)表3 不難看出, 當(dāng)格基安全參數(shù)n和p較大時, Schoolbook multiplication 算法[22]效率較低.文獻[58] 采用輕量化設(shè)計, 引入新的高效參數(shù), 在保證性能的同時, 偏向資源節(jié)約型優(yōu)化, 降低多項式乘法器模塊的尺寸, 使整個格基公鑰加密算法架構(gòu)資源占用減少, 能夠部署在資源受限的設(shè)備中. 文獻[62] 利用bits 約減和DSP 復(fù)用技術(shù), 增強架構(gòu)性能, 在資源消耗增長不多的前提下, 與文獻[58] 相比吞吐量提升約4 倍.

4.2 數(shù)論變換算法(NTT)

NTT 算法的本質(zhì)是定義在有限域上的快速傅里葉變換(FFT),使用有限域上的單位原根代替了FFT中的復(fù)數(shù)原根, 由模q上的整數(shù)運算代替了浮點數(shù)運算. 使用快速NTT 算法能夠?qū)q上多項式乘法的計算復(fù)雜度降為O(nlogn), 當(dāng)多項式的階數(shù)n增大時, NTT 算法優(yōu)勢明顯. 該算法的應(yīng)用場景非常廣泛, 在數(shù)字信號處理中可用于濾波器、圖像濾波等, 在格基密碼方案中可用于多項式乘法的計算.

4.2.1 數(shù)論變換算法的基本概念

在Zq上(q是素數(shù)), 對于給定的n階單位原根ωn, 正向NTT 變換是將長度為n的向量a=(a0,a1,··· ,an-1) 變換為長度為n的向量A= (A0,A1,··· ,An-1), 表示為:A= NTT(a), 正向NTT變換定義為:

逆向NTT 變換是將長度為n的向量A= (A0,A1,··· ,An-1) 變換為長度為n的向量a=(a0,a1,··· ,an-1). 逆向NTT 變換表示為:a=NTT-1(A), 定義為:

NTT 變換存在的條件是: 第一, 對于q中的每一個素因子p,n都可以整除p- 1[66]. 第二,ω是n階原根,ωn= 1 modq且對于任何除數(shù)p,ωn/p/= 1 modq[67]. 如果q是素數(shù),n是2 的冪,nmod(q-1)=1, NTT 變換可以使用快速算法計算.

卷積理論[68]. 令ω是Zq上的2n階單位原根, 向量a= (a0,a1,··· ,an-1),b= (b0,b1,··· ,bn-1)為Zq上長度為n的向量. 在向量a,b后增加n個0, 得到向量a′= (a0,a1,··· ,an-1,0,··· ,0),b′=(b0,b1,··· ,bn-1,0,··· ,0), 長度為2n.a和b的卷積可以表示為:

利用卷積定理, 可以在多項式環(huán)Rq=Zq[X]/(Xn+1) 上做任意兩個多項式乘法, 首先在兩個多項式系數(shù)向量a,b后補n個0, 通過計算得到它們的NTT 變換, 對NTT 變換結(jié)果進行點乘, 對點乘結(jié)果進行INTT 變換, 再進行多項式模(Xn+1) 約減, 得到最終結(jié)果. 由于要在兩個系數(shù)向量后補0, INTT 變換后還要進行多項式模(Xn+1) 約減, 利用該卷積理論計算Rq上的多項式乘法效率較低.

Wrapped 卷積理論[68]. 令ω是Zq上的n階單位原根,φ2=ω. 向量a= (a0,a1,··· ,an-1),b=(b0,b1,··· ,bn-1) 為Zq上長度為n的向量.

(1)a,b的positive-wrapped 卷積為: INTT(NTT(a)°NTT(b)).

(2)a,b的negative-wrapped 卷積為: PowMulφ-1(INTT(NTT(a′)°NTT(b′))). 其中,a′=PowMulφ(a)=(a0,φa1,··· ,φn-1an-1).

Positive-wrapped 卷積定理適用于多項式模(Xn-1)約減,negative-wrapped 卷積定理適用于(Xn+1) 約減. 根據(jù)理想格Rq的定義, 可以利用negative-wrapped 卷積定理計算多項式乘法. 在φ存在,q為素數(shù),n為2 的冪,q= 1 mod 2n的條件下, 在Rq上的多項式乘法計算過程中可以避免在多項式系數(shù)向量后補0, 避免多項式模(Xn+1) 約減步驟, 節(jié)省內(nèi)存資源和時鐘循環(huán), 提高計算效率.

4.2.2 硬件中NTT 模塊的架構(gòu)設(shè)計

根據(jù)不同應(yīng)用場景對于吞吐量、資源消耗、能耗、時延等方面的需求, 目前主流的NTT 模塊設(shè)計方式有2 種. 第1 種, 采用流水線并行結(jié)構(gòu)[9,10], 每一個時鐘循環(huán)完成一個NTT 變換步驟. 這種并行結(jié)構(gòu)所帶來的優(yōu)勢是運算速度快, 吞吐量大, 劣勢是硬件資源消耗巨大(特別是內(nèi)存和寄存器). 第2 種, 緊致壓縮結(jié)構(gòu)[69,70]. 利用內(nèi)存、地址生成器(digital address generator, DAG)、少量的操作單元(processing element, PE), 進行迭代計算, 根據(jù)步驟順序執(zhí)行完成NTT 變換. 與第1 種方法相比, 雖然吞吐量有所降低, 但是節(jié)省資源, 能夠部署在資源受限的硬件設(shè)備上.

在文獻[9] 中, 由于安全參數(shù)n,p較小(n= 64,p= 257), Gy?rfi 等人設(shè)計了一套全并行流水線NTT 硬件架構(gòu), 由= 6 個蝶形步驟組成, 每個蝶形步驟包含64/2 = 32 個蝶形計算單元, 電路控制部分采用valid-ready 握手協(xié)議. 該方案采用diminished-one 數(shù)字系統(tǒng)[71], 在此數(shù)字系統(tǒng)上設(shè)計并優(yōu)化模加/減電路, 節(jié)省資源消耗, 提升計算效率. 乘法器采用查找表(look up table, LUT) 法實現(xiàn), 通過查表僅需一個時鐘循環(huán)即可得出計算結(jié)果. 該NTT 架構(gòu)吞吐量高, 在150 MHz 頻率運行下, 一個時鐘循環(huán)即可完成一次64 點NTT 變換, 但是代價是硬件資源消耗巨大, 在Virtex-5 上實現(xiàn), 僅NTT 模塊就需要3639 個SLICEs 和68 個BRAMs.

Gottert 等人[10]基于文獻[72] 架構(gòu)設(shè)計NTT 模塊, 也采用并行流水線結(jié)構(gòu). 根據(jù)原根的性質(zhì), 作者發(fā)現(xiàn)在INTT 計算過程中, 只需計算奇數(shù)項的INTT 即可得到多項式乘法約減后的結(jié)果, 簡化了計算過程. 模乘法采用Montgomery 乘法器[73], 由于整體架構(gòu)采用并行流水線結(jié)構(gòu), 資源消耗量仍然很大, 當(dāng)安全參數(shù)n ＞128 時, Virtex-6 器件的資源已經(jīng)無法滿足格基密碼方案的硬件架構(gòu)需求.

與上述兩種NTT 模塊架構(gòu)不同, P?ppelmann 等人[74]提出了基于內(nèi)存的緊致壓縮結(jié)構(gòu)NTT 模塊架構(gòu), 將NTT 變換需要的多項式系數(shù)和常數(shù)變換因子存入BRAM 中, 構(gòu)造1 個或少量的操作單元(PE)和地址生成器(DAG), 串行迭代計算NTT 變換. 隨著n的增大, NTT 模塊中除了BRAMs 的消耗線性增長明顯外, 其他單元硬件消耗變化不大. 模約減電路采用的是文獻[67] 的方案, 乘法器根據(jù)不同應(yīng)用場景可以采用DSP 法、LUT 法等. 與上述2 個方案相比, 該方案在硬件資源消耗方面下降明顯, 甚至可以在資源量較少的Spartan-6 上運行. 作者還設(shè)計了Schoolbook multiplication 算法架構(gòu)模塊, 并與NTT算法架構(gòu)模塊進行了對比, 在公鑰加密方案和半同態(tài)加密方案中, 隨著安全參數(shù)n的增大, NTT 算法架構(gòu)模塊在計算效率, 吞吐量方面優(yōu)勢明顯, 而Schoolbook multiplication 算法架構(gòu)模塊資源消耗少, 電路簡單, 運行頻率高.

在文獻[74] 的基礎(chǔ)之上, Aysu 等人[75]對NTT 模塊架構(gòu)進行了進一步的優(yōu)化, 首先, 在多項式系數(shù)載入階段, 與文獻[74] 中先計算后載入不同, 作者設(shè)計時鐘循環(huán)時刻表, 以增加1–2 個DSP 為代價實時產(chǎn)生預(yù)計算乘數(shù)因子φi, 在多項式系數(shù)載入的過程中, 并行完成NTT 變換預(yù)乘計算, 該方法節(jié)省了大量的ROM 資源和時鐘循環(huán). 其次, 在NTT 變換中的常數(shù)變換因子生成方面, 與文獻[74] 中將NTT 變換所需的常數(shù)變換因子存入ROM 中不同, 作者調(diào)整了NTT 變換主算法中兩個循環(huán)的順序, 根據(jù)設(shè)計好的時鐘循環(huán)時刻表, NTT 常數(shù)變換因子迭代循環(huán)實時產(chǎn)生, 不僅節(jié)省了大量的ROM 資源, 還避免了大量的內(nèi)存訪問. 最后, 作者發(fā)現(xiàn)在NTT 變換執(zhí)行過程中, 兩個多項式對應(yīng)的系數(shù)操作模式相同, 例如{ai,bi}系數(shù)對, 在運算過程中, 對預(yù)計算乘數(shù)和常數(shù)變換因子的需求和操作相同. 基于這個發(fā)現(xiàn)可以將兩個多項式對應(yīng)的系數(shù)以系數(shù)對的形式存入同一地址, 這樣操作不僅能夠節(jié)省內(nèi)存空間, 而且一次內(nèi)存訪問即可獲得2 個數(shù)據(jù), 降低了內(nèi)存訪問次數(shù), 提升了內(nèi)存訪問效率. 與文獻[74] 相比, 綜合性能提升明顯, 根據(jù)不同的安全參數(shù)n, 可節(jié)省BRAMs 約66%–80%, 節(jié)省BRAM 訪問次數(shù)約60%, 節(jié)省SLICEs 約52%–67%.

在前人的基礎(chǔ)之上, Roy 等人[76]提出了更加優(yōu)化的NTT 模塊架構(gòu). 在NTT 變換中的常數(shù)變換因子生成方面, 作者也采用與文獻[75] 類似的迭代循環(huán)實時產(chǎn)生方法, 與文獻[75] 不同的是,ω的迭代放在次循環(huán)中, 而不是最內(nèi)側(cè)循環(huán), 這樣可以節(jié)省大量計算開銷. 在NTT 變換預(yù)乘計算方面, 作者將常數(shù)變換因子ω的初始值由1 變?yōu)棣?m, 巧妙的把negative-wrapped 卷積中需要提前預(yù)乘的φi融入到主算法中去, 不僅省去了正向NTT 變換預(yù)乘計算的時鐘循環(huán)消耗, 而且省去了文獻[75] 中的硬件乘法器. 在內(nèi)存優(yōu)化方面, 雖然都是在同一地址中存入1 組系數(shù)對, 但是該方案與文獻[75] 不同, 計算開始, 一次讀取2個地址(獲取4 個數(shù)據(jù)), 進行2 次蝶形計算, 將計算結(jié)果的4 個數(shù)據(jù)按照下一次蝶形計算的順序重新排列成2 個數(shù)據(jù)對, 存入同一地址, 該內(nèi)存優(yōu)化不僅減少了內(nèi)存訪問次數(shù), 而且提高了內(nèi)存利用率. 如果模q的尺寸超過了18 bits (Virtex-6 中的BRAM 位寬最大36 bits), 多余的bit 值存儲在窄分布型RAM 中.

上面提到的NTT 模塊架構(gòu)在系數(shù)載入階段都需要進行bit 翻轉(zhuǎn)操作, 將載入的系數(shù)按照要求重新排列. 與他們的設(shè)計不同, Du 等人[70]提出, 在NTT 運算過程中通過bit 翻轉(zhuǎn)內(nèi)存訪問地址的方法實時讀取數(shù)據(jù), 從而避多項式系數(shù)載入時的bit 轉(zhuǎn)換操作, 以計算一次n階多項式乘法為例, 該方法能夠節(jié)省(3×2n= 6n) 次內(nèi)存訪問和(3×n= 3n) 次時鐘循環(huán). 受到Roy 等人[76]的啟發(fā), 作者將NTT 變換預(yù)乘因子φi融入到主算法中去, 節(jié)省計算開銷, 不同的是, 該方案中預(yù)乘因子φi不是實時計算產(chǎn)生, 而是存入ROM 中, 這樣做不僅能夠避硬件資源消耗(乘法器的使用), 還能夠節(jié)省時鐘循環(huán). 作者還利用消去引理[72], 將NTT 變換的預(yù)乘因子φi、常數(shù)變換因子ωj, INTT 變換的后乘因子φ-in-1、常數(shù)變換因子ω-j進行壓縮, 由4n個壓縮約減到2.5n個, 節(jié)省37.5% 的ROM 空間. 基于文獻[76] 的思想, 作者將NTT 主算法的兩個循環(huán)調(diào)轉(zhuǎn), 保證在一個循環(huán)內(nèi)蝶形計算所使用的常數(shù)變換因子相同, 減少了75%(n= 256) 和77% (n= 512) 的ROM 訪問次數(shù). 為了使蝶形操作單元的利用率最大化, 作者將需要相乘的兩個多項式系數(shù)存儲在兩個不同的RAM 中, 采取奇、偶交替的方式從兩個RAM 中讀取和寫入運算數(shù)據(jù), 完成兩組系數(shù)的NTT 變換. INTT 計算時, 將待變換的系數(shù)分半存在兩個RAM 中, 采用與NTT 一致的方法進行計算, 與文獻[74] 相比能夠節(jié)省約50% 的RAM 位寬.

針對能源供給受限的硬件設(shè)備, 如電池供電的物聯(lián)網(wǎng)設(shè)備、移動終端等. Fritzmann 等人[69]提出了首個面向低功耗、可拓展的NTT 架構(gòu). 與絕大多數(shù)采用雙端口RAM 的方案不同, 該方案使用單端口RAM,可以節(jié)省約30%的功耗. 在常數(shù)變換因子優(yōu)化方面,作者采取“半ROM 存儲半實時計算”的方式,在ROM 中存儲每一個蝶形變換步驟開始時需要的第一個常數(shù)變換因子(共logn個), 剩下的實時計算產(chǎn)生. 當(dāng)常數(shù)變換因子ω重新選定時, 只需替換ROM 中少量的常數(shù)變換因子即可, 增強了該NTT 架構(gòu)的可拓展性. 作者對NTT 和INTT 變換的最后一輪算法進行優(yōu)化, 一次讀取j和j+1 兩個地址的數(shù)據(jù)進行蝶形計算, 使用該方法可以節(jié)省n/4 個時鐘循環(huán). 在模約減電路設(shè)計方面采用Barrett 和Montgomery約減, 進一步提升約減效率, 增強了該方案的可拓展性, 但缺點是需要使用大量的DSP, 導(dǎo)致資源消耗增大. 為了約減INTT 的后乘操作, 作者引入了4 個乘數(shù)因子輔助計算, 將n-1和φ-i整合進主算法, 避免INTT 的后乘操作, 節(jié)省了時鐘循環(huán), 但就INTT 的后乘操作而言, 乘法計算的數(shù)量并沒有減少, 而且還需要增加額外的2 個乘法器, 該方案使用DSP 的總數(shù)量達到26 個.

在之前研究的基礎(chǔ)上, Ma 等人[77]面向資源節(jié)約型架構(gòu)進行優(yōu)化, 提出一套低資源消耗低功耗的NTT 架構(gòu), 優(yōu)化掉了NTT 模塊架構(gòu)中的DSP, 進一步提高了資源利用率和方案的通用性. 在模乘法器設(shè)計方面, 作者將多項式系數(shù)值采用D1-code 表示, 該方法表示的正整數(shù)比其真實值小1, 利用此方法, 模乘法的計算僅需簡單的bit-shift 和bit-reverse 即可, 不再需要DSP, 極大地簡化電路結(jié)構(gòu), 提升運行頻率.為了增強NTT 架構(gòu)的通用性, 作者采用一套蝶形單元. 在內(nèi)存訪問和管理方面, 作者采用Roy 等人[76]的方案, 在n階多項式計算中, 將內(nèi)存占用由5n降低為3n.

在面向可變參數(shù)的場景下, Mert 等人[78]針對NTT 算法的靈活性、可拓展性方面進行了進一步研究和優(yōu)化, 提出了可配置通用NTT 硬件處理器架構(gòu). 在模乘法器設(shè)計方面, 作者利用Montgomery 算法思想, 并對其進行優(yōu)化改進, 提出Word-Level Montgomery 模乘法器, 使其能夠支持多種階數(shù)的多項式環(huán)和多種位寬的模q; 在PE 設(shè)計方面, 采用Gentleman-Sande 型蝶形架構(gòu), 并在偶數(shù)項系數(shù)電路中添加寄存器, 以保證流水線流暢運行; 在內(nèi)存訪問方面, 為每個PE 配置2 個雙端口BRAMs. 該NTT 架構(gòu)可根據(jù)不同的應(yīng)用場景, 配置不同數(shù)量的PE, 能夠在性能和面積之間進行權(quán)衡, 作者還首次將該架構(gòu)應(yīng)用在同態(tài)加密的深度神經(jīng)網(wǎng)絡(luò)和格基數(shù)字簽名方案qTESLA 中, 在性能和面積權(quán)衡方面獲得了良好的效果.

Nguyen 等人[79]對NTT 模塊架構(gòu)進行進一步優(yōu)化. 在模約減電路方面, 作者采用文獻[80] 的思想,利用q=k·2m+1 的特殊結(jié)構(gòu), 設(shè)計約減電路KRED 和KRED2x; 在內(nèi)存管理方面, 作者提出先進的內(nèi)存回寫方案, 在NTT 架構(gòu)中采用4 個串行并行輸出(SIPO) 寄存器, 將計算結(jié)果按照下一次NTT 乘法次序?qū)懭雰?nèi)存, 進一步提高內(nèi)存利用率; 在整體架構(gòu)方面, 作者采用4 套蝶形單元, 一個時鐘循環(huán)能夠完成4 點NTT 變換, 采用多路選擇器控制整體架構(gòu)在乘法計算和NTT 變換計算之間來回切換, 進一步提高硬件資源利用率. 作者將此架構(gòu)在知名格基密碼方案NewHope、FALCON、qTESLA、CRYSTALSDILITHIUM 中進行應(yīng)用, 取得了良好效果. 但是由于該架構(gòu)采用4 點NTT 變換設(shè)計, 僅當(dāng)logN2為偶數(shù)時效率較高.

基于文獻[76]的思想,Zhang 等人[81]利用Cooley-Turkey 頻域抽取(decimation in frequency,DIF)型NTT 算法, 通過調(diào)整常數(shù)變換因子的初始值, 將NTT 變換預(yù)乘因子φi與主算法合并, 避免NTT 的預(yù)乘操作, 能夠節(jié)省22.2% (n= 512) 和20% (n= 1024) 次模乘法運算. 基于文獻[82] 的思想, 作者利用Gentleman-Sande 時域抽取(decimation in time, DIT) 型INTT 算法, 根據(jù)推導(dǎo)結(jié)果調(diào)整INTT 變換的常數(shù)變換因子的值, 將φi和n-1整合到INTT 變換的算法中去, 消除了INTT 變換的后乘操作, 節(jié)省了30.8% (n=512) 和28.6% (n=1024) 次模乘法運算. 在消除NTT 和INTT 的預(yù)乘操作和后乘操作的過程中, 沒有增添額外的資源消耗和時鐘消耗. 由于NTT 和INTT 采用兩種不同的變換方式(DIF,DIT), 硬件中需要引入兩套蝶形計算單元, 隨后作者對這兩個蝶形單元進行了壓縮和整合, 減少了資源占用. 內(nèi)存方面采用4 個雙端口RAM 滿足高速帶寬需求, 根據(jù)q=12289 采用一個DSP 并設(shè)計一套4 級流水線的高效模約減電路, 與通用的Barrett 和Montgomery 模約減電路相比更節(jié)省資源和時鐘循環(huán).

根據(jù)表3 可以看出, 文獻[9,10] 中設(shè)計的NTT 模塊架構(gòu)由于采用全并行結(jié)構(gòu), 計算速度快, 吞吐量大, 但當(dāng)n逐漸增大時, 資源消耗巨大, 很難部署在資源受限的硬件設(shè)備中. 文獻[74] 中設(shè)計的NTT 模塊架構(gòu)率先采用基于內(nèi)存的串行緊致壓縮結(jié)構(gòu), 與上述并行結(jié)構(gòu)的NTT 模塊架構(gòu)相比雖然吞吐量有所降低, 但是在資源消耗方面下降明顯, 能夠部署在更廣泛的應(yīng)用場景中. 在文獻[74] 的基礎(chǔ)上, 文獻[75] 以增加1–2 個DSP 的代價, 在吞吐量基本相同的前提下, 通過技術(shù)優(yōu)化進一步壓縮NTT 模塊架構(gòu)的面積,節(jié)省資源. 該方案中, 多項式系數(shù)成對存放在RAM 的同一地址中, 由于不同型號硬件中RAM 的位寬不同, 多項式系數(shù)的長度會有所限制. 在文獻[76] 中, 對NTT 主算法進行優(yōu)化, 減少了常數(shù)變換因子ω的計算開銷, 消除了NTT 變換預(yù)乘計算, 降低資源消耗, 提升了算法效率. 文獻[70] 的NTT 架構(gòu)設(shè)計以訪問地址翻轉(zhuǎn)代替系數(shù)載入時的bit 翻轉(zhuǎn), 針對內(nèi)存管理進行了全面優(yōu)化, 與文獻[74] 相比不僅SLICEs使用降低了約58.9%–61.1%、BRAMs 使用降低了約20%–37.5%, 而且吞吐量提升1.31–1.38 倍; 與文獻[75] 相比DSP 使用下降50%–67%、RAM 寬度減少50%, 吞吐量提升1.46–1.53 倍. 文獻[77] 采用了資源節(jié)約型設(shè)計思路, 對模乘法器進行重新設(shè)計, 與文獻[70] 相比, 雖然增加了部分FF 的消耗, 但是其整個架構(gòu)不需要DSP, 極大地提升了該架構(gòu)的通用性. 文獻[78] 提出Word-Level Montgomery 模乘法器,可以支持多種階數(shù)的多項式環(huán)和多種位寬的模q, 整體架構(gòu)還能夠根據(jù)應(yīng)用場景需求自動分配不同數(shù)量的PE, 與其他架構(gòu)相比, 雖然資源消耗偏大, 但是該架構(gòu)靈活性、通用性強, 能夠在面積和性能之間動態(tài)調(diào)配. 文獻[79] 采用4 套蝶形單元, 與其他架構(gòu)不同, 每個時鐘循環(huán)完成4 點NTT 變換, 采用4 個串行并行輸出寄存器對計算結(jié)果進行內(nèi)存回寫, 提升了資源利用率, 但是由于4 點NTT 變換設(shè)計, 該架構(gòu)僅對logN2為偶數(shù)時效率較高. 文獻[69] 在設(shè)計方面采用單端口RAM, 目的是降低NTT 模塊的功耗, 該方案在通用性、可拓展性方面做了很多優(yōu)化, 但代價是增加了26 個DSP 的使用. 文獻[81] 不僅消除了NTT變換預(yù)乘操作, 同時還消除了INTT 變換后乘操作, 針對特定的模q設(shè)計了專用的模約減電路, 極大地提升了運行效率, 綜合考慮計算效率、資源消耗, 文獻[81] 的NTT 模塊架構(gòu)性能最優(yōu).

表3 格基硬件多項式乘法器對比Table 3 Lattice-based hardware polynomial multiplier comparison

5 格基密碼方案的硬件實現(xiàn)

目前, 格基密碼被視為在后量子時代能夠有效抵抗量子攻擊的密碼算法之一, 在實際應(yīng)用中有望替代傳統(tǒng)密碼體制. 正如前文所述, 硬件具有能夠部署快速算法、并行處理、權(quán)衡性能與資源消耗等特點和優(yōu)勢. 利用硬件實現(xiàn)格基密碼方案自然而然成為了當(dāng)前研究的熱點, 圍繞計算性能、資源消耗、功耗等方面,各路學(xué)者對其進行優(yōu)化提升, 提出了大量新穎的研究成果. 本節(jié)中, 我們討論和對比格基密碼方案在公鑰密碼、數(shù)字簽名、密鑰交換方面的硬件實現(xiàn)和優(yōu)化設(shè)計.

5.1 格基公鑰加密方案的硬件實現(xiàn)

格基公鑰加密方案的硬件實現(xiàn)對比詳情如表4 所示. Gottert 等人[10]分別對軟硬件實現(xiàn)格基公鑰加密方案進行了評估. 在軟件實現(xiàn)方面, 作者使用集成NTL 庫, 在Linux 系統(tǒng)上完成格基公鑰加密方案, 其中高斯采樣使用拒絕采樣算法. 在硬件實現(xiàn)方面, 作者給出了一組硬件友好型格基安全參數(shù), 在多項式乘法器模塊中, 作者在文獻[72] 算法的基礎(chǔ)上進一步優(yōu)化, 消除了逆NTT 一半的剩余乘法操作, 約減了關(guān)鍵路徑, 提升了模塊性能. 同時, 作者使用線性反饋移位寄存器(linear feedback shift register, LFSR) 和RAM 設(shè)計了一套基于查找表的硬件離散高斯采樣器, 采樣速度提升明顯. 在相同安全等級下, 硬件實現(xiàn)格基公鑰密碼方案比軟件實現(xiàn)在加密、解密方面分別快200 倍和70 倍. 由于采用全并行結(jié)構(gòu), 該方案資源消耗巨大, 當(dāng)安全參數(shù)n ＞128 時, Virtex-6 上的硬件資源已經(jīng)無法滿足該方案的需求.

表4 格基公鑰密碼硬件實現(xiàn)對比Table 4 Comparison of hardware implementation of lattice-based public key cryptography

P?ppelmann 等人[23]發(fā)現(xiàn)去掉密文c2中的一些低bit 位數(shù)據(jù)并不會影響解密的正確性, 利用這一發(fā)現(xiàn)能夠有效降低密文膨脹. 在提高解密正確率方面, 與以往1 bit 消息隱藏在1 個多項式系數(shù)中不同,作者通過將1 bit 消息隱藏在u個多項式系數(shù)中的方法, 大幅提高解密正確性. 同時作者對之前的架構(gòu)進行了進一步優(yōu)化, 在文獻[74] 的基礎(chǔ)上, 將簡單的多項式乘法器拓展為成熟的可配置微代碼引擎. 同時首次設(shè)計并采用積累分布表離散高斯采樣器. 所有模塊時鐘循環(huán)消耗固定, 能夠抵抗邊信道攻擊. 與全并行架構(gòu)的文獻[10] 相比, 在n= 256 時, 密鑰生成、加密、解密資源消耗分別減小為原來的1/32、1/65、1/27, 而性能只下降約33%–50%.

Roy 等人[76]設(shè)計了一個高效緊致的格基公鑰加密方案硬件處理器. 首先, 作者將NTT 模塊中negative-wrapped 卷積的預(yù)乘計算融合到主算法中去, 消除了negative-wrapped 卷積的預(yù)乘計算, 同時進一步優(yōu)化實時計算常數(shù)變換因子的結(jié)構(gòu), 減少了時鐘循環(huán)和內(nèi)存占用. 其次, 作者優(yōu)化內(nèi)存訪問機制, 按照下一輪NTT 變換順序存儲和訪問數(shù)據(jù). 最后, 作者對NTT 主算法流水線結(jié)構(gòu)進行優(yōu)化, 簡化關(guān)鍵路徑提高運行頻率, 將處理器的加密系統(tǒng)構(gòu)架由5 組NTT 模塊降低為4 組, 速度提升20%. 方案中的離散高斯采樣使用文獻[60] 提到的Knuth-Yao 型采樣器. 作者在Virtex-6 上實現(xiàn)該架構(gòu), 與文獻[23] 相比,本方案在性能和資源消耗方面都占優(yōu).

Brakerski 等人[65]發(fā)現(xiàn), 格基公鑰密碼中q不一定必須為素數(shù), 可以為2 的冪, 并給出了一組安全參數(shù)(256,4096,8.35), 這組安全參數(shù)對于硬件實現(xiàn)來講非常高效. 在此基礎(chǔ)上, P?ppelmann 等人[58]在多項式乘法器模塊中, 采用資源消耗更低的Schoolbook multiplication 算法多項式乘法器. 在離散高斯采樣器模塊中, 作者采用伯努利型離散高斯采樣器, 與文獻[49] 的Knuth-Yao 型采樣器相比, 雖然需要增大隨機bit 的消耗, 但是可以節(jié)省10 個SLICEs. 作者采用一系列優(yōu)化技術(shù), 進一步降低了格基公鑰密碼硬件實現(xiàn)的資源消耗, 該方案可以在資源量較少的Spartan-6 上實現(xiàn), 雖然吞吐量有所下降, 但是與文獻[23]相比, 整體資源消耗下降明顯.

5.2 格基數(shù)字簽名方案的硬件實現(xiàn)

格基數(shù)字簽名方案的硬件實現(xiàn)對比詳情如表5 所示. Güneysu 等人[22]在文獻[38,39] 格基簽名方案的基礎(chǔ)上進行了部分優(yōu)化, 基于DCKp,n問題(決策型緊湊背包問題), 在保證安全證明的前提下, 采用壓縮算法, 使簽名和密鑰尺寸降低了近一半. 在該方案的硬件架構(gòu)中, 作者設(shè)計的隨機數(shù)生成器模塊、Schoolbook multiplication 乘法器模塊、簽名驗證模塊跨越3 個時鐘域. 由于簽名算法有一定拒絕率, 為保證簽名和驗證速度, 該方案設(shè)計了大量BUFFER 用于存儲多項式對, 在s·c的計算中, 一旦檢測出某個系數(shù)超過拒絕采樣值, 立即停止當(dāng)前計算和壓縮, 從BUFFER 中載入新的多項式對重新計算. 該方案可以運行在硬件資源較少的Spartan-6 上, 與運行在Virtex-4 上的RSA 簽名[83]相比, 不僅資源消耗減少一半, 而且性能提升1.5 倍.

表5 格基數(shù)字簽名硬件實現(xiàn)對比Table 5 Comparison of hardware implementation of lattice-based digital signature

Ducas 等人[51]進一步優(yōu)化了Lyubashevsky 的格基簽名方案[39], 作者結(jié)合雙峰高斯分布, 針對原方案的核心拒絕采樣算法進行了重新設(shè)計, 新方案在同等安全等級下, 比RSA 和ECDSA 更加高效, 同時進一步降低簽名和密鑰尺寸. P?ppelmann 等人[11]采用了這種雙峰格基簽名方案(BLISS), 并設(shè)計了對應(yīng)的硬件架構(gòu), 在資源較少的Spartan-6 上首次使用硬件實現(xiàn)該數(shù)字簽名算法. 該硬件架構(gòu)與文獻[22]類似, 采用2 級流水線結(jié)構(gòu), NTT 多項式乘法與哈希函數(shù)并行執(zhí)行. 作者利用Peikert[56]的卷積定理和Kullback-Leibler 散度定理進一步設(shè)計和優(yōu)化了積累分布表離散高斯采樣器, 有效降低了采樣器積累分布表的內(nèi)存占用, 提高了采樣效率. 與伯努利采樣器相比, 每次采樣消耗更少的隨機比特和時鐘循環(huán). 與文獻[22] 方案相比不僅資源占用少, 而且簽名和驗證速度更快, 效率更高.

Güneysu 等人[84]基于文獻[38,39] 的理論基礎(chǔ)上, 對簽名方案進行改進, 將簽名尺寸降低為原來的一半, 并給出安全證明. 作者設(shè)計了驗證專用單元、簽名專用單元和簽名驗證單元, 具體包括隨機數(shù)生成器模塊、輕量化的哈希函數(shù)模塊、高效NTT 模塊等. 該方案的理論部分與文獻[22] 類似, 不同之處主要在于2 個方面, 第一, 多項式乘法模塊由Schoolbook multiplication 算法替換為NTT 算法, 提高了多項式乘法計算效率. 第二, 簽名中z1,z2的計算由串行優(yōu)化為并行. 與文獻[22] 相比, 該硬件架構(gòu)不僅在簽名速度方面提升約1.8 倍, 在驗證速度方面提升約7.4 倍, 而且資源消耗有所下降.

5.3 格基密鑰交換方案的硬件實現(xiàn)

格基密鑰交換方案的硬件實現(xiàn)對比詳情如表6 所示. Oder 等人[61]首次在 FPGA 上實現(xiàn)了NewHope-Simple[12]格基密鑰交換方案. 文中采樣器使用k= 16 的二項采樣替代離散高斯采樣, 能夠減少內(nèi)存占用, 提高性能. 在生成隨機多項式a時, 采用1 個SHAKE-128 和3 個分析器并行采樣,使拒絕概率可以忽略不計. 多項式乘法模塊采用NTT 算法, 在文獻[82] 的基礎(chǔ)上進行優(yōu)化, 正向NTT變換采用Cooley-Turkey 蝶形單元, INTT 變換采用Gentleman-Sande 型蝶形單元, 蝶形單元采用2 個DSP 并行計算, 提高計算效率. 模q約減采用與文獻[11] 相同的方法. 該方案在兼顧性能的同時, 面向資源節(jié)約方向進行優(yōu)化, 使之能夠部署在資源受限的設(shè)備上, 在Artix-7 上運行頻率為117 MHz, 完成一次密鑰交換協(xié)議需要350 416 個時鐘循環(huán). 該硬件架構(gòu)消耗時鐘循環(huán)固定, 能夠抵抗邊信道攻擊.

表6 格基密鑰交換硬件實現(xiàn)對比Table 6 Comparison of hardware implementation of lattice-based key exchange

在前人研究的基礎(chǔ)上, Kuo 等人[85]進一步優(yōu)化了NewHope 密鑰交換方案, 提出了一個高性能硬件實現(xiàn)架構(gòu). 在生成多項式a的隨機均勻系數(shù)時, 為了避免采樣偏執(zhí), 作者對16 bits (5q) 采樣值進行拒絕采樣, 成功接收概率為93.76%. 采樣器方面, 與文獻[61] 一致, 使用二項分布替代離散高斯分布. 在NTT模塊和協(xié)商機制模塊設(shè)計中, 作者分別采用4 個蝶形單元和2 套HelpRec/Rec 電路, 與文獻[61] 相比,硬件資源消耗增多約4 倍. 隨后, 作者在K-RED 模塊中, 采用4 級流水線架構(gòu), 在模約減電路中, 采用Longa-Naehrig 技術(shù), 提高運行頻率, 降低資源消耗, 與文獻[61] 相比, 在性能方面提升約19 倍. 綜合考慮性能和資源消耗, 該方案優(yōu)勢明顯.

6 結(jié)束語

本文回顧了格基密碼的歷史、背景、基礎(chǔ)知識以及在公鑰密碼、數(shù)字簽名、密鑰交換等領(lǐng)域的應(yīng)用現(xiàn)狀. 介紹了格基密碼體制硬件實現(xiàn)架構(gòu)中的兩大重要模塊, 離散高斯采樣器模塊和多項式乘法器模塊.對比分析了不同離散高斯采樣器的特點以及其在實踐中的應(yīng)用, 同時還重點介紹和對比了Schoolbook multiplication 算法和NTT 算法在多項式乘法器模塊中的應(yīng)用, 根據(jù)不同優(yōu)化方向(面向性能或面向資源) 探討了不同改進型多項式乘法器模塊的架構(gòu)和優(yōu)劣. 最后, 討論和分析了格基密碼體制中公鑰密碼、數(shù)字簽名、密鑰交換等在硬件實現(xiàn)中的具體設(shè)計思路和實現(xiàn)細(xì)節(jié).

在后量子時代, 格基密碼體制以其強大的安全性、高效性、靈活性、實用性等特點從眾多后量子密碼體制中脫穎而出. 格基密碼體制與硬件實現(xiàn)相結(jié)合, 更加凸顯其實用性和高效性的優(yōu)勢, 相信在不久的未來, 格基密碼體制能夠替代傳統(tǒng)密碼體制, 在實際中得到廣泛應(yīng)用.