一种基于CPU-GPU混合系统的并行同态加密算法∗

郑志蓉

（91977部队 北京 100036）

1 引言

同态加密算法这一类具有特殊性质加密算法的出现，真正从根本上解决了将用户数据及其操作委托给第三方时的保密问题，满足将计算托付给云服务提供商，并兼顾了数据的安全性。但是，同态加密具有不可忽视的计算复杂度，从而阻碍了同态加密算法的实际应用。因而本文致力于构建基于CPU-GPU混合系统搭建并行计算框架，实现基于整数同态加密算法的加速计算平台。

1978年，Rivest等［1］首次提出了同态加密的概念，这是一种可以对密文直接进行操作的加密算法。RSA就是一种可以实现单一乘法的同态算法。但在2009年之前都没有获得满意结果。仅仅只获得了一些半同态的或者仅能做有限步的全同态加密方案。2009年，Gentry［2］基于理想格困难问题构造出了第一个全同态加密方案，也被称为“隐私同态”或“全同态加密”，成为了信息安全领域的重要技术突破，使得加密信息，即刻意被打乱的数据仍能够被深入和无限的分析，而不会影响其保密性。从此，学术界开始了对同态加密算法的广泛关注和深入研究。

但是，全同态加密算法在实际应用中，由于全同态加密算法的计算复杂度巨大，从而失去了实际的应用价值。因此，在2010年，由Dijk，Gentry等［3］又提出了另外一种更加简洁易懂的全同态加密方案，表示为DGHV，该算法仅使用整数上的加法、乘法和最基本的模运算，舍弃掉了Gentry的基于多项式环的理想格。因此，DGHV方案的计算效率与理想格的全同态方案相比，计算复杂度相对降低了，执行效率相对更高，也便于利用计算机实现。然而，DGHV算法实际运算的复杂度还是很高的。例如：在一个简单的明文检索系统里应用DGHV算法，其计算量将增加数万亿次。因此，本文是基于DGHV算法进行的并行方案设计，以改善算法的实际应用效果。

近年来，许多并行计算框架被提出并成功应用到各个领域。因此，本文的核心思想是将同态加密算法与并行计算框架结合从而提高同态加密算法的执行效率。文章基于CPU-GPU混合系统提出一种并行计算模式。并且，从运行时间定量分析文章提出的并行同态加密算法的有效性。文章为了进一步提高算法的并行度，设计了一种流水线处理模式，减少了系统内各个单元等待的时间，从而进一步提高算法的执行效率。

2 相关工作

由于云计算平台中，许多常用的加密算法不适用。因此，同态加密算法由于代数同态的特征而引起学者的注意。但同态算法的高计算复杂度阻碍了实际应用。因此，近年来许多学者研究了如何提高同态加密算法的效率，从而在云计算环境中推广同态加密算法的应用。文献［4］试图提出一种有效的算法，结合了概率知识和同态加密技术的特征，以从同态算法本身的角度提高执行效率。然而实验却表明，时间的复杂性并没有减少多少。因此，我们放弃了改进的同态算法本身，以提高效率。

在并行计算模型方面，Sethi等［5］提出了一种基于MapReduce框架的并行同态加密的模型。类似的，文献［6］利用16个核心和4个节点构造基于MapReduce环境的并行同态加密方案。上述两项研究的证据表明，一个好的并行方案可以提高同态加密的性能。这也是本文利用CPU-GPU混合系统构造并行同态加密算法的动机。尤其在医疗和金融领域，保护敏感个人信息的隐私是一个重要的研究内容。文献［7］建议使用GPU加速同态加密算法，以进行安全的医疗计算。文献［8］设计了一个利用GPU辅助计算的同态加密算法，用于部分同态加密算法里的矩阵乘法运算。因此，本文提出了一种基于CPU-GPU混合系统的大规模数据加密的并行处理方案，这与现有的研究方案有所不同。并且，流水线处理方式也没有相关学者研究用于提高并行同态加密算法的并行度。

3 本文方案

近年来，许多并行方案采用GPU辅助加速计算。此外，随着架构的不断改进，GPU由于其强大的计算能力，已经成功应用于并行、多线程、多核处理器等系统中数据的并行处理。本文设计的并行方案利用GPU辅助加速数据加密的执行，其他任务则是由CPU执行。具体来讲，本文采用CPU-GPU混合系统构造同态加密算法的并行计算方案。并且，通过对比实验，定量地分析并行方案相比串行方案在系统性能和时间上的改进。

