同態(tài)加密算力開銷如何彌補(bǔ)？港科大等提出基于FPGA實現(xiàn)的同態(tài)加密算法硬件加速方案

當(dāng)前，各行各業(yè)中的隱私泄露問題層出不窮，人們對于隱私安全保護(hù)的需求日益提高。隨著相關(guān)法律法規(guī)體系的逐漸成熟，眾多隱私計算技術(shù)也應(yīng)運(yùn)而生，聯(lián)邦學(xué)習(xí)就是其中的佼佼者。通過結(jié)合同態(tài)加密、秘密共享、不經(jīng)意傳輸?shù)劝踩嬎惴椒?，?lián)邦學(xué)習(xí)使得多個數(shù)據(jù)持有者，可以在保證數(shù)據(jù)安全的前提下，協(xié)同構(gòu)建機(jī)器學(xué)習(xí)模型。在聯(lián)邦學(xué)習(xí)中所使用的多種隱私計算技術(shù)中，同態(tài)加密的功能和實用性舉足輕重。

在各行各業(yè)，不難想象這樣的場景，A 公司擁有大量數(shù)據(jù)，然而其并沒有人力或計算能力對這些數(shù)據(jù)進(jìn)行分析處理，因此，A 公司希望購買 B 公司的計算服務(wù)對數(shù)據(jù)進(jìn)行處理，但是，A 公司不希望 B 公司獲取這些數(shù)據(jù)的具體信息，因此，如果可以將數(shù)據(jù)進(jìn)行加密，再傳遞給 B 公司進(jìn)行處理，則可以滿足 A 公司的所有需求。因此，在這樣的場景下，我們需要一套加密體系，對密文執(zhí)行的一些運(yùn)算操作，可以等效為對明文執(zhí)行的運(yùn)算。

支持對密文進(jìn)行運(yùn)算操作的加密體系，被統(tǒng)稱為同態(tài)加密，而同態(tài)運(yùn)算則泛指對密文執(zhí)行的各種運(yùn)算。根據(jù)密文可執(zhí)行運(yùn)算的范圍，同態(tài)加密算法被劃分為全同態(tài)加密、部分同態(tài)加密、近似同態(tài)加密等。一般來說，對同態(tài)運(yùn)算沒有限制的加密算法被稱為全同態(tài)加密，而僅支持單一同態(tài)運(yùn)算的加密算法被稱為部分同態(tài)加密。誠然，全同態(tài)加密是一種非常理想、需求巨大的算法，然而，目前主流的全同態(tài)加密算法，運(yùn)算復(fù)雜度都相當(dāng)之高，計算時間之漫長，使其幾乎無法在生產(chǎn)行業(yè)中實現(xiàn)落地。因此，部分同態(tài)加密成為了更加現(xiàn)實的解決方案。Paillier 加密就是一套被廣泛使用的部分同態(tài)加密算法，它支持密文之間的加法運(yùn)算。

盡管相對于全同態(tài)加密，Paillier 加密的計算效率已經(jīng)較為可觀，但是，相比較于高效的明文處理，Paillier 加密系統(tǒng)還是不可避免地引入了大量計算開銷。在大數(shù)據(jù)相關(guān)產(chǎn)業(yè)迅速發(fā)展的今天，成千上萬的數(shù)據(jù)需要得到實時處理，而傳統(tǒng) CPU 的計算能力已經(jīng)無法滿足需求。

FPGA（Field Programmable Gate Array），全稱為現(xiàn)場可編程邏輯門陣列，是一種可以根據(jù)需求對底層電路結(jié)構(gòu)進(jìn)行設(shè)計更新的芯片，在通信、圖像處理等領(lǐng)域擁有廣泛的應(yīng)用。通過使用 FPGA 內(nèi)部邏輯資源構(gòu)建計算電路，例化大量計算引擎，可以提高計算并行度，實現(xiàn)對指定算法的加速計算。傳統(tǒng)意義上的 FPGA 開發(fā)為 RTL（Register-transfer Level）開發(fā)，開發(fā)人員通過硬件描述語言（Verilog 或 VHDL）控制寄存器讀寫、規(guī)劃時序邏輯等，描述具體的硬件功能。這種開發(fā)模式需要大量的開發(fā)經(jīng)驗以及較長的硬件開發(fā)周期，并不適用于開發(fā)人員經(jīng)驗不足或者亟須產(chǎn)出的項目開發(fā)。因此，HLS（High Level Synthesis）開發(fā)受到了很多開發(fā)者，尤其是科研工作者的青睞。HLS 是一種代碼綜合技術(shù)，開發(fā)人員可以通過高級語言（C 或 C++）描述運(yùn)算，HLS 開發(fā)套件將高級語言編譯為 Verilog 或 VHDL 代碼，再生成具體網(wǎng)表。開發(fā)者無需關(guān)心具體硬件電路的設(shè)計，只需構(gòu)造合理運(yùn)算邏輯，即可在短期內(nèi)完成一項 FPGA 工程。

