郝世迪， 孫冬旎， 梁志闖， 鄭婕妤， 沈詩(shī)羽， 趙運(yùn)磊

1. 復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院， 上海 200433

2. 復(fù)旦大學(xué) 軟件學(xué)院， 上海 200433

1 引言

公鑰密碼學(xué)由Whitfield Diffie 與Martin Hellman 于1976 年首次提出[1]， 現(xiàn)已有各種基于不同困難問(wèn)題的公鑰密碼體制. 目前應(yīng)用廣泛的公鑰密碼RSA (基于大整數(shù)分解問(wèn)題) 和ECC (基于橢圓曲線離散對(duì)數(shù)問(wèn)題)， 能被Shor 量子算法[2]在量子計(jì)算機(jī)上多項(xiàng)式時(shí)間內(nèi)攻破. 為了應(yīng)對(duì)量子計(jì)算的迅速發(fā)展， 能夠抵抗量子攻擊的密碼—后量子密碼成為國(guó)內(nèi)外研究的熱點(diǎn).

基于標(biāo)準(zhǔn)格的方案中耗時(shí)的運(yùn)算是有限域上的矩陣乘法， 而基于理想格和模格的方案中基礎(chǔ)且耗時(shí)的運(yùn)算是多項(xiàng)式的乘法. 數(shù)論變換(NTT) 因?yàn)槠涑錾臄M線性復(fù)雜度O(nlogn)， 成為計(jì)算多項(xiàng)式乘法最高效的算法. 另外， NTT 在算法和實(shí)現(xiàn)上還有諸多的優(yōu)點(diǎn): (1) 計(jì)算向量-向量多項(xiàng)式乘法時(shí)能利用NTT的線性性減少逆向NTT 個(gè)數(shù); (2) 用戶存儲(chǔ)多項(xiàng)式的NTT 的結(jié)果不需要額外的內(nèi)存開(kāi)銷， 并能夠多次使用多項(xiàng)式的NTT 結(jié)果; (3) NTT 能夠進(jìn)行即位運(yùn)算(指的是一對(duì)數(shù)據(jù)經(jīng)過(guò)一個(gè)蝴蝶操作的結(jié)果仍存放在原來(lái)這對(duì)數(shù)據(jù)的內(nèi)存地址中)， 并利于高度向量化實(shí)現(xiàn). 這些優(yōu)點(diǎn)使得那些能夠使用NTT 的方案的計(jì)算效率更優(yōu).

美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院(NIST) 于2016 年開(kāi)始面向全球發(fā)起后量子密碼標(biāo)準(zhǔn)化的算法征集工作，征集范圍主要是PKE、KEM 和數(shù)字簽名. 目前， NIST 公布了進(jìn)入第三輪的15 個(gè)算法[5]， 其中， 七個(gè)決賽算法會(huì)作為通用算法， 未來(lái)得到更深入的研究和更廣泛的應(yīng)用; 此外還有八個(gè)算法作為備選， 可用來(lái)進(jìn)一步優(yōu)化提升或服務(wù)于具體的應(yīng)用. 在七個(gè)候選決賽算法中有五個(gè)是基于格構(gòu)造的. 其中基于MLWE 的Kyber[6]和基于MLWR 的Saber[7]被認(rèn)為是非常有前途的KEM 方案. 特別地， Saber 其所有模數(shù)均為2 的方冪， 這帶來(lái)以下優(yōu)勢(shì): 避免使用較為復(fù)雜的拒絕采樣; 不需要顯式的模約減模塊， 可直接通過(guò)移位操作完成模約減. 但是， 另外一方面， 其不是NTT 友好素?cái)?shù)， 因此不能使用NTT 來(lái)加速多項(xiàng)式乘法.Saber 轉(zhuǎn)向使用Karatsuba/Toom-Cook 算法， 但它們?cè)趯?shí)現(xiàn)效率方面明顯劣于NTT. 然而， 近期工作[8]表明， 結(jié)合中國(guó)剩余定理(CRT)， Saber 也能使用NTT 計(jì)算多項(xiàng)式乘法， 進(jìn)而提高其計(jì)算效率.

如今NIST 后量子密碼標(biāo)準(zhǔn)算法競(jìng)賽已進(jìn)行到了第三輪， 制定標(biāo)準(zhǔn)算法需要兼顧安全性、實(shí)現(xiàn)效率等性能. 而對(duì)格密碼的研究雖然熱度非常高但尚不成熟， 考慮到Saber 在NIST 后量子密碼標(biāo)準(zhǔn)征集中的出色表現(xiàn)， 對(duì)其進(jìn)行優(yōu)化實(shí)現(xiàn)是十分重要的. 本文主要對(duì)Saber 進(jìn)行優(yōu)化， 提出了對(duì)Saber 進(jìn)行改進(jìn)的一種方案: 結(jié)合CRT， 選取最優(yōu)參數(shù)對(duì)Saber 使用NTT 加速多項(xiàng)式乘法. 本文工作對(duì)后量子密碼標(biāo)準(zhǔn)算法的優(yōu)化和實(shí)際應(yīng)用具有重要現(xiàn)實(shí)意義.

1.1 主要貢獻(xiàn)

本文的主要貢獻(xiàn)有以下3 個(gè)方面:

(1) 本文對(duì)Saber 提出一套新參數(shù)集， 相比原參數(shù)， 新參數(shù)集可以更好的平衡錯(cuò)誤率、安全強(qiáng)度和通信帶寬的關(guān)系.l= 2 時(shí)， 通信帶寬節(jié)省了96 字節(jié)， 約6.8%， 量子安全強(qiáng)度由2107提高為2111;l= 3，4 時(shí)， 新參數(shù)可以在相近的安全強(qiáng)度下(172 對(duì)比170， 236 對(duì)比228)， 擁有更低的錯(cuò)誤率(分別從2-136， 2-165降低為2-138， 2-187) 和更小的通信帶寬(分別節(jié)省192 字節(jié)， 約9.2% 和64 字節(jié)， 約2.3%).

(2) 本文應(yīng)用NTT 與CRT 結(jié)合的方式計(jì)算多項(xiàng)式乘法， 為了給該方案選定兩個(gè)NTT 友好素?cái)?shù)， 本文根據(jù)新參數(shù)(向量維數(shù)、多項(xiàng)式維度、模數(shù)和中心二項(xiàng)分布參數(shù)) 的具體取值， 并考慮到16 位之內(nèi)的素?cái)?shù)適合于NTT 的AVX2 實(shí)現(xiàn)， 最終選取NTT 友好素?cái)?shù)為q1= 7681 和q2= 3329.選取這兩個(gè)素?cái)?shù)有如下幾點(diǎn)好處: ①選取的素?cái)?shù)3329 有利于正向NTT 使用延遲約減的策略; ②選取素?cái)?shù)3329 能夠降低本文方案私鑰的尺寸; ③本文使用了跟Aigis-512/768 相同的模數(shù)7681，以及跟Kyber Round3 相同的模數(shù)3329， 這便于在軟件實(shí)現(xiàn)上復(fù)用它們的代碼， 硬件實(shí)現(xiàn)上共享它們的NTT 模塊.

