基于AVX512 的格密碼高速并行實(shí)現(xiàn)

雷斗威，何德彪，羅敏，彭聰

（武漢大學(xué)國(guó)家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢 430072）

0 引言

隨著量子計(jì)算的迅速發(fā)展，現(xiàn)有的公鑰密碼體系受到了嚴(yán)重威脅。Shor 量子算法［1］利用量子計(jì)算機(jī)，可在多項(xiàng)式時(shí)間內(nèi)破解大整數(shù)分解問題和橢圓曲線上的離散對(duì)數(shù)問題，從而攻破現(xiàn)有的公鑰密碼算法（RSA）和橢圓加密算法（ECC）。為了應(yīng)對(duì)量子計(jì)算帶來的威脅，能夠抵抗量子攻擊的密碼即后量子密碼（PQC）成為國(guó)內(nèi)外的研究熱點(diǎn)。

美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院（NIST）于2016 年開啟了后量子密碼標(biāo)準(zhǔn)的征集活動(dòng)，旨在提出PQC 標(biāo)準(zhǔn)，以應(yīng)對(duì)隨時(shí)可能到來的量子計(jì)算的威脅。格密碼因性能與安全性的優(yōu)秀表現(xiàn)，在后量子密碼標(biāo)準(zhǔn)征集活動(dòng)中占據(jù)了重要地位。經(jīng)過多年的篩選和評(píng)估，NIST 于2022 年5 月確定 了4 個(gè)PQC 標(biāo)準(zhǔn)算 法，涵蓋公鑰加密（PKE）、密鑰封裝（KEM）和數(shù)字簽名，其中3 個(gè)算法是基于格的，可以看出格密碼在PQC中的重要地位。

Kyber 是NIST 確定的4 個(gè)PQC 標(biāo)準(zhǔn)算法之一，安全性基于模誤差學(xué)習(xí)（MLWE）問題。簡(jiǎn)單而言，判定性MLWE 問題是指：給定上的隨機(jī)矩陣A以及上服從特定分布的s和e，區(qū)分(A，t=As+e)和隨機(jī)選取的(A，t)是困難的。搜索性MLWE 問題是指：給定隨機(jī)矩陣A以及t=As+e，其中s和e服從上的某些分布，求得s是困難的?，F(xiàn)有的量子算法并不能有效地解決MLWE 問題，從而保證了Kyber的抗量子安全性。

隨著PQC 標(biāo)準(zhǔn)的確定，為了后續(xù)的推廣和落地工作，對(duì)標(biāo)準(zhǔn)算法的高速實(shí)現(xiàn)的需求也日益增加。Kyber 包括一組PKE 算法以及利用Fujisaki-Okamoto轉(zhuǎn)換得到的KEM 算法。由于Fujisaki-Okamoto 轉(zhuǎn)換主要是哈希（Hash）操作，并非實(shí)現(xiàn)的重點(diǎn)，因此主要聚焦于對(duì)其PKE 算法的優(yōu)化實(shí)現(xiàn)。本文基于512位高級(jí)向量擴(kuò)展（AVX512），針對(duì)不同安全級(jí)別下的Kyber進(jìn)行高速實(shí)現(xiàn)。根據(jù)Kyber 中q為12 bit 的特點(diǎn)，使用16 bit對(duì)其進(jìn)行存儲(chǔ)與運(yùn)算，將512 bit寄存器分為32組16 bit 進(jìn)行并行處理，實(shí)現(xiàn)32 路并行多項(xiàng)式運(yùn)算。同時(shí)，利用惰性模約減的思想大大減少模操作的次數(shù)，充分發(fā)揮了16 bit存儲(chǔ)空間的性能。在抽樣過程中，利用AVX512 每次同時(shí)產(chǎn)生8 組偽隨機(jī)比特串并對(duì)其進(jìn)行合理分配，從而高效完成了對(duì)多項(xiàng)式的抽樣。

1 相關(guān)工作

