徐鵬飛, 李楨旻, 王曉蕾, 杜高明

(合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院,安徽 合肥 230601)

全同態(tài)加密的概念首次由文獻(xiàn)[1]提出,然而構(gòu)造全同態(tài)加密策略卻是一個(gè)難題;文獻(xiàn)[2]首次提出基于理想格的全同態(tài)加密策略(fully homomorphic encryption,FHE),在無需解密的情況下可以直接對(duì)明文進(jìn)行任意計(jì)算,為云端安全計(jì)算以及隱私保護(hù)提供一種解決方法,但是由于性能過低無法應(yīng)用到實(shí)踐中。目前速度已經(jīng)成為全同態(tài)加密策略應(yīng)用的最主要限制因素,可以通過軟件或者硬件實(shí)現(xiàn)方式來對(duì)全同態(tài)加密策略進(jìn)行加速。然而相較于硬件加速,軟件實(shí)現(xiàn)的效率對(duì)于實(shí)際應(yīng)用來說還是太低了；文獻(xiàn)[3]的研究中,有限層次全同態(tài)加密方案BGV中的矩陣-向量乘法器基于GPU實(shí)現(xiàn)也至少需要2 s;文獻(xiàn)[4-7]采用硬件實(shí)現(xiàn)的方式來對(duì)加密方案進(jìn)行加速;文獻(xiàn)[8]首次提出GSW(Gentry-Sahai-Waters)全同態(tài)加密算法,加密后的密文是一個(gè)較大的矩陣,利用近似特征向量作為密鑰的方式來構(gòu)造加密策略。為了降低加密延遲,文獻(xiàn)[8]采用硬件實(shí)現(xiàn)該加密算法,并通過FPGA開發(fā)板對(duì)其進(jìn)行加速,將加密時(shí)間與CPU加密GSW算法時(shí)間進(jìn)行對(duì)比,平均加速比可以達(dá)到36.29。

1 GSW全同態(tài)加密基本概念

1.1 基本原理

GSW同態(tài)加密方案可以根據(jù)不同的解密算法構(gòu)造出如下2套解密方案:① 選擇Dec作為解密算法,該解密算法僅能解密出0或1;② 解密算法是MPdec解密算法,使用該算法可以解密出u∈Zq。在GSW同態(tài)加密方案中,密文C是一個(gè)帶有較小誤差的N×N階矩陣,私鑰v是一個(gè)至少擁有一個(gè)較大系數(shù)的N階向量,解密需要采用公式Cv=uv+e,其中e為一個(gè)較小的帶錯(cuò)向量。為了能夠從密文中正確解密出明文u,需要選取密文的第i行,即

x←〈Ci,v〉=uvi+ei

(1)

(2)

從原理上來看,GSW同態(tài)加密算法本質(zhì)上是利用近似特征向量與特征值的關(guān)系,其中私鑰v是密文C的近似特征向量,同時(shí)明文u也是密文C的特征值。

1.2 加解密步驟

(3)

同時(shí)令v=Powersof 2(s),函數(shù)Powersof 2是將向量s中的第i個(gè)數(shù)值si分別乘以2i,假設(shè)b是一個(gè)n維向量,那么Powersof 2滿足:

Powersof 2(b)=(b1,2b1,…,2l-1b1,…,

bn,2bn,…,2l-1bn)

(4)

(3) 加密算法。隨機(jī)生成矩陣R←{0,1}N×m,根據(jù)如下公式得到密文矩陣,即

(5)

Flatten(a′)=BitDecomp(Bitdecomp-1(a′))

(6)

函數(shù)Bitdecomp-1滿足:

(7)

(8)

(5) 根據(jù)解密公式D1v=uv得到明文u。

1.3 參數(shù)設(shè)置

根據(jù)選定的安全等級(jí)分別確定各類安全參數(shù)以及所需要的硬件內(nèi)存,見表1、表2所列。

表1 GSW同態(tài)加密參數(shù)以及數(shù)據(jù)位寬

表2 矩陣的數(shù)據(jù)位寬及所需內(nèi)存

2 硬件加速方法

