走近隐私计算 | 联邦学习中基于隐私集合求交(PSI)的样本对齐

前言

隐私计算作为保障数据价值挖掘过程中隐私安全的技术集合，能够在释放数据价值的同时，实现数据处于加密状态或非透明状态下的流通与计算，以达到各参与方隐私保护的目的。

本系列“走近隐私计算”将陆续带来隐私计算的几种技术路径（安全多方计算、同态加密、零知识证明、可信执行环境、联邦学习等）的整体介绍，以及部分经典论文的学术研读。

本期将作为“走近隐私计算”系列的第一期，浅谈在联邦学习中，如何实现基于隐私集合求交的样本对齐。

在过去几年里，人工智能(Artificial Intelligence, AI)技术迅猛发展并在工业界产生了许多应用。人工智能的基础技术如机器学习、深度学习等都建立在大量数据的基础上，训练人工智能应用模型所需要的训练数据是十分庞大的，然而在许多应用领域，单一数据持有方很难达到仅依靠本地数据训练出有效模型，不同数据持有方之间的数据孤岛问题正阻碍着人工智能技术的发展与应用。联邦学习是一种可行的办法使得各组织之间联合训练，构建全局模型的同时确保参与方的隐私和数据安全。

联邦学习主要分为以下三种：

横向联邦学习

横向联邦学习(Horizontal Federated Learning)^[1][2]也称按样本划分的联邦学习，可以应用于联邦学习各参与方的数据集有重叠的特征空间和不同的数据样本的场景。举例来说，两个地区的通信运营商在各地有自己的用户群体，他们之间的用户交集非常小，因此他们的数据集中有不同的样本ID，但他们的业务非常相似，因此他们之间的特征空间是相同的。联合进行横向联邦学习可以更好的构建套餐推荐等模型。

纵向联邦学习

纵向联邦学习(Vertical Federated Learing)^[1][2]可以理解为按特征划分的联邦学习，数据集上具有相同的样本空间、不同特征空间可以归为纵向联邦学习问题。举例说明，某银行A与某电商公司B达成合作，双方之间有着大量重合客户，银行A有着客户收入贷款等特征信息和还款情况等标签信息，公司B有着客户网购等消费特征数据，但数据之间存在隐私壁垒，无法通过传统的机器学习等方式联合训练模型。公司B与银行A通过纵向联邦学习将各自独有的特征信息相结合训练出一个更强大的客户信用风险识别模型，且不用泄露本地隐私数据。

迁移联邦学习

在实践中，我们经常会面临各参与方并没有足够的特征或样本，这些数据集的分布情况可能差别很大，数据集规模可能差异巨大，某些参与方可能只有数据，没有或只有很少的标注数据，联邦学习可以结合迁移学习技术^[3]使其可以应用于更广泛的业务，同时可以帮助只有少量数据和弱监督的应用建立有效精准的机器学习模型。迁移学习是一种为跨领域知识迁移提供解决方案的学习技术，而联邦迁移学习(Federated Transfer Learning)^[2][4]可以帮助上述场景中有数据安全使用问题的企业更好的开展机器学习应用，在零售、金融、医疗等领域中都有不少应用场景完成落地。

联邦学习在计算机科学和机器学习领域曾以多种形式出现过，例如，面向隐私保护的机器学习^[5]、面向隐私保护的深度学习^[6]、分布式机器学习^[7]等。除上述贡献以外，还有很多新的关于联邦学习的定制化研究^[11][12]。

联邦学习的发展历程

2.1

样本对齐

联邦学习是一种保证数据隐私的分布式机器学习框架，目的是在保证数据隐私的前提下提升AI模型效果。在纵向联邦学习中，样本分别属于不同组织，组织之间样本空间各有差异，进行纵向联邦学习的第一步就是在隐私保护下对参与方之间具有不同特征的重叠用户进行样本对齐。然后，所有参与方通过隐私保护协议共同学习一个机器学习模型。

纵向联邦学习的第一步是样本对齐，即跨域找出数据样本的公共集合(如共同用户)，而共同用户则代表双方数据集合中用户ID的交集部分。用户ID可以是手机号、身份证号等唯一标识，但此类敏感信息不适合于直接进行交集运算。有些联邦学习平台通过哈希函数对用户ID进行撞库实现样本对齐，哈希函数具有单向性，哈希值不会直接泄露隐私，但是通过碰撞攻击极易还原出用户ID的原始值，所以需要一种安全性更高的隐私计算方案实现ID隐私对齐。

2.2

隐私集合求交(Private Set Intersection, PSI)

隐私集合求交技术允许私有集合数据持有方联合计算出集合交集而不泄露除交集外的任何隐私信息，如图1所示，Alice持有集合  ，Bob持有集合  ,他们的公共集合  ，在常见的PSI协议中双方或者其中某一方可以得知公共集合  ，而无法得知另一方除  以外的任何其他元素信息。作为安全多方计算中的重要密码学工具，PSI技术是许多密码协议的基础模块，也是纵向联邦学习中隐私数据对齐的重要解决方案之一。

图1  集合交集

隐私集合求交技术也产生了许多实际应用，私有联系人查找是其中的一个典型的应用场景。当用户注册一种新的服务(如抖音、Whatsapp)时，从用户的通讯录中查找有哪些人注册了同类服务已经成为了非常常见的功能。如：Alice首次下载了Whatsapp并进行了登录，此时Alice想知道她有哪些朋友也注册了这个APP,将Alice的本地通讯录直接发给服务器，由服务器对比之后返回交集是一个解决办法，但通讯录一般被认为是非常隐私的信息，用户不愿意暴露给外部。