為了更好地構(gòu)建格密碼，REGEV［2］提出容錯(cuò)學(xué)習(xí)（LWE）問題，使得格密碼方案的構(gòu)造更加便捷。為了得到更優(yōu)的計(jì)算效率，LANGLOIS 等［3］將LWE問題進(jìn)行了擴(kuò)展，得到了其模格形式MLWE，極大提高了格 密碼的 計(jì)算效 率。BOS 等［4］基 于MLWE 問題，構(gòu)建了選擇明文不可區(qū)分（IND-CPA）安全的公鑰加密方案，并使 用Fujisaki-Okamoto 轉(zhuǎn)換［5］，得到了選擇密文不可區(qū)分（IND-CCA）下安全的密鑰封裝方案。SEILER［6］利用高級(jí)向量擴(kuò)展2（AVX2）指令集，加速實(shí)現(xiàn)了快速數(shù)論變換（NTT），并將其運(yùn)用到格密碼方案NewHope 上，獲得了較好的性能提升。LONGA 等［7］針對(duì)特殊的素?cái)?shù)q，提出一種新的模約減技巧，提高了模約減效率，并利用該技巧加速NTT的實(shí)現(xiàn)。GUERON 等［8］利用冗余抽樣技術(shù)，提高了拒絕抽樣的成功率，降低了對(duì)偽隨機(jī)比特串的需求，同時(shí)結(jié)合AVX2 指令集，實(shí)現(xiàn)了高效的并行抽樣。ROY［9］利用AVX2，并行實(shí)現(xiàn)了不同安全級(jí)別下的格密碼算 法Saber。CABRAL 等［10］利 用AVX512 指 令集，以2 種不同的方式并行實(shí)現(xiàn)了安全哈希算法3（SHA-3）系列函數(shù)：第1 種方式是通過將函數(shù)內(nèi)部并行化，提升了單個(gè)函數(shù)的執(zhí)行效率；第2 種方式是同時(shí)執(zhí)行8 組不同輸入的SHA-3 函數(shù)，從而可以同時(shí)輸 出8 組不同 的Hash 運(yùn)算結(jié)果。ALKIM 等［11］在ARM Cortex-M4 處理器上實(shí)現(xiàn)了Kyber 和NewHope兩種格密鑰方案，填補(bǔ)了該方面實(shí)現(xiàn)的空白。ALKIM 等［12］對(duì)RISC-V 指令集進(jìn)行擴(kuò)展，并基于該擴(kuò)展設(shè)計(jì)一種非常緊湊的PQC 軟硬件協(xié)同實(shí)現(xiàn)方式，獲得了較大的性能提升。WONG 等［13］設(shè)計(jì)一種平衡速度和資源的架構(gòu)，并用該架構(gòu)在現(xiàn)場(chǎng)可編程門陣列（FPGA）上實(shí)現(xiàn)了SHA-3 系列函數(shù)，實(shí)驗(yàn)結(jié)果顯示：最終吞吐量達(dá)到較為理想的16.51 Gb/s。顧麗紅等［14］通過分析AES 加解密算法，結(jié)合龍芯平臺(tái)體系結(jié)構(gòu)特征，提出基于多媒體指令擴(kuò)展（SIMD）優(yōu)化AES 性能的方法，獲得了較好的性能提升。KARMAKAR 等［15］研究了Saber 在資源受限的ARM Cortex-M 系列微控制器中的實(shí)現(xiàn)方式，并針對(duì)速度和內(nèi)存資源的平衡進(jìn)行優(yōu)化，為未來物聯(lián)網(wǎng)設(shè)備中使用格密碼方案做好了前期準(zhǔn)備工作。FRITZMANN 等［16］針對(duì)格密碼方案NewHope、Kyber和Saber 提出一系列硬件加速器，并將其整合進(jìn)RISA-V 的流水線，同時(shí)增加了29 條新的RISA-V 指令集，并在FPGA 上進(jìn)行了模擬，最終提升了格密碼方案的實(shí)現(xiàn)性能。ZHOU 等［17］針對(duì)Dilithium 方案提出一種基于FPGA 的軟硬件協(xié)同處理方式，提高了實(shí)現(xiàn)效率。郭渝洛等［18］提出一種基于SIMD 的并行傅里葉空間圖像相似度算法，經(jīng)該算法優(yōu)化后的程序可獲得平均5.132 倍的加速，并且具有較強(qiáng)的魯棒性。

2 相關(guān)知識(shí)

2.1 基本符號(hào)和定義

2.2 快速數(shù)論變換

對(duì)于環(huán)Rq=Zq[X]/(Xn+1)上的多項(xiàng)式乘法，如果直接進(jìn)行相乘，則計(jì)算復(fù)雜度是O(n2)。在格密碼方案頻繁使用多項(xiàng)式相乘的情況下，效率低下。通過快速數(shù)論變化可以將多項(xiàng)式乘法的計(jì)算復(fù)雜度從O(n2)降到O(nlbn)，從而有效提高計(jì)算效率。

