隐私计算关键技术与创新*

符芳诚 侯忱 程勇 陶阳宇

(1.北京大学信息科学技术学院高可信软件技术重点实验室，北京 100871；2.腾讯数据平台部数据中心，北京 100083)

0 引言

随着数字经济的深入发展，大数据已经成为一种新的生产要素和战略资源。大数据产业的发展和应用普及能够显著提高生产效率和社会智能化程度。基于大数据的人工智能(Artificial Intelligence，AI)技术已经开始规模商用，逐渐进入生产、生活的方方面面，如人脸识别、语音识别、文本翻译、商品推荐等。一方面，各行各业都受益于大数据和AI产业带来的便捷和智能化；另一方面，潜在的数据滥用和用户隐私泄露风险也是不可忽视的问题。在实际应用中，由于隐私保护、数据安全、商业竞争等原因，不同机构拥有的数据很难整合到一起，导致在不同机构之间形成数据孤岛，阻碍大数据和AI的应用发展。协同多个机构的数据进行联合计算、建模与分析，在保护每个机构用户隐私与数据安全的同时，增强机器学习模型表达能力、释放更多的数据协同价值，成为学术界与产业界广泛研究的课题。为解决跨机构数据协同应用与隐私保护矛盾，隐私计算(Privacy Preserving Computing)应运而生[1-4]，受到业界广泛关注。

隐私计算是一种由两个或多个参与方进行联合计算的技术和系统，在不泄露各自数据的前提下，参与方通过协作对他们的数据进行联合机器学习或联合分析。在隐私计算框架下，参与方的数据明文不出本地，在保护数据安全的同时实现多方数据协同应用和联合计算，可以破解数据融合应用与隐私保护难题。近年来，在数据协同和隐私保护的双重驱动下，隐私计算受到广泛关注，成为当前政府、产业、学术研究等各界关注的热点。伴随着应用密码学、硬件技术的发展以及加速商业化，隐私计算技术的路径也处于高速的演进和产品化过程中，其中联邦学习、多方安全计算和可信计算是当前的主流技术路径，也是当下产品化的主要方向[5-7,10]。随着隐私计算技术和产品的发展，且在数据协同应用的驱动下，有多个机构推出了隐私计算平台型产品。本文主要介绍隐私计算的关键技术与创新，并对这些技术与创新在Angel PowerFL通用隐私计算平台中的应用进行分析和研究。

1 联合建模关键技术与创新

1.1 隐私集合求交协议

1.1.1 PSI是隐私计算关键技术之一

隐私集合求交(Private Set Intersection，PSI)[15-17]是多方安全计算领域中的经典问题，它要求参与方在互相不公开本地集合的前提下，共同计算得出多个参与方的集合的交集，且不能向任何参与方泄露交集以外的信息。PSI是隐私计算关键技术之一，也是纵向联邦学习的关键支撑技术。在纵向联邦学习场景中，PSI也被称为样本对齐(Sample Alignment)或者数据库撞库，即各参与方需要首先求出各自的训练样本ID集合之间的交集，基于计算得到的训练样本ID交集进行后续的纵向联邦模型训练。考虑到PSI在纵向联邦学习中的重要作用，本文重点介绍多方PSI、工程优化、安全性提升、软硬件结合这4个方向上的创新。

1.1.2 多方PSI

在多方场景中，即隐私计算参与方大于等于3的场景(见图1)，PSI算法的计算复杂度会显著变高。为避免过大的时间消耗，通常采用两两求交集的替代方法来实现“等效的多方PSI”，包括基于Diffie-Hellman密钥交换的DH算法[11,14]、基于盲签名的Blind-RSA算法[11,13]和基于不经意传输(Oblivious Transfer，OT)的算法[11]。然而，尽管这一方法可以降低计算的复杂度，却会带来一个非常严重的安全隐患，即会泄露那些属于两方交集但不属于多方交集的数据。针对此问题，基于Freedman协议提出了一种严格的多方安全PSI协议[17]，可以保证除了多方样本ID交集信息之外，任何其他信息均不会泄露。进一步通过工程实现以上的优化，将多方PSI的计算复杂度从O(n3)降低为O(n)，实现了可以在实际应用中支撑海量数据计算的多方PSI协议。

