魔方派:面向全同態加密的存算模運算加速器設計

李 冰 劉懷駿 張偉功

①(首都師范大學交叉科學研究院 北京 100048)

②(首都師范大學信息工程學院 北京 100048)

1 引言

模算法是密碼學中的核心計算，從傳統密碼[1]到后量子密碼全同態加密(Fully Homomorphic Encryption , FHE)幾乎都會用到模運算。基于理想格構建的全同態加密由于具有抗量子計算的安全性，自2009年Gentry[2]提出后備受關注，其完整過程如圖1所示。經過十幾年的發展，全同態密碼逐漸從理論走向實際，以BFV[3]為代表的全同態密碼機制在醫療診斷、云計算、生物醫藥、機器學習等領域得到應用[4]。比如，在云計算領域，用戶端將數據進行加密，加密數據上傳到云端服務器，不解密完成計算，計算結果下載到用戶端完成解密，用戶端得到計算結果。云端不需要解密完成隱私數據的計算，進一步提高隱私數據的安全。雖然全同態密碼提高了隱私計算的安全性，但是全同態密碼高昂的計算代價阻礙了其廣泛應用。即使經過算法和軟件設計優化，FHE全同態加密中一個整數明文的密文數據規模達到53 MByte[5]，端側生成的密鑰最大都會達到11 k Byte[6]。密文以及密鑰數據規模過大引起嚴重的計算和訪存瓶頸，導致FHE密文上的計算相比未加密數據的計算慢10 000～100 000倍[7]。端側計算設備的硬件資源有限，一般無法部署能耗高的GPU計算單元，傳統的計算機架構[8]在面對全同態加密中數據規模幾十MByte的密文以及密鑰處理時就會遇到嚴重的內存墻問題，產生大量數據搬運造成能量消耗。

圖1 全同態加密完整過程

存內計算(Processing In Memory, PIM)是不同于傳統計算架構的新興計算范式，具備在存儲器內執行計算的能力，基于存內計算的計算設備往往有功耗低、面積小、計算速度高的特點，因而存內計算是為在端側執行數據密集型應用提供有效的解決途徑[9]。本文對端側全同態加密計算的計算進行分析發現，在端側的整體計算中，模計算延遲開銷占比較大，而且即使是采用優化的計算算法，計算執行時間減少不明顯，根本原因是模計算執行過程中，訪存行為占用了大量時間。綜上，結合存內計算以及全同態加密計算的特性，本文設計一個名為魔方派(Processing-In-Memory Modular , M2PI)的模運算加速器，用來優化全同態加密在端側中的計算。本文的主要貢獻：

(1) 本文分析了CPU 平臺上，BFV加密、解密、密鑰生成操作中各個關鍵算子的計算開銷，發現模計算的計算開銷占比達到了平均41%。進一步地，分析優化的巴雷特算法計算過程中計算和訪存操作的延遲，發現訪存延遲是造成模計算計算延遲過大的原因。

(2) 本文提出一種基于存內計算陣列的模計算電路。一方面，針對存內計算陣列的計算特性，對巴雷特模計算算法進行優化，減少了計算步驟；另一方面，提出一種基于存內計算陣列的減法電路，完成巴雷特模計算算法中的減法操作。減法操作的優勢來自兩方面：(a)基于10T-SRAM的存儲單元，能夠用更低延遲完成NOT,NOR等邏輯操作；(b)優化的加法電路。相比于以往存內計算的加法電路，本文所提的電路用更少的計算周期完成計算。

(3) 在實驗中，對全同態BFV方案的各計算操作中，不同規模的被模數和模數的模計算進行評估，實驗結果表明，本文所提加速器相比CPU中模計算有1.77倍的計算速度提升以及32.76倍能量的節省。

2 背景

2.1 全同態密碼的模計算

模運算是許多加密應用必不可少的，并且密碼方案的性能在很大程度上取決于模運算[10]的速度。為了優化模計算的執行，巴雷特模算法是通常采用的優化算法，將模計算中的除法用位運算以及減法來實現。巴雷特模計算的算法如算法1所示。