NTT 是有限域上的離散傅里葉變換，詳細(xì)內(nèi)容可參見文獻(xiàn)［19］，下面對(duì)其核心思路進(jìn)行概括描述。在Kyber 所選參數(shù)中，n取256，滿足n|q-1 且n=2d（d=8）的條件，因此有限域Zq上存在n原根，記作ζn，滿足條 件且那么環(huán)Rq=Zq[X]/(Xn+1) 可以寫作另一種形式Rq=通過利用環(huán)上的中國(guó)剩余定理［20］可以得 到，其中×表示直積。利用同構(gòu)性質(zhì)，可以將環(huán)上的多項(xiàng)式計(jì)算投射到環(huán)上。繼續(xù)對(duì)環(huán)使用環(huán)上的中國(guó)剩余定理并重復(fù)迭代該過程，最終可以得到同構(gòu)

2.3 Kyber 和AVX512 指令集

Kyber 詳細(xì)算法可參見文獻(xiàn)［21］，不再進(jìn)行重復(fù)說明。

2008 年，英特爾發(fā)布了高級(jí)矢量擴(kuò)展（AVX）指令集，引入256 bit 位寬矢量指令。2013 年，英特爾將其位寬擴(kuò)展至512 bit 并命名為AVX512 指令集。利用AVX512 指令集，計(jì)算機(jī)既可直接對(duì)512 bit 數(shù)據(jù)進(jìn)行處理，如進(jìn)行比特異或非等操作，又可將512 bit數(shù)據(jù)進(jìn)行劃分，并行處理多組數(shù)據(jù)，如32 組16 bit 數(shù)據(jù)、16 組32 bit 數(shù)據(jù)、8 組64 bit 數(shù)據(jù)等。AVX512 指令集的誕生擴(kuò)展了計(jì)算機(jī)處理位寬，提高了計(jì)算機(jī)并行效率。

為了能夠使編程人員不用進(jìn)行匯編編程就可以直接編寫匯編語(yǔ)句，英特爾設(shè)計(jì)了內(nèi)聯(lián)指令并將SIMD 指令集（包括AVX512 指令集）與內(nèi)聯(lián)指令進(jìn)行一一對(duì)應(yīng)。采用內(nèi)聯(lián)指令避免了繁瑣的匯編編程，增強(qiáng)了程序的易讀性和可移植性。在后續(xù)使用AVX512 時(shí)，本文將使用內(nèi)聯(lián)指令描述算法，使表達(dá)過程更加通俗易懂。內(nèi)聯(lián)指令_mm512_loadu_epi16可通過給定地址將512 bit 數(shù)據(jù)從內(nèi)存裝入寄存器中，_mm512_storeu_epi16 可將寄存器內(nèi)512 bit 的數(shù)據(jù)存到給定地址的內(nèi)存中，在使用AVX512 指令集進(jìn)行實(shí)現(xiàn)的過程中，會(huì)頻繁使用這兩條指令進(jìn)行數(shù)據(jù)的裝載和存儲(chǔ)。在后續(xù)部分，將忽略重復(fù)性的數(shù)據(jù)裝載和存儲(chǔ)操作，并專注于算法本身，從而使對(duì)算法的描述更加簡(jiǎn)潔。對(duì)于一些算法計(jì)算過程中所要用到的參數(shù)，利用_mm512_set 和_mm512_set1 系 列指令，通過立即數(shù)裝載進(jìn)寄存器，這在后續(xù)部分將多次重復(fù)使用且不再贅述。

3 多項(xiàng)式計(jì)算優(yōu)化

Kyber 上的計(jì)算包括多項(xiàng)式向量相加減、多項(xiàng)式向量相乘、多項(xiàng)式矩陣乘以多項(xiàng)式向量以及多項(xiàng)式向量?jī)?nèi)積。由于后兩者的計(jì)算可由前兩者得到，因此本文的重點(diǎn)在于前兩者的優(yōu)化，即多項(xiàng)式向量相加減和多項(xiàng)式向量相乘的優(yōu)化。

3.1 Zq上的計(jì)算優(yōu)化

多項(xiàng)式Rq=Zq[X]/(Xn+1)上的計(jì)算在具體實(shí)現(xiàn)過程中最終取決于Zq上的模運(yùn)算。為了提高多項(xiàng)式的計(jì)算效率，需要對(duì)Zq上的模運(yùn)算進(jìn)行優(yōu)化。