使用 HLS 開發(fā)實現(xiàn)基于 FPGA 的 Paillier 加密運(yùn)算，不僅可以提高計算效率，對于同態(tài)加密以及聯(lián)邦學(xué)習(xí)的硬件加速探索，也有十分重要的意義。

為了實現(xiàn)硬件加速，合適的算法選擇十分必要。基于二進(jìn)制進(jìn)行運(yùn)算的芯片，包括 CPU，都可以輕松實現(xiàn)高效的加法、乘法、位移等運(yùn)算；然而取模、除法等運(yùn)算則一直是硬件電路難以啃下的硬骨頭，計算效率十分低下，顯然 Paillier 加密運(yùn)算中存在不可避免的取模和冪運(yùn)算。眾所周知，冪運(yùn)算由若干乘法組成，而模冪運(yùn)算圖片，可以由大名鼎鼎的快速冪算法拆解為若干少量的模乘運(yùn)算圖片。

那么是否存在一種算法，無需單獨(dú)取模，就可以實現(xiàn)模乘運(yùn)算呢？答案是肯定的，這個算法就是蒙哥馬利模乘算法。

圖一：蒙哥馬利模乘算法。

蒙哥馬利算法的基本思想如圖一所示，其中 l 為 M 的位寬，k 為基數(shù)，一般為 16、32、64 這樣遠(yuǎn)小于 1024，且 FPGA 可以直接進(jìn)行乘法運(yùn)算的位寬。可以看到，這個算法本質(zhì)上是一個二重循環(huán)，和普通的大數(shù)乘法十分相似，但是該算法通過引入?yún)?shù) q，保證中間結(jié)果可以被2^k整除（被 2 的整數(shù)次冪除本質(zhì)上就是向右移位），從而可以無誤差地通過移位操作完成除法，同時保證，完成了移位之后得到的最終結(jié)果一定位于區(qū)間[0,2M），從而可以通過一次數(shù)值比較和減法，將最終結(jié)果限制在[0,M），無形中完成了冪運(yùn)算。基于蒙哥馬利模乘運(yùn)算，再實現(xiàn)就成為了非常簡單的操作，實現(xiàn)的方法也有很多。

系統(tǒng)設(shè)計介紹

論文鏈接：https://arxiv.org/pdf/2007.10560.pdf

來自港科大 iSing Lab 等機(jī)構(gòu)的研究者以蒙哥馬利模乘運(yùn)算為核心，提出了一套基于 FPGA 的同態(tài)加密加速體系，如圖二所示，該系統(tǒng)被設(shè)想為部署在云服務(wù)器端，這些服務(wù)器屬于聯(lián)邦學(xué)習(xí)的參與方。該系統(tǒng)包括上位機(jī) CPU 以及 FPGA，二者使用 PCIe 接口通信。CPU 負(fù)責(zé)機(jī)器學(xué)習(xí)模型的正常訓(xùn)練工作，并將機(jī)器學(xué)習(xí)使用的浮點(diǎn)數(shù)編碼為適配同態(tài)加密方案的大整數(shù)，同時它將加密請求分批發(fā)送給 FPGA；FPGA 中為 Paillier 加密設(shè)計了高性能處理器，且硬件模塊被封裝為 OpenCL 內(nèi)核由 CPU 進(jìn)行調(diào)用。接下來，我們對 FPGA 內(nèi)部高性能處理器的設(shè)計進(jìn)行詳細(xì)介紹。

圖二：FPGA 聯(lián)邦學(xué)習(xí)加速系統(tǒng)。

一個 Paillier 處理器中包含了模冪、隨機(jī)數(shù)生成等所需的運(yùn)算功能，此 HLS 設(shè)計中例化了若干 Paillier 處理器以實現(xiàn)運(yùn)算的并行處理。此外，為了管理多處理器的工作，需要頂部模塊執(zhí)行數(shù)據(jù)分發(fā)以及計算結(jié)果收集的工作。顯然，由于 FPGA 內(nèi)部邏輯資源有限，此系統(tǒng)的運(yùn)算效率取決于可以例化多少 Paillier 處理器，而 Paillier 處理器的主要組成部分是蒙哥馬利模乘。因此，如何在硬件上優(yōu)化蒙哥馬利模乘運(yùn)算成為了主要工作。我們從資源分配和時序分析兩個方面對優(yōu)化工作進(jìn)行介紹。

資源分配

對于一個以計算功能為主的 FPGA 工程設(shè)計中，DSP、LUT 和 RAM 是總量最有限、最需要仔細(xì)規(guī)劃使用的底層邏輯資源。DSP 是 FPGA 內(nèi)部實現(xiàn)乘法運(yùn)算不可缺少的底層邏輯資源，目前主流 FPGA 中的單個 DSP 塊，可以在高時鐘頻率下實現(xiàn)兩個 16 比特?zé)o符號整數(shù)之間的乘法運(yùn)算，而通過串聯(lián)多個 DSP 塊，可以搭建出位寬更高的乘法器，比如，實現(xiàn)兩個 64 比特?zé)o符號整數(shù)之間的乘法運(yùn)算需要 16 個 DSP；LUT（lookup table 查找表）是 FPGA 內(nèi)部最基本的邏輯資源，我們需要結(jié)合 LUT 和其他邏輯資源構(gòu)建加法器、整數(shù)比較、有限狀態(tài)機(jī)等其他邏輯電路；RAM 是 FPGA 底層集成的高速存儲器，分為 BRAM 和 URAM 兩類，一般來說，單個 RAM 可以存儲 36Kb 數(shù)據(jù)，而單個 URAM 可存儲 288Kb 數(shù)據(jù)，在當(dāng)前工程中，可以使用 RAM 存放輸入輸出數(shù)據(jù)以及運(yùn)算中間結(jié)果。

