翻译--A PRIVACY-PRESERVING WAY TO FIND THE INTERSECTION OF TWO DATASETS 在保护隐私的前提下找两个数据集的交集--隐私数据集求交

隐私数据集交集（PSI）是一种强大的加密技术，它允许两方计算其数据的交集，而无需将其原始数据暴露给另一方。换句话说，PSI允许测试各方是否共享一个公共数据点（例如位置，ID等）。

在这篇文章中，我们介绍：

1、PSI的解释

2、PSI如何在COVID-19危机技术中发挥作用

3、技术细节：如何实现以及在实际情况下如何工作

基本概念
如果您没有密码学背景，请不要担心！我们将以一些基础知识和常见术语的介绍开始，以使您熟悉该语言。

最好将密码学描述为秘密通信的研究领域。当一方希望与另一方共享消息同时在数学上确保任何第三方都无法接收到此消息的真实含义时，它就是密码学。该第三方通常被称为对手。攻击者可以通过多种方式尝试干扰（或以密码学的方式来攻击）通信传输。如果您想了解更多信息，请在您喜欢的搜索引擎中输入术语“对抗攻击(adversary attacks)”。

为了隐藏消息的真实含义，我们需要引入另一个术语，即密码学下的一个级别：加密。当真实信息通过数学方式编码为看起来随机的事物时，某些事物将被加密，因此对于不打算读取真实信息的人完全没有意义。
例如，可以使用秘密密钥对通常可读的纯文本形式的消息进行数学加密，从而成为不可读的密文。加密的一个安全目标是，生成的密文与随机文本是无法区分的。秘密消息不一定必须是文本。它可以是仅应在双方之间共享的任何数据。当然，有许多算法和关联的工具来加密和解密消息。

在进入PSI的目的之前，我们将更深入地研究一种特定的加密形式，该形式可用于构造PSI协议：同态加密。

一般而言，同态加密是一种可以对加密消息执行计算而无需知道普通（非加密）消息的技术。这样的计算产生加密的结果，该结果在解密时与该计算将在纯文本上执行的结果相同。例如，在您是云提供商的客户并且想要对云中本地存储的数据运行某种算法，但又想确保数据（想象中的个人数据！）保持私有的情况下，这很有用。云提供商无法读取。同态加密是任何受到严格监管的行业最好的朋友，因为它可以让您计算加密数据的结果，而无需与任何（云）服务提供商共享密钥。只有拥有秘密密钥的人（即您）才能解密此类计算的输出。

请记住，同态加密只是许多可能的加密技术之一，PSI也可以与其他技术一起使用。存在多种类型，例如完全，部分和某种程度上的同态加密。区别在于可以进行的算术运算，但这超出了本概述的范围。同态加密非常适合某些用例，但是如果最适合这种情况，则必须查看特定要求，尤其是在需要可扩展至国家/地区人口规模的情况下。

密码学的另一个子领域值得一提的是安全多方计算（SMPC）。 SMPC负责保护相互通信的双方的数据。现在：击鼓，因为我们已经进入了第一部分的核心和结尾：隐私数据求交（PSI）！

PSI是一种技术，它使两个都有一组数据点的一方能够比较这些数据集，而又不放弃其各自的数据保密性。这是一种隐私保护技术，允许两方计算其数据的交集。结果是仅包含双方共同的那些元素的第三数据集。

您将在使用PSI的地方阅读最常见的设置，即服务器-客户端方案，其中只有客户端会收到在两个原始数据集之间共享的元素的相交结果数据集。当然，在实践中还存在采用PSI的其他变体：这些变体涉及以下设置：客户端仅了解路口的大小（即路口中的元素数），或者由客户端对路口进行计算。在下一段之后，我们将研究与这些设置相关的实际用例。

由于服务器-客户端方案不仅常见而且很简单，所以我们将在下图中为您提供正确的工作示例。

最后一个概念最终融合了加密方案和PSI这两个概念：两者结合在一起构成了PSI协议，该协议可以看作是特定加密任务的回执。

当您要设计一种对于用例足够安全且足够快的协议时，需要考虑许多用例设置。这些涉及数据服务器和客户端自身的大小，可能的对手攻击对于防止以及如果要使用有限的资源（例如在移动设备上。想象一下一个巨大的决策树，您需要遍历该树才能为您的个人设置找到理想的收据。我们已经遍历了这棵树，因此您不必担心以下部分针对所有用例的特定注意事项。

最后，让我们看一下以下PSI协议有用的示例用例列表。请记住PSI的主要特征：双方都希望不相互展示数据，但需要对交叉点中的元素进行查找/处理：

用例                                                  描述
私人联系人发现                      以用户（客户端）的身份查找我的私人联系人中还具有特定通信应用程序（服务器）的人

DNA测试和模式匹配                  用户对他们的DNA进行测序，并希望找到与遗传疾病相关的序列，这些序列存储在数据库（服务器）中。
远程诊断                            医疗诊断程序为矢量化患者（客户）的电子健康记录分配状态（患病或未患某种疾病）。当客户得知自己的病情时，程序本身仍然是秘密的，程序所有者（服务器）不了解客户数据。