3.1.1 惰性模約減

惰性模約減技術(shù)即不再每一次計(jì)算過程中進(jìn)行模約減，而是等到數(shù)據(jù)快要溢出存儲(chǔ)空間時(shí)再進(jìn)行統(tǒng)一處理。在Kyber 中，q取3 329，占12 個(gè)比特長(zhǎng)，但本文采用16 bit 存儲(chǔ)Zq上的數(shù)據(jù)。因此，在計(jì)算過程中，如果數(shù)據(jù)未超過16 bit 而是僅超出絕對(duì)最小剩余系Sq，便可正常存儲(chǔ)與計(jì)算，將不再對(duì)其進(jìn)行模約減操作。利用該方法，通過合理利用計(jì)算機(jī)存儲(chǔ)資源，減少了大量的模約減操作，提高了Zq上的計(jì)算效率。對(duì)于模加減而言，當(dāng)結(jié)果未超出16 bit 時(shí)，直接進(jìn)行加減忽略模約減操作，將這種直接加減法記作DAdd 和DSub。

3.1.2 優(yōu)化的蒙哥馬利模約減

當(dāng)Zq上的數(shù)據(jù)達(dá)到16 bit 長(zhǎng)度時(shí)需要對(duì)其進(jìn)行模約減操作。在進(jìn)行Zq上的模乘運(yùn)算時(shí)會(huì)得到一個(gè)無(wú)窮范數(shù)較大的相乘結(jié)果，因其比特長(zhǎng)度已經(jīng)超過16 bit，需要對(duì)其進(jìn)行模約減操作。一般而言，對(duì)無(wú)窮范數(shù)較大的數(shù)據(jù)進(jìn)行模約減操作需要除法運(yùn)算，對(duì)于計(jì)算機(jī)而言，這將耗費(fèi)大量的計(jì)算資源。1985 年，MONTGOMERY［22］提出一種快速的模約減方法，即蒙哥馬利模約減。蒙哥馬利模約減僅利用少量的加法和乘法操作，便可完成對(duì)較大數(shù)據(jù)的模約減操作，解決了一般模約減過程中除法效率過低的問題。傳統(tǒng)的蒙哥馬利模約減會(huì)在最后一步進(jìn)行一次判斷操作，并依據(jù)判斷結(jié)果對(duì)數(shù)據(jù)進(jìn)行修正，從而將數(shù)據(jù)徹底約減到Sq。仿照惰性模約減的思路，取消最后一次判斷以及修正操作，在數(shù)據(jù)不溢出16 bit 存儲(chǔ)空間的情況下，不會(huì)影響最終的計(jì)算結(jié)果，具體見算法1 所示，在后文中，將算法1 簡(jiǎn)記作MontRed。需要注意到的是：對(duì)于最終得到的結(jié)果r1≡a·b·β-1(modq)中額外引入的β-1，將在后續(xù)統(tǒng)一處理。

3.1.3 模乘運(yùn)算

由于相乘后的數(shù)據(jù)一般超過16 bit 的存儲(chǔ)范圍，因此需要對(duì)結(jié)果進(jìn)行模約減，直接采用MontRed 進(jìn)行模約減。在Kyber 的具體實(shí)現(xiàn)過程中，所用到的模乘可分為2 種：1）一般情況下的模乘，兩乘數(shù)均未知，這常用于多項(xiàng)式相乘中，本文將其記作MMul；2）一乘數(shù)提前確定的模乘，這常用于NTT 和INTT轉(zhuǎn)換的過程中，將其記作FMMul。對(duì)于MMul，對(duì)相乘后的結(jié)果直接使用MontRed 進(jìn)行模約減，如算法2所示；對(duì)于FMMul，對(duì)提前確定的乘數(shù)進(jìn)行預(yù)處理再進(jìn)行后續(xù)操作，如算法3 所示。在后續(xù)部分，將采用合適的方法消除MontRed 引入的β-1。

3.2 Rq 上的計(jì)算優(yōu)化

3.2.1 NTT 優(yōu)化方案

