資源密集型NTT 算法硬件設計與實現研究*

王明東，梅 瑞，吳朋庭，李 軍，何衛國，毛發英

（成都三零嘉微電子有限公司，四川 成都 610041）

0 引言

美國國家標準與技術研究院（National Institute of Standards and Technology，NIST）自2016 年12 月開始面向全球公開征集并制定后量子密碼算法，在所有候選算法中，基于格理論的后量子密碼算法在數量上占據明顯優勢。同時整數型、浮點型主流全同態密碼算法，如BGV[1]、BFV[2]、CKKS[3]算法均是基于格理論的密碼體制。格基密碼方案的計算主要是基于多項式環開展，涉及多項式環上的加/減法、乘法、模約減等運算，其中加/減法的計算復雜度為O(n)，樸素乘法的計算復雜度為O(n2)。隨著多項式階n的不斷增大，多項式乘法運算變得異常復雜。相較于CRYSTALS-KYBER 等后量子密碼算法中環上多項式階與模數較小，在硬件設計時不存在資源利用的瓶頸[4]，而在全同態密碼算法中，多項式的次數可以達到上萬階，模數達幾百比特，是一種資源密集型算法，在硬件實現整個架構中，多項式乘法部分是最耗時、最耗資源的模塊。

目前快速數論變換（Number Theoretic Transforms，NTT）是多項式乘法中最有效的方法之一。NTT算法的本質是定義在有限域上的快速傅里葉變換（Fast Fourier Transform，FFT），使用有限域上的單位原根代替了FFT中的復數原根，由模上的整數運算代替了浮點數運算。使用快速NTT 算法能夠將多項式環上乘法的計算復雜度由O(n2)降為O(nlog2n)，當多項式的階數n增大時，NTT 算法優勢明顯。高效率的NTT 算法實現是后量子與同態密碼算法最關鍵的核心。

本文基于全同態密碼算法資源密集型的特點，結合典型NTT 算法實現流程，分析NTT 算法硬件實現的關鍵問題與難點，提出多周期并行化設計與全流水化設計兩種硬件方案，并對方案的資源消耗與性能進行對比分析。在資源與性能折中的情況下，采用流水化設計具有較高的資源性能比，為優先方案；若完全以性能為主，在資源盡可能滿足的條件下，可采用多周期并行化方案，同時進一步提高蝶形運算并行度，獲得更高的性能需求。

1 NTT 算法簡介

快速數論變換NTT 算法可以看作離散傅里葉變換（Discrete Fourier Transform，DFT）在有限域上的推廣形式，其運算流程與快速傅里葉變換的思想相同，主要是通過對多項式在特殊點進行求值運算將多項式的系數表示轉變為點值表示，并將求值點選擇在n個單位原根（FFT 為n個單位復根）處，則可以通過迭代運算的方式完成點值運算，其時間復雜度為O(nlog2n)。

Zq表示整數環模q的商環，Rq=Zq[x]/φ(x)表示模多項式φ(x)的整系數多項式環，其中φ(x)為不可約簡多項式。對于同態密碼算法，大部分情況下φ(x)=xn+1。Zq的n次單位原根ωn滿足ωnn≡1 modq，且當0＜i＜n時，對于多項式a(x)∈Rq，其系數為(a0,a1,…,an-1)，對a(x)在旋轉因子ωni處進行求值，可以得到其點值表示，其中滿足?i∈[0,n-1]。

式中：⊙為卷積。

對于同態密碼算法中的多項式環Rq=Zq[x]/(xn+1)，ω，?分別表示n階、2n階的原根，那么xn+1 可以分解為

因此，可以得到NTT 運算對應的矩陣形式為：

可以看到，Rq=Zq[x]/(xn+1)上的NTT 運算實際上是先對a(x)∈Rq做預處理變換a'=(a0,a1,…,an-1)⊙(?0,?1,…,?n-1)，然后進行標準的NTT 運算。相應地，環上多項式乘法表示為：

NTT 典型算法流程如下：

2 關鍵問題分析

2.1 存儲開銷大

在環上容錯學習問題（Ring Learning with Errors Problem，RLWE）的全同態加密方案中，為了獲得更深電路的計算，希望模數q取得盡可能的大，同時為了保證方案的安全性，在q增大的同時，可以增加環多項式維數N的值，所以q與N在全同態加密方案中需要一種平衡，以保證方案的安全性和同態計算能力。

對于k比特安全性，滿足如下關系式[6]：

以128 bit 安全，典型安全參數為q=256 bit，維數N為8 192，單個參數可達256 KB。當安全強度增大時，參數的存儲量呈爆炸式增長。