图1 多方PSI(除三方集合的交集，其他任何信息都不能暴露)

多方PSI协议的核心思想是将样本ID集合编码成特殊的数据结构，即不经意多项式，其中每一个样本ID均为不经意多项式的根。利用半同态加密算法对多项式参数进行保护，使多个参与方可以在密文空间下进行多项式求值，同时又无法读取多项式参数的明文。然而，大整数多项式系数展开和求值的计算复杂度均为O(n3)，为了解决这一计算瓶颈，提出了一种基于哈希分桶的优化方法。具体而言，利用哈希分桶技术将ID集合均匀映射到若干ID分桶中，这里要求各参与方使用相同的哈希函数，以便确保相同的样本ID被映射到相同的分桶中。这样一来，只需要进行“桶内计算、桶间合并”即可得到完整的多方ID集合的交集。将单个桶内样本数量视为一个常数，算法的计算复杂度可以优化到O(n)。实际测试结果显示，在通过哈希分桶技术优化后，三方PSI任务可以得到9倍以上的效率提升。

1.1.3 非对称隐私集合求交

在某些实际应用场景里，一个参与方A的样本量远远小于另一参与方B，这里称拥有样本量少的A为弱势方，称拥有样本量多的B为强势方(见图2)。此时，PSI的计算结果可能非常接近弱势方的真实样本ID集合，存在一定的数据泄露风险。例如，广告平台和商家进行联邦建模，广告平台拥有海量用户，商家客户数量少且具有高度隐私性(如购买某种特定类别的药物的客户)，若商家将客户ID信息暴露给广告平台方，可能会使客户隐私受到侵害。业界将这种场景定义为非对称联邦学习场景[18]。

图2 非对称PSI场景

针对上述非对称联邦学习场景，在PSI流程中，提出从强势方的ID集合中随机抽取部分密文ID数据混入最终交集中，可以得到如下效果。

(1)最终计算得到的PSI交集由真实交集和混淆集合组成，其中混淆集合全部来自强势方的样本ID。

(2)弱势方可以获得PSI交集，同时可以通过对比本地ID集合和ID交集得到真实的样本ID交集，但是无法获取混淆交集部分的样本ID(由密文保护)，保护了强势方的数据安全。

(3)强势方可以获得PSI交集，但是无法判断哪些样本属于真实ID交集。

(4)在实际场景中，当弱势方和强势方数据量之比在1:100时，只需要取真实交集与强势方集合数据量之比为1:10，即可将弱势方数据的安全性提升10倍。

1.1.4 利用可信执行环境实现PSI

可信执行环境(Trusted Execution Environment，TEE)是一种硬件技术，借助硬件构建安全的“飞地”(Enclave)，用于存放敏感数据与代码，并保证它们的机密性与完整性。目前，在隐私计算领域最常用的TEE是因特尔公司推出的SGX[25]。通过采用TEE作为可信计算模块，结合联合计算软件框架和TEE硬件模块，可以为隐私计算应用场景提供定制化解决方案，例如基于TEE的PSI方案(见图3)。

图3 基于TEE/SGX的PSI解决方案

基于TEE的PSI方案已经在很多场景落地应用，可以支持任意数量的参与方，且只要求其中至少一方部署TEE服务即可。在计算开始阶段，各参与方将本地样本ID集合排序并加密，均匀分配并上传到部署TEE服务的若干个参与方，由TEE可信计算模块解密并完成样本ID集合求交。与传统纯软件实现的PSI方案相比，基于TEE的PSI方案部署灵活，可适用于多种场景。由于使用硬件代替多方安全算法来保护数据，计算时间得到很大优化，例如两方PSI场景的十亿级别数据计算速度可提升3倍以上，三方PSI场景的十亿级别数据计算速度可提升10倍以上。

1.2 斜向联邦学习