在Kyber 中進(jìn)行NTT 轉(zhuǎn)換的多項(xiàng)式系數(shù)范圍為(-q，q)。在算法4的第6行中，DAdd 和DSub不會(huì)進(jìn)行模操作，因此每一輪迭代均會(huì)使數(shù)據(jù)的范圍發(fā)生改變。在經(jīng)過7 輪迭代后，多項(xiàng)式系數(shù)的范圍從(-q，q)增加到(-8q，8q)。由于(-8q，8q)內(nèi)的數(shù)據(jù)仍能被16 bit 正常存儲(chǔ)，因此不對(duì)其進(jìn)行額外處理。

3.2.2 多項(xiàng)式乘法優(yōu)化方案

通過NTT將n-1 階多項(xiàng)式上的乘法轉(zhuǎn)換為個(gè)一階多項(xiàng)式的乘法。不妨設(shè)(a1x+a0)，(b1x+b0)∈Zq[X]/(X2-σi)，相乘的過程可以寫作(a1x+a0)·(b1x+b0)=(a1·b1)x2+(a0·b1+a1·b0)x+a0·b0=(a0·b1+a1·b0)x+(a1·b1·σi+a0·b0)。對(duì)于a0·b1、a1·b0、a1·b1、a0·b0，使用MMul進(jìn)行乘操作；對(duì)于(a1·b1) ·σi，由于σi是提前確定的乘數(shù)，預(yù)計(jì)算σi·βmod±q及σi·β·q-1mod±β，并使用FMMul 進(jìn)行乘操作。對(duì)于加法，使用DAdd。由于省略了部分模約減操作，最終得到的結(jié)果范圍為(-2q，2q)。由于使用MontRed，最終計(jì)算的結(jié)果乘上了額外的β-1。這些將在INTT中統(tǒng)一處理。

3.2.3 INTT 優(yōu)化方案

在INTT 的過程中，需要處理由MontRed 引入的β-1，同時(shí)需要防止計(jì)算過程中數(shù)據(jù)溢出16 bit 長(zhǎng)度。在INTT 的每一輪迭代過程中系數(shù)的無(wú)窮范數(shù)均會(huì)翻倍，而16 bit 最多可以存儲(chǔ)的數(shù)據(jù)范圍為(-9q，9q)。因此，在數(shù)據(jù)即將產(chǎn)生溢出前，使用MontRed 對(duì)其進(jìn)行模約減。設(shè)輸入數(shù)據(jù)的系數(shù)范圍為(-4q，4q)，整個(gè)INTT 迭代過程的數(shù)據(jù)變化如下：

第2 輪迭代：(-q，q)→(-2q，2q)；

第3 輪迭代：(-2q，2q)→(-4q，4q)；

第5 輪迭代：(-q，q)→(-2q，2q)；

第6 輪迭代：(-2q，2q)→(-4q，4q)；

在第1 和4 輪迭代中使用MontRed 進(jìn)行模約減，同時(shí)不會(huì)將預(yù)乘上β。這樣在每一次模約減后，數(shù)據(jù)范圍將變成(-q，q)且會(huì)引入β-1，如算法5 的第11 和12 行所示。在INTT 的最后一輪迭代過程中，通過乘上2-(m-1)來消除每一輪迭代過程中引入的倍數(shù)2，通過乘上β-2來消除第1 和4 輪迭代中進(jìn)行模約減引入的β-2，通過乘上β來消除最后一輪迭代過程中使用FMMul 進(jìn)行模乘引入的β-1，如算法5 的第21 和22 行所示。利用改進(jìn)的INTT 算法，消除了之前運(yùn)算引入的β-1并得到了無(wú)窮范數(shù)較小的結(jié)果。

4 基于AVX512 的并行實(shí)現(xiàn)

本節(jié)詳細(xì)描述如何利用AVX512 進(jìn)行具體實(shí)現(xiàn)。采用16 bit 存儲(chǔ)Zq上的元素，每512 bit 可存儲(chǔ)32 組16 bit 數(shù) 據(jù)。

4.1 Rq 上計(jì)算的并行實(shí)現(xiàn)

4.1.1 32 路并行加減

對(duì)于加減法而言，使用惰性模約減技術(shù)，利用_mm512_add_epi16 和_mm512_sub_epi16 實(shí) 現(xiàn)32 路并行加減法。

4.1.2 32 路并行模約減

4.1.3 32 路并行模乘