PSI协议可以求出参与方私有集合的交集而不暴露参与方非交集部分的任何集合元素信息。将Alice的本地通讯录信息作为PSI的一方输入，服务提供商的所有用户名单作为PSI的另一方的输入，可以找出Alice有哪些朋友也在使用这个APP，同时，Alice的私人通讯录信息不会有泄露的风险。

图2  私有联系人查找

目前已有大量隐私集合求交方案被提出，主要有基于公钥密码学的PSI方案、基于混淆电路的PSI方案和基于不经意传输(Oblivious Transfer)的PSI方案。常被应用于联邦学习的PSI算法主要有基于RSA的PSI方案和基于Diffie-Hellman的隐私集合求交方案，我们本次主要介绍基于Diffie-Hellman^[16]的隐私集合求交方案。

Decisional Diffie-Hellman(DDH)假设:双方协定群  和生成元  ， 对于随机选取的  ，  与  是不可区分的。

协议1  基于Diffie-Hellman的隐私集合求交方案

参与者：持有集合  的Alice,持有集合  的Bob

输出：  

1. Alice选取随机数  作为私钥，Bob选取随机数  作为私钥。

2. Alice计算  并将其发送给Bob，其中  表示安全的哈希函数。

3. Bob计算  以及  并将结果发送给Alice。

4. Alice计算  

5. Alice对比  和  中的公共元素即可得到隐私集合的交集。

图3   基于Diffie-Hellman的隐私集合求交^[17]

安全性分析：密文的安全性由已被证明的DDH假设保证。

正确性分析：

• 若  ，则  。

• 若  ，则  且Alice无法从  中获得任何敏感信息。

联邦学习是学术界和工业界的热点，是一种保证数据隐私的分布式机器学习框架，目的是在保证数据隐私的前提下提升AI模型效果。

本文首先介绍了联邦学习的概念以及联邦学习的三种基本场景，随后介绍了如何通过隐私集合求交技术解决联邦学习中的数据对齐问题并介绍了一个隐私集合求交(PSI)方案。

PSI技术可以使得参与双方求解隐私集合的交集而不泄露除交集以外的信息，该技术已被应用于许多联邦学习开源项目中解决数据对齐问题。文中介绍的PSI方案意在帮助读者理解，但实际应用在工程领域时应当选取更加高效的隐私集合求交方案。

参考文献

[1]   Kairouz P, McMahan H B, Avent B, et al. Advances and open problems in federated learning[J]. arXiv preprint arXiv:1912.04977, 2019.

[2]   杨强, 刘洋, 程勇等. 联邦学习[M].电子工业出版社, 2020.

[3]   Pan S J, Yang Q. A survey on transfer learning[J]. IEEE Transactions on knowledge and data engineering, 2009, 22(10): 1345-1359.

[4]   Yang Q, Liu Y, Chen T, et al. Federated machine learning: Concept and applications[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2019, 10(2): 1-19.

[5]   Vaidya J, Clifton C. Privacy-preserving decision trees over vertically partitioned data[C]//IFIP Annual Conference on Data and Applications Security and Privacy. Springer, Berlin, Heidelberg, 2005: 139-152.

[6]   Aono Y, Hayashi T, Wang L, et al. Privacy-preserving deep learning via additively homomorphic encryption[J]. IEEE Transactions on Information Forensics and Security, 2017, 13(5): 1333-1345.

[7]   Li M, Andersen D G, Park J W, et al. Scaling distributed machine learning with the parameter server[C]//11th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 14). 2014: 583-598.

[8]   McMahan B, Moore E, Ramage D, et al. Communication-efficient learning of deep networks from decentralized data[C]//Artificial intelligence and statistics. PMLR, 2017: 1273-1282.

[9]   Smith V, Chiang C K, Sanjabi M, et al. Federated multi-task learning[J]. arXiv preprint arXiv:1705.10467, 2017.

[10]   Yang L ,  Chen T ,  Qiang Y . Secure Federated Transfer Learning[A/OL]. arXiv preprint arXiv: 1812.03337, 2018.

[11]   Cheng K, Fan T, Jin Y, et al. Secureboost: A lossless federated learning framework[A/OL]. arXiv preprint arXiv: 1901.08755, 2019.

[12]   Bhagoji A N, Chakraborty S, Mittal P, et al. Analyzing federated learning through an adversarial lens[C]//International Conference on Machine Learning. PMLR, 2019: 634-643.

[13]   Zhuo H H, Feng W, Xu Q, et al. Federated reinforcement learning[A/OL]. arXiv preprint arXiv: 1901.08277, 2020.

[14]   Dayan I, Roth H R, Zhong A, et al. Federated learning for predicting clinical outcomes in patients with COVID-19[J]. Nature medicine, 2021, 27(10): 1735-1743.

[15]   Qin H, Chen G, Tian Y, et al. Improving Federated Learning for Aspect-based Sentiment Analysis via Topic Memories[C]//Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. 2021: 3942-3954.

[16]   Diffie W, Hellman M. New directions in cryptography[J]. IEEE transactions on Information Theory, 1976, 22(6): 644-654.

[17]   Benny Pinkas. Private Set Intersection. Jan. 2015. Available: https://cyber.biu.ac.il/wp-content/uploads/2017/01/15.pdf

—END—

  排版 | 刘晨      图片 | 杨雅清

推荐阅读