因此，在存儲的使用上，盡量采用單口（Single Port）SRAM，避免使用雙口（Dual Port）SRAM 進行設計。

2.2 存儲跨越式訪問

NTT 算法本質上是以蝶形單元為基本操作，共log2n層，每層的蝶形單元為n/2 個，共(n/2)×log2n個蝶形操作。以維數n=8 進行分析說明，如圖1 所示。

圖1 蝶形單元存儲跨越式訪問

第1 層存儲訪問：（0,4），（1,5），（2,6），（3,7）。

第2 層存儲訪問：（0,2），（1,3），（4,6），（5,7）。

第3 層存儲訪問：（0,1），（2,3），（4,5），（6,7）。

可以看到，存儲跨越式訪問為算法的高并行或者流水線設計帶來了特別大的設計困難。

2.3 讀寫沖突問題

NTT 算法的蝶形單元操作為算法1 中描述的7～11 步操作。蝶形單元結構如圖2 所示。

圖2 蝶形單元結構

為了減少存儲資源的開銷，在設計上應盡量避免使用雙口SRAM。因此，上述蝶形單元中對存儲的兩次讀、兩次寫操作，以及存儲地址的跨越式訪問，不論采用并行化設計還是流水線設計，都將不可避免地帶來存儲的讀寫沖突問題。

2.4 減少額外的存儲訪問

由于同態密碼算法多項式環的維數n通常可達210～217，額外的存儲訪問開銷將直接帶來NTT 算法性能的明顯降低。

（1）避免對數據的直接Bit Reverse 操作：算法1 流程中的Bit_Reverse_Copy(a’,A)應當直接避免。

（2）NTT運算后的結果，應可直接作用于INTT 運算，避免增加額外Bit Reverse 操作。

2.5 算法設計問題

NTT 算法的標準流程為3 層的for 循環描述，不利于硬件化的高效實現。因此，需要對算法的第2、第3 次循環進行展開式描述，以方便實現高并行或者流水化設計。但是，這會進一步增大存儲的跨越式訪問與讀寫沖突問題。

3 硬件設計方案

3.1 NTT 算法流程優化

3.1.1 規避Bit_Reverse_Copy 操作

規避算法1 流程中的Bit_Reverse_Copy(a’,A)操作，即數據的比特逆序拷貝操作。蝶形運算單元中，對存儲地址直接進行比特逆序訪問。

3.1.2 蝶形單元并行化展開

NTT 的算法描述為3 層for 循環，不利于按層次化進行蝶形單元運算流程控制和并行化設計。因此將后兩層for 循環描述進行合并，提出以下并行化地址映射算法流程以2 路并行為例，算法相應地可擴展為多路并行運算，地址映射如下所示。

3.1.3 INTT 優化

INTT 在NTT 的算法流程下，最后一步對所有多項式環系數參數需要做模逆n的操作，由于n是2 的冪次，因此可等效在每層的蝶形操作上增加模除以2 運算，省略INTT 最后的模逆n運算，提升性能。其中，模除以2 運算可優化設計為：

通過向右移位、加法和邏輯與進行實現，簡化x除以2 的求模運算。

3.1.4 NTT/INTT 復用

對NTT 的運算進行正向位序數據輸入，比特逆序位序輸出。對INTT 的運算采用比特逆序位序輸入，正向位序數據輸出。

采用上述處理方式，復用NTT/INTT 模塊，減少硬件資源使用，無須再對數據進行比特逆序操作，只用改變相應的旋轉因子，以及INTT 的蝶形單元操作多一個模除以2 運算。

3.2 模乘算法方案

蝶形單元操作中涉及一次大整數的模乘運算。為支持大位寬的模乘運算，同時使模數q具有靈活性，采用經典的Montgomery 算法。算法描述如下：

算法3 中，步驟1 到步驟3 為3 次乘法，分別占用1 個周期，步驟4 到步驟6 一共占用1 個周期，那么一次完整的模乘運算需要4 個周期來完成。

3.3 多周期并行化方案

結合模乘算法方案，將模乘運算的最后一步減法與蝶形操作的一次模加、一次模減進行合并，蝶形單元的單次操作可細化為圖3 的形式。

圖3 蝶形單元單次操作

（1）若采用單口SRAM 進行數據存儲，共需8 個周期完成一次蝶形操作。

（2）若采用雙口Dual Port SRAM進行數據存儲，將兩次讀和兩次寫操作同批完成，共需6 個周期完成一次蝶形操作。例如，在性能提升25%的情況下，以單雙口面積的初步比例估計，存儲將翻倍增長。同時，若需要達到(n/2)×log2n的性能規模，需要同時并行8 個或者6 個蝶形單元，并將SRAM 分成8 個或者6 個BANK 并行訪問，隨之帶來的是乘法器與加法器的成倍數增長。