谷歌于2016年率先提出了联邦学习的概念[6]，主要用来解决如何在数据不出域的情况下，联合多个终端(如智能手机)中的数据进行模型训练的问题，并应用在输入法预测改进等场景。国内的学者进一步拓展了联邦学习的概念[5]，提出了横向(Horizontal)和 纵向(Vertical)两种联邦学习框架(见图4)。其中，谷歌提出的联邦学习范式可以看作是横向联邦学习。随着技术的不断发展成熟，以及人工智能落地过程中数据痛点愈发凸显，联邦学习得到了更多的关注，学术界和工业界开始联合起来系统化地研究整个技术体系，越来越多的企业开始尝试引入联邦学习并将其作为打通多方数据的一种解决方案。实践已经证明，纵向联邦学习可以显著提升机器学习模型的效果和表达能力。

图4 联邦学习两种形态：横向、纵向联邦学习

在实际应用场景中，还有一种联邦学习形态，称之为斜向联邦学习(Diagonal Federated Learning，DFL)。在斜向联邦学习场景里，参与方A和参与方B各拥有一部分特征，且两个参与方分别拥有一部分由两方PSI获得的交集中的样本的标签信息，具体参见图5。

图5 联邦学习第三种形态：斜向联邦学习

两方斜向联邦学习适用的场景是联邦学习的两个参与方A和B的训练数据有重叠的数据样本，两方拥有的数据特征却不同，两方数据特征空间形成互补，类似于纵向联邦学习场景。与纵向联邦学习不同的是，在两方斜向联邦学习里，参与方A和参与方B各拥有一部分PSI交集里的样本对应的标签信息，甚至参与方A和参与方B可能同时拥有一部分样本的标签信息。因此，从标签信息维度看，斜向联邦学习又类似于横向联邦学习。

斜向联邦学习的应用场景常见于金融领域。不同的金融机构(如银行与支付平台)拥有的数据特征不一样，且可能各自拥有一部分样本的标签信息。斜向联邦学习的算法协议可以从纵向联邦学习演化发展得到。例如，在两方纵向联邦逻辑回归(Logistic Regression，LR)协议里，拥有标签信息的一方称为Guest，另外一方称为Host。在两方斜向联邦LR协议里，可以请两个参与方A和B分别轮流担任Guest和Host的角色，这样就可以分别使用参与方A和B拥有的标签信息。需要注意的是，在进行小批次(Mini-batch)数据划分时，每个小批次中的训练样本的标签信息必须属于同一个参与方。如参与方A和B都拥有某些样本的标签信息，那么可以通过协商，提前约定使用哪一方的标签信息，或者通过试验来确定使用哪一方的标签信息训练的模型效果更好。

1.3 异步并行计算策略：计算与通信重叠

在联邦学习中，由于数据来源于不同的参与方，联邦学习算法通常需要在多个参与方之间进行加密中间计算结果或转化结果的交换，导致不同参与方之间的计算逻辑存在依赖性。例如，在纵向联邦学习中，为了保护标签信息，拥有标签信息的Guest方需要对模型损失函数的反向偏导数进行加密，再将加密后的偏导数发送至其他Host方进行后续计算。最后，Guest方还需将Host方的计算结果进行收集、解密。显然，这种依赖性容易导致参与方之间的互相等待。例如，在Guest方完成加密操作之前，Host方将处于一个等待接收的空闲状态；Guest方等待接收Host方的计算结果的期间也存在一个较长的空闲状态；在Guest方完成解密操作之前，Host方将再次陷入空闲等待的状态。毫无疑问，这种交替的互相等待，将极大地降低联邦学习系统的整体运行效率以及资源使用率。

在传统机器学习的研究与应用中，有许多使用异步并行优化来减少空闲等待时间的技术，如异步并行更新(Asynchronous Parallel，ASP)、梯度编码(Gradient Coding)等。然而，这类相关工作所关注的通常是数据并行中节点之间的同步开销，在这种场景中，每个节点拥有完整的机器学习模型，并可以自主地完成模型的正向计算与梯度反向传播。而在联邦学习场景中，特别是纵向联邦学习场景中，每个参与方通常无法独立完成计算，所以现有的异步并行优化技术无法直接应用于纵向联邦学习中。

