实际应用方法

在纵向联邦学习中，需要进行用户对齐，即交集计算。比如公司A有用户集合，公司B有用户集合，这里，我们需要在不泄漏各个参与方(公司A和B)输入信息下，协同计算输入集合的交集，即参与方只能获得交集部分的ID，而不会获得或泄漏非交集的ID。

在实际的业务中，现在很难直接拿到设备号等数据锁定唯一用户，因为IOS禁掉了UDID和IDFA，Android在Android 11后也基本拿不到用户唯一识别ID，所以现在大家基本都采用多维度加某一算法唯一确定用户，比如取手机型号/系统版本/版本更新时间/手机用户名….等个维度，代入比如md5算法，最后输出一个值作为这个用户的唯一识别ID，如果有维度数据变化了，会重新计算更新之前计算的值。由于md5算法具有不可逆性(根据 MD5 值计算不出原始数据)，所以数据是安全的。

但在实际操作中，我们即使获取尽可能多的用户特征维度，也无法百分之百保证锁定的用户是唯一的，即有两个或至少两个用户个维度是相同的，我们代入算法后输出值也一致，这两个或至少两个用户就共享了同一个唯一识别ID。由于现在业界还没有一套标准解决方案(由于大家选择的维度和算法不一致，导致现在市面上有多套唯一识别ID，比如阿里有一套，京东有一套…)，而且也不可能会出现一套标准解决方案(如果某一方案应用特别广，利益涉及公司比如苹果公司会对这个方案使用公司发律师函，毕竟这是苹果手机厂商天然的护城河)。所以在实现纵向联邦学习时，各合作方间会商量好唯一识别码的计算方式，通过唯一识别码进行交集计算。

联邦学习交集计算，即隐私保护交集计算，主要分为三类：基于公钥加密、基于混淆电路和基于不经意传输的方法，这里分别进行介绍。

交集计算算法

基于公钥加密

在这类方法中，公钥加密方法被用于对集合中的元素进行加密，然后通过对密文的处理实现交集计算。

基于指数

一种简单的思想是，利用这一性质，对于分别由双方所持有的元素和，双方分别产生和，并共同验证和是否相等。具体来讲，持有的一方计算并且把结果发送给另一方，而另一方计算并且把结果发送给对方。双发得以计算和并且把结果发送给对方，从而验证两个元素和是否相等。为了防止另一方通过对数运算推出明文，这里的所有指数运算的结果都对进行取模运算，其中为双方共同选取的质数。双方将各自集合的元素两两组合，计算并验证是否相等，获得交集。

基于多项式

Freedman等人提出了基于公钥加密体制的隐私保护交集计算方法。它的具体过程如下。客户端对于其集合构造多项式，并且用同态加密算法加密多项式系数，然后发给服务端

服务端对于其集合中每个元素计算

并且发送给客户端。式中，表示密文；为服务端产生的随机数。显然，如果，即，则，从而。因此，当客户端收到并解密后，如果发现该结果在集合中，那么它为交集元素。

这种方法对于长度为的序列占用了的传输负荷和的计算量。它在半诚实环境下的标准模型下是安全的，在恶意环境中的随机预言机模型(Random Oracle Model，ROM)下也是安全的。其中随机预言机模型是一个“黑箱”。它类似于哈希函数。对于某个输入数据，它可以在多项式时间内计算输出数据；对于相同的输入数据可产生相同的输出数据，且输出数据在输入数据的取值空间内均匀分布，没有碰撞。随机预言机模型是构造搞笑密码学方案的有效工具。然而，它只是一个理想化的原型，在实际应用中可能被哈希函数，例如SHA所取代。

基于RSA

De Cristofaro等人基于RSA公钥体系，提出了一种效率更高的方法。设客户端持有集合，服务端持有集合，并且双方知道两个哈希函数和，则步骤如下：

1. 在离线阶段，服务端对各个元素计算和
2. 客户端对各个元素选取，并计算
3. 进入在线阶段，客户端向服务端发送各个
4. 服务端对各个计算，并将各个与发送给客户端
5. 客户端计算和，并计算出

此后，Chen等人实现了效率的进一步提升。该方法基于全同态加密，先给出了基础协议，而后进行了种种优化。其中，基础协议如下：

