同态加密的硬件卸载及其在隐私保护计算中的应用

周慧凯，华 蓓

(中国科学技术大学 计算机科学与技术学院，合肥 230027)

1 引 言

随着云计算的广泛应用，越来越多的用户选择将数据存储在云端，有些甚至将计算也外包给云端.然而，用户对数据安全和隐私泄露的担心阻碍了云计算的进一步推广使用.尽管常规加密技术可以保证数据在存储和传输过程中的机密性，但是当计算外包给云服务商或第3方时，由于需要先解密数据才能计算，数据机密性仍然得不到保证.随着大数据时代的到来，数据已成为一种重要的财富和资源，利用数据发现问题和解决问题已成为大数据和人工智能时代的主要特征.然而人们对数据机密和隐私泄露的担心同样限制了数据的流通和共享使用，导致各行各业的数据形成“数据孤岛”，不能产生应有的价值.

计算外包和数据共享的共同点是数据拥有方和数据计算方分离，数据拥有方希望数据计算方在计算的过程中不接触原始明文数据，并且也不能推断出原始明文数据.目前解决这个问题的方法大致分为基于密码学的方法和基于扰动变换的方法，基于密码学的方法支持在密文上进行计算，而基于扰动变换的方法通过向原始数据添加足够的噪声来保证数据隐私.基于密码学的方法安全性高，但计算开销巨大.

同态加密是具有特殊自然属性的一类加密方法，利用同态加密技术在多个密文上进行计算的结果，与在明文上先计算再对计算结果进行加密是等价的，从而可解决第3方计算的数据安全问题，在隐私保护的信息检索、多方安全计算、密文数据库等方面有着重要的应用.根据对同态特性支持的完整性，同态加密分为全同态加密、类同态加密、半同态加密3类.全同态加密支持在密文上的任意多次加、乘同态运算；类同态加密同时支持加、乘同态运算，但运算次数有限；而半同态加密仅能支持加同态或乘同态运算.许多研究工作致力于提高同态加密的计算效率，包括改进加密算法和利用GPU/FPGA/ASIC硬件加速器等.文献[1]利用GPU加速全同态算法ATV[2]，对32KB数据进行AES-128运算需要4.15小时，完全无法实用.基于大数模幂运算的半同态加密是目前最接近实用的同态加密方案，其中，加同态加密算法Paillier[3]已被应用到电子投票[4]、电子拍卖[5]等小型应用中，但由于计算开销大仍然无法应用到大规模计算中.近几年已有一些针对Paillier加密算法的硬件卸载工作，San等人[6]在FPGA上实现了Paillier加密算法，完成一次Paillier-1024加密运算耗时11.29ms；Cai等人[7]设计了Paillier算法的专用ASIC芯片，将一次Paillier-1024加密时间缩短到5.9ms.尽管这两个利用FPGA和ASIC的卸载方案在功耗上有一定优势，但是它们的加密性能还不及一些高端CPU(见5.2节表1).

Intel QAT(Intel QuickAssist Technology)[8]是一款卸载加解密操作和压缩解压缩操作的硬件板卡，性能高、功耗低和开发环境友好是其优势.QAT卡封装了AES、RSA、ECC等常规加密算法以及Deflate压缩算法，并为调用这些算法提供了方便易用的高层接口.QAT卡已在一些需要大量进行加解密和压缩解压缩操作的系统中得到应用，如加速OpenSSL、Hadoop[8]等.但是QAT卡并未提供同态加密功能，只有一个未经封装的大数模幂运算的低层调用接口.大数模幂运算是多种半同态加密算法(如Paillier、ElGamal[9]等)的基本运算，也是这些加密算法的计算瓶颈所在.本文从硬件卸载的角度研究同态加密的高性能计算问题，提出一个基于QAT加速器的半同态加密卸载框架QHCS(QAT-based Homomorphic Encryption Scheme)，着重实现Paillier算法的异步卸载，并将其应用到一个隐私保护的线性回归应用中，希望推动同态加密在数据安全计算领域的实际应用.

2 相关知识

2.1 Paillier算法和Libhcs库

c=E(m)=gm·rnmodn2

(1)

对任意明文m1，m2有：

=gm1+m2(r1r2)n=E(m1+m2)

(2)