在全同態加密系統中，端側主要完成密鑰生成、加密和解密計算，在這幾種計算中，模操作頻繁出現。下面以BFV同態加密方案的密鑰生成和加密計算為例說明全同態加密的模計算操作。

(1) 密文生成(Enc)：在加密過程，明文多項式(m)與公鑰對 (p0,p1) ，經過一定計算得到密文對c=(c0,c1)， 密文對生成計算公式為c0=[?·m+p0·u+e0]q,c1=[p1·u+e1]q，其中u, e0和e1是從高斯分布x采樣得到的，e0和e1為誤差，[]q是模q計算。

算法 1 巴雷特模算法

(2) 公鑰對 (p0,p1)生成(Pk_gen)：計算公式，p0=[-(a·s+e)]q,p1=a，其中a從多項式環Rq隨機抽樣的多項式，e是從高斯分布x隨機抽樣的誤差，s是私鑰，一個n次多項式，通過從多項式環R2隨機抽樣得到，[]q是模q計算。

(3) 重線性化鑰生成(Rk_gen)：全同態乘法計算會導致密文規模變大，所以需要重線性化鑰來控制密文規模。重線性化鑰是一組多項式，([-(ai·s+ei+Ti·s2)]q,ai),i∈{0,1,...,l}其中T=。ai從多項式環Rq隨機抽樣的多項式，ei是從高斯分布x隨機抽樣的誤差。

其中計算中所涉及的多項式次數為n，n通常是2的冪且大于210、而密文模數q通常是2的冪，通常是215, 219, 227甚至更大[11]。因此，全同態加密方案中，模數和被模數規模過大，對模計算的執行造成了巨大壓力。本文分析發現在BFV方案端側的密鑰生成、加密和解密操作計算過程中頻繁的模計算，而且耗時占比最高。

2.2 存內計算交叉陣列

存內計算(PIM)作為一種非常有潛力的新興技術，支持在存儲單元內完成計算，減少了數據的移動過程，從而緩解數據密集算法在馮·諾依曼架構的數據瓶頸問題。在眾多存內計算實現的存儲設備中，與憶阻器(Resistive Random Access Memory,ReRAM)和動態隨機存取存儲器(Dynamic Random Access Memory, DRAM)這些存儲設備相比，靜態隨機存取存儲器(Static Random-Access Memory,SRAM)由于其成熟的CMOS制造工藝、低訪問延遲和幾乎無限的寫耐久性備受關注。基于SRAM存內計算陣列可以實現矩陣乘、邏輯計算甚至高精度的浮點計算[12]，基于SRAM 的存內計算已經被應用到全同態加密計算中，用于提高全同態加密計算的執行效率。例如文獻 [13]利用6T-SRAM實現了格密碼加密機制中用到的數論變換(Number Theoretic Transform, NTT)算法的加速；文獻[6]也是為了加速格密碼加密機制中用到的NTT；還有一些工作也用到了存內計算架構來加速加密過程，如文獻[14]主要優化了全同態計算(全同態加、減和乘)，他們在提出的設計結構中實現了大數乘法，以此提高整體加密計算的速度；文獻[15]在內存中實現端到端的全同態加密(FHE)計算，并且全同態加密計算中開銷最大的自舉(Bootstrapping)操作進行了加速。這些工作都展示了存內計算陣列是有效緩解全同態加密中內存墻問題的解決方案，但是這些工作大多都是為了加速云側的全同態計算，對于端側的各個計算過程執行過程以及算子尚缺少深入的分析，而端側的全同態加密在云計算場景中至關重要，所以本文提出了基于存內計算的加速端側計算的瓶頸：模運算，以此使得端側的計算執行過程速度得到提高。

3 基于存內計算陣列的模計算

3.1 研究動機