由圖一所示，蒙哥馬利模乘算法由內(nèi)外兩重循環(huán)構(gòu)成，我們將單次內(nèi)部循環(huán)操作封裝為如圖三所示的處理單元，每個處理單元中包含兩個乘法器，分別用于計算 x*y 和 q*m，兩個乘法結(jié)果與外層循環(huán)的上一輪計算結(jié)果以及進(jìn)位（圖中未畫出）執(zhí)行加法操作。同時，為了避免 HLS 編譯代碼展開循環(huán)后，造成乘法器資源大幅膨脹，需要使用 ALLOCATION 指令將處理單元的個數(shù)限制為 1 個。

圖三：算法 1 內(nèi)部循環(huán)處理單元。

圖四：Karatsuba 快速乘法。

在處理單元的設(shè)計中，同時采用了 Karatsuba 算法，如圖四所示。根據(jù)乘法運(yùn)算的原理，容易看出，乘法運(yùn)算操作數(shù)的位寬減半，則總計算時間將減少至原先的四分之一左右。Karatsuba 算法將整數(shù)乘法拆分為了三個位寬僅為原來一半的整數(shù)乘法，從而節(jié)省了計算時間。根據(jù)該算法的原理，可以相應(yīng)地使用 DSP 資源例化出所需的乘法器。

在 RAM 的使用方面，不難注意到，用于加密的輸入數(shù)據(jù)大多是由浮點(diǎn)數(shù)編碼而成的，與大整數(shù)位寬相比，其有效數(shù)字很少。因此，可以將輸入數(shù)據(jù)存儲為稀疏向量，即只記錄非零元素和它們的索引，減少存儲占用。

時序分析

時序分析在 FPGA 開發(fā)中的重要性，絲毫不亞于對算法的優(yōu)化以及邏輯資源的分配。從電路的角度簡單來說，如果沒有合理的邏輯設(shè)計和資源布局，不僅會使得信號傳遞時間過長，還有可能出現(xiàn)多組信號爭搶相同硬件資源，導(dǎo)致局部堵塞的問題。

通常來說，開發(fā)者可操控的最小粒度的 FPGA 工作時間為一個時鐘周期，而 FPGA 完成一個時鐘周期所需的時間由時鐘頻率決定，即