也即对密文进行乘运算等效于对明文先进行加运算，然后进行加密的结果，满足加法同态.该特性可推广到对任意明文m1,m2,…，mn有：

E(m1)·E(m2)·…·E(mn)=E(m1+m2+…+mn)

(3)

即Paillier算法满足任意次的加法同态运算.

Libhcs[10]是一个用C语言实现的开源同态加密库，实现了Paillier、ElGamal等半同态加密算法，尤其对Paillier算法进行了完善的实现，提供了方便的API接口供应用层调用.

2.2 QAT架构及基于QAT的TLS异步卸载框架

每一块QAT卡包含多个计算引擎，每个计算引擎可以独立执行加解密或压缩解压缩操作.应用程序通过使用QAT卡分配的实例(instance)和调用相关的QAT APIs，将工作负载下发到某个计算引擎上完成，计算结果通过同步或异步模式返回.

QAT与CPU之间通过位于内存中的一系列硬件辅助的环形数据结构进行通信，如图1所示.环成对存在，每一对环由一个请求环和一个响应环组成，CPU将计算任务提交给请求环，QAT将计算结果放入响应环.QAT在通信环和计算引擎之间进行负载均衡，将CPU提交的计算任务高效均匀地分配到多个计算引擎上.QAT驱动提供同步和异步两种卸载模式：在同步模式中，CPU通过QAT API提交任务后，CPU被阻塞直到QAT完成运算；在异步模式中，CPU通过QAT API提交任务后，不必等待QAT运算结束即可执行其它任务.同步调用是最直接最简单的卸载方法，几乎不需要修改上层应用，但会导致CPU和QAT串行执行，QAT利用率低.虽然采用多线程同步调用可以提高QAT的利用率，但大量线程产生的线程切换开销会限制系统的性能.

图1 Intel QAT架构图Fig.1 Architecture of Intel QAT

QTLS[11]是一个基于QAT的TLS(Transport Layer Security)异步卸载框架，它将OpenSSL中的常规加解密算法卸载到QAT中，并实现了高效的异步调用.QTLS重新设计了TLS的软件栈，以使每一层都支持异步操作.QTLS软件栈从上到下分为事件驱动的应用(如Nginx)、TLS 库(即OpenSSL)和QAT引擎3个层次.在应用层，通过增加一个异步状态“TLS ASYNC”并结合TLS状态机，实现Nginx对加密卸载的异步支持.由于OpenSSL本身不支持异步卸载，QTLS通过在OpenSSL中增加协程(fibre)支持来实现异步调用.协程是用户态线程，以协作方式进行调度，并且调度也在用户态完成，避免了切换内核的开销.协程可以在任意位置中断，让出CPU，并可以在任意时刻重入协程，从上次退出的执行点继续向下执行，该特性使得协程提供了一种自然的异步调用方式.QAT引擎向下与QAT驱动交互，向上对OpenSSL实现接口适配和数据类型转换.为兼顾吞吐量与延迟两方面的性能要求，QTLS实现了一种启发式轮询机制，通过自动调节轮询周期来高效地获取加密结果.

2.3 隐私保护的线性回归应用

文献[12]面向众包场景提出了一种隐私保护的岭回归计算模型，用于在加密后的众包数据上进行线性回归计算.该模型包括数据提供者、评估者和加密服务提供者3方，如图2所示.每个数据提供者提供一条数据(xi，yi)，该数据生成的矩阵(Ai；bi)用Paillier算法加密后(得到矩阵ci)发送给评估者，评估者将所有加密矩阵ci相加(同态加)得到聚合后的矩阵C，然后与加密服务提供者进行协同，通过构造乱码电路[13]来求解C.该工作巧妙地设计了同态加密与乱码电路相结合的方案，整个过程中评估者和加密服务提供者都没有接触到明文数据.

图2 文献[12]中的隐私保护岭回归计算模型Fig.2 Privacy-preserving ridge regression in [12]

3 QHCS的设计与实现

3.1 QHCS的架构设计与异步卸载实现

QAT提供了一个大数模幂运算的低层接口，可用于卸载半同态加密算法中的模幂运算操作.本文旨在将Libhcs中的Paillier加密算法卸载到QAT中，并为上层提供方便易用的调用接口.该方法同样可用于实现乘同态加密算法ElGamal的QAT卸载.