(3) 本文針對(duì)Saber 的新參數(shù)進(jìn)行了AVX2 優(yōu)化實(shí)現(xiàn). 具體而言， 對(duì)算法中的約減模塊、多項(xiàng)式運(yùn)算模塊、中心二項(xiàng)分布模塊、私鑰序列化模塊、并行壓縮模塊以及并行編碼/解碼模塊等進(jìn)行AXV2優(yōu)化實(shí)現(xiàn). 實(shí)驗(yàn)結(jié)果表明， 本文在多項(xiàng)式乘法模塊方面相比于Saber Round3 使用的Toom-Cook算法，算法性能平均提升約37%. 其中，向量與向量乘法的性能平均提升47%，矩陣與向量乘法平均提升27%. 另外， 本文的AVX2 優(yōu)化實(shí)現(xiàn)相比于C 參考實(shí)現(xiàn)， 密鑰生成算法性能提升約86%，密鑰封裝算法提升約88%， 密鑰解封裝算法提升約90%; 相比于Saber Round3 的AVX2 實(shí)現(xiàn)，密鑰生成算法性能提升約21%， 密鑰封裝算法提升約23%， 密鑰解封裝算法提升約23%.

1.2 相關(guān)工作

在NIST 后量子密碼標(biāo)準(zhǔn)化的算法征集第三輪中， Saber 是唯一的基于MLWR 的密鑰封裝方案.Saber 首先基于MLWR 困難問(wèn)題構(gòu)造一個(gè)IND-CPA 安全的公鑰加密方案; 接著通過(guò)Fujisaki-Okamoto轉(zhuǎn)換[9]得到IND-CCA 安全的密鑰封裝方案. Saber 使用Karatusba/Toom-Cook 計(jì)算多項(xiàng)式乘法. 現(xiàn)階段對(duì)Saber 的優(yōu)化主要分為兩部分: 一是對(duì)多項(xiàng)式乘法的算法進(jìn)行優(yōu)化， 二是多平臺(tái)的軟硬件優(yōu)化實(shí)現(xiàn). 文獻(xiàn)[10] 對(duì)Saber 使用了時(shí)間-內(nèi)存平衡的Toom-Cook 算法. 文獻(xiàn)[11] 將NTT 應(yīng)用于Saber 的多項(xiàng)式乘法， 提升算法效率. 文獻(xiàn)[12] 對(duì)Saber 使用AVX2 指令來(lái)并行批處理， 包括使用SHAKE-128 生成偽隨機(jī)數(shù)， 使用SHA3 進(jìn)行哈希以及多項(xiàng)式乘法三部分. 除此之外， 文獻(xiàn)[13] 在ARM Cortex-M 上實(shí)現(xiàn)了Saber， 并在速度和內(nèi)存占用方面進(jìn)行了優(yōu)化. 文獻(xiàn)[14] 采用CRT 與NTT 結(jié)合的方式， 設(shè)計(jì)了可應(yīng)用于Saber 的加速模塊， 文中針對(duì)n= 256 的情況， 選取q1= 12289，q2= 13313，q3= 15361. 文獻(xiàn)[15]提出了一種基于NTT 的快速多項(xiàng)式算法的通用硬件體系結(jié)構(gòu). 即便是Saber 參數(shù)均為二次冪， 也能直接應(yīng)用NTT 通用組件， 無(wú)需更改硬件設(shè)計(jì)， 并且在此基礎(chǔ)上提出了Saber 的首個(gè)掩碼HW/SW 協(xié)同設(shè)計(jì).

2 預(yù)備知識(shí)

本節(jié)主要介紹一些預(yù)備知識(shí)， 包括基本定義與符號(hào)表示、Saber 算法、數(shù)論變換以及AVX2 指令集.

2.1 基本定義與符號(hào)表示

2.2 Saber

Saber 是文獻(xiàn)[7] 基于MLWR 設(shè)計(jì)的IND-CCA 安全的密鑰封裝方案. Saber 的構(gòu)造分以下兩步:第一步， 構(gòu)造得到IND-CPA 安全的公鑰加密方案(PKE); 第二步， 通過(guò)Fujisaki-Okamoto 轉(zhuǎn)換[9]得到IND-CCA 安全的密鑰封裝方案(KEM). 為方便讀者能夠直觀地理解， Saber 的IND-CPA 安全的公鑰加密方案的偽代碼見(jiàn)算法1-3， IND-CCA 安全的密鑰封裝方案KEM 詳細(xì)偽代碼見(jiàn)附錄. 其中， gen 為某輸出偽隨機(jī)的擴(kuò)展函數(shù)， 在Saber 中使用的是SHAKE-128.h1和h2是兩個(gè)常數(shù)多項(xiàng)式:h1= 2?q-?p-1，h2= 2?p-2-2?p-?T-1+2?q-?p-1. 其模約減操作和乘等操作可直接通過(guò)移位來(lái)完成. 另外， 不需要拒絕采樣生成A ∈Rl×lq. Saber 選擇的參數(shù)如p，q均為2 的方冪， 詳細(xì)參數(shù)見(jiàn)表1. 其中|pk|、|ct|、|B| 分別表示公鑰長(zhǎng)度、密文長(zhǎng)度以及總帶寬， 單位為字節(jié)，δ表示錯(cuò)誤率， Classical Core-SVP 表示Core-SVP的經(jīng)典安全強(qiáng)度， Quantum Core-SVP 表示Core-SVP 的量子安全強(qiáng)度.

表1 Saber 原參數(shù)表Table 1 Parameters of Saber

算法1 Saber.PKE.KeyGen Input: None Output: pk := (seedA，b)，s 1 seedA$←- {0，1}n 2 A = gen(seedA) ∈Rl×l q 3 s ←βl μ 4 b = ((ATs+h) mod q) ?(?q -?p) ∈Rl×1 p 5 return (pk := (seedA，b)，s)

算法2 Saber.PKE.Enc Input: pk := (seedA，b)，m ∈R2 Output: c := (cm，b′)1 A = gen(seedA) ∈Rl×lq 2 s′ ←βl μ 3 b′ = ((As′ +h) mod q) ?(?q -?p) ∈Rl×1p 4 v′ = bT(s′ mod p) ∈Rp 5 cm = (v′ +h1 -2?p-1m mod p) ?(?p -?T) ∈RT 6 return c := (cm，b′)算法3 Saber.PKE.Dec Input: s，c = (cm，b′)Output: m′1 v = b′(sT mod p) ∈Rp 2 m′ = ((v-2?p-?T cm +h2) mod p) ?(?p -1) ∈R2 3 return m′

2.3 數(shù)論變換

數(shù)論變換(NTT) 是離散傅立葉變換(DFT) 在有限域上的特殊情形. 標(biāo)準(zhǔn)的基于負(fù)折疊卷積[16，17]的n點(diǎn)NTT 需要參數(shù)滿足q ≡1 (mod 2n)， 其中n是2 的方冪，q是素?cái)?shù). 正向NTT 為?f=NTT(f)，詳細(xì)地:

Rq中多項(xiàng)式乘法h=fg ∈Rq能夠通過(guò)h= INTT(NTT(f)°NTT(g)) 計(jì)算， 其中°表示點(diǎn)乘.FFT-trick[18]是計(jì)算NTT 的快速算法， 其復(fù)雜度為O(nlogn)， 而直接計(jì)算NTT 的復(fù)雜度為O(n2).由于ζn=-1 (modq)， 則有xn+1=(xn/2-ζn/2)(xn/2+ζn/2)， 正向FFT-trick 使用中國(guó)剩余定理表示為:

圖1 Cooley-Turkey 蝴蝶Figure 1 Cooley-Turkey butterfly

圖2 Gentleman-Sande 蝴蝶Figure 2 Gentleman-Sande butterfly

FFT-trick 計(jì)算NTT 的偽代碼見(jiàn)文獻(xiàn)[19]. 完整的FFT-trick 過(guò)程能夠表示為:

其中br(i) 表示無(wú)符號(hào)整數(shù)i的比特翻轉(zhuǎn)值. 完整的FFT-trick 樹(shù)形圖表示見(jiàn)圖3:

圖3 完整的FFT-trick 樹(shù)形圖Figure 3 Complete FFT-trick tree diagram

FFT-trick 的計(jì)算過(guò)程并非必須進(jìn)行到線性多項(xiàng)式項(xiàng). 在文獻(xiàn)[6] 中， 正向FFT-trick 只進(jìn)行到:

得到NTT 域中的n/2 個(gè)線性多項(xiàng)式， 其中只需要Zq中n次本原單位根ω存在. 點(diǎn)乘是對(duì)應(yīng)線性多項(xiàng)式的乘法. 然后再做逆向FFT-trick. 這種NTT 稱為“不完整的NTT”[8]， 或者“裁剪的NTT”[20]， 它能弱化NTT 的參數(shù)限制條件到q ≡1 (modn). “裁剪NTT” 的FFT-trick 樹(shù)形圖見(jiàn)圖4.

圖4 “裁剪NTT” 的FFT-trick 樹(shù)形圖Figure 4 FFT-trick tree diagram of truncated NTT

其中，mi=(q1q2···qi-1)-1mod±qi.

文獻(xiàn)[8] 利用這種方法計(jì)算Saber 的Rq中的多項(xiàng)式乘法h=fg ∈Rq， 因?yàn)镾aber 的q不是NTT友好素?cái)?shù)， 即q=2eq′+1 的形式， 無(wú)法在Rq中直接使用NTT. 簡(jiǎn)單來(lái)說(shuō)， 文獻(xiàn)[13] 考慮到Saber 中多項(xiàng)式的系數(shù)取值范圍， 選取N=q1q2， 其中q1= 7681 和q2= 10 753 都是NTT 友好素?cái)?shù). 使用NTT分別計(jì)算f，g在Zqi[x]/(xn+1) 中的積， 再通過(guò)定理1 得到ZN[x]/(xn+1) 中的結(jié)果. 最后模q便得到f，g在Rq中的積.

2.4 AVX2 指令集

2008 年， 英特爾發(fā)布了高級(jí)矢量擴(kuò)展(AVX) 指令集， 引入了256 位寬矢量指令. 這是對(duì)之前適用于128 位XMM 寄存器的SSE 指令集的改進(jìn). 除了從128 位寬度擴(kuò)展到256 位寬度的SIMD 操作之外，AVX 還支持3、4 操作數(shù)， 且擁有更為寬松的內(nèi)存對(duì)齊約束. AVX 在被稱為ymm 的256 位SIMD 寄存器上運(yùn)行， 分為兩個(gè)128 位通道: 高通道和低通道. 大多數(shù)指令在“通道內(nèi)” 工作， 即每個(gè)源元素僅應(yīng)用于同一通道的其他元素， 不同通道不能互取數(shù)據(jù).

AVX2 是2011 公布的AVX 的擴(kuò)展， 它將多數(shù)128 位SIMD 整數(shù)指令擴(kuò)展為256 位. AVX2 支持4路64 位整數(shù)加法、異或和向量移位[21]. AVX 由Sandy Bridge 微架構(gòu)的英特爾處理器支持. 第一個(gè)商業(yè)化的處理器是2011 年1 月發(fā)布的的Core i7 和Core i5. 而AVX2 指令集是Intel 在2013 年的Haswell 22 nm 架構(gòu)上首次引入的.

3 Saber 方案新參數(shù)選取與優(yōu)化實(shí)現(xiàn)

3.1 方案算法描述及新參數(shù)選取

本文使用顯式中國(guó)剩余定理(定理1) 和NTT 來(lái)計(jì)算Saber 中的多項(xiàng)式乘法， 其中， IND-CPA 安全的PKE 的偽代碼見(jiàn)算法4-6， KEM 的偽代碼見(jiàn)附錄.

算法4 密鑰生成算法PKE.KeyGen Input: None Output: pk := (seedA，b)，sk := (?s1，?s2)1 seedA$←- {0，1}n 2 A = gen(seedA) ∈Rl×l q 3 s ←βl μ 4 ?s1 = NTT1(s)5 ?s2 = NTT2(s)6 b1 = INTT1(NTT1(AT)° ?s1)7 b2 = INTT2(NTT2(AT)° ?s2)8 b = CRT(b1，b2)9 b = ((b+h) mod q) ?(?q -?p) ∈Rl×1 p 10 return (pk := (seedA，b)，sk := (?s1，?s2))算法5 公鑰加密算法PKE.Enc Input: pk := (seedA，b)，m ∈R2 Output: c := (cm，b′)1 A = gen(seedA) ∈Rl×l q 2 s′ ←βl μ 3 ?s′1 = NTT1(s′)4 ?s′2 = NTT2(s′)5 b′1 = INTT1(NTT1(A)° ?s′1)6 b′2 = INTT2(NTT2(A)° ?s′2)7 b′ = CRT(b′1，b′2)8 b′ = ((b′ +h) mod q) ?(?q -?p) ∈Rl×1 p 9 v′1 = INTT1(NTT1(bT)° ?s′1)10 v′2 = INTT2(NTT2(bT)° ?s′2)11 v′ = CRT(v′1，v′2)12 cm = (v′ +h1 -2?p-1m mod p) ?(?p -?T) ∈RT 13 return c := (cm，b′)算法6 解密算法PKE.Dec Input: s，c = (cm，b′)Output: m′1 v1 = INTT1(?sT1 °NTT1(b′))2 v2 = INTT2(?sT2 °NTT2(b′))3 v = CRT(v1，v2)4 m′ = ((v-2?p-?T cm +h2) mod p) ?(?p -1) ∈R2 5 return m′