为解决计算和交互效率痛点，提出了参与方之间的异步并行计算优化技术(见图6)，主要的技术手段包括：将数据进行分批处理，不同的小批量数据之间可以异步并行计算，从而实现参与方的计算与跨参与方的通信之间的重叠，显著降低每个参与方的空闲等待时间；并借助机器学习模型对延迟更新的鲁棒性，使用异步更新打破不同迭代之间的壁垒，实现更进一步的多批次的异步并行。

图6 基于Spark的异步并行计算：计算与通信重叠

1.4 通信消息压缩机制

隐私保护是联邦学习最主要的目标之一，因此联邦学习通常需要采用半同态加密的手段来对重要信息进行加密保护。然而，半同态加密会带来密文膨胀问题，引入巨大的通信开销，例如采用3072位Paillier同态加密后[12]，单个浮点数的体积可能膨胀至6144位，在进行密文传输时，通信开销凸显，阻碍实际应用。

在机器学习中，模型参数与中间计算结果(正向计算激活输出、反向梯度等)通常会落在一个非常小的值域范围内。基于这个事实，许多已有的研究工作都考虑对数据进行量化压缩，从而降低通信量。然而，已有的量化压缩方法所适用的对象均为浮点数，对于联邦学习涉及的密文传输，已有的量化压缩方法并不适用。

尽管现有方法无法直接应用于密文传输，关于数据值域的分析提供了新的解决思路，即为了对浮点数进行加密，通常做法是对其进行某种大整数编码，相比于大整数的最大表示范围(如1024位)，编码后的大整数真实值往往落在一个非常狭小的范围内。借助这一性质，提出了一种基于多项式偏移的密文打包压缩算法，例如该算法可将64个密文进行打包压缩，从而将密文的通信开销降低了64倍，显著提高了算法的运行效率和降低了通信开销。

1.5 单向发起通信连接

在联邦学习场景里，参与方之间需要进行加密中间计算结果或转化结果的交互，因此需要允许参与方之间开放端口以进行网络通信。然而，在金融领域，金融机构网络防火墙的策略往往比较严格，内部任务不允许监听任何对外端口，即不允许对外暴露端口。在此背景下，一方无法主动向另一方(如银行)发送数据，导致现有的双向主动通信框架不可用。为了应对这一挑战，对跨参与方的通信架构进行了改造，以支持单向发起主动通信的模式。

如图7所示，以基于Pulsar消息队列的通信框架为例，与传统的双向主动发起通信模式不同，在单向主动发起通信模式中，参与方A不需要对参与方B暴露网络端口信息，只有参与方B向参与方A提供网络端口信息。在单向主动发起通信模式下，参与方A通过拉取的方式接收参与方B发送的消息，即参与方A向参与方B主动发送Pull消息，参与方B通过回复Response消息来向参与方A发送消息。在这种单向主动发起通信设计下，有较高网络安全要求的一方(参与方A)不再需要对外暴露网络端口，极大地提高了安全性，适用于众多与银行、保险、政务等行业的联邦学习应用场景。

图7 传统双向发起通信与单向发起通信的对比

2 联合分析关键技术与创新

安全多方联合数据分析也是隐私计算重要的应用场景。通过和实际业务的深入接触，发现在非机器学习的场景中，隐私数据的联合统计分析有着很大的需求和应用空间。例如，参与方A和B分别持有一些数据，需要联合统计某些维度上的数据，产出一份联合数据分析报表，但是又不能向彼此泄露原始数据。为了在符合安全隐私计算规范的条件下满足上述需求，基于结构化数据查询与处理工具，设计了安全联合数据分析框架。根据用户不同的安全等级需求，定制化地提供不同的安全联合查询、计算、统计等功能。

2.1 联合分析架构设计

安全联合数据分析的整体技术架构如图8所示，主要分为三层功能组件。

图8 联合数据分析技术架构

(1)用户接口层：联合数据分析充分借鉴传统的SQL用户接口习惯，通过安联合计算编译器，对用户SQL进行编译，解析抽象语法树(Abstract Syntax Tree，AST)。

