一種基于CPU-GPU混合系統(tǒng)的并行同態(tài)加密算法?

鄭志蓉

（91977部隊 北京 100036）

1 引言

同態(tài)加密算法這一類具有特殊性質(zhì)加密算法的出現(xiàn)，真正從根本上解決了將用戶數(shù)據(jù)及其操作委托給第三方時的保密問題，滿足將計算托付給云服務(wù)提供商，并兼顧了數(shù)據(jù)的安全性。但是，同態(tài)加密具有不可忽視的計算復(fù)雜度，從而阻礙了同態(tài)加密算法的實(shí)際應(yīng)用。因而本文致力于構(gòu)建基于CPU-GPU混合系統(tǒng)搭建并行計算框架，實(shí)現(xiàn)基于整數(shù)同態(tài)加密算法的加速計算平臺。

1978年，Rivest等［1］首次提出了同態(tài)加密的概念，這是一種可以對密文直接進(jìn)行操作的加密算法。RSA就是一種可以實(shí)現(xiàn)單一乘法的同態(tài)算法。但在2009年之前都沒有獲得滿意結(jié)果。僅僅只獲得了一些半同態(tài)的或者僅能做有限步的全同態(tài)加密方案。2009年，Gentry［2］基于理想格困難問題構(gòu)造出了第一個全同態(tài)加密方案，也被稱為“隱私同態(tài)”或“全同態(tài)加密”，成為了信息安全領(lǐng)域的重要技術(shù)突破，使得加密信息，即刻意被打亂的數(shù)據(jù)仍能夠被深入和無限的分析，而不會影響其保密性。從此，學(xué)術(shù)界開始了對同態(tài)加密算法的廣泛關(guān)注和深入研究。

但是，全同態(tài)加密算法在實(shí)際應(yīng)用中，由于全同態(tài)加密算法的計算復(fù)雜度巨大，從而失去了實(shí)際的應(yīng)用價值。因此，在2010年，由Dijk，Gentry等［3］又提出了另外一種更加簡潔易懂的全同態(tài)加密方案，表示為DGHV，該算法僅使用整數(shù)上的加法、乘法和最基本的模運(yùn)算，舍棄掉了Gentry的基于多項式環(huán)的理想格。因此，DGHV方案的計算效率與理想格的全同態(tài)方案相比，計算復(fù)雜度相對降低了，執(zhí)行效率相對更高，也便于利用計算機(jī)實(shí)現(xiàn)。然而，DGHV算法實(shí)際運(yùn)算的復(fù)雜度還是很高的。例如：在一個簡單的明文檢索系統(tǒng)里應(yīng)用DGHV算法，其計算量將增加數(shù)萬億次。因此，本文是基于DGHV算法進(jìn)行的并行方案設(shè)計，以改善算法的實(shí)際應(yīng)用效果。

近年來，許多并行計算框架被提出并成功應(yīng)用到各個領(lǐng)域。因此，本文的核心思想是將同態(tài)加密算法與并行計算框架結(jié)合從而提高同態(tài)加密算法的執(zhí)行效率。文章基于CPU-GPU混合系統(tǒng)提出一種并行計算模式。并且，從運(yùn)行時間定量分析文章提出的并行同態(tài)加密算法的有效性。文章為了進(jìn)一步提高算法的并行度，設(shè)計了一種流水線處理模式，減少了系統(tǒng)內(nèi)各個單元等待的時間，從而進(jìn)一步提高算法的執(zhí)行效率。

2 相關(guān)工作

由于云計算平臺中，許多常用的加密算法不適用。因此，同態(tài)加密算法由于代數(shù)同態(tài)的特征而引起學(xué)者的注意。但同態(tài)算法的高計算復(fù)雜度阻礙了實(shí)際應(yīng)用。因此，近年來許多學(xué)者研究了如何提高同態(tài)加密算法的效率，從而在云計算環(huán)境中推廣同態(tài)加密算法的應(yīng)用。文獻(xiàn)［4］試圖提出一種有效的算法，結(jié)合了概率知識和同態(tài)加密技術(shù)的特征，以從同態(tài)算法本身的角度提高執(zhí)行效率。然而實(shí)驗(yàn)卻表明，時間的復(fù)雜性并沒有減少多少。因此，我們放棄了改進(jìn)的同態(tài)算法本身，以提高效率。