本節(jié)將介紹基于FPGA的硬件設(shè)計(jì)方法,并結(jié)合改進(jìn)的10×10脈動(dòng)陣列和數(shù)據(jù)拼接及復(fù)用方法來降低系統(tǒng)功耗和減小訪存次數(shù),最終縮短加密所需時(shí)間。

2.1 脈動(dòng)陣列的介紹

脈動(dòng)陣列(systolic array,SA)的概念是一種應(yīng)用于多處理器的體系結(jié)構(gòu),由多個(gè)相同的、結(jié)構(gòu)簡(jiǎn)單的計(jì)算單元(processing element,PE)以網(wǎng)絡(luò)的形式連接而成,具有并行性、規(guī)律性、局部通信的特征。脈動(dòng)陣列可以是單維的也可以是二維或三維的。本文使用二維脈動(dòng)陣列,二維脈動(dòng)陣列有2個(gè)輸入方向,暫且定為X和Y方向,并采用脈動(dòng)陣列來對(duì)2個(gè)矩陣進(jìn)行乘法運(yùn)算。矩陣R從X方向輸入到脈動(dòng)陣列中,而矩陣A將從Y方向輸入。由于矩陣R中的每個(gè)數(shù)據(jù)均為1 bit,而矩陣A的每個(gè)數(shù)據(jù)位寬為12 bit,本文將傳統(tǒng)的脈動(dòng)陣列PE乘法單元優(yōu)化,如圖1所示。

圖1 普通PE與優(yōu)化后PE結(jié)構(gòu)對(duì)比

圖1a所示為普通的脈動(dòng)陣列PE計(jì)算單元,由一個(gè)加法器和乘法器以及2個(gè)寄存器R構(gòu)成。圖1b所示為優(yōu)化后的PE計(jì)算單元,矩陣R的每個(gè)數(shù)據(jù)為1 bit,當(dāng)輸入值b為1時(shí),乘法結(jié)果為a的輸入;當(dāng)輸入值b為0時(shí),乘法結(jié)果為0。因此本文用一個(gè)選擇器來代替乘法器,隨著脈動(dòng)陣列維數(shù)的增加,減小的乘法器數(shù)量也會(huì)越大。圖1中的寄存器R用來寄存輸入值以及PE計(jì)算單元的乘累加結(jié)果。本文將普通PE計(jì)算單元和優(yōu)化后的PE計(jì)算單元進(jìn)行對(duì)比,經(jīng)過Design Compiler綜合后,采用SMIC 40 nm工藝,最終得到的結(jié)果見表3所列。從表3可以看出,通過這種優(yōu)化方法可以大量減少DSP資源和功耗,單個(gè)PE計(jì)算單元功耗從83.27 μW降低到80.22 μW,下降了3.7%,單個(gè)PE計(jì)算單元面積從475.93 μm2降到474.96 μm2。

表3 2種PE資源對(duì)比

2.2 脈動(dòng)陣列數(shù)據(jù)輸入端控制單元

若要脈動(dòng)陣列單元完成正確的乘法計(jì)算,則需要控制好脈動(dòng)陣列2個(gè)輸入端的數(shù)據(jù)格式,本文輸入端控制單元的作用就是為脈動(dòng)陣列組織好數(shù)據(jù)格式,由于脈動(dòng)陣列的X軸和Y軸的數(shù)據(jù)均按照后一個(gè)數(shù)據(jù)輸入相對(duì)于前一個(gè)數(shù)據(jù)輸入延遲1個(gè)周期的規(guī)律,這也是由脈動(dòng)陣列的特點(diǎn)決定的,這里采用移位寄存的方法,將輸入的數(shù)據(jù)按照不同的通道寄存相應(yīng)的周期數(shù),從而保證數(shù)據(jù)輸入的正確性?？刂茊卧慕Y(jié)構(gòu)如圖2所示。

圖2 輸入端控制單元結(jié)構(gòu)

本文將采用10×10二維脈動(dòng)陣列,故X軸和Y軸各有1個(gè)數(shù)據(jù)控制單元,每個(gè)控制單元各有10個(gè)數(shù)據(jù)輸入通道,數(shù)據(jù)輸入端控制單元工作時(shí)要求每個(gè)周期10個(gè)數(shù)據(jù)同時(shí)進(jìn)入到10個(gè)通道中。然而1個(gè)周期僅能從存儲(chǔ)器Rom中讀出1個(gè)數(shù)據(jù),為了能夠在1個(gè)周期中一次性讀出10個(gè)數(shù)據(jù),下面將介紹一種數(shù)據(jù)拼接方法。