因此，在降低時鐘周期數(shù)的同時提高時鐘頻率，是提升 FPGA 運(yùn)算性能的有效手段。

一般來說，實現(xiàn)一套算法所需要的時鐘周期數(shù)由其關(guān)鍵路徑所決定，所謂關(guān)鍵路徑，就是工作流程中，時間延遲最大的一條路徑。通過觀察蒙哥馬利模乘運(yùn)算的兩重循環(huán)，可以整理出，整個運(yùn)算包含次乘法，因此，如果我們例化了 n 個乘法器，每個乘法器需要運(yùn)行 t 個時鐘周期，則理想中整個蒙哥馬利模乘的時鐘周期為。考慮到之前所介紹的內(nèi)部循環(huán)處理單元中的兩個乘法可以并行執(zhí)行，我們可以例化兩個乘法器同時進(jìn)行計算；但是，由于不同的循環(huán)之間存在數(shù)據(jù)依賴關(guān)系，因此只能串行執(zhí)行循環(huán)。因此，系統(tǒng)設(shè)計的目標(biāo)是讓總時鐘周期接近。為了實現(xiàn)這一目標(biāo)，系統(tǒng)中進(jìn)行了以下三項優(yōu)化。

展開內(nèi)層循環(huán)：展開內(nèi)層循環(huán)的最大好處就是將內(nèi)層循環(huán)從一個單一的整體拆解為多個組成部分，從而實現(xiàn)多次迭代中無數(shù)據(jù)依賴部分之間的時間交疊（overlap），進(jìn)而最大程度地壓縮整體運(yùn)行時間。該操作可以通過 HLS 中的 UNROLL 指令實現(xiàn)。

將 q 的運(yùn)算插入內(nèi)層循環(huán)中：蒙哥馬利算法中 q 是執(zhí)行內(nèi)層循環(huán)的前提，但是從 q 的表達(dá)式中可以發(fā)現(xiàn)，只依賴于 S_i 的部分比特位，因此，當(dāng)某次迭代中 S_i 的這些比特位計算完畢后，即可同時開始進(jìn)行下一次迭代 q 中的計算。從而節(jié)省這部分的時間開銷。

流水線處理外層循環(huán)：通過展開內(nèi)層循環(huán)，并且使用 HLS 中的 PIPELINE 指令，設(shè)置流水線初始化間隔為內(nèi)層循環(huán)的迭代次數(shù)，內(nèi)層循環(huán)將自動地根據(jù)拆解的操作執(zhí)行流水線調(diào)度。該流水線處理示意圖如圖五所示。內(nèi)層循環(huán)展開后被拆分為四個部分 S_0 ， S_1 ,  S_2 和 S_3 。當(dāng) S_0 計算完畢后，即可開啟下次迭代中 q 的計算。而 q 計算完畢后，下一次迭代計算即可開始。

圖五：蒙哥馬利模乘運(yùn)算流水線處理示意圖。

通過以上處理，不同迭代的運(yùn)算操作被最大程度地交疊在一起，考慮到完成外層循環(huán)所需迭代次數(shù)較多，可以近似認(rèn)為，完成整個蒙哥馬利模乘運(yùn)算所需時鐘周期約為圖片。

達(dá)成時鐘周期的設(shè)計目標(biāo)后，我們還希望能夠提高 FPGA 邏輯電路的時鐘頻率。盡管主流 FPGA 中的 DSP 組件的工作頻率都可以達(dá)到 400MHz 以上，但是，由于硬件資源的限制，并且考慮到系統(tǒng)中邏輯電路的復(fù)雜程度，將整個系統(tǒng)的工作頻率提高到這個數(shù)值幾乎不可能。為了盡力提高工作頻率，本系統(tǒng)設(shè)計中做出了如下優(yōu)化：

限制乘法操作數(shù)位寬：在蒙哥馬利算法的介紹中，我們提及，基數(shù)一般選擇為 FPGA 可以輕易進(jìn)行乘法運(yùn)算的位寬。顯然，如果直接將選擇為 1024，F(xiàn)PGA 需要漫長的時間才能完成如此大位寬的乘法運(yùn)算。因此，可以將限制為 32，便于掌控整個時序邏輯。