图1 基于CPU-GPU混合系统的并行同态加密方案

图1 显示了基于CPU-GPU混合系统中主机、系统总线和GPU的任务处理和执行状态。并且，为了尽可能地缩短等待时间，设计了流水线处理模式如图2所示，目的是减少系统内各个单元等待的时间，从而进一步提高并行同态加密算法的执行效率。

预处理：主要包括三个子任务，即初始化、数据划分和任务分配。这三个步骤都是在CPU和主机内存中处理的，组合在一起称为预处理过程。首先，主机获取输入数据。下一步，数据划分的任务主要是将数据块分割成更小的数据单元，供GPU内的多线程并行执行加密运算。

传输和加密：输入的数据从主机传输给GPU，GPU执行加密运算。并且，当GPU执行加密运算时，主机仍然可以执行预处理等操作，从而让CPU和GPU并行执行各个子任务，这也是并行方案相比串行方案效率提高的根本原因。在整个过程中，GPU一直处于工作状态。因此，GPU和系统总线都是CPU-GPU混合系统的关键执行单元。

合并和输出：主机需要把加密的数据合并，以构成完整的密文信息。并且，CPU-GPU混合系统采用了流水线模式的管道体系结构，如图2所示。各个执行单元如同流水线生产中的各个设备，不间断的执行各个子任务，极大程度的提高算法的并行度。

图2 基于CPU-GPU系统的流水线处理流程

最后，主机把数据单元的密文合并成数据块的密文并作为输出。这些步骤将被视为合并和输出的过程。基于上面的抽象，为CPU-GPU混合系统提供管道体系结构的流水线处理模式如图3所示。

图3 同态加法的运行时间对比

其中，预处理步骤主要由主机中的执行单元CPU处理，表示为Host_Proc1，传输和加密步骤主要由系统总线和GPU执行单元处理，表示为Host_Proc2_GPU，合并和输出步骤主要由主机中的执行单元CPU处理，表示为Host_Proc3。由于处理数据的粒度对执行效率非常重要，因此，实验部分将分析不同粒度数据对系统吞吐量和响应时间的影响。

4 实验分析

4.1 实验环境

本文的实验中采用了C++和CUDA的混合编程模式。具体而言，实验采用英特尔酷睿的型号为i5-5200u的CPU，包括2个2.20 GHz时钟频率的内核，12G内存以及Windows 10操作系统。GPU采用NVIDIA Tesla c2050，具有3 GB的内存。编程环境采用C++和CUDA混合编程模式，这是一个NVIDIA GPU的SDK，它是一个针对C++和CUDA的集成包。

实验使用的是由一系列随机整数构成的大小为128MiB的数据集作为明文。其中，每一位整数由64个比特的二进制数据表示，这也是系统处理的最小数据单元。实验中对数据集进行了划分，分别对大小从8MiB到64MiB的数据集进行实验分析，以评估并行同态加密算法的性能。

4.2 实验验证

图4 同态乘法的运行时间对比

为了验证本文提出的并行计算架构的有效性，定量地对串行同态加密（SHE）与快速的并行同态加密（FPHE）关于执行同态加法和同态乘法的运行时间进行对比，验证本文提出的基于CPU-GPU混合系统的并行性同态加密算法的有效性。图3和图4分别是在不同大小的数据块上执行同态加法和同态乘法时，SHE和FPHE的运行时间对比。实验结果表明，FPHE相比SHE在执行同态加法时，效率提高了90%；FPHE相比SHE在执行同态乘法时，效率提高了71%。从实验结果得出结论，基于CPU-GPU混合系统的同态加密算法可以极大地提高执行效率。

5 结语

本文研究基于CPU-GPU混合系统的并行同态加密方案，其中CPU负责管理、调度、输入/输出、合并等任务，GPU负责执行加密运算。实验结果表明GPU可以有效地辅助提高执行效率。但是，为了进一步改善本文提出的方法的有效性，未来仍有很多问题需要解决。例如研究基于CPU和多GPU的并行计算框架等。