(2)优化策略层：对查询命令进行最小功能划分，把AST转换成以安全计算算子为原子任务的分布式执行计划，然后分发到执行引擎。

(3)安全计算层：在底层计算协议的实现上，采用半同态加密、秘密分享、多方安全计算等技术构建安全算子，在不泄露用户隐私的条件下实现原子任务的执行。具体安全算子的实例有PSI、安全GroupBy、跨源用户定义函数(User Defined Function，UDF)与用户定义聚合函数(User-Defined Aggregate Functions，UDAF)等。

2.2 联合计算编译器

为了满足易用性，联合数据分析需要严格遵循SQL语法，其编译优化技术栈可以分为以下三步。

(1)AST转化：与传统的数据库查询相同，首先将用户输入的SQL进行词法分析与语法分析，得到对应的AST。

(2)安全计算分析：在解析得到AST后，对AST进行安全计算分析。一方面，对AST中所有涉及两表关联查询(如Join操作)替换成安全算子，对于可能造成隐私泄露的(如单列查询)，如果未经授权则编译发出警告；另一方面，对AST中涉及到的所有表与字段进行权限分析，若发起方尝试对未被授权访问的表或字段进行查询，将会拒绝该查询请求。

(3)执行计划优化：在完成AST安全分析后，将AST映射为实际的执行计划。在生成执行计划时，还进行了两方面的优化。首先，传统的查询优化技术可以无缝衔接到联合数据分析平台中。此外，着重对联合安全算子进行了分析优化。其主要原因为，与传统的算子相比，联合安全算子涉及多方的安全计算，所需要的耗时往往更长，计算代价更高。为此，可以采用数种基于代价的优化策略，如列裁剪、谓词下推、常量折叠等，对联合安全分析进行有针对性的优化。

2.3 安全算子

联合数据分析的关键点在于如何在联合多个参与方的数据进行分析时，保证各方的数据隐私安全。为此，设计了全栈的安全算子，以覆盖绝大多数的应用场景，如Join算子(见图9)。

图9 联合数据分析中的安全Join算子

2.3.1 PSI算子

两表或多表求交集(如Join操作)是数据库中最重要和常用的操作之一。在安全联合数据分析中，Join操作同样有着十分广泛的应用场景。例如，参与方A为某应用(如游戏、社交、短视频APP等)的运营部门，持有用户行为日志(如注册、登录、使用时长、充值行为等)，参与方B为渠道方，持有曝光数据，A和B双方希望联合计算某时间段内指定渠道的曝光量或充值情况，这需要对双方的数据表进行求交，抽取符合条件的数据进行统计。

由于不同的数据表来自于不同的参与方，在进行数据表求交的同时，还需对交集之外的行ID进行保护，可以使用前文所介绍的PSI技术来实现安全数据分析中的Join操作，在高效完成数据表求交的同时，保证各参与方的数据安全。

2.3.2 安全GroupBy与UDAF

多方聚合计算同样是安全联合数据分析中最常见的操作之一。随着数据隐私保护条例的出台，不同职能的公司、机构所拥有的用户数据有着很大的易构性。因此，为了实现更细粒度的用户数据统计与分析，多方安全聚合是至关重要的一项技术。

常见的联合数据分析应用包括两种多方安全聚合计算场景，具体如下。

(1)“单方分组，联邦聚合”，即以一方的数据作为分组条件，对另一方的数据进行聚合操作。

(2)“联邦分组，联邦聚合”，即将分组条件拓展至使用两个或多个参与方的数据，并进行指定数据列的聚合操作。

基于半同态加密、秘密分享等技术手段，可以实现求和、求最值、取平均等多种安全聚合算子。此外，还提供用户自定义安全聚合接口，用户可根据实际业务需求以及数据安全接口，实现自定义的聚合操作，服务于更广泛的业务场景。

3 Angel PowerFL隐私计算平台