將乘法器聲明為流水（Pipelined）乘法器：流水乘法器可以將大位寬的乘法拆分到多個時鐘周期執(zhí)行，從而緩解緊張的時序。簡單來說，如果我們設(shè)置系統(tǒng)頻率為 200MHz，乘法器幾乎不可能在一個時鐘周期，也就是 5 納秒內(nèi)完成 64 比特整數(shù)之間的乘法，但是如果將乘法時間延長到 6 個時鐘周期，則乘法器則可以相對容易地在 30 納秒內(nèi)完成該乘法操作。

簡化控制邏輯：這幾乎是 FPGA 開發(fā)中不可缺少的優(yōu)化操作了，通過縮短邏輯電路的長度，可以增加 FPGA 在更高時鐘頻率下完成信號傳遞的頻率。在本工程中，可以使用獨(dú)熱編碼（One-hot Encoding）表示狀態(tài)機(jī)的狀態(tài)，獨(dú)熱編碼可以有效提高狀態(tài)機(jī)的查詢和匹配速度，優(yōu)化時序邏輯。

系統(tǒng)性能測試

完成硬件設(shè)計后，通過使用 OpenCL API，上位機(jī)可以調(diào)用 FPGA 實現(xiàn)運(yùn)算的硬件加速。我們使用 FPGA 硬件加速內(nèi)核分別構(gòu)建了 Paillier 加密和解密運(yùn)算算子，并對比了它們和 CPU 的運(yùn)算性能，其中 CPU 的運(yùn)算通過調(diào)用 Paillier 運(yùn)算庫 PHE 實現(xiàn)，對比結(jié)果如圖六和圖七所示。當(dāng)公鑰位寬為 1024 比特時，F(xiàn)PGA 加速系統(tǒng)在加解密運(yùn)算中分別實現(xiàn)了 10.62 倍和 2.76 倍的加速比。

圖六：FPGA 和 CPU 加密性能對比。    

圖七：FPGA 和 CPU 解密性能對比。

將 FPGA 硬件加速集成到主流聯(lián)邦學(xué)習(xí)框架 FATE 中后，我們也看到了不錯的性能提升。我們使用 PyOpenCL API 將 FPGA 硬件加速功能集成為單一模塊，嵌入到 FATE 中執(zhí)行加密運(yùn)算。分別執(zhí)行十次邏輯回歸迭代和十次線性回歸迭代后，我們得到了圖八所示的測試結(jié)果：FPGA 加速 FATE 削減了原始 FATE 中 71.2% 的加密時間。

圖八：單次訓(xùn)練迭代中 FPGA 加速 FATE 和原始 FATE 的加密時間對比。

總結(jié)及展望

同態(tài)加密是一種強(qiáng)有力的隱私保護(hù)技術(shù)，對于它們的探索，是近年來炙手可熱的研究方向；FPGA 是一種資源豐富的運(yùn)算處理芯片，對于高并行度的計算任務(wù)可以帶來顯著的性能提升。對于高性能 FPGA 工程的追求，在當(dāng)前階段還是難以擺脫長期的 RTL 開發(fā)。通過使用 HLS 快速開發(fā)基于 FPGA 的同態(tài)加密工程，是對 FPGA 在隱私安全計算行業(yè)進(jìn)行角色定位的有效探索與嘗試。近年來，F(xiàn)PGA 的主流供應(yīng)商 Xilinx 和 Intel 在可編程硬件的高級語言開發(fā)上不斷增加投入，F(xiàn)PGA 的入手難度也逐漸降低。相信隨著數(shù)據(jù)安全重要性的不斷提升，工業(yè)界將浮現(xiàn)出更多基于 FPGA 的安全計算產(chǎn)品，而類似于 HLS 的硬件上層開發(fā)模式，也將在這個領(lǐng)域逐漸占據(jù)一片天地。

本文作者為香港科技大學(xué) iSing Lab 楊照雄、胡水海、陳凱。iSing Lab 是一所專注于高性能數(shù)據(jù)中心網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)系統(tǒng)以及聯(lián)邦學(xué)習(xí)框架研究的實驗室。近 5 年時間中，該實驗室在網(wǎng)絡(luò)系統(tǒng)領(lǐng)域頂級會議 ACM SIGCOMM 和 USENIX NSDI 等定會發(fā)布論文 10 篇，根據(jù)計算機(jī)科學(xué) CSRankings 的排名, 名為亞洲第一。