下文將對(duì)算法4-6 的具體細(xì)節(jié)進(jìn)行解釋. 算法4 和算法5 中的A ∈Rl×lq由gen(seedA) 生成， 其以seedA為種子通過(guò)SHAKE128 哈希函數(shù)產(chǎn)生隨機(jī)比特串， 然后將每12 個(gè)比特拼接成一個(gè)系數(shù). 該哈希函數(shù)每次只能產(chǎn)生168 個(gè)字節(jié)， 針對(duì)l= 2，3，4 的情況分別需要運(yùn)行10 次， 21 次， 37 次才能產(chǎn)生相應(yīng)長(zhǎng)度的比特串.

算法4-6 使用的CRT() 函數(shù)， 將輸入的兩個(gè)多項(xiàng)式(向量) 的系數(shù)通過(guò)定理1 計(jì)算它們的中國(guó)剩余定理顯式解. 如算法6 第3 行的v=CRT(v1，v2) 是將多項(xiàng)式v1和v2中對(duì)應(yīng)分量上的系數(shù)通過(guò)定理1 計(jì)算得到v中對(duì)應(yīng)分量的結(jié)果.

表2 給出了本文Saber 優(yōu)化實(shí)現(xiàn)方案的參數(shù)選取. 本文對(duì)于LightSaber、Saber、FireSaber 三種情況， 使用統(tǒng)一的q=212=4096， 以及q1=7681，q2=3329.|pk|、|ct|、|B|分別表示公鑰長(zhǎng)度、密文長(zhǎng)度以及總帶寬， 單位為字節(jié)，δ表示錯(cuò)誤率， Classical Core-SVP 表示Core-SVP 的經(jīng)典安全強(qiáng)度， Quantum Core-SVP 表示Core-SVP 的量子安全強(qiáng)度. 其中， 錯(cuò)誤率和安全強(qiáng)度的數(shù)據(jù)根據(jù)Saber Round3 提供的Sage 腳本測(cè)試得到.

表2 新參數(shù)表Table 2 New parameters for Saber

本文提出的新參數(shù)與原參數(shù)(見(jiàn)表1) 相比:q由213減小為212;p在l=2，3 的情況下， 由210減小為29;T在l=2，3，4 的情況下， 由23、24、26統(tǒng)一為24. 其中， 公鑰長(zhǎng)度|pk|=(l?pn/8)+|seedA|， 故對(duì)于Saber、FireSaber 參數(shù)集， 新參數(shù)的公鑰長(zhǎng)度會(huì)減少ln/8， 即分別減少了64 字節(jié)、96 字節(jié); 三組參數(shù)的密文長(zhǎng)度|ct|=(l?pn/8)+?T n/8 也分別減少了32 字節(jié)、96 字節(jié)、64 字節(jié).

LightSaber 新參數(shù)與原參數(shù)相比， 通信帶寬|B| =|pk|+|ct| 節(jié)省了96 字節(jié)， 約6.8%， 經(jīng)典安全強(qiáng)度由2118提高為2122， 量子安全強(qiáng)度由2107提高為2111; Saber、FireSaber 新參數(shù)可以在相近的安全強(qiáng)度下(189 260 對(duì)比187 251)， 以更低的錯(cuò)誤率(從2-136、2-165降低為2-138、2-187) 和更小的通信帶寬(分別節(jié)省192 字節(jié)， 約9.2% 和64 字節(jié)， 約2.3%) 封裝256 比特的密鑰. 可以看到本文提出的LightSaber 新參數(shù)規(guī)模變小， 但安全強(qiáng)度提高了， 這是因?yàn)楸疚氖褂玫腟aber Round3 提供的Sage 腳本是基于文獻(xiàn)[22] 提供的模擬器， 此模擬器測(cè)試(M)LWR 安全強(qiáng)度需要把其轉(zhuǎn)換為(M)LWE 方式測(cè)試.其中， 影響安全強(qiáng)度的變量有向量維數(shù)和多項(xiàng)式維度的積(l*n)、模數(shù)q、秘密多項(xiàng)式的分布(參數(shù)為μ的中心二項(xiàng)分布) 以及噪音分布. 新參數(shù)表中減小了模數(shù)q和p的值， 噪音分布不變，l*n的值不變， 假如保持參數(shù)μ不變， 此時(shí)求解(M)LWR 問(wèn)題會(huì)更加困難， 安全強(qiáng)度會(huì)變高， 但同時(shí)錯(cuò)誤率也會(huì)變高. 所以本文減小了中心二項(xiàng)分布的參數(shù)μ， 以平衡安全強(qiáng)度和錯(cuò)誤率. 以上分析表明本文提出的新參數(shù)可以更好地平衡安全強(qiáng)度、錯(cuò)誤率和通信帶寬的關(guān)系.

3.2 多項(xiàng)式的表示

在Saber 算法中， 多項(xiàng)式使用長(zhǎng)度為n的數(shù)組來(lái)存儲(chǔ)， 其中多項(xiàng)式的每一個(gè)系數(shù)的類型定義為無(wú)符號(hào)16 位整型. 本文的多項(xiàng)式系數(shù)使用[-q/2，q/2)∩Z 中的代表元來(lái)表示. 與采用無(wú)符號(hào)16 位整型相比，這樣做的優(yōu)勢(shì)有以下兩點(diǎn): (1) 在進(jìn)行系數(shù)相減操作時(shí)， 若出現(xiàn)負(fù)數(shù)結(jié)果， 則可直接存儲(chǔ)， 不需要額外操作(如模q) 使其轉(zhuǎn)換為正值. (2) 常見(jiàn)高效的模約減算法， 如Barrett 約減[23]和Montgomery[24]約減(詳細(xì)偽代碼見(jiàn)算法7 和算法8) ， 均作用于有符號(hào)整型. 這使得本文的方案能夠使用以上高效模約減算法， 從而提升實(shí)現(xiàn)效率.

算法7 Barrett 約減Input: -β/2 ≤a ＜β/2， 0 ≤q ＜β/2 Output: r ≡a (mod q)，0 ≤r ≤q 1 v = ■2■log(q)」-1β/q■2 t = ■va/(2■log(q)」-1β)」3 t = tq mod β 4 r = a-t 5 return r算法8 樸素Montgomery 約減Input: -β/2 ≤a ＜β/2，-(q-1)/2 ≤b ≤(q-1)/2 Output: r ≡β-1ab (mod q)1 t0 = ■ab/β」 //得到a，b 乘積的高位2 v = ab mod β //得到a，b 乘積的低位3 v = vq-1 mod ±β 4 t = ■vq/β」5 r = t0 -t 6 return r

3.3 基于NTT 的方案改進(jìn)優(yōu)化

多項(xiàng)式乘法操作主要應(yīng)用于矩陣-向量乘法和向量-向量乘法. 在此以向量-向量乘法為例來(lái)進(jìn)行參數(shù)選擇說(shuō)明. 在Saber 中， 需要計(jì)算v=sTb， 其中s和b均為l維的多項(xiàng)式向量， 每個(gè)元素是n維的多項(xiàng)式. 利用NTT 的線性性，v能夠通過(guò)下式計(jì)算:

其中，si系數(shù)取值范圍為[-μ/2，μ/2]，bi系數(shù)取值范圍為[-q/2，q/2)， 則v的系數(shù)在Z 上的取值范圍為[-nqμl/4，nqμl/4]. 本文選取兩個(gè)素?cái)?shù)q1，q2使得在數(shù)值上滿足q1q2＞nqμl/2. 除此之外， 還需考慮到:(1) 為了能夠使用NTT，q1，q2需要是NTT 友好素?cái)?shù). (2) 為了方便使用AVX2 指令進(jìn)行高效的并行計(jì)算，q1，q2需選擇在16 比特以內(nèi). (3) 在滿足前兩點(diǎn)的基礎(chǔ)上， 為了能夠在存儲(chǔ)數(shù)據(jù)時(shí)節(jié)省內(nèi)存開(kāi)銷，q1，q2盡量小.

將表2 中對(duì)應(yīng)的參數(shù)值n= 256，q= 4096， 以及三個(gè)參數(shù)集中μ，l的最大值μ= 4，l= 4 代入q1q2＞nqμl/2. 本文選擇q1= 7681，q2= 3329. 可見(jiàn)，q1≡1 (mod 2n)， 可對(duì)模數(shù)7681 使用標(biāo)準(zhǔn)的NTT. 但由于3329 不滿足256 點(diǎn)標(biāo)準(zhǔn)NTT 的參數(shù)條件， 只滿足q2≡1 (modn)， 故本文對(duì)模數(shù)3329使用裁剪NTT. 具體而言， 本文使用256 點(diǎn)7 層的裁剪NTT， 點(diǎn)乘不再是對(duì)應(yīng)數(shù)值的乘法， 而是對(duì)應(yīng)線性多項(xiàng)式的乘法. 對(duì)模數(shù)7681 使用2n次本原單位根ζ= 62， 使用8 層的完整的NTT; 對(duì)模數(shù)3329 使用n次本原單位根ω=17， 使用7 層的裁剪的NTT.

圖5 給出了以v=sTb為例， 使用CRT 與NTT 計(jì)算向量-向量乘法的詳細(xì)過(guò)程. 需要說(shuō)明的是，圖中l(wèi) ∈{2，3，4}，q= 4096，q1= 7681 以及q2= 3329. 對(duì)多項(xiàng)式向量進(jìn)行正向NTT 和逆向NTT(INTT)、多項(xiàng)式向量之間的點(diǎn)乘和CRT 函數(shù)， 都跟4.1 節(jié)的介紹相同， 其中CRT 對(duì)輸入v1和v2通過(guò)定理1 得到Rq1q2中的多項(xiàng)式.

圖5 使用NTT 計(jì)算向量-向量乘法Figure 5 Compute vector-vector multiplication by using NTT

在此將詳細(xì)分析選取q1=7681，q2=3329 這兩個(gè)NTT 友好素?cái)?shù)帶來(lái)的三點(diǎn)好處:

(1) 本文選取的q2= 3329 有利于正向NTT 使用延遲約減的策略. 裁剪NTT 的正向NTT 共需要計(jì)算7 層. 在每一層的CT 蝴蝶操作中， 我們調(diào)用Montgomery 約減來(lái)計(jì)算系數(shù)和本原單位根的積， 而其輸出的數(shù)值范圍為(-q2，q2). 正向NTT 每計(jì)算一層， 多項(xiàng)式系數(shù)范圍便擴(kuò)大(-q2，q2).由于多項(xiàng)式系數(shù)初始范圍為[-q2/2，q2/2)， 那么經(jīng)過(guò)7 層的計(jì)算之后， 其輸出的系數(shù)范圍依然在有符號(hào)16 位整型可以表示的范圍內(nèi)， 且無(wú)數(shù)據(jù)溢出情況發(fā)生. 因此無(wú)需在正向NTT 過(guò)程中進(jìn)行Barrett 約減， 而是在完成整個(gè)正向NTT 后才進(jìn)行Barrett 約減. 這大大減少額外約減操作，提高算法實(shí)現(xiàn)效率.

(2) 在本文的Saber 優(yōu)化實(shí)現(xiàn)方案中傳輸?shù)乃借€為(?s1，?s2)， 其中?s2的系數(shù)取值范圍為[0，q2). 存儲(chǔ)?s2的系數(shù)只需要12 比特. 相比文獻(xiàn)[8] 選擇的模數(shù)10 753， 本文選取的3329 能夠降低私鑰的尺寸， 減少私鑰占用的存儲(chǔ)空間. 對(duì)于LightSaber、Saber、FireSaber 三種情況(對(duì)應(yīng)l=2，3，4)，私鑰的尺寸分別能夠減少128、192、256 字節(jié).

(3) 7681 和3329 是基于理想格和模格方案常用的模數(shù)， 其中， 7681 是全國(guó)密碼算法設(shè)計(jì)競(jìng)賽獲獎(jiǎng)算法Aigis[25]在Aigis-512/768 參數(shù)集下使用的模數(shù)， 而3329 是Kyber-Round3 使用的模數(shù). 本文使用了跟它們相同的模數(shù)， 這便于在軟硬件實(shí)現(xiàn)上進(jìn)行代碼復(fù)用. 詳細(xì)來(lái)說(shuō)， 在軟件實(shí)現(xiàn)方面，本文使用模數(shù)7681 的NTT 時(shí)可復(fù)用Aigis-512/768 的代碼， 使用模數(shù)3329 的NTT 時(shí)可參考Kyber-Round3 的代碼; 在硬件實(shí)現(xiàn)方面， 本文方案能夠跟Aigis-512/768 和Kyber-Round3共享NTT 模塊或者直接移植它們的NTT 模塊. 這同時(shí)能夠?yàn)橛?jì)算模塊共享提供一致性模塊接口， 也能夠降低格密碼落地化帶來(lái)的經(jīng)濟(jì)成本. 另外， 本文方案若是使用經(jīng)過(guò)安全驗(yàn)證的開(kāi)源組件， 可避免出現(xiàn)意外漏洞.

本文方案除以上提到的在參數(shù)選取方面有創(chuàng)新外， 在采樣以及加解密的實(shí)現(xiàn)中也有以下優(yōu)化:

本文采用gen(seedA) 函數(shù)生成A， 對(duì)A分別做模數(shù)q1，q2的正向NTT 得到 ?A1， ?A2， 而不仿照Kyber-Round3 的做法， 直接從拒絕采樣得到 ?A1， ?A2. 這是因?yàn)椋?雖可節(jié)省2l2個(gè)正向NTT 操作， 但顯然與本方案中 ?A1， ?A2需滿足的 ?A2=NTT2(INTT1( ?A1)) 不符.

在參數(shù)選取的第(2) 點(diǎn)優(yōu)勢(shì)中提到， 本文方案是存儲(chǔ)私鑰s的NTT 形式?s1，?s2， 這樣做可以節(jié)省2個(gè)正向NTT、2 個(gè)逆向NTT 和1 步CRT: (1) 密鑰生成算法KeyGen 的行4 和行5 得到?s1和?s2后，不需要分別做逆向NTT 和CRT 得到s后再傳輸. (2) 解密算法Dec 中計(jì)算v=sTb′modp時(shí)， 可直接用?sT1，?sT2分別與?b′1，?b′2做點(diǎn)乘以及逆向NTT， 具體見(jiàn)Dec 的行1 和行2. 除此之外， 在加密算法Enc中， 行3 和行4 中對(duì)s′做正向NTT 得到?s′1，?s′2并存儲(chǔ)后， 還可繼續(xù)用于后續(xù)的向量?jī)?nèi)積， 具體見(jiàn)Enc的行5 和行6， 以及行9 和行10. 這樣能夠避免對(duì)s′重復(fù)做正向NTT.