1. 接收者输入集合，其大小为；发送者输入集合，其大小为
2. 双方商定一个全同态加密方案。接收者产生一个公钥-私钥对，其中私钥保密
3. 接收者加密其集合中的所有元素，并发送个密文给发送者
4. 对于每个，发送者随机产生一个非零明文，并且同态地计算。发送者返回密文给接收者
5. 接收者解密密文，并输出

它结合全同态加密中的批量化(Batching)技术、哈希函数和窗口化(Windowing)技术等，实现了对该基础协议的优化。不失一般性，假设，则优化后的协议的通信复杂度为

基于公钥加密体制的方法每一步仅处理一个元素，因此内存占用量小，则容易实现并行计算；如果双方集合的大小相差甚远，那么计算量很大的公钥加密操作可以集中在一方进行

基于混淆电路

假设在双方集合中的元素都是位的元素，即取自。当很小时，可以利用两个长度为的位向量分别表示双方集合中的元素，然后利用逐位与运算(bitwise-and，BWA)进行比较。

当较大时，这个时间复杂度的方法不再适用，此时可采用逐位比较(pairwise-comparisons，PWC)方案。逐位比较方案即对来自双方集合的两两元素判断是否相等，而判断相等的电路通过对它们进行异或运算之后再进行非运算来实现。这一方案的复杂度为双方集合大小的乘积，并且与呈线性关系。

假设双方的集合大小都是，则这个复杂度就是。而排序-比较-洗牌(sort-compare-shuffle)方案将这一复杂度降至。在这个方案中，

1. 双方首先对其集合进行排序
2. 然后，通过不经意合并网络(Oblivious Merging Network)，双方合并排序后的集合，并排序
3. 双方再通过混淆电路比较相邻元素，从而得出集合
4. 最后，双方不经意地打乱交集的顺序，以避免信息泄漏 | A | B | | —- | —- | | 2，1，4，3(A的原始数据) | -1，3，2，5(B的原始数据) | | 1，2，3，4(各自排序后) | -1，2，3，5(各自排序后) | | -1，1，2，2，3，3，4，5(合并排序后) | | | 2，3(在相邻元素中找到相等元素) | |

计算交集的电路连接到其他电路，就能够进行一些其他计算，如计算集合大小、元素求和等。这种易扩展性时基于公钥加密体制的方法和基于不经意传输协议的方法所不具备的。但是，再基于混淆电路的方法中，电路方案占据了大量的内存，其计算复杂度与电路中的与门的数量成正比，而并行化能否实现取决于电路的结构

基于不经意传输

得益于不经意传输协议的发展和不经意传输扩展协议(Oblivious Transfer Extensions)的提出，一种隐私保护交集计算技术能够在300秒内计算百万量级集合的交集。经过效率和安全方面的不断改进，基于不经意传输协议的隐私保护交集计算方法已经将这一时间缩减到60秒。

如何具体描述不经意传输协议的定义呢？它可以分为选不经意传输协议和选不经意传输协议。在2选1不经意传输协议的次调用中，发送者持有个元素对，式中，，接收者持有位向量。在协议完成后，接收者获得各个被选择的元素，但是不会知道另外的元素，而发送者则不会知道。这里把这个不经意传输协议记作。相应地，表示对于位元素的、次调用的选不经意传输协议。结合不经意传输协议和随机预言机，Ishai等人和Kolesnikov等人分别给出了高效的选不经意传输扩展协议和选不经意传输扩展协议。

其他方法

此外，还有一种不完全安全的协议可以用于交集计算，也是实际操作中最常用的方法。在该协议中，双方共同确定一个密码学哈希函数，比如md5，然后一方将自己的各个元素的哈希值发送给另一方，另一方计算交集。这种方法在输入域很小的情况下是不安全的，但在输入域很大的情况下是安全的。不安全的方法和基于公钥加密体制的方法每一步仅处理一个元素，因此内存占用量小，且容易实现并行计算。

另外，基于全同态加密的方法也可用于交集计算。全同态加密允许电路直接对密文进行计算。一方将数据加密后发送给另一方，另一方计算后将结果返回，该方再进行解密。随着两个集合的元素数量之和和电路深度增加，基于全同态加密的方法的计算是一种比较低效的方案。