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

鄭志蓉

（91977部隊 北京 100036）

1 引言

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

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

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

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

2 相關工作

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

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

3 本文方案

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

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

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

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

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

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

圖2 基于CPU-GPU系統的流水線處理流程

最后，主機把數據單元的密文合并成數據塊的密文并作為輸出。這些步驟將被視為合并和輸出的過程?；谏厦娴某橄螅瑸镃PU-GPU混合系統提供管道體系結構的流水線處理模式如圖3所示。

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

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

4 實驗分析

4.1 實驗環(huán)境

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

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

4.2 實驗驗證

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

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

5 結語

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