3.4 AVX2 指令集對(duì)方案的優(yōu)化實(shí)現(xiàn)

Saber 的AVX2 優(yōu)化實(shí)現(xiàn)主要針對(duì)Saber 參考實(shí)現(xiàn)中耗時(shí)且可并行處理的功能模塊進(jìn)行優(yōu)化加速，主要包含約減模塊、多項(xiàng)式運(yùn)算模塊、中心二項(xiàng)分布模塊、私鑰序列化模塊、并行壓縮以及并行編碼/解碼模塊.

3.4.1 約減模塊

模塊化約減是加速NTT 并行實(shí)現(xiàn)的核心. 在本文優(yōu)化實(shí)現(xiàn)中， 模數(shù)一定時(shí)， 如果使用C 語(yǔ)言的“%”運(yùn)算符來(lái)取模， 那么算法的時(shí)間不是恒定的， 會(huì)有遭受側(cè)信道攻擊的風(fēng)險(xiǎn)且效率較低. 為了安全且高效地實(shí)現(xiàn)算法， 本文參考文獻(xiàn)[19] 中常數(shù)時(shí)間的約減算法， 即Barrett 約減和Montgomery 約減. 偽代碼分別見(jiàn)算法7 和8. 其中β=216.

算法9 改進(jìn)的Montgomery 約減Input: -β/2 ≤a ＜β/2，-(q-1)/2 ≤b ≤(q-1)/2，b′ = bq-1 mod β Output: r ≡β-1ab (mod q)1 t0 = ■ab/β」 //得到a，b 乘積的高位2 v = ab′ mod β 3 t = ■vq/β」4 r = t0 -t 5 return r

Barrett 約減算法[19]是將[-β/2，β/2) 上的a約減到[0，q] 中. 該算法采用預(yù)先計(jì)算的單字近似倒數(shù)v=/q」. 有了這個(gè)倒數(shù)， 當(dāng)約減無(wú)符號(hào)的單字整數(shù)時(shí)， 就可以得到小于2q的代表元. 當(dāng)素?cái)?shù)q接近β/2 時(shí)， 就可以使用精度更高的單字倒數(shù)， 即v=2(q)」-1β/本文方案中， 在進(jìn)行模數(shù)為q1=7681的NTT 時(shí)， 正向NTT 每計(jì)算一層， 輸出系數(shù)的范圍會(huì)擴(kuò)大(-q1，q1)， 可計(jì)算出: 在第二層結(jié)束后系數(shù)范圍已經(jīng)超出16 位有符號(hào)整型可表示的范圍， 此時(shí)需要對(duì)所有系數(shù)進(jìn)行Barrett 約減; 同理， 在第五、第八層也需要進(jìn)行Barrett 約減. 而在進(jìn)行模數(shù)為q2=3329 的NTT 時(shí)， 正向NTT 每計(jì)算一層， 輸出系數(shù)的范圍會(huì)擴(kuò)大(-q2，q2)， 可計(jì)算出七層正向NTT 之后， 系數(shù)范圍仍可用有符號(hào)16 位整型來(lái)表示且無(wú)數(shù)據(jù)溢出， 故本文在模數(shù)為q2= 3329 的正向NTT 內(nèi)部并沒(méi)有使用Barrett 約減. 除此之外， 本文在私鑰序列化模塊使用Barrett 約減來(lái)使私鑰的范圍在[0，q1) 和[0，q2)， 保證后續(xù)計(jì)算的正確性， 減少了不必要的約減， 提高了效率.

Montgomery 約減算法是將a和b的乘積ab ∈(-βq/2，βq/2) 約減到(-q，q) 中. 算法并不是直接計(jì)算r ≡a(modq) 而是計(jì)算r′≡β-1a(modq). 在樸素的Montgomery 約減算法[19]中， 得到ab的高低位后， 需要對(duì)低位進(jìn)行乘以q-1的運(yùn)算. 而本文使用改進(jìn)的Montgomery 約減算法[8]， 該算法的輸入不僅有要做乘積的a和b， 還有預(yù)計(jì)算的b′=bq-1modβ. 這樣做的好處在于可以省去樸素算法行3 中v乘q-1的乘法. 在本文方案中， 改進(jìn)的Montgomery 約減用在蝴蝶操作中計(jì)算多項(xiàng)式系數(shù)和本原單位根ζ的積. 在本文的AVX2 優(yōu)化實(shí)現(xiàn)中， 預(yù)計(jì)算表不僅存儲(chǔ)ζ還存儲(chǔ)了ζ ·q-1. 這樣可以將樸素算法中系數(shù)先乘ζ再乘q-1的兩個(gè)乘法轉(zhuǎn)換為預(yù)計(jì)算的ζ·q-1與系數(shù)的一個(gè)乘法， 可節(jié)約一個(gè)乘法指令.

3.4.2 多項(xiàng)式運(yùn)算模塊

Saber 的多項(xiàng)式運(yùn)算模塊主要包含NTT 運(yùn)算操作(正向NTT、逆向NTT、點(diǎn)乘)、多項(xiàng)式矩陣-向量乘法操作、多項(xiàng)式向量?jī)?nèi)積操作.

在AVX2 優(yōu)化實(shí)現(xiàn)中， NTT 運(yùn)算操作預(yù)計(jì)算表中ζ以及ζ·q-1的值都重復(fù)相應(yīng)的次數(shù)， 使得并行載入時(shí)可以一次全部載入， 避免使用廣播指令. 完整的正向NTT 劃分為兩部分: 對(duì)q1= 7681 正向NTT，共8 層， 分為第一層和第二到八層兩部分; 對(duì)于q2= 3329 的正向NTT， 共7 層， 分為第一層和第二到七層兩部分. 對(duì)于一個(gè)完整的正向NTT， 針對(duì)上述兩部分分別設(shè)計(jì)一個(gè)函數(shù)來(lái)進(jìn)行分層次調(diào)用. 在設(shè)計(jì)兩個(gè)函數(shù)的時(shí)候， 要盡量充分利用AVX2 的寄存器， 設(shè)計(jì)一個(gè)正向NTT 第一層的函數(shù)最多可以用八個(gè)256ymm 寄存器， 去做128 個(gè)系數(shù)的蝴蝶操作(也就是64 對(duì)系數(shù)的正向NTT 第一層操作)， 因此第一層對(duì)所有系數(shù)做蝴蝶操作需要分兩次進(jìn)行. 在做完第一層之后， 計(jì)算結(jié)果被存回內(nèi)存.