（3）多周期并行化處理需要解決算法層地址比特逆序訪問的并行化處理，為并行化處理的關鍵核心。可采用算法2 中的蝶形單元并行化展開的算法流程。

3.4 流水化方案

3.4.1 流水線劃分

NTT 算法的本質是(n/2)×log2n個蝶形運算操作，考慮全流水化方式設計。

原始蝶形單元操作如圖4 所示。

圖4 原始蝶形單元操作

為方便流水線設計，將兩次讀與兩次寫分別合并，設計6 級流水線，如圖5 所示。

圖5 蝶形單元6 級流水

圖5 中，DR 為單周期兩次讀操作，M1 為第一級乘法，M2 為第二級乘法，M3 為第三級乘法，A為模乘的最后一級減法、蝶形操作的模加、模減、INTT 的模除以2 操作的集合，DW 為單周期兩次寫操作。

3.4.2 存儲設計

由于同態密碼算法的NTT 運算存儲資源消耗巨大，在存儲的使用上采取以下策略。

（1）為節省面積，首選單口SRAM 緩存數據。

（2）為解決DR、DW 的流水讀寫訪問沖突，采用乒乓BUFFER 的思路，如圖6 所示，將每層的結果寫入另一塊RAM。同時，多項式乘法時，可復用此RAM。

圖6 乒乓RAM

（3）將單個數據存儲劃分為2 個BANK，支持單周期兩讀兩寫操作，同時方便蝶形操作。

（4）對于NTT 與INTT 的旋轉因子，可選擇同步計算匹配或靜態預先存儲。若考慮靜態型，旋轉因子數據可存儲在ROM 中。

3.4.3 蝶形地址映射

全流水設計的蝶形地址訪問是NTT 算法設計最關鍵的要素。以n=16 進行說明，地址實際訪問序列如圖7 所示。

圖7 蝶形單元地址訪問序列

（1）首先，將0～7 位序數據存儲在BANK0 的0～7 地址；其次，將8～15 位序數據存儲在BANK1的0～7 地址。形成第一層的蝶形比特逆序訪問。

（2）完成單次蝶形運算后，按正常流程，如（0,8）序列對，運算結果需要相應地寫入實際地址0、地址8。但是，第二層的0、8 地址位于同一個BANK，將造成單周期兩次讀的沖突，并且不滿足第二層（0,4）蝶形序列對的要求。相應地，提出以下的存儲調整方案思路，如圖8 所示。

圖8 蝶形單元地址調整方案

①將SRAM0 蝶形操作（0,8）位序的0 位序結果寫入SRAM1 BANK0 的0 位序，8 位序結果寫入SRAM1 BANK1 的4 位序。

②將SRAM0 蝶形操作（1,9）位序的0 位序結果寫入SRAM1 BANK0 的1 位序，9 位序結果寫入SRAM1 BANK1 的9 位序。

③以此類推，形成圖8中第二層的存儲分布關系。

（3）調整讀順序，匹配實際讀序列對的需求。

調整后的位序同實際的位序位置關系對比如圖9所示。

圖9 蝶形調整地址與實際地址對比

可以看到，只需要對帶雙括號的讀順序進行互換，就可滿足真實的蝶形比特逆序操作，問題得以解決。

3.4.4 旋轉因子

旋轉因子模塊是NTT 中的重要子模塊，在實現中分為動態運算型旋轉因子電路與靜態存儲型旋轉因子電路。

動態型的資源花費主要在模乘運算上，在流水化設計中，需要提前啟動旋轉因子的運算，與NTT運算流水線進行匹配，如圖10 所示。同時需要調整蝶形的地址映射，使旋轉因子的模冪指數連續化。以n=16 為例，動態運算型需存儲對應每層的單位根，共log2n=4 個數據，第一層?0，第二層?8，第三層?4，第四層?2，?為2n階原根。每層經模乘器運算動態匹配，旋轉因子存儲量由n/2 減少到logn。

圖10 旋轉因子動態計算流水匹配

靜態存儲型旋轉因子電路由RAM 或者ROM 存儲所有運算的旋轉因子和相關參數。與動態型相比，靜態型只花費存儲資源，且主要與數據寬度和多項式維度n相關。旋轉因子的數據深度為n/2。

3.4.5 流水中斷

考慮以下兩個問題。