私有记录链接                             两个数据所有者为同一个人（例如客户）持有不同类型的信息。为了使数据挖掘成为可能，必须将两个记录链接在一起并在不放弃存储的任何其他私有数据的情况下可用。

在这次新冠病毒危机中PSI的崛起
2020年是PSI技术大放异彩的一年！

如果您定期关注OpenMined，您肯定已经看过许多有关隐私保护技术及其在开发Covid-19应用程序以安全地实现数字联系人跟踪方面所做的工作的帖子。

在我们的合作中，apheris AI和OpenMined共同为实现联系人跟踪以通知COVID-19患者的潜在联系人的任何应用开发PSI代码。

我们将共同开发针对专用集合路口的核心技术和开放源代码库，以便在多种情况下在许多设备上运行，这将使任何Covid-19跟踪应用程序都能在用户电话内外保护隐私。

您可以从3月31日发布的白皮书中获取有关Covid-19应用程序重要性的更多详细信息。它的执行摘要：对疾病传播的流行病学模型表明，高精度的自我隔离是制止这种大流行并从而最大程度地减少其经济损失的最佳方法。在此处阅读更多信息：https://www.covid-app.io/

目前有很多Covid-19应用正在开发和发布。它们具有不同的功能，但总的来说，它们的核心工作流程是相似的。可以这样描述：每个用户都在他们的手机上收集跟踪数据。如果当地卫生部门诊断出用户感染冠状病毒，则该用户可以（但通常不必！）共享其数据并将其传输到服务器。现在，该应用程序的任何其他用户都可以通过向服务器询问更新的数据来了解他们是否可能与正测试的用户联系。

此工作流包含两个隐私问题，在共享和比较数据时需要考虑这些问题：诊断的患者隐私和用户的跟踪数据。

在用户方面，PSI允许用户检查他们收集的跟踪数据是否与诊断出的患者的踪迹相匹配，而不会向服务器泄露其私人跟踪数据。然后，根据PSI协议的类型，客户端将仅了解匹配迹线本身或匹配迹线的计数。

在被诊断的患者方面，与服务器共享数据的患者的情况需要另一种协议。但是它也要求一种快速，安全和匿名的协议，并且不能泄露其个人信息。

仅当有足够数量的人群采用Covid-19应用程序时，该应用程序才会成功。决定应用程序采用率的因素很多，包括文化，平台可用性和电信基础设施的发展。但是，可以肯定地推动采用的一件事是隐私和信任。 PSI是向大规模采用迈出的一大步。

PSI范例

最后，我们要深入了解这个冰山一角，现在我们将讨论PSI的各个实现。

OpenMined的COVID警报应用程序证明了一种实现此方法的方法，该应用程序实现了部分同态加密方案，即Paillier密码系统，其中客户端的加密值与服务器上的未加密值相乘，从而得到仅客户端的加密结果。可以解密。这种方法凸显了同态加密的优点，尽管对于一般的PSI而言，其他加密方案也非常可行，并且如果要访问大型数据集（如国家或大洲的人口），则在可伸缩性方面具有优势。

现在，我们将详细介绍在我们的库中实现的RSA-PSI协议，并将重点关注该协议的Python版本。您可以在这里找到我们的开源python实现，但这里也有一个JavaScript版本。我们所有的库都应该是可互操作的，这意味着您可以在客户端使用JavaScript的同时使用Python实现服务器。

RSA-PSI协议分为三个主要阶段，即基础阶段，设置阶段和在线阶段。我们将描述它们中的每一个，并使用我们的库给出一个实现示例。我们将假设客户端拥有一组整数Y，服务器拥有一组整数X。如果您的用例涉及其他类型的元素，则只需将您的元素编码为整数即可。

基础
该基础包括服务器，该服务器生成RSA私钥并与客户端共享公钥。客户端将为其集合Y中的每个元素生成一个随机数，并存储其加密和模块化逆运算。客户端可以异步运行此操作。

# Note that the package is not yet available to install via pip
# but you can always install it from source
from psi.protocol import rsa

# server will run this and share the public-key with the client
server = rsa.Server(key_size=2048, e=0x10001)
public_key = server.pulic_key

# client will use the public_key
client = rsa.Client(public_key)
random_factors = client.random_factors(len(Y))
设置
在此阶段，服务器将使用私钥对集合中的元素进行签名，然后将其插入到Bloom过滤器中，与客户共享。
signed_server_set = [server.sign(x) for x in X]
# must encode integers to bytes
signed_server_set = [str(sss).encode() for sss in signed_server_set]
bf = bloom_filter.build_from(signed_server_set)

线上
客户端在这里使用他在设置阶段生成的随机数的加密来遮蔽集合中的元素，将其发送到服务器，服务器将对其签名并发送回客户端。然后，客户端进行盲法的逆运算，以最终获得其每个元素的签名。然后，客户端将检查Bloom筛选器中每个签名的存在，如果签名匹配，则将关联元素放入相交处。