利用QAT卸载Paillier算法的最直接方法是将Paillier实现中对模幂运算函数的调用替换成对QAT模幂运算接口的同步调用，然而由于上层应用及Libhcs都是采用同步设计，在调用返回之前应用与Libhcs都不能进行后续操作，导致QAT的利用率非常低.为此，需要重新设计软件栈来实现高效的异步卸载，以充分利用QAT的计算能力.

受QTLS框架的启发，本文同样采用3层结构来设计半同态加密异步卸载框架，从上往下依次为应用层、同态加密库(Libhcs)层、QAT访问层，如图3所示.应用层根据应用逻辑对加密任务进行封装和调度.考虑到同态加密应用大多采用同步加密模式，不像Nginx那样涉及事件驱动，Libhcs也不存在像TLS状态机这样的机制，我们对同态加密库层和应用层统一采用协程来实现异步功能.在具体实现时，可通过调用OpenSSL的Async_job族函数来实现协程的异步功能.QAT访问层向下与QAT驱动交互，向上对Libhcs实现接口适配和数据类型转换.

图3 QHCS的整体架构Fig.3 Architecture of QHCS

整个异步卸载过程包括任务封装与提交、轮询与异步协程重入、后处理3个阶段.

a)任务封装与提交.每一次独立的Paillier加密调用封装为一个加密任务，包括获取数据、加密数据、写密文数据等一系列步骤，该封装由应用层实现.之后加密任务作为一个协程被调用，协程首先根据参数获取待加密的数据，然后调用同态加密库，同态加密库调用QAT访问层，QAT访问层通过异步API提交加密请求，之后马上通过相关调用暂停该协程执行，控制权返回给应用层.应用层调度下一个加密任务.

b)轮询与异步协程重入.为了确定加密请求是否完成，应用层主动对QAT实例进行轮询.轮询到新的响应之后，QAT用户态驱动调用预设的回调函数.回调函数根据与加密结果相关联的协程句柄，直接重入到该协程，继续进行后续处理.

c)后处理.重入被暂停的协程时，该协程仍停留在QAT访问层任务提交结束的状态，由此开始逐层向上进行后处理过程.后处理包括软件栈中每一层相关的后续处理，对于QAT访问层来说是加密数据类型的转换和数据包装，对于同态加密库来说是进一步的加密过程处理，对于应用层来说是写加密数据等后续处理.重入协程完成全部的后处理之后，该加密任务也就完成了，协程被终止.

3.2 单次Paillier加密过程的双协程实现

根据公式(1)，Paillier加密一个数据需要进行两次模幂运算，即需要执行两次QAT卸载.3.1采用了一种简单的实现方法，将两次模幂运算集成在一个协程中，先提交第1次模幂运算请求，第1次回调重入该协程后提交第2个模幂运算请求，第2次回调重入该协程后完成后处理，这样两次任务卸载完全串行执行.

考虑到Paillier加密的两次模幂运算是没有关联的，它们可以并行执行，从而减少单次加密的延时.经了解QAT默认开启了保序功能，即QAT会将计算结果按照任务的提交顺序依次放入响应环中，为此我们的第2种实现方法是将两次模幂运算解耦，用两个协程来实现.第1个协程提交第1个模幂运算，第2个协程提交第2个模幂运算并进行后续处理，两个协程按顺序调度，确保在第2个协程进入后处理阶段时两个模幂运算的结果都已返回.为实现双协程并发提交计算任务，需要对OpenSSL的Async_job族函数进行一些改造，使得其支持在协程中调度新协程的特性.

4 基于QHCS实现隐私保护的线性回归

本文基于QHCS实现了一个面向数据交易的隐私保护线性回归应用.在该设想的场景中，数据卖家提供加密的数据集，数据交易平台根据数据买家的请求在数据集上完成线性回归计算，将最终的计算结果交付给数据买家.整个计算过程中交易平台和数据买家均不接触明文数据，从而实现隐私保护的数据交易.

本文对文献[12]的隐私保护岭回归计算模型稍加修改，将其应用于数据交易场景中，如图4所示.在这里，数据提供者是拥有某个数据集的实体，评估者为数据交易平台，加密服务提供者用一个CA(Certificate Authority)实现，提供密钥管理与乱码电路构建服务.数据提供者对每一条数据生成矩阵(Ai；bi)，采用Paillier算法加密后(得到ci矩阵)发送给交易平台，交易平台对ci矩阵进行聚合，然后与加密服务提供者协同完成乱码电路的构建和求解，得到回归模型.3方之间采用文献[12]中的第2种协议进行交互.