第二到七層/八層載入128 個(gè)系數(shù)， 在第一層的時(shí)候， 是間隔128 的一對(duì)系數(shù)進(jìn)行蝴蝶操作， 而后面層數(shù)則可以對(duì)連續(xù)的128 個(gè)系數(shù)進(jìn)行操作， 不需要額外的載入和存儲(chǔ)系數(shù)， 只需要進(jìn)行shuffle 重排系數(shù)順序. 因此本文只使用了四次載入和存儲(chǔ)就完成了256 個(gè)系數(shù)的正向NTT 操作， 減少了中間多次的載入和存儲(chǔ)操作， 從而提高整體速度.

3.4.3 中心二項(xiàng)分布模塊

在本文方案中， 私鑰s的每一個(gè)系數(shù)均由中心二項(xiàng)分布算法來(lái)生成. 本文針對(duì)μ= 2 的情況， 對(duì)中心二項(xiàng)分布算法進(jìn)行了AVX2 的優(yōu)化實(shí)現(xiàn)， 細(xì)節(jié)見(jiàn)算法10. 該算法每次輸入一個(gè)256 位的比特串buf， 得到私鑰s的64 個(gè)系數(shù). 算法需要先從buf 數(shù)組中取兩組兩比特來(lái)生成一個(gè)系數(shù)， 而使用AVX2 指令的操作數(shù)數(shù)據(jù)類型至少為8 位有符號(hào)整數(shù)， 此時(shí)以8 比特為一組直接進(jìn)行運(yùn)算會(huì)與預(yù)期結(jié)果有位置上的不同， 所以該運(yùn)算結(jié)束后需要對(duì)其結(jié)果進(jìn)行位置調(diào)整.

算法10 中心二項(xiàng)分布生成私鑰AVX2 實(shí)現(xiàn)Input: 字節(jié)數(shù)組buf Output: 多項(xiàng)式r 的64 個(gè)系數(shù)1 vpbroadcastd (a，b，c)2 vmovdqu v0 ← buf[i]3 vpsrld v1 ← v0 ? 1 4 vpand (v0，v1)← (a & v0，a & v1)5 vpaddd v0 ← v0+v1 6 vpsrld v1 ← v0 ? 2 7 vpand (v0，v1)← (b & v0，b & v1)8 vpsrld (v2，v3)← (v0，v1) ? 4 9 vpand (v0，v1，v2，v3)← (c & v0，c & v1，c & v2，c & v3)10 vpsubb (v1，v3)← (v0-v1，v2-v3)11 vpmovsxbw (v0，v1，v2，v3)← (v1，v3)12 vpunpcklwd (v0，v1)← ((v0，v2)low，(v1，v3)low)13 vpunpckhwd (v2，v3)← ((v0，v2)high，(v1，v3)high)14 vmovdqa (v0，v1，v2，v3)

3.4.4 私鑰序列化模塊

私鑰包括?s1和?s2. 由于AVX2 實(shí)現(xiàn)的正向NTT 采用延遲約減策略， 因此產(chǎn)生私鑰的系數(shù)范圍不一定在[0，q1) 和[0，q2). 為了正常進(jìn)行私鑰序列化操作， 對(duì)?s1和?s2的系數(shù)在序列化之前做了一次額外的約減， 使得其范圍在[0，q1) 和[0，q2). 此處采用Barrett 約減(偽代碼見(jiàn)算法7) 并行處理16 個(gè)系數(shù). 由于AVX2 向量寄存器個(gè)數(shù)有限， 故本文一次性使用8 個(gè)ymm 寄存器做128 個(gè)系數(shù)的約減， 分兩次完成對(duì)所有系數(shù)的約減.

3.4.5 并行壓縮模塊

在KeyGen 和Enc 過(guò)程中都存在對(duì)多項(xiàng)式的壓縮過(guò)程以節(jié)省帶寬(見(jiàn)算法4 第9 行和算法5 第8行). 這個(gè)過(guò)程中有p/q和向下取整的運(yùn)算. 由于本文方案的參數(shù)均為2 的方冪， 因此除法和向下取整可以用移位操作來(lái)實(shí)現(xiàn)， 即=x ?(?q-?p). 除此之外， 此過(guò)程可以用AVX2 實(shí)現(xiàn)并行優(yōu)化. 首先將要做壓縮的多項(xiàng)式系數(shù)載入一個(gè)256 位的AVX2 寄存器中， 這樣一個(gè)寄存器可以存放16 個(gè)系數(shù)， 此時(shí)就可以對(duì)其一次性完成算法11 的壓縮運(yùn)算， 對(duì)于多項(xiàng)式向量中的一個(gè)多項(xiàng)式， 只要做16 次運(yùn)算就可以完成該多項(xiàng)式所有系數(shù)的壓縮過(guò)程. 最后將最終結(jié)果存回之前的變量位置.

算法11 壓縮過(guò)程的AVX2 實(shí)現(xiàn)Input: 多項(xiàng)式b Output: 每個(gè)系數(shù)被壓縮至?p 比特后的b 1 vpaddw b ←b+h1 2 vpsraw b ←b ?(?q -?p)

3.4.6 并行編碼/解碼

算法5 行12 和算法6 行4 分別被稱為編碼和解碼過(guò)程， 這里以編碼過(guò)程為例來(lái)進(jìn)行描述: 編碼算法的輸入為明文m， 以及多項(xiàng)式v′. 其中明文m為256 位的比特串， 算法需要對(duì)其每一位分別進(jìn)行編碼操作， 此過(guò)程可以用AVX2 實(shí)現(xiàn)并行優(yōu)化(詳細(xì)見(jiàn)算法12). 首先要一次性取出明文m中的16 位， 而后與v′的16 個(gè)系數(shù)并行完成后續(xù)操作， 所以對(duì)于明文m， 只需要做16 次運(yùn)算便可以完成編碼.

算法12 編碼過(guò)程AVX2 實(shí)現(xiàn)Input: 明文m， 多項(xiàng)式v′Output: 密文cm 1 vpand m ←m & 1 2 vpsllw m ←m ??p -1 3 vpand m ←m & {1}?p 4 vpaddw v′ ←v′ +h1 5 vpsubw cm ←v′ -m 6 vpsrlw cm ←cm ?(?p -?T)

算法13 解碼過(guò)程的AVX2 實(shí)現(xiàn)Input: 密文cm， 多項(xiàng)式v Output: 解密明文m′1 vpand cm ←cm & {1}T 2 vpsllw cm ←cm ?(?p -?T)3 vpaddw v ←v+h2 4 vpsubw cm ←v-cm 5 vpand cm ←cm & {1}?p 6 vpsrlw m′ ←cm ?(?p -1)

3.5 恒定時(shí)間實(shí)現(xiàn)