# client run this and send A to the server
A = client.blind_set(Y, random_factors)

# server run this and send B back to the client
B = server.sign_set(A)

# client do the intersection
unblinded_client_set = [client.unblind(b, rf) for b, rf in zip(B, random_factors)]
# must encode integers to bytes
unblinded_client_set = [str(ucs).encode() for ucs in unblinded_client_set]

intersection = []
for y, u in zip(Y, unblinded_client_set):
    if u in bf:
        intersection.append(y)

print(“intersection is {}”.format(intersection))

瞧！客户现在持有交叉路口！值得注意的是，服务器未学习RSA-PSI协议中的交集。客户端学习交叉路口的所有元素，这使该应用程序可以在发现可能与受感染用户联系的地方显示详细信息。这使用户能够通过排除不可能发生的相遇来手动检查误报，例如，该应用程序显示您三天前下午可能遇到了被感染的人，但是您知道自己当时只能在家时间。

除了产生交点本身的RSA-PSI之外，我们在这里还有PSI基数协议的实现，该协议仅给出交点的大小，即交点中元素的数量，而不是交点本身。该协议不是基于RSA，而是基于Diffie-Hellman密钥交换。
摘要
为了理解PSI，我们从密码学的基本概念和术语入手。密码学的一个分支是加密，它是将消息转换为不可读密文的数学运算。同态加密是一种特殊的加密形式，它允许对密文进行计算而无需知道各自的明文。 SMPC是密码学的另一个分支，它包含所有技术，包括PSI，在这种技术中，两方共同计算结果，但将输入数据保密。

这些基本概念有助于详细了解PSI作为一项技术的工作原理。使用COVID-19联系人跟踪应用程序的用例来说明apheris AI和OpenMined我们如何使用PSI协议来启用联系人跟踪，同时保护每个人的隐私。

PSI允许应用程序用户将他们的联系方式与存储在服务器上的COVID-19患者的联系方式进行比较，而不会放弃他们的隐私。在进行这些解释之后，将逐步介绍我们的RSA-PSI协议实现。您可以在此处找到适用于Python和Javascript的开源实现。对于我们的PSI基数协议，这是一个实现，所有主要语言的包装器都将遵循该实现。

如果您坚持到最后：很酷，希望您喜欢它。反馈，想法和想法在这里：info@apheris.com。有关任何保护隐私的技术问题或其他疑问，请与我们联系。
本文翻译自openmined官方博客，链接：https://blog.openmined.org/private-set-intersection/

作者：

Sabrina Steinert

Data Scientist and Business Manager at apheris AI

Ayoub Benaissa

Crypto Team Member. Master Student working on homomorphic encryption and deep learning.

Robin Roehm

CEO & Co-Founder of apheris AI

Michael Hoeh

CTO & Co-Founder of apheris AI

一些补充说明:

1.什么是Private Set intersection（PSI）？
用英文定义是：A private set intersection protocol consists of two parties,a Sender and a Receiver, each having a set as input, which respectively are denoted X and Y . Together they want to compute the intersection of their sets,X ∩ Y , without revealing elements not contained in the intersection. Usually the Receiver will learnX ∩ Y and |X| without learning X \ Y , while the Sender learns|Y | and nothing else.

简单中文来说就是两个数据集求他们的交集的协议，但是却不泄露任何一方除了交集之外的信息！

有什么用呢？总之就是为了找相同敏感的元素。比如可以让两个公司找出他们共同的客户而不必要泄露所有的用户给对方。政府特工判断恐怖分子是否在航空名单上。

2.有哪些PSI协议呢？
到现在为止，PSI协议种类很多，但是主要还是分为以下几个部分：

（1）基于天真的哈希解决方案的PSI：这种方案主要是应用加密的哈希函数，然后计算哈希结果。缺点是安全性很差。

（2）基于公钥加密的PSI：有基于Diffie-Hellmann(DH)的，有基于RSA盲签名的，有基于bloom filter的，基于OPRF的，基于多项式插值的。

（3）基于电路的PSI：这个主要分为两个小部分，一个是基于GoldreichMicali-Wigderson protocol 计算协议，另外一个是基于姚期智教授的混淆电路计算协议。

（4）基于遗忘传输的PSI。这也现在比较流行的PSI协议，并且有文献优化算法成为了如今最快的PSI协议。最新的基于OT的PSI协议B.Pinkas, T.Schneider, M. Zohner.Scalable Private Set Intersection Based on OT

Extension.Availableat http://eprint.iacr.org/2016/930.并且作者给出了源码，笔者在ubuntu上跑，效果可以。源码链接：https://github.com/encryptogroup/PSI

如表8是各种协议的运算时间比较，在上面这篇论文中可以找到。

3.资料分享
主要是上面这篇论文，总结很全面的PSI协议，并且还给出了详细的引用。还有一篇国外AARHUS
AU UNIVERSITY 的硕士论文：Breaking and Fixing Private Set Intersection Protocols。

————————————————
版权声明：本文为CSDN博主「我的暑假作业没写完」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yinhui_zhang/article/details/75091321