在并行計算模型方面，Sethi等［5］提出了一種基于MapReduce框架的并行同態(tài)加密的模型。類似的，文獻(xiàn)［6］利用16個核心和4個節(jié)點(diǎn)構(gòu)造基于MapReduce環(huán)境的并行同態(tài)加密方案。上述兩項研究的證據(jù)表明，一個好的并行方案可以提高同態(tài)加密的性能。這也是本文利用CPU-GPU混合系統(tǒng)構(gòu)造并行同態(tài)加密算法的動機(jī)。尤其在醫(yī)療和金融領(lǐng)域，保護(hù)敏感個人信息的隱私是一個重要的研究內(nèi)容。文獻(xiàn)［7］建議使用GPU加速同態(tài)加密算法，以進(jìn)行安全的醫(yī)療計算。文獻(xiàn)［8］設(shè)計了一個利用GPU輔助計算的同態(tài)加密算法，用于部分同態(tài)加密算法里的矩陣乘法運(yùn)算。因此，本文提出了一種基于CPU-GPU混合系統(tǒng)的大規(guī)模數(shù)據(jù)加密的并行處理方案，這與現(xiàn)有的研究方案有所不同。并且，流水線處理方式也沒有相關(guān)學(xué)者研究用于提高并行同態(tài)加密算法的并行度。

3 本文方案

近年來，許多并行方案采用GPU輔助加速計算。此外，隨著架構(gòu)的不斷改進(jìn)，GPU由于其強(qiáng)大的計算能力，已經(jīng)成功應(yīng)用于并行、多線程、多核處理器等系統(tǒng)中數(shù)據(jù)的并行處理。本文設(shè)計的并行方案利用GPU輔助加速數(shù)據(jù)加密的執(zhí)行，其他任務(wù)則是由CPU執(zhí)行。具體來講，本文采用CPU-GPU混合系統(tǒng)構(gòu)造同態(tài)加密算法的并行計算方案。并且，通過對比實(shí)驗(yàn)，定量地分析并行方案相比串行方案在系統(tǒng)性能和時間上的改進(jìn)。

圖1 基于CPU-GPU混合系統(tǒng)的并行同態(tài)加密方案

圖1 顯示了基于CPU-GPU混合系統(tǒng)中主機(jī)、系統(tǒng)總線和GPU的任務(wù)處理和執(zhí)行狀態(tài)。并且，為了盡可能地縮短等待時間，設(shè)計了流水線處理模式如圖2所示，目的是減少系統(tǒng)內(nèi)各個單元等待的時間，從而進(jìn)一步提高并行同態(tài)加密算法的執(zhí)行效率。

預(yù)處理：主要包括三個子任務(wù)，即初始化、數(shù)據(jù)劃分和任務(wù)分配。這三個步驟都是在CPU和主機(jī)內(nèi)存中處理的，組合在一起稱為預(yù)處理過程。首先，主機(jī)獲取輸入數(shù)據(jù)。下一步，數(shù)據(jù)劃分的任務(wù)主要是將數(shù)據(jù)塊分割成更小的數(shù)據(jù)單元，供GPU內(nèi)的多線程并行執(zhí)行加密運(yùn)算。

傳輸和加密：輸入的數(shù)據(jù)從主機(jī)傳輸給GPU，GPU執(zhí)行加密運(yùn)算。并且，當(dāng)GPU執(zhí)行加密運(yùn)算時，主機(jī)仍然可以執(zhí)行預(yù)處理等操作，從而讓CPU和GPU并行執(zhí)行各個子任務(wù)，這也是并行方案相比串行方案效率提高的根本原因。在整個過程中，GPU一直處于工作狀態(tài)。因此，GPU和系統(tǒng)總線都是CPU-GPU混合系統(tǒng)的關(guān)鍵執(zhí)行單元。