本文分析全同態加密中端側執行的4個計算過程：公鑰生成(Pk_gen)、重線性化鑰生成(Rk_gen)、加密(Enc)以及解密(Dec)，發現在每個計算步驟中，巴雷特模計算的執行時間超過多項式計算的執行時間，而巴雷特計算執行時間過長的問題是訪存延遲造成的。在實驗中，本文參考pyFHE[16]庫在C++中實現了BFV方案，統計各個計算步驟中模計算以及多項式計算在Intel(R) Core(TM) i7-7700HQ CPU平臺上的執行時間。考慮到模計算的數據規模由多項式系數n，密文模數q決定，在不同規模的密文模數q情況下，對端側4個計算過程中模計算的執行時間分別進行了統計，并與它們各自的多項式計算延遲進行對比。端側4個計算過程中模計算與多項式計算執行時間對比如圖2所示。參考文獻[17]，將密文多項式的系數n設置為1 024，圖2(a)—圖2(c)中密文模數分別對應q=215, q=219以及 q=227。可以看出，在不同計算過程中，模運算比多項式計算的執行時間長，尤其是在重線性化密鑰生成(Rk_gen)的計算中，模計算的執行時間是多項式乘法的1.6倍。本文進一步分析了巴雷特模計算的執行時間，結果如圖3所示，可以看出巴雷特模的執行時間與普通模計算相比，計算執行時間并沒有顯著下降，甚至有的計算中，巴雷特模比模運算的執行時間還略高，比如重線性化密鑰生成(Rk_gen)中模計算的計算執行時間反而比之前增大了19%。本文以q=227為例，分析端側4個計算過程中巴雷特模中計算時間和訪存時間比例，結果如圖4所示，4個計算中，巴雷特模計算用于計算的時間最高僅僅占到了模計算總時間的3%，而訪存時間最高卻占到了97%的比例，訪存明顯成為模計算計算效率的瓶頸，而存內計算能夠在存儲器中完成計算，大大降低了巴雷特模中數據搬運導致的過高的計算延遲。

圖2 不同參數規模下各階段算子執行時間對比

圖3 優化前后模計算延遲對比

圖4 巴雷特模運算中計算和訪存時間對比

3.2 模計算陣列設計

針對模計算的訪存瓶頸，本文提出一種基于PIM陣列的模計算執行單元，在被模數的存儲位置進行計算，避免了數據搬運產生的開銷。模計算存內陣列的總體設計如圖5(a)所示。本文的模計算PIM陣列是128×512大小，陣列的基本存儲單元是10TSRAM[18]，支持讀寫并行，如圖6(a)所示。在計算之前，被模數(即多項式系數)存儲在SRAM的行中。特別地，巴雷特模計算中的除法和乘法操作由存內計算陣列的移位操作完成。如圖5(b)所示陣列用來執行大數的移位和減法操作，其中每個存儲單元完成按位邏輯運算。為了實現移位和減法操作，本文存內計算陣列包含以下功能模塊：預充電器、控制器、行解碼器、移位掩碼器、讀控制器、寫控制器和比較器[19]，用于支持讀寫的同時進行，以及邏輯計算操作，下面介紹各功能模塊的不同作用：

圖5 用于模計算的 PIM 陣列

圖6 按位邏輯計算

(1)控制器：控制電路操作的執行，產生讀、寫、具體的邏輯計算操作的控制信號。

(2)行解碼器：激活需要寫操作時的WL線，讀操作和計算時RTL和RFL線。

(3)移位掩碼器：接受模數的位數信息，用于產生移位操作的地址掩碼以及移位操作的方向，其中掩碼最高位是移位碼，1表示左移，0表示右移。

(4)讀控制器：根據RTL和RFL線的選通情況控制電路每列的RT和RF線進行讀取操作，RT和RF線僅用來進行讀操作，以及邏輯計算。

(5)寫控制器：根據WL選通的待寫入行，控制電路的各個WT和WF線對SRAM單元進行寫操作，WT和WF線僅用來進行寫。本文設計獨立的讀位線和寫位線，支持讀寫并行性。