图4 面向数据交易的隐私保护岭回归计算模型Fig.4 Privacy-preserving ridge regression model for data trading

应用的计算开销包括对矩阵(Ai；bi)进行同态加密、对加密矩阵ci进行聚合、以及针对聚合矩阵C构造乱码电路并求解.其中，主要的计算开销是同态加密和矩阵聚合，它们均与数据集规模成正比；而矩阵C的规模仅与数据维度有关，与数据集的规模无关，因此乱码电路构建与求解的计算量是固定的.应用的主要通信开销是ci矩阵的传输.为提高整个应用系统的性能，我们采用了如下优化措施.

1)利用QHCS卸载Paillier加密过程.为提高矩阵(Ai；bi)的加密速度，数据提供者利用QHCS将加密过程卸载到QAT上.考虑到实际应用中明文数据大多较短，QHCS采用了文献[12]中提到的batch优化技术，即将多个较短的明文数据用若干个零隔开后打包成一个较长的明文数据，再进行Paillier加密.该技术可将多次加密过程转化为一次加密过程，极大地提高加密速度.

2)利用GPU实现加密矩阵的聚合.所有ci矩阵通过同态加来生成聚合的C矩阵.同态加是一个简单的模乘运算，虽然单次模乘运算的计算量不大，但是大量的模乘运算仍会产生较大的计算开销.由于QAT没有开放模乘运算接口，无法利用QAT来加速模乘运算.考虑到矩阵的模乘运算实际上是一个向量运算，本文采用GPU来加速这个过程.

在模乘运算中模运算是一个性能瓶颈，考虑到在本文场景下每一个输入只进行一次模乘运算，且模运算中的模数唯一，我们选择用Barrett reduction[14]算法来加速模运算.在利用GPU进行并行计算时，我们通过设计高效的GPU归约算法对批量数据执行Reduce操作，加快聚合速度.

3)在数据提供者网络中完成加密矩阵聚合.每一条源数据经过向量乘及Paillier加密后生成ci矩阵，这个过程会产生极大的数据膨胀.以每条数据20个字段、密钥长度1024比特为例，采用batch技术后，100百万条源数据生成的加密矩阵的数据量约为2GB.如果将这些加密矩阵都传输到交易平台进行计算，将产生巨大的通信开销.为此，我们将矩阵聚合的功能移到数据提供者一侧完成，在数据提供者的局域网中设置一个聚合代理，代表交易平台完成对加密矩阵的聚合，仅将聚合矩阵C发送到交易平台进行求解，避免了大批量数据的远程传输.在数据提供者网络中进行加密矩阵聚合还能够进一步减轻数据提供者对数据泄露的担心，因为只有聚合矩阵才会离开本地网络.

5 实验评估

5.1 实验设置

本文使用2台服务器来模拟图4的计算环境.第1台服务器配置Intel D-1541/2.1GHz处理器和一块QAT DH8970加速卡，第2台服务器配置Intel E5-2689/2.6GHz处理器和一块Nvidia K80 GPU，均运行CentOS 7操作系统，关闭超线程.两台服务器通过10Gbps网络连接.

第1台服务器运行数据提供者的功能，对数据集中的每一条源数据生成ci矩阵，第2台服务器运行交易平台和加密服务提供者(CA)的功能.由于CA的计算量和通信量都很小，对系统性能影响不大，因此实验时将CA和交易平台运行在同一台服务器上.另外，由于乱码电路的求解与矩阵聚合在执行时间上不重叠，实验时将聚合代理也运行在第2台服务器上，注意到这样做并不会对系统性能的测量结果产生影响.聚合代理、乱码电路求解和CA分别用一个进程实现，3者之间的通信开销忽略不计.

本文设计两组实验，第1组实验评估不同的Paillier加密实现方案的性能，第2组实验评估基于QHCS的隐私保护线性回归应用的性能.由于Paillier最常使用的密钥长度为1024比特，本文所有实验均采用1024比特密钥长度.

5.2 不同Paillier加密实现方案的性能评估