計(jì)時(shí)攻擊[26]是一種常見(jiàn)的側(cè)信道攻擊. 它指的是攻擊者能夠根據(jù)密碼方案在軟件或硬件中的執(zhí)行時(shí)間信息來(lái)推斷出所執(zhí)行的運(yùn)算操作， 甚至能夠推算出該操作所涉及的一些秘密信息， 如私鑰. 針對(duì)計(jì)時(shí)攻擊最簡(jiǎn)單的對(duì)策是確保實(shí)現(xiàn)的執(zhí)行時(shí)間獨(dú)立于所處理的秘密數(shù)據(jù). 目前來(lái)說(shuō)， NIST Round 3 中的方案實(shí)現(xiàn)均考慮了計(jì)時(shí)攻擊， 并采用了恒定時(shí)間(constant-time) 實(shí)現(xiàn)策略. 因此， 本文的優(yōu)化實(shí)現(xiàn)方案采用了以下的恒定時(shí)間實(shí)現(xiàn)策略. 對(duì)于方案中涉及到模約減的地方， 如NTT 運(yùn)算中的modq1和modq2， 本文使用Barrett 約減和Montgomery 約減， 而并沒(méi)使用“%” 運(yùn)算符. 這是因?yàn)椤?” 運(yùn)算符的執(zhí)行時(shí)間與輸入數(shù)據(jù)長(zhǎng)度密切相關(guān). 而B(niǎo)arrett 約減和Montgomery 約減均是恒定時(shí)間實(shí)現(xiàn)， 能夠大大降低泄露秘密數(shù)據(jù)的風(fēng)險(xiǎn). 由于AVX2 指令集缺乏與“%” 運(yùn)算符有關(guān)的指令， 而B(niǎo)arrett 約減和Montgomery 約減僅使用到加減乘法和移位， 使用Barrett 約減和Montgomery 約減更利于AVX2 實(shí)現(xiàn). 對(duì)于本文中的生成公鑰A的gen 函數(shù)， 由于模數(shù)q為212，A的每一個(gè)系數(shù)均可以直接由12 個(gè)隨機(jī)比特拼接得到， 而無(wú)需使用拒絕采樣. 因?yàn)閝是固定的， 所以生成A的時(shí)間是恒定的. 這區(qū)別于Kyber 生成A的執(zhí)行時(shí)間與拒絕概率有關(guān). 針對(duì)生成秘密多項(xiàng)式s和s′的中心二項(xiàng)分布模塊， 它使用μ個(gè)比特生成一個(gè)系數(shù). 它生成s和s′的時(shí)間明顯也是恒定的. 針對(duì)壓縮模塊， 與Saber 原來(lái)的實(shí)現(xiàn)方式[7]一樣， 本文使用移位(即x ?(?q-?p)) 來(lái)處理每一個(gè)系數(shù)， 移位的執(zhí)行時(shí)間也獨(dú)立于被操作數(shù)x.

4 性能測(cè)試與比較

本節(jié)給出了Saber 優(yōu)化方案的C 參考實(shí)現(xiàn)和AVX2 優(yōu)化實(shí)現(xiàn)的性能測(cè)試數(shù)據(jù). 本文進(jìn)行的性能測(cè)試都是在關(guān)閉Hyper Threading 和Turbo Boost 的情況下， 硬件運(yùn)行環(huán)境為2.30 GHz 的8 核Intel Core i7-10510U 處理器， 16 GB 的內(nèi)存， 軟件運(yùn)行環(huán)境為Ubuntu 20.04.1 操作系統(tǒng)， 編譯器為gcc 9.3.0， AVX2優(yōu)化實(shí)現(xiàn)的編譯選項(xiàng)為-Wall -Wextra -O3 -fomit-frame-pointer -msse2avx -mavx2 -march=native -lcrypto. C 參考實(shí)現(xiàn)的編譯選項(xiàng)為-Wall -Wextra -Wmissing-prototypes -Wredundant-decls -O3 -fomitframe-pointer-march=native. 本文使用CPU 周期來(lái)衡量各算法的效率，故運(yùn)行密鑰生成算法KeyGen，密鑰封裝算法Encaps 和密鑰解封裝算法Decaps 10 000 次， 取其平均值.

4.1 多項(xiàng)式乘法部分性能對(duì)比

圖6 給出本文提出的Saber 優(yōu)化實(shí)現(xiàn)方案，與Saber Round3 和文獻(xiàn)[8]中向量-向量乘法以及矩陣-向量乘法操作的對(duì)比. 由圖中測(cè)試結(jié)果顯示， 多項(xiàng)式乘法部分采用NTT 與CRT 結(jié)合的方式， 借助AVX2指令集的單指令多數(shù)據(jù)的特性， 可最大化增加并行處理的數(shù)據(jù)量， 從而比文獻(xiàn)[8] 的性能平均提升26%， 其中向量與向量乘法部分性能平均提升40%， 矩陣與向量乘法部分平均提升11%; 與Saber Round3 相比，向量與向量乘法部分性能平均提升47%， 矩陣與向量乘法部分平均提升27%.

圖6 多項(xiàng)式乘法的性能對(duì)比Figure 6 Performance comparisons of polynomial multiplication

4.2 本文方案參考實(shí)現(xiàn)與優(yōu)化實(shí)現(xiàn)的性能對(duì)比

圖7 給出本文提出的Saber 優(yōu)化實(shí)現(xiàn)方案的AVX2 優(yōu)化實(shí)現(xiàn)與參考實(shí)現(xiàn)的對(duì)比. 由圖中測(cè)試結(jié)果顯示， 密鑰生成算法比參考實(shí)現(xiàn)提升約86%， 密鑰封裝算法比參考實(shí)現(xiàn)提升約88%， 密鑰解封裝算法比參考實(shí)現(xiàn)提升約90%.

圖7 參考實(shí)現(xiàn)與優(yōu)化實(shí)現(xiàn)的性能對(duì)比Figure 7 Performance comparisons of reference and optimized implementation

4.3 本文方案與Saber Round3 優(yōu)化實(shí)現(xiàn)的性能對(duì)比

圖8 給出本文提出的Saber 優(yōu)化實(shí)現(xiàn)方案， 與同類算法方案Saber Round3 的AVX2 優(yōu)化實(shí)現(xiàn)的對(duì)比. 由圖中測(cè)試結(jié)果顯示， 相比于Saber Round3 的AVX2 實(shí)現(xiàn)， 密鑰生成算法性能提升約21%， 密鑰封裝算法提升約23%， 密鑰解封裝算法提升約23%.

圖8 優(yōu)化實(shí)現(xiàn)的性能對(duì)比Figure 8 Performance comparisons of optimized implementation

結(jié)果顯示， 本文方案在實(shí)現(xiàn)效率上有很大的提升. 在Saber Round3 中， 使用Karuatsuba/Toom-Cook 算法來(lái)進(jìn)行多項(xiàng)式乘法， 而本文結(jié)合CRT， 選取更優(yōu)的參數(shù)對(duì)Saber 使用復(fù)雜度更低、更利于高度向量化實(shí)現(xiàn)的NTT 進(jìn)行加速， 使得本文方案的計(jì)算效率更優(yōu). 除此之外， 本文選取的NTT 友好素?cái)?shù)與文獻(xiàn)[8] 選取的素?cái)?shù)相比， 使得本文方案有更小的私鑰長(zhǎng)度以及更少的約減操作， 達(dá)到計(jì)算效率上的最優(yōu).