一种寻找两个数据集交集的隐私保护方法

2022 年 4 月 29 日 CCF计算机安全专委会

隐私集合求交（private set intersection，下面简称为PSI）是一种强大的密码学技术，可以允许双方在不向对方公开原始数据的情况下计算他们数据的交集。换句话说，PSI允许测试双方是否共享一个共同的数据点（如位置、ID等）。本文将从基本概念开始介绍PSI及其在新冠疫情背景下的应用。

基本概念

如果您不具备密码学背景，不必担心，我们将从一些基本概念和常见术语开始介绍。

密码学被描述为是研究秘密通信的领域。当一方希望与另一方共享秘密消息，同时从数学意义上能够确保没有第三方接受到该消息的真正含义时，就是密码学。这种第三方通常成为敌手。敌手可以通过多种方式尝试干扰——或用密码学术语来说，攻击——通信传输。

为了隐藏消息的真实含义，我们引入另一个术语：加密。该术语是比密码学低一层的术语。我们说某些消息被加密是指当真实信息通过数学编码成看起来随机的东西，因此对于不打算阅读真实信息的人来说根本没有意义。

例如，通常可读的明文消息可以使用密钥进行数学操作加密变成不可读的密文。加密的一个安全目标是生成的密文与随机文本无法区分。秘密消息不一定是文本消息，可以是仅应在双方之间共享的任何数据。当然，有很多算法和相关的工具可以用来加密和解密消息。

在进入研究PSI之前，我们将深入了解一种特定的加密形式，它可以用于构建PSI协议：同态加密（Homomorphic Encryption）。

通常而言，同态加密是一种可以在不知道明文（未加密）消息的情况下，对密文执行计算的密码学技术。这样计算后会产生一个加密结果，解密后的结果与明文执行相同计算的结果相同。比如，在一个场景下，作为云服务提供商的用户，希望对云中存储的数据运行某种算法但可以确保数据（想象为敏感的个人数据）保密的情况下，也就是说对云服务提供商是不可见的。同态加密是任何高度监管的行业的最好的朋友，因为它可以让您计算加密数据的结果，而无需与任何（云）服务提供商共享密钥。只有拥有密钥的人，即您，才能解密此类计算的输出。

请记住同态加密只是众多加密技术之一，PSI也可以与其他技术一起使用。同态加密技术也存在多种分类，例如全同态加密、部分同态加密和半同态加密技术等。主要区别是支持算数运算的程度，但这超出了本文的范围。

密码学另一个值得一提的子领域是多方安全计算（secure Multi-Party Computation）。多方安全计算可以解决通信双方/多方的数据保护问题。现在我们将进入第一部分的核心——隐私集合求交（PSI）。

PSI是一种技术，使双方都拥有一组数据点，可以在不放弃个人数据隐私的情况下比较这些数据集。它是一种隐私保护技术，允许双方计算他们的数据交集。输出的结果是第三个数据集，其中仅包含双方共有的那些元素。

在使用PSI的场景中，最常见是“服务器—客户端场景”，其中仅有客户端将接收到两个原始数据集的交集集合。当然，PSI的其他变体也在实际中应用：如客户端只获得交集集合的大小（也就是交集集合中元素的个数），或客户端在交集中执行运算的结果。接下来，我们将研究这些设置下的实际应用。由于服务器—客户端场景不仅常见而且简单，下图给出一个正确的工作示例。

最后一个概念融合了加密方案和PSI这两个概念：两者结合可组成PSI协议。当您想要为用户场景设计一种安全且高效的协议时，需要考虑很多的使用设置。包括服务器、客户端拥有数据的大小，如何阻碍敌手可能的攻击，计算资源受限的情况（如在一个手机设备上）。想象一个巨大的决策树，您需要遍历它才能为您的个人使用场景找到一个完美的解决方法。我们已经遍历了这棵树，因此您不必担心下一节的用例特定的考虑因素。

最后，我们看看以下用户需求场景中PSI协议发挥了很大作用。请记住PSI主要的特征：双方参与，并且双方都不希望向对方展示他们自己的数据但是需要去找到交集或对交集中元素做一些事情。

在新冠疫情下PSI的应用

apheris AI和OpenMined共同开发了PSI代码，用于开发密切接触者追踪程序，可以通知COVID-19患者的潜在接触者。

目前正在开发和发布相当多的Covid-19应用程序。虽然它们各自具有不同的功能，但总的来说，它们的核心工作流程是相似的：从手机上收集每个用户的活动轨迹数据；如果当地卫生当局诊断出用户感染了新冠病毒，则用户可以（但通常不必！）共享他们的数据并将其传输到服务器；任何使用该程序的其他用户都可以通过向该服务器询问更新的数据来了解他们是否可能与测试呈阳性的用户接触过。此工作流包含两个在共享和比较数据时需要考虑的隐私问题：确诊患者的隐私和用户的活动轨迹数据。

在用户方面，PSI允许用户检查他们收集的活动轨迹数据是否与确诊患者的活动轨迹相符，而无需向服务器透露他们的私人活动轨迹数据。根据PSI协议的类型，客户端将只学习到相互匹配的数据本身，或匹配的活动轨迹的个数。

在确诊患者方面，患者与服务器共享数据的情况需要另一种协议。但它也需要一个快速、安全和匿名的协议，不会泄露他们的个人信息。

Covid-19应用程序只有在被足够多的人群采用时才能成功。决定应用程序采用率的因素有很多，包括文化、平台可用性和电信基础设施的发展。然而，推动采用的一件事肯定是隐私和信任。PSI是朝着大规模采用迈出的一大步。

PSI实现示范

最后，我们讨论PSI算法的实现。一种实现方法在OpenMined的COVID警报应用程序中得到了验证，该应用程序使用了部分同态加密方案Paillier加密系统，其中来自客户端的加密值乘以服务器上的未加密值，产生只有客户端可以解密的加密结果。这种方法突出了同态加密的优点，尽管对于一般的PSI，其他加密方案也非常可行。

现在将介绍实现的RSA-PSI协议，您可以找到我们的开源Python实现。

RSA-PSI协议有3个主要阶段——基础阶段、设置阶段和在线阶段。假设客户端持有一组整数Y，而服务器持有一组整数X。如果您的用例涉及其他类型的元素，那么只需将您的元素编码为整数。

基础阶段：基础部分包含服务器生成RSA公私钥对，并将公钥共享给客户端。客户端为其集合Y中的每个元素都生成一个随机数，并存储它们的密文和模逆。客户端可以异步进行此操作。

设置阶段：在此阶段，服务器将使用私钥对其私有集合中的元素进行签名，然后将它们插入布隆过滤器，并向客户端共享该过滤器。

在线阶段：客户端使用在基础阶段生成的随机数来加密其集合中的元素，并将它们发送给服务器端，随后服务器端进行签名并将结果返回给客户端。客户端进行逆运算操作，最终得到每个元素的签名。然后客户端将检查布隆过滤器中每个签名的存在，如果签名匹配，则将相关元素放入交集。

现在客户端拥有交集集合了。值得注意的是，服务器端不会知道RSA-PSI协议中的交集。客户端可以知道活动轨迹交集的所有元素，这使应用程序能够在发现可能与确诊患者接触的地方显示详情。这使用户能够通过手动检查误报来排除异常情况，例如该程序显示您可能在三天前的下午遇到的确诊病人，但是您知道自己那段时间是在家中。

除了产生交集本身的RSA-PSI协议之外，还有一个PSI-基数协议的实现，它只给出交集的大小，而不是交集本身。该协议不是基于RSA，而是基于Diffie-Hellman密钥交换。