(6)比較器：用于對計算結果是否在需要的范圍內進行判定，然后根據判斷的不同情況決定下一步的操作。

3.2.1 邏輯計算存內計算單元

(1)按位邏輯計算。本文設計的陣列采用10TSRAM單元，其電路圖如圖6(a)所示，支持同時讀寫，每個存儲單元完成按位邏輯計算。RT和RF位線用于邏輯運算的實現，當僅導通RTL線時晶體管T0會先被導通，將RT0預充電到VDD電位，如果存儲單元中存儲的數據是1也就是高電位，晶體管T1就會導通，經過兩個晶體管T0和T1將RT0線的電位放電至低電位。反之如果存儲的是0，晶體管T1就不會導通，這樣一來RT0就保持了高電位。依據此邏輯，將一列中兩個單元同時用RT線讀取，讀出的匯聚電壓就是兩單元的NOR邏輯運算結果。圖6給出了本文利用10T-SRAM單元完成NOR計算和NOT計算電路示意圖。圖6(b)是完成兩個數值的NOR，其中實線表示選通的線，虛線表示沒有選通，同列中兩個單元分別存儲了1和0，同時導通RTL0和RTL1線，輸出結果0從RT0讀出，這樣，通過讀操作完成NOR的計算。如圖6(c)所示，單個單元導通RTL0用RT0線讀取，就實現了NOT邏輯，得到NOT結果0。

(2)N位邏輯計算。依據以上按位邏輯計算的存內單元，實現N位數據的邏輯計算，如圖7所示。圖7(a)中兩個N bit數據的邏輯NOR運算，兩個N bit數據分別存儲第0行第0列到n–1列和第1行第0列到n–1列，執行計算時，RTL0和RTL1線同時導通，NOR運算的結果從RT0到RTn–1進行讀取。同理，一個N bit數據的NOT計算，如圖7(b)所示，通過導通RTL, NOT計算結果從RT0到RTn–1進行讀取。

圖7 多比特邏輯運算

3.2.2 基于存內計算陣列的巴雷特模

本文首先約簡巴雷特模算法，消除其中的除法和乘法，簡化為1次右移，1次左移以及1次減法；之后利用PIM按位并行計算的優勢，在存內陣列實現高效的移位和減法操作，從而完成巴雷特模計算。

(1)巴雷特模優化。算法2是優化后的巴雷特模，這里省略算法1中第(1)步的除法過程，合并了第(2)(3)(4)和第(6)步中的右移和乘法，將它們轉化為1次右移和1次左移運算，如算法2中(1),(2)步所示。

(2)優化后的存內巴雷特模計算。存內計算陣列中的移位和減法計算如圖8(a)、圖8(b)所示。

圖8 PIM 中實現計算

(a) 右移：根據移位掩碼器給出的掩碼地址信息，在模計算結果行的MSB位地址單元開始依次寫入n–1個0，同時，將被模數c的MSB位寫入之后的位置，直到該行數據寫滿。這樣，c中溢出部分自動截斷，完成右移計算，移位結果x存儲在陣列中。陣列同一行中存儲的所有被模數都可以同時進行計算，所以只需使能1次移位計算就可以同時得出該行所有待計算數據的移位結果。

(b) 左移：根據移位掩碼器給出的掩碼地址信息和左移信號，在結果行的LSB位地址開始寫入n–1個0，被模數x 從LSB位順序寫入余下地址，移位結果a存儲在陣列中。

算法 2 PIM中執行巴雷特模算法

(c) 減法：最后執行c-a操作，這里通過補碼加法實現。本文在內存陣列中首先實現了全加器邏輯[20]，減法過程如算法3所示，其中形如(c+na)′的計算表示N OR(c,na)， t和b為中間結果變量。NOR運算按照3.2.1節中多比特邏輯計算進行的。在陣列中開辟一行存儲a的補碼，再依據多比特邏輯計算完成第(1)步中的NOR計算。需要注意的是，第(2)步是加法邏輯中的進位計算過程，并不能按照多比特邏輯計算那樣完成所有比特的計算結果，因為高比特需要等待低比特的進位結果再執行計算，由此只能逐比特進行計算(將b最低位初始化為0)，如圖8(b)所示的計算流程。最后再根據多比特邏輯計算完成第(3)步得到Sub這一行就是c與a的減法結果。