Angel PowerFL(简称PowerFL)安全联合计算平台是通用型隐私计算平台，兼顾了工业界的高可用性和学术界的创新性，同时支持联邦建模与联合数据分析，并已在金融、广告、医疗、政务等多个行业应用落地。

3.1 PowerFL平台特点

在数据保护方面，PowerFL平台提供多种隐私保护机制，包括半同态加密、秘密分享、差分隐私、TEE等[21-25]。并且PowerFL采用去中心化的架构设计，不依赖任何中心节点。PowerFL平台提供多样化的、可按需选择的隐私保护机制，更加安全，适合实际应用场景。

在功能方面，PowerFL平台拥有全栈的安全联合机器学习和深度学习功能，支持多方及非对称PSI、斜向联邦学习、多方联邦在线预测和模型版本管理，并支持多方安全联合数据分析功能。

在性能方面，依托Angel机器学习平台的海量数据处理能力，PowerFL支持千亿级别的海量数据计算，通过异步高并发计算、通信消息压缩、硬件加速等多种技术创新来提高计算和通信效率。基于Pulsar消息队列的底层通信组件更加增强了系统的稳定性和容错能力。基于Spark的计算框架和基于Pulsar的底层通信框架都是业界首创。

在易用性方面，PowerFL平台采用云原生设计，支持容器化部署、支持基于YARN和K8S的灵活资源扩缩容等特性。PowerFL平台采用计算层和服务层分离，在高并发计算和灵活资源扩缩容方面优势凸显。

3.2 PowerFL平台框架

如图10所示，PowerFL平台包括五层功能组件，自底向上依次如下。

图10 Angel PowerFL平台框架

(1)资源管理：PowerFL支持YARN和K8S两种主流的计算资源调度方式，并支持从多种数据源读取数据，包括HDFS、Ceph、COS云存储等。

(2)计算框架：基于Angel-PS的高性能分布式参数服务器[8-9]，PowerFL支持多种高效的分布式联邦机器学习算法，提供基于Spark SQL的联合数据查询与数据分析功能。PowerFL支持Pulsar消息队列、gRPC、Socket等多种通信机制，在保证数据安全的前提下，实现了稳定可靠的高性能跨网传输。

(3)算法协议：PowerFL针对不同场景实现了常见的联邦学习算法协议，包括多方联邦LR、XGBoost模型用户自定义神经网络模型等，以及常用的联合数据分析算子。

(4)产品交互：PowerFL既支持以REST API的形式调起任务，也支持各参与方在联合工作区上协同工作。

(5)应用场景：PowerFL平台已经在金融、广告、智慧政务、智慧医疗等多个行业应用落地。

3.3 PowerFL联邦学习系统设计

图11展示了PowerFL平台在两方协同场景下的系统架构图。在整个联合建模与分析的过程中，A和B双方的原始数据均不出本地。PowerFL系统架构具有以下特点。

图11 Angel PowerFL平台系统设计

(1)A、B两方独立部署PowerFL的本地框架，支持YARN、K8S等多种资源申请方式，与现有大数据业务系统完全兼容。

(2)本地PowerFL Executor的计算采用Spark，充分利用其内存优先和分布式异步并行的优点，效率高且易于和现有大数据生态(如HDFS等)对接。

(3)本地平台构建在Angel-PS参数服务器之上，支持海量数据的分布式训练。Angel-PS支持Checkpoint，具有很好的容错性和断点续训功能。

(4)在A、B两方之间直接进行安全通信，实现了“去中心化”，整个隐私计算流程仅需要协调双方。

4 结束语

本文主要介绍了隐私计算的关键技术与创新，并介绍了这些技术与创新在Angel PowerFL通用隐私计算平台中的应用。隐私计算和联邦学习技术正在快速演进和产品化，规模化商业应用还处于起步阶段，在安全方面还没有一套完善且业界认可的标准规范，加密和解密带来的计算开销和通信开销也需要进一步优化。隐私计算是解决数据协同与隐私保护矛盾的有效技术方案，并将随着大数据与AI产业的发展，在跨机构数据协同、数据隐私保护等方面将会发挥越来越重要的作用，有着广阔的应用前景。