（1）如果采用動態型同步計算旋轉因子的方式，須將旋轉因子的地址映射調整為連續性訪問（旋轉因子為連續型模乘運算），對應的蝶形單元的地址映射為比特逆序操作。由于是地址比特逆序的訪問操作，在每層流水分界線前后，將帶來讀寫數據相關性問題。

（2）如圖11 所示，在NTT 運算每層的流水分界線后，同一時刻的下一層DR 與上一層的DW 操作將產生同片RAM 讀寫沖突問題。

圖11 流水讀寫沖突

在上述兩個問題中，問題（1）的處理方式一般采用數據前推操作，但是比特逆序的前后相關性問題在相關性的直接判斷上，難以進行統一判斷處理。結合問題（2），直接采用中斷流水的方式，可同時解決問題（1）和（2），如圖12 所示。

圖12 流水中斷

在性能上，由于每層蝶形運算將中斷5 個周期，性能降低約5/(n/2)，n通常取8 192，163 84 等，降低約0.1%及以下，可忽略不計。

3.4.6 模塊整體結構

NTT 算法流水化設計整體結構如圖13 所示，包括流水化蝶形單元、存儲模塊、地址映射模塊等。

圖13 NTT 算法流水化設計整體結構

ntt_pipe：6 級流水的訪問控制、存儲的讀寫訪問控制。

butterfly_pipe：蝶形單元的4 級流水運算。可同時支持6 級流水蝶形運算，4 級流水模乘操作，單周期的模加、模減運算。

madd_alg：模乘運算的最后一步減法操作、蝶形模加、蝶形模減、模除以2 運算。

addr_reflect：地址重映射，每層運算實際位序的調整。

bit_rev：地址逆序模塊，對最后一層蝶形運算的數據調整，用以支持INTT 運算的位序以及結果的正常序輸出。

SPRAM0/1：數據存儲器，存儲多項式系數。

ROM：mtwd 模塊存儲NTT 旋轉因子；minvtwd模塊存儲INTT 旋轉因子。

3.4.7 性能評估

采用單蝶形單元全流水實現，NTT/INTT 運算的周期數約等于(n/2)×log2n個周期。當n=256 時，約1 000 個周期；當n=8 192 時，約5.3 萬個周期。

當n=256 時，硬件RTL 代碼仿真波形如圖14所示，一次NTT 運算的周期數為1 065，同時經INTT 運算后，數據可成功還原。

圖14 NTT 算法流水化實現仿真驗證波形

3.5 方案評估對比

以(n/2)×log2n個時鐘周期為等同參考量：若n=8 192，q=256 bit，時鐘頻率約束500 MHz 的情況下，一次NTT/INTT 約耗時0.1 ms。方案評估結果對比說明如表1 所示

表1 方案評估結果對比說明

在資源的消耗上，若采用靜態型旋轉因子，單蝶形單元流水化設計需要3 個乘法器以及一組乒乓SRAM（即兩個單口SRAM）。

多周期并行化方案，若采用雙口SRAM，蝶形單元需要1 個乘法器，單次蝶形操作需要6 個時鐘周期，因此在并行6路的情況下，共使用6個乘法器。若采用單口SRAM，則單次蝶形操作需要8 個時鐘周期，并行8 路共使用8 個乘法器。

若采用動態型旋轉因子，乘法器資源相對于靜態型旋轉因子方案將翻倍。

因此，在資源與性能折中的情況下，采用流水化設計具有較高的資源性能比，為優先方案；若完全以性能為主，在資源盡可能滿足的條件下，可采用多周期并行化方案，同時進一步提高蝶形運算并行度，獲得更高的性能需求。

4 結語

本文針對典型整數型、浮點型全同態密碼算法資源密集型的特點，結合典型NTT 算法的實現流程，分析了NTT 算法硬件實現的關鍵問題與難點，為了支持算法參數的普適性，基于Montgomery 模乘算法結構，提出了多周期并行化設計與全流水化設計方案。方案中重點給出了蝶形單元并行化展開的地址映射算法，分析了全流水化設計的核心要點并給出了模塊整體結構以及仿真驗證結果。最后對兩種實現方案進行了資源性能的對比分析，依據資源和性能需求，為資源密集型NTT 算法的高效硬件設計提供參考。

另外，為了進一步提高整個模塊或系統的頻率，針對同態密碼算法的大位寬乘法器，可采用Wallace 壓縮樹[8]，對乘法器進行兩級或多級展開。在性能資源等同參考量下，對于多周期并行方案，將直接增加并行度的資源消耗，相應地，流水化設計僅增加流水深度和少量流水寄存器消耗，因此流水化設計將更具優勢。