本组实验测试3类共5种Paillier加密实现方案的吞吐量(OPS)和平均加密延时(ms)，分别是软件方案(SW，由Libhcs实现)、QAT同步卸载方案(分为单线程同步方案QAT+S1与多线程同步方案QAT+S2)、QAT异步卸载方案(分为单协程异步方案QHCS1与双协程异步方案QHCS2)，并对比了FPGA和ASIC方案的论文数据.所有实验方案中产生的CPU线程皆绑定到一个固定的CPU物理核上，以此来比较CPU端资源一定(只用单核)时不同方案的性能.每次实验加密30000个随机数，计算吞吐量和平均加密延时.每个实验运行3次，取3次结果的平均值，实验结果见表1.

表1 不同Paillier实现方案的性能Table 1 Performance of different Paillier implementations

对于软件方案SW和单线程同步方案QAT+S1，直接测量3万次加密所用的时间，然后计算出吞吐量和平均每次加密延时.

多线程同步方案QAT+S2的加密性能与线程数量有关：若线程数过少，则QAT负载不足；若线程数过多，大量的线程切换开销也会影响性能.为获得QAT+S2的最佳性能，实验时改变线程数量，测量不同线程数下的加密性能.实验发现，当线程数为1000时吞吐量最高，表1中QAT+S2报告的即为该设置下的吞吐量和平均加密延时.为获得平均加密延时，实验时统计每个线程的运行时间及加密次数，计算出该线程的平均加密延时，然后对所有线程的平均加密延时求平均值.

对于QAT异步卸载方案(QHCS1和QHCS2)，吞吐量的测量方法与其它3个方案相同，平均加密延时则是通过测量 每一次完整加密过程的延时并计算平均值得到.

由表1可以看到，单线程同步方案(QAT+S1)的性能只比软件方案(SW)略好.这是因为在同步模式下QAT和CPU串行执行，且QAT每次只执行一个模幂运算，负载严重不足，导致性能提升十分有限.

多线程同步方案(QAT+S2)的吞吐量是单线程同步方案(QAT+S1)的46倍，这是因为多线程方案有效增大了QAT的负载，使得QAT的计算能力得到很大的释放.注意到在该吞吐量下，多线程方案的平均加密延时增大至单线程方案的21倍，这是因为大量的任务请求在request ring中排队，产生了较大的排队延迟.

单协程异步方案(QHCS1)的吞吐量是多线程同步方案(QAT+S2)的1.76倍，这是因为协程具有比线程小得多的切换和调度开销，从而CPU可以调度更多的计算任务到QAT上，令QAT的计算能力得到更加充分的利用.注意到单协程异步方案的平均加密延时比多线程同步方案降低了33%，这里有两个方面的原因.首先，采用异步方式提交任务使得CPU和QAT上的处理过程能够重叠执行，减少了加密延时；其次，由于协程的调度和切换延时远小于线程的调度和切换延时，这也使得协程方案的加密延时较小.

双协程异步方案(QHCS2)的吞吐量比单协程异步方案(QHCS1)略低，这是因为双协程方案使用了较多的协程，增加了CPU端的处理开销.值得注意的是，双协程方案的加密延时只有单协程方案的一半，这是因为单协程方案的第2次计算任务须在第1次任务的结果返回后才提交，而双协程方案的第2次计算任务可以紧接在第1次任务后提交，两个计算结果通过一次轮询即可获得，从而降低了加密延时.

从这组实验可以看到，QAT异步卸载方案的吞吐量明显高于同步卸载方案，并远远超过当前的软件实现方案，是软件方案的110倍.追求高吞吐的应用可以采用单协程卸载方案，关注延时的应用可以采用双协程卸载方案.

最后与文献中报告的FPGA方案[6]和ASIC方案[7]进行一个比较.表1中这两个方案的性能数据均来自相关文献.为便于描述，这里将CPU物理核、QAT计算引擎、FPGA和ASIC的加密运算单元统称为计算实例.在SW、FPGA、ASIC和QAT+S1这4种方案中都只有一个计算实例参与计算，适合一起比较.可以看到，ASIC方案的吞吐量与延时均优于FPGA方案，但都不如SW和QAT+S1.这说明FPGA及ASIC方案的性能还不如软件方案(CPU实现)，也不如QAT.