MMul 的實(shí)現(xiàn)思路是將兩輸入乘數(shù)相乘后進(jìn)行MontRed 處理。本文同樣利用_mm512_mulhi_epi16和_mm512_mullo_epi16，32 路并行獲得兩相乘結(jié)果的高16 bit 和低16 bit 并將得到的結(jié)果輸入32 路并行MontRed 進(jìn)行處理，如算法7 所示。FFMul 的32 路并行計(jì)算方法和上述類似，但需要注意的是由于提前確定了1/2 的乘數(shù)并存入了寄存器y中，可以預(yù)計(jì)算得到y(tǒng)qinv=y·q-1mod±β，因此，與MMul 相比，F(xiàn)FMul 少了一 次_mm512_mullo_epi16 運(yùn) 算，提高了計(jì)算效率，如算法8 所示。

4.1.4 32 路并行NTT 和INTT

將第4.1.1～4.1.3 節(jié)中的32 路并行計(jì)算方法運(yùn)用到NTT 和INTT 過程中，即可得到32 路并行NTT 和INTT，但有2 點(diǎn)需要注意：1）將預(yù)計(jì)算的參數(shù)進(jìn)行冗余存儲(chǔ)使其達(dá)到512 bit，通過該方法，當(dāng)向512 bit 寄存器裝載數(shù)據(jù)時(shí)可以直接讀入512 bit 冗余存儲(chǔ)的數(shù)據(jù)，而不再需要通過復(fù)雜的廣播指令進(jìn)行數(shù)據(jù)的擴(kuò)展；2）在NTT 和INTT 的第1 次迭代過程中，將多項(xiàng)式的系數(shù)裝載進(jìn)寄存器，256 個(gè)系數(shù)共需要8 個(gè)寄存器，這對(duì)于AVX512 來說是可實(shí)現(xiàn)的。在所有迭代完成后，再將8 個(gè)寄存器中的數(shù)據(jù)存入內(nèi)存，通過該方法，省去了大量裝載數(shù)據(jù)與存儲(chǔ)數(shù)據(jù)的操作，從而提升了計(jì)算效率。

4.1.5 32 路并行多項(xiàng)式乘法

利用NTT 將n-1 階多項(xiàng)式上的乘法轉(zhuǎn)換為個(gè)一階多項(xiàng)式的乘法。因?yàn)檩斎氲亩囗?xiàng)式是不確定 的，所以采 用MMul 進(jìn)行相 乘。將32 組a1、a0、b1、b0分別裝載 到4 個(gè)不同的512 bit 寄 存器，再使用相應(yīng)的32 路并行MMul 和32 路并行加法完成32 組一階多項(xiàng)式的相乘，從而實(shí)現(xiàn)32 路并行多項(xiàng)式乘法。

4.2 8 路并行SHAKE 函數(shù)

SHA-3 是NIST 于2015 年8 月5 日 發(fā)布的安全 哈希算法系列標(biāo)準(zhǔn)。SHAKE128、SHAKE256 是SHA-3中的兩個(gè)函數(shù)［23-24］，最大的特點(diǎn)是可以輸出任何比特長(zhǎng)度。Kyber 通過SHAKE128 和SHAKE256 擴(kuò)展隨機(jī)種子，獲得所需長(zhǎng)度的偽隨機(jī)比特串，用于執(zhí)行后續(xù)的抽樣操作。使用AVX512 可以同時(shí)執(zhí)行8 路SHAKE128（SHAKE256）操作［10］，從而同時(shí)拋出8 組偽隨機(jī)比特串，具體如圖1 所示。

圖1 8 路并行SHAKE 函數(shù)Fig.1 8-way parallel SHAKE functions

4.3 并行抽樣

在Kyber 中利用拒絕抽樣技術(shù)［25］和SHAKE128，通過給定的種子生成上的隨機(jī)矩陣，具體如算法9 所示。由于是上的隨機(jī)矩陣，因此可以將其作為已經(jīng)經(jīng)過NTT 運(yùn)算的矩陣使用，從而節(jié)省NTT 運(yùn)算所耗費(fèi)時(shí)間。

4.3.1 并行拒絕抽樣

對(duì)于隨機(jī)的12 bit，當(dāng)數(shù)值在[0，q)時(shí)將其取出，否則將不使用該12 bit，繼續(xù)使用下一串隨機(jī)的12 bit 進(jìn)行上述處理。根據(jù)條件概率，當(dāng)成功抽取一個(gè)數(shù)值時(shí)，滿足[0，q)的均勻分布。這種抽樣方式被稱為拒絕抽樣［25］。設(shè)是第i行、第j列的元素的每一 個(gè)系數(shù) 范圍均 為[0，q)。為了使?jié)M足上的均勻分布，需要使的每一個(gè)系數(shù)滿足[0，q)上的均勻分布。在具體抽樣過程中，將重復(fù)進(jìn)行拒絕抽樣，直至抽出整個(gè)。

