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

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

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

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

1 引言

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

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

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

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

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

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

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

2 基礎(chǔ)知識(shí)

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

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)向量稱為格的基, 基中的向量個(gè)數(shù)稱為格的維數(shù).

2.2 循環(huán)格

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

2.3 理想格

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

2.4 格上的困難問題

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

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

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

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

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

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

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

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

3.1 拒絕采樣

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

3.2 Ziggurat 采樣

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

3.3 積累分布表采樣

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

3.4 伯努利采樣

3.5 Knuth-Yao 采樣

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

3.6 二項(xiàng)采樣

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

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

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

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

4.1 Schoolbook multiplication 算法

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

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

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

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

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

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

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

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

在Zq上(q是素?cái)?shù)), 對(duì)于給定的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 變換存在的條件是: 第一, 對(duì)于q中的每一個(gè)素因子p,n都可以整除p- 1[66]. 第二,ω是n階原根,ωn= 1 modq且對(duì)于任何除數(shù)p,ωn/p/= 1 modq[67]. 如果q是素?cái)?shù),n是2 的冪,nmod(q-1)=1, NTT 變換可以使用快速算法計(jì)算.

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

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

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

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

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

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

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

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

在文獻(xiàn)[74] 的基礎(chǔ)之上, Aysu 等人[75]對(duì)NTT 模塊架構(gòu)進(jìn)行了進(jìn)一步的優(yōu)化, 首先, 在多項(xiàng)式系數(shù)載入階段, 與文獻(xiàn)[74] 中先計(jì)算后載入不同, 作者設(shè)計(jì)時(shí)鐘循環(huán)時(shí)刻表, 以增加1–2 個(gè)DSP 為代價(jià)實(shí)時(shí)產(chǎn)生預(yù)計(jì)算乘數(shù)因子φi, 在多項(xiàng)式系數(shù)載入的過程中, 并行完成NTT 變換預(yù)乘計(jì)算, 該方法節(jié)省了大量的ROM 資源和時(shí)鐘循環(huán). 其次, 在NTT 變換中的常數(shù)變換因子生成方面, 與文獻(xiàn)[74] 中將NTT 變換所需的常數(shù)變換因子存入ROM 中不同, 作者調(diào)整了NTT 變換主算法中兩個(gè)循環(huán)的順序, 根據(jù)設(shè)計(jì)好的時(shí)鐘循環(huán)時(shí)刻表, NTT 常數(shù)變換因子迭代循環(huán)實(shí)時(shí)產(chǎn)生, 不僅節(jié)省了大量的ROM 資源, 還避免了大量的內(nèi)存訪問. 最后, 作者發(fā)現(xiàn)在NTT 變換執(zhí)行過程中, 兩個(gè)多項(xiàng)式對(duì)應(yīng)的系數(shù)操作模式相同, 例如{ai,bi}系數(shù)對(duì), 在運(yùn)算過程中, 對(duì)預(yù)計(jì)算乘數(shù)和常數(shù)變換因子的需求和操作相同. 基于這個(gè)發(fā)現(xiàn)可以將兩個(gè)多項(xiàng)式對(duì)應(yīng)的系數(shù)以系數(shù)對(duì)的形式存入同一地址, 這樣操作不僅能夠節(jié)省內(nèi)存空間, 而且一次內(nèi)存訪問即可獲得2 個(gè)數(shù)據(jù), 降低了內(nèi)存訪問次數(shù), 提升了內(nèi)存訪問效率. 與文獻(xiàn)[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ù)變換因子生成方面, 作者也采用與文獻(xiàn)[75] 類似的迭代循環(huán)實(shí)時(shí)產(chǎn)生方法, 與文獻(xiàn)[75] 不同的是,ω的迭代放在次循環(huán)中, 而不是最內(nèi)側(cè)循環(huán), 這樣可以節(jié)省大量計(jì)算開銷. 在NTT 變換預(yù)乘計(jì)算方面, 作者將常數(shù)變換因子ω的初始值由1 變?yōu)棣?m, 巧妙的把negative-wrapped 卷積中需要提前預(yù)乘的φi融入到主算法中去, 不僅省去了正向NTT 變換預(yù)乘計(jì)算的時(shí)鐘循環(huán)消耗, 而且省去了文獻(xiàn)[75] 中的硬件乘法器. 在內(nèi)存優(yōu)化方面, 雖然都是在同一地址中存入1 組系數(shù)對(duì), 但是該方案與文獻(xiàn)[75] 不同, 計(jì)算開始, 一次讀取2個(gè)地址(獲取4 個(gè)數(shù)據(jù)), 進(jìn)行2 次蝶形計(jì)算, 將計(jì)算結(jié)果的4 個(gè)數(shù)據(jù)按照下一次蝶形計(jì)算的順序重新排列成2 個(gè)數(shù)據(jù)對(duì), 存入同一地址, 該內(nèi)存優(yōu)化不僅減少了內(nèi)存訪問次數(shù), 而且提高了內(nèi)存利用率. 如果模q的尺寸超過了18 bits (Virtex-6 中的BRAM 位寬最大36 bits), 多余的bit 值存儲(chǔ)在窄分布型RAM 中.

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

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

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

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

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

基于文獻(xiàn)[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) 次模乘法運(yùn)算. 基于文獻(xiàn)[82] 的思想, 作者利用Gentleman-Sande 時(shí)域抽取(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) 次模乘法運(yùn)算. 在消除NTT 和INTT 的預(yù)乘操作和后乘操作的過程中, 沒有增添額外的資源消耗和時(shí)鐘消耗. 由于NTT 和INTT 采用兩種不同的變換方式(DIF,DIT), 硬件中需要引入兩套蝶形計(jì)算單元, 隨后作者對(duì)這兩個(gè)蝶形單元進(jìn)行了壓縮和整合, 減少了資源占用. 內(nèi)存方面采用4 個(gè)雙端口RAM 滿足高速帶寬需求, 根據(jù)q=12289 采用一個(gè)DSP 并設(shè)計(jì)一套4 級(jí)流水線的高效模約減電路, 與通用的Barrett 和Montgomery 模約減電路相比更節(jié)省資源和時(shí)鐘循環(huán).

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

表3 格基硬件多項(xiàng)式乘法器對(duì)比Table 3 Lattice-based hardware polynomial multiplier comparison

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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