2.3 數(shù)據(jù)拼接方法

因?yàn)樽x取存儲(chǔ)器Rom時(shí)1個(gè)周期只能讀出1個(gè)數(shù)據(jù),然而為了與10×10脈動(dòng)陣列的20個(gè)通道結(jié)合起來,本文提出一種數(shù)據(jù)拼接方法,將矩陣R每10行的10個(gè)數(shù)據(jù)拼成1個(gè)數(shù)從而得到1個(gè)10 bit數(shù)據(jù),同時(shí)將矩陣A的每10列的10個(gè)數(shù)據(jù)拼接成1個(gè)數(shù),即得到1個(gè)120 bit數(shù)據(jù),從而將原來需要相乘的2個(gè)矩陣R(1 260×2 320)、A(2 320×9)轉(zhuǎn)化為R(1 260×2 320)、A(2 320×9)。最后將矩陣R中的數(shù)據(jù)按行存儲(chǔ)形式存到Rom-R中,矩陣A中的數(shù)據(jù)按照列存儲(chǔ)方式存到Rom-A中。這樣從存儲(chǔ)器中一次讀出1個(gè)數(shù)據(jù)相當(dāng)于一次讀出10個(gè)數(shù)據(jù),存儲(chǔ)器的訪存次數(shù)是沒有數(shù)據(jù)拼接情況訪存次數(shù)的1/10,矩陣R和矩陣A的數(shù)據(jù)拼接示意圖如圖3所示。

圖3 矩陣A和矩陣R數(shù)據(jù)的拼接方式

2.4 脈動(dòng)陣列數(shù)據(jù)存儲(chǔ)方式

基于10×10脈動(dòng)陣列對(duì)2個(gè)矩陣進(jìn)行乘法操作,但是脈動(dòng)陣列PE中計(jì)算值并不是同時(shí)計(jì)算出來的。每當(dāng)計(jì)算出1組10×10矩陣值時(shí),需要將這些PE值進(jìn)行存儲(chǔ)。其中一種方法是當(dāng)所有PE值計(jì)算完1組數(shù)據(jù)后將所有數(shù)據(jù)進(jìn)行存儲(chǔ);另一種方法是使用移位寄存器的形式,設(shè)立10組移位寄存器,根據(jù)脈動(dòng)陣列自身的規(guī)律,每當(dāng)PE計(jì)算出數(shù)值時(shí),將數(shù)據(jù)按順序移到相應(yīng)的寄存器中,脈動(dòng)陣列設(shè)計(jì)整體架構(gòu)如圖4所示。從圖4可以看出,左上角的第1個(gè)PE將會(huì)計(jì)算出第1個(gè)數(shù)值,數(shù)據(jù)按照斜對(duì)角的形式依次計(jì)算出來,數(shù)據(jù)存儲(chǔ)控制單元將按照脈動(dòng)陣列的規(guī)律，將PE計(jì)算單元計(jì)算出來的結(jié)果依次存儲(chǔ)到存儲(chǔ)器中。

脈動(dòng)陣列整體架構(gòu)包含了矩陣R數(shù)據(jù)存儲(chǔ)器和矩陣A數(shù)據(jù)存儲(chǔ)器,這2個(gè)存儲(chǔ)器用來存儲(chǔ)矩陣R和A中的數(shù)據(jù),另外還包括數(shù)據(jù)輸入端控制單元,數(shù)據(jù)復(fù)用單元,脈動(dòng)陣列PE計(jì)算單元,數(shù)據(jù)存儲(chǔ)控制單元。

圖4 脈動(dòng)陣列設(shè)計(jì)整體架構(gòu)