合并和輸出：主機(jī)需要把加密的數(shù)據(jù)合并，以構(gòu)成完整的密文信息。并且，CPU-GPU混合系統(tǒng)采用了流水線模式的管道體系結(jié)構(gòu)，如圖2所示。各個執(zhí)行單元如同流水線生產(chǎn)中的各個設(shè)備，不間斷的執(zhí)行各個子任務(wù)，極大程度的提高算法的并行度。

圖2 基于CPU-GPU系統(tǒng)的流水線處理流程

最后，主機(jī)把數(shù)據(jù)單元的密文合并成數(shù)據(jù)塊的密文并作為輸出。這些步驟將被視為合并和輸出的過程。基于上面的抽象，為CPU-GPU混合系統(tǒng)提供管道體系結(jié)構(gòu)的流水線處理模式如圖3所示。

圖3 同態(tài)加法的運(yùn)行時間對比

其中，預(yù)處理步驟主要由主機(jī)中的執(zhí)行單元CPU處理，表示為Host_Proc1，傳輸和加密步驟主要由系統(tǒng)總線和GPU執(zhí)行單元處理，表示為Host_Proc2_GPU，合并和輸出步驟主要由主機(jī)中的執(zhí)行單元CPU處理，表示為Host_Proc3。由于處理數(shù)據(jù)的粒度對執(zhí)行效率非常重要，因此，實(shí)驗(yàn)部分將分析不同粒度數(shù)據(jù)對系統(tǒng)吞吐量和響應(yīng)時間的影響。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)中采用了C++和CUDA的混合編程模式。具體而言，實(shí)驗(yàn)采用英特爾酷睿的型號為i5-5200u的CPU，包括2個2.20 GHz時鐘頻率的內(nèi)核，12G內(nèi)存以及Windows 10操作系統(tǒng)。GPU采用NVIDIA Tesla c2050，具有3 GB的內(nèi)存。編程環(huán)境采用C++和CUDA混合編程模式，這是一個NVIDIA GPU的SDK，它是一個針對C++和CUDA的集成包。

實(shí)驗(yàn)使用的是由一系列隨機(jī)整數(shù)構(gòu)成的大小為128MiB的數(shù)據(jù)集作為明文。其中，每一位整數(shù)由64個比特的二進(jìn)制數(shù)據(jù)表示，這也是系統(tǒng)處理的最小數(shù)據(jù)單元。實(shí)驗(yàn)中對數(shù)據(jù)集進(jìn)行了劃分，分別對大小從8MiB到64MiB的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，以評估并行同態(tài)加密算法的性能。

4.2 實(shí)驗(yàn)驗(yàn)證

圖4 同態(tài)乘法的運(yùn)行時間對比

為了驗(yàn)證本文提出的并行計算架構(gòu)的有效性，定量地對串行同態(tài)加密（SHE）與快速的并行同態(tài)加密（FPHE）關(guān)于執(zhí)行同態(tài)加法和同態(tài)乘法的運(yùn)行時間進(jìn)行對比，驗(yàn)證本文提出的基于CPU-GPU混合系統(tǒng)的并行性同態(tài)加密算法的有效性。圖3和圖4分別是在不同大小的數(shù)據(jù)塊上執(zhí)行同態(tài)加法和同態(tài)乘法時，SHE和FPHE的運(yùn)行時間對比。實(shí)驗(yàn)結(jié)果表明，F(xiàn)PHE相比SHE在執(zhí)行同態(tài)加法時，效率提高了90%；FPHE相比SHE在執(zhí)行同態(tài)乘法時，效率提高了71%。從實(shí)驗(yàn)結(jié)果得出結(jié)論，基于CPU-GPU混合系統(tǒng)的同態(tài)加密算法可以極大地提高執(zhí)行效率。

5 結(jié)語

本文研究基于CPU-GPU混合系統(tǒng)的并行同態(tài)加密方案，其中CPU負(fù)責(zé)管理、調(diào)度、輸入/輸出、合并等任務(wù)，GPU負(fù)責(zé)執(zhí)行加密運(yùn)算。實(shí)驗(yàn)結(jié)果表明GPU可以有效地輔助提高執(zhí)行效率。但是，為了進(jìn)一步改善本文提出的方法的有效性，未來仍有很多問題需要解決。例如研究基于CPU和多GPU的并行計算框架等。