在QAT+S2、QHCS1和QHCS2这3种方案中，QAT有多个计算实例参与计算，单次加密运算的耗时均大于FPGA和ASIC方案，这是由批量处理带来的影响.在吞吐量方面，按照FPGA中每个计算实例占用的硬件资源和FPGA设备总的硬件资源数量来计算，一块FPGA设备最多可以同时运行13个计算实例，在完全发挥FPGA设备算力的情况下吞吐量也只有1151(OPS)，仅为QHCS1的4.2%，若要达到QHCS1(单QAT设备)的吞吐量需要24块FPGA板.ASIC方案若需要达到QHCS1(单QAT设备)的吞吐量需要160个计算实例(计算核心).可见，相比于已有的FPGA方案或ASIC方案，QHCS在性能方面具有显著的优势.

5.3 隐私保护的线性回归应用的性能评估

本组实验测量隐私保护的线性回归应用的性能，包括同态加密、矩阵聚合、乱码电路求解3个部分的运行耗时.实验所需的数据集采用文献[12]中的算法生成，见算法1.

算法1.数据集生成算法

输入：数据条数n，数据维度d

输出：X∈n×d,y∈n

3. 计算y=Xβ+e，其中e～N(0,1)

首先利用以上算法生成n=1，000，000条高维源数据，每条数据包含d=20个维度.对每条源数据(xi；yi)生成待加密的(Ai；bi)矩阵，每个矩阵包含420个元素.这一百万个矩阵(共包含4.2亿个数据)即为数据提供者要加密的数据.数据提供者对每个(Ai；bi)矩阵进行Paillier加密，输出加密矩阵ci.

对于同态加密部分，分别测量两种异步卸载方案的加密耗时.为优化性能，采用了batch技术，将每个矩阵中的数据打包成17个长度为1024比特的数，即需要进行17次Paillier加密.表2给出了两种方案的加密时间，其中单协程方案QHCS1耗时10.6分钟，双协程方案QHCS2耗时10.7分钟.这个实验再次表明，两个方案的吞吐量很接近，相比而言单协程方案的吞吐量略高一些.

表2 隐私保护的线性回归应用的性能分解Table 2 Performance breakdown of privacy-preserving ridge regression

矩阵聚合部分测量GPU对矩阵ci执行同态加所用的时间.为最大化GPU的计算效率，我们通过实验的方法确定GPU kernel的最佳运行参数.实验发现，GPU每批次处理25，000个加密矩阵(即ci)时性能最好，在此设置下得到100万个矩阵同态加的耗时为116秒，见表2.

乱码电路部分测量构造和求解乱码电路的时间.ABY[15]是一个完善而高效的安全计算框架，本文使用ABY框架来实现乱码电路部分内容.乱码电路的复杂度和计算开销仅与矩阵C有关，而与源数据的条数n无关，实验中测得这部分的运行时间为20秒，见表2.

数据提供者和聚合代理之间需要传输一百万个加密矩阵，这部分的数据量约为2GB.采用10Gbps链路进行传输，传输时间只需数秒.

综合以上实验数据可以看到，对大规模加密数据进行线性回归计算的最主要瓶颈是同态加密，利用QAT卸载同态加密可以极大地缩短计算时间，使得在实际生产中应用同态加密技术成为可能.需要说明的是，本实验只使用了一块QAT加速卡，如果使用多块QAT卡，则加密时间将成比例地下降.

6 总 结

计算外包、数据共享等正成为大数据时代的迫切需要.虽然同态加密是实现安全数据计算的重要技术，但是极高的计算开销阻碍了同态加密的实际应用.本文基于Intel QAT加速卡和开源同态加密库Libhcs实现了针对Paillier半同态加密算法的硬件卸载框架QHCS，通过重构同态加密应用的软件栈，并采用协程、异步调用等方式实现了加密性能的最大化.本文进一步将QHCS应用于一个面向数据交易场景的隐私保护线性回归应用中.实验表明，QHCS的加密吞吐量是目前软件实现的110倍，在百万量级的高维数据上执行隐私保护的线性回归计算仅需十几分钟，可以较好地满足实际应用的需要.未来打算将基于模幂运算的其它半同态加密算法集成到QHCS中，并将QHCS应用于更多类型的隐私保护数据计算中，如隐私保护的机器学习和数据挖掘等.