算法 3 PIM 中實現減法

4 實驗結果及分析

4.1 實驗設計

為了評估本設計的延遲和能耗，本文首先通過Virtuoso平臺采用65 nm工藝，激勵源時鐘頻率為100 MHz，供電電壓為1.1 V，對10T-SRAM單元進行了驗證仿真，得到其讀寫延遲為6.61 ns，讀能量293.3 fJ，寫能量316.3 fJ，如表1所示。器件的參數參考了Yang等人[21]的工作。然后本文修改Neurosim[11]模擬器中的陣列設計參數，采用同樣的65 nm工藝，陣列的時鐘頻率為100 MHz，供電電壓為1.1 V，陣列單元總數為65 536個，每個單元存儲1 bit數據。對本文設計的模計算陣列進行了延遲和能量的仿真計算。存內計算陣列的總面積為0.069 mm2。

表1 實驗參數設置[11,21]

為分析本設計對于加密算法中模運算效能的提升，本文根據實驗設置1：q=215；實驗設置2：q=219；實驗設置3：q=227來進行優化效果驗證。觀測分析這3種實驗參數下，本文設計的PIM陣列中執行模運算的效果。依據本文的實驗設計對實驗CPU中的延遲和能耗進行了統計，并將實驗結果與在CPU中直接進行模計算結果(圖10中CPU_Mod)以及在CPU中執行巴雷特模計算結果(圖10中CPU_Barrett)進行了對比。

4.2 實驗結果

本文方法相較于軟件中執行巴雷特模計算算法(CPU_Barrett)，在q=215, q=219, q=2273種參數設置下執行時間都有非常明顯的提升，如圖9所示。q=215時巴雷特模計算速度提升最高，其4個計算過程的模計算執行速度總和提升了3.27×104倍；而q=227時巴雷特模計算相對提升的速度較少，但4個計算過程的模計算執行速度總和也提升了1.74×104倍。而后本文又以在CPU中直接執行4個計算過程的總時間為基準，對比了3種參數設置下端側4個計算過程總時間(模計算加多項式計算時間和)在本設計中執行速度的提升。結果如圖10所示，3種參數設置下的執行時間均有明顯提升，其中在q=227時整體計算執行速度提升了1.77倍。公鑰生成(Pk_gen)階段在q=227時提升速度最高達到1.74倍，3個參數設置的公鑰生成速度平均提升了1.63倍；重線性化密鑰生成階段(Rk_gen)在q=219時提升速度最高達到1.94倍，3個參數設置的重線性化密鑰生成速度平均提升了1.91倍；加密階段(Enc)在q=215時提升速度最高達到1.7倍，3個參數設置的加密速度平均提升了1.66倍；解密階段(Dec)在q=215時提升速度最高達到1.84倍，3個參數設置的解密速度平均提升了1.76倍。本文統計了端側4個計算過程總體計算過程能量的消耗情況，如圖11所示。本文以在CPU中直接計算4個計算過程的執行能量為基準，可以看出：在本文所提出的方案中進行計算能量消耗最低在q=215時相較于CPU 4個計算過程平均節省了32.76倍，在q=227時消耗能量最高4個計算過程也平均節省了7.99倍。

圖9 PIM 中執行模運算與之前結果對比

圖11 優化前后 4 個計算過程執行能量節省

5 結論

本文提出一種基于存內計算陣列的模運算加速器，并針對不同參數設置下的模運算分別進行了實驗比對。結果表明，本文加速器相比CPU有1.77倍的計算速度提升以及32.76倍能耗的節省。