從圖4可以看出,從矩陣R數(shù)據(jù)存儲(chǔ)器中讀出的數(shù)據(jù)將流入到數(shù)據(jù)復(fù)用單元,此處介紹數(shù)據(jù)復(fù)用單元的作用。圖4中矩陣R數(shù)據(jù)存儲(chǔ)器中的數(shù)據(jù)已經(jīng)是拼接好后的數(shù)據(jù),每當(dāng)讀出R的一行數(shù)據(jù)和A的一列數(shù)據(jù)后,經(jīng)過脈動(dòng)陣列單元計(jì)算后得到1組10×10數(shù)據(jù)。在整個(gè)計(jì)算過程中矩陣R的每一行數(shù)據(jù)要分別與矩陣A的每一列數(shù)據(jù)作運(yùn)算,從而提出一種數(shù)據(jù)復(fù)用方法,即預(yù)先將矩陣R的每一行數(shù)值存儲(chǔ)到數(shù)據(jù)復(fù)用單元中,此時(shí)只需讀取A的每一列數(shù)據(jù),當(dāng)讀完A的所有列數(shù)據(jù)后,將數(shù)據(jù)復(fù)用單元清空,并預(yù)讀入R的下一行數(shù)據(jù),以此往復(fù),最終矩陣乘法運(yùn)算總共訪問的存儲(chǔ)器次數(shù)從原來的5 216 400次降低到2 900 520次,次數(shù)減少了44.39%。數(shù)據(jù)存儲(chǔ)控制單元的時(shí)序如圖5所示。從圖5可以看出,后面的寄存器相較于前面的寄存器延遲1個(gè)周期存入數(shù)據(jù)。

圖5 數(shù)據(jù)存儲(chǔ)單元時(shí)序圖

3 硬件整體實(shí)現(xiàn)與實(shí)驗(yàn)分析

同態(tài)加密的整體硬件架構(gòu)如圖6所示,同態(tài)加密整體架構(gòu)包括了主控制器、脈動(dòng)陣列矩陣乘法單元、明文u與單位陣IN乘法單元、位展開單元以及加法模塊,其中主控制器用狀態(tài)機(jī)來實(shí)現(xiàn),以協(xié)調(diào)整體硬件模塊的功能,位展開單元實(shí)際上是完成BitDecomp函數(shù),將輸入的每個(gè)數(shù)據(jù)按14 bit二進(jìn)制數(shù)進(jìn)行展開,經(jīng)位展開后的數(shù)據(jù)將與存儲(chǔ)器中的數(shù)值一起進(jìn)入到加法模塊中進(jìn)行相加操作,加法模塊求和得到的結(jié)果將是最終需要得到的密文矩陣。

同時(shí),將加密算法分別在CPU和FPGA軟硬件中實(shí)現(xiàn),其中處理器為Intel(R) Core(TM) i5-4570 CPU,而FPGA采用ZCU-102開發(fā)板,CPU與FPGA 2種平臺(tái)分別對(duì)不同大小的明文數(shù)據(jù)進(jìn)行加密所需時(shí)間對(duì)比，結(jié)果見表4所列。實(shí)驗(yàn)結(jié)果表明通過硬件加速后,可以大幅度縮短加密時(shí)間,相對(duì)于軟件平臺(tái),平均加密時(shí)間得到了大幅度地縮短。最終,GSW加密算法的FPGA的綜合結(jié)果見表5所列。從表5可以看出,LUT資源需要37.24 kiB,BRAM資源需要150 kiB,系統(tǒng)可達(dá)到的最高時(shí)鐘頻率為360.36 MHz。

圖6 同態(tài)加密整體硬件架構(gòu)

表4 CPU實(shí)現(xiàn)與FPGA加密時(shí)間對(duì)比 單位:ms

表5 GSW加密算法FPGA綜合結(jié)果

4 結(jié) 論

本文基于GSW加密算法提出高性能、低延遲的VLSI架構(gòu),基于改進(jìn)的脈動(dòng)陣列提出了一種數(shù)據(jù)拼接方法,同時(shí)設(shè)計(jì)了數(shù)據(jù)復(fù)用模塊,降低了訪問存儲(chǔ)器的次數(shù),從而降低了系統(tǒng)的動(dòng)態(tài)功耗,實(shí)驗(yàn)結(jié)果表明,加密算法通過FPGA硬件加速后,加密時(shí)間得到了大幅度降低。