一個(gè)512 bit 寄存器可以裝載64 Byte 數(shù)據(jù)，每3 Byte 可以組成2 組12 bit 數(shù)據(jù)。利用_mm512_permutexvar_epi8，將3 Byte的中間部分重復(fù)一次，接著使用_mm512_mask_srli_epi16、_mm512_and_si512以及預(yù)先計(jì)算好的mask 消除多余部分，如圖2 所示。利用上述方法可以將寄存器中前48 Byte 數(shù)據(jù)同時(shí)轉(zhuǎn)換為32 組12 bit 數(shù)據(jù)存放在一個(gè)512 bit 寄存器中，其余數(shù)據(jù)在下一次抽樣中使用。使用_mm512_cmplt_epi8_mask 判斷哪些數(shù)據(jù)在[0，q)內(nèi)并生成標(biāo)志位。利用標(biāo)志位，將滿足要求的數(shù)據(jù)作為的系數(shù)存入內(nèi)存。

圖2 數(shù)據(jù)排列與處理Fig.2 Arrangement and processing of data

4.3.2 偽隨機(jī)比特串分配

由于直接生成隨機(jī)比特串較為復(fù)雜，Kyber 中利用SHAKE128 擴(kuò)展輸入的種子得到偽隨機(jī)比特串，并利用該偽隨機(jī)比特串替換隨機(jī)比特串完成對(duì)A的抽樣，從而提高效率且不會(huì)降低安全性。如4.2 節(jié)所述，通過AVX512 能夠進(jìn)行8 路SHAK128 操作，同時(shí)生成8 組偽隨機(jī)比特串，充分利用該8 組偽隨機(jī)比特串對(duì)抽樣性能的提升非常重要。本文的核心方法是通過對(duì)多項(xiàng)式進(jìn)行拆分抽樣，使其能夠完全利用8 組偽隨機(jī)比特串。

當(dāng)k取2 時(shí)中共有4 個(gè)多項(xiàng)式。對(duì)于中第i行、第j列的元素αi，j，利 用SHAKE128(seed‖ ‖i‖j0)生成其低128 bit 系數(shù)，SHAKE128(seed‖i‖j‖1)生成其高128 bit 系數(shù)。通過該方法，生成4 個(gè)多項(xiàng)式需要用到8 組偽隨機(jī)比特串，從而充分利用了8 路并行SHAKE128 函數(shù)且降低了SHAK128 的循環(huán)次數(shù)。

當(dāng)k取3 時(shí)，中共有9 個(gè)多項(xiàng)式。對(duì)于中第3 行、3 列的元素，將其拆分成8 個(gè)部分，每個(gè)部分有32 項(xiàng)系數(shù)。利 用SHAKE128(seed‖ 3 ‖3 ‖index)為每一部分生成偽隨機(jī)比特串。對(duì)于的其他元素，直接利用SHAKE128(seed‖i‖j)生成對(duì)應(yīng)的偽隨機(jī)比特串，不再進(jìn)行拆分。通過該方法，充分利用了8 路并行SHAKE128 函 數(shù)。

當(dāng)k取4 時(shí)，中共含16 個(gè)多項(xiàng) 式，正好是8 的倍 數(shù)。因 此，對(duì) 于中 第i行、第j列的元 素，直 接利用SHAKE128(seed‖i‖j)生成對(duì)應(yīng)的偽隨機(jī)比特串，不再進(jìn)行拆分，從而充分利用了8 路并行SHAKE128 函數(shù)。

4.4 并行抽樣Sη

在Kyber 中，利用中心二項(xiàng)分布（CBD）抽樣抽取Sη，如算法10 所示。CBD 抽樣利用固定長(zhǎng)度的偽隨機(jī)比特串抽取Sη上的元素，未使用較為繁瑣的拒絕抽樣技術(shù)，運(yùn)行效率更高。

由于直接生成隨機(jī)比特串較為復(fù)雜，Kyber 中利用SHAKE256 擴(kuò)展輸入的種子得到偽隨機(jī)比特串，利用偽隨機(jī)比特串替換隨機(jī)比特串完成對(duì)Sη的抽樣，η取值為2 或者3。當(dāng)η為2 時(shí)，每個(gè)長(zhǎng)度為4 的偽隨機(jī)比特串可通過CBD 抽樣得到Sη的一個(gè)系數(shù)，整個(gè)Sη的CBD 抽樣需要消耗長(zhǎng)度為1 024 bit 的偽隨機(jī)比特串，而SHAKE256 一次循環(huán)能產(chǎn)生長(zhǎng)度為1 088 的偽隨機(jī)比特串，因此只需一次Squeeze 操作，便可完成一次Sη的CBD 抽 樣。當(dāng)η為3 時(shí)，每個(gè)長(zhǎng)度為6 的偽隨機(jī)比特串可通過CBD 抽樣得到Sη的一個(gè)系數(shù)，整個(gè)Sη的CBD 抽樣需要消耗長(zhǎng)度為1 536 bit 的偽隨機(jī)比特串，需要SHAKE256 循環(huán)2 次。當(dāng)進(jìn)行實(shí)現(xiàn)時(shí)，較難處理3 bit 的并行操作，因此利用冗余比特技術(shù)，對(duì)每4 bit 進(jìn)行并行處理，并忽略最高比特。通過上述方法，整個(gè)Sη的CBD 抽樣需要消耗長(zhǎng)度為2 048 bit 的偽隨機(jī)比特串，SHAKE256依然只需循環(huán)2 次，未造成額外的開銷，如圖3所示。

圖3 CBD 抽樣的比特處理Fig.3 Bit processing of CBD sampling

5 性能分析

利用AVX512 實(shí)現(xiàn)了不同安全參數(shù)下的Kyber算法，即Kyber512、Kyber768 和Kyber1 024，并與其C 語(yǔ)言版本的實(shí)現(xiàn)進(jìn)行了性能對(duì)比與分析［21］。使用的處理器是11th Gen Intel?CoreTMi5-1135G7@2.40 GHz 2.42 GHz，內(nèi)存大小為16 GB。操作系統(tǒng)選用Windows 10，編譯器選用GCC，優(yōu)化等級(jí)為-O3。將各算法運(yùn)行20 000 次，并計(jì)算其平均時(shí)鐘周期作為性能指標(biāo)。

通過表1～表3 可以看出：在多項(xiàng)式計(jì)算方面，由于對(duì)算法進(jìn)行優(yōu)化且利用AVX512 實(shí)現(xiàn)了32 路并行，從而獲得了55～95 倍的加速；在多項(xiàng)式抽樣方面，利用8 路SHAKE 函數(shù)以及優(yōu)化的抽樣方法獲得了4～7 倍的加速；從整體來看，對(duì)于包含抽樣操作的密鑰生成算法和加密算法獲得了10～16 倍的加速，對(duì)于主要由多項(xiàng)式計(jì)算構(gòu)成的解密算法獲得了約56 倍的加速。

表1 Kyber512 的性能測(cè)試與對(duì)比 Table 1 Performance testing and comparison of Kyber512

表2 Kyber768 的性能測(cè)試與對(duì)比 Table 2 Performance testing and comparison of Kyber768

表3 Kyber1 024 的性能測(cè)試與對(duì)比 Table 3 Performance testing and comparison of Kyber1 024

6 結(jié)束語(yǔ)

本文針對(duì)Kyber 算法的公鑰加密部分進(jìn)行高速并行實(shí)現(xiàn)。在多項(xiàng)式計(jì)算方面，利用惰性模約減、優(yōu)化的蒙哥馬利模約減、一般模乘和固定乘數(shù)模乘等技術(shù)，提高了模運(yùn)算的效率，采用NTT 和INTT 變換提高了多項(xiàng)式計(jì)算的效率，將優(yōu)化后的模運(yùn)算融入NTT 和INTT 過程，同時(shí)利用AVX512 進(jìn)行高速并行實(shí)現(xiàn)，獲得了55～95 倍的加速。在多項(xiàng)式抽樣方面，通過拆分抽樣、冗余抽樣等技術(shù)優(yōu)化抽樣過程，同時(shí)利用AVX512 進(jìn)行高速并行實(shí)現(xiàn)，獲得了4～7 倍的加速。在整體上，獲得了10～56 倍的性能提升。在后續(xù)工作中將繼續(xù)研究不同后量子密碼標(biāo)準(zhǔn)在不同硬件平臺(tái)上的高速實(shí)現(xiàn)。