隐私保护集合求交（PSI）是一种加密技术，它允许双方在不透露任何东西的情况下计算他们的集的交集，除了交集。我们使用完全同态加密来构建一个快速的PSI协议，其通信开销很小，当两个集合中的一个比另一个小得多时，该协议特别好用，并且对半诚实的对手是安全的。
计算效率最高的PSI协议是使用哈希函数和遗忘转移等工具构建的，但这些方法的一个潜在限制是通信复杂度，它与较大集合的大小呈线性扩展。当在一个持有小集合的受限设备（手机）和一个大型服务提供商（如WhatsApp）之间执行PSI时，这是一个特别值得关注的问题，例如在私人联系人发现应用中。
我们的协议的通信复杂度与小集合的大小成线性关系，而与大集合成对数关系。更确切地说，如果集合的大小是 $N_y < N_x$，我们实现的通信开销是 $O(N_y \log N_x)$。我们的运行时间优化基准显示，将5000个32位字符串与1600万个32位字符串相交，需要36秒的在线计算，71秒的非交互式（独立于接收器）预处理，以及仅12.5MB的往返通信。与之前的工作相比，这大约减少了38-115倍的通信量，而计算开销的差别很小。
隐私保护集合求交（PSI）指的是这样一种情况：双方各自持有一个私有项目集，并希望在不透露任何信息的情况下学习他们的集合的交集，除了交集本身。在过去的几年里，由于一长串的出版物，例如[9, 18, 37, 39, 46, 48-50, 53]，PSI已经成为真正实用于各种应用。最有效的协议是由Pinkas等人[50]和Kolesnikov等人[37]提出。虽然这些协议非常快，但它们的通信复杂度在两个集合的大小上是线性的。当一个集合明显小于另一个集合时，与非私有解决方案相比，通信开销变得相当大，后者的通信量与较小集合的大小呈线性关系。
全同态加密是一个强大的加密原语，它允许算术电路直接在加密的数据上进行评估，而不是先解密数据。尽管其基本思想很古老[54]，但在2009年才由Craig Gentry[25]给出第一个构造。虽然早期的全同态加密方案是不切实际的，但在短短几年内，研究人员设法构建了更有效的方案（例如[8, 12, 13, 21, 28, 41]），使实际应用接近于现实[26, 29, 45]。
乍一看，使用完全同态加密来实现PSI中的低通信成本似乎很容易。拥有较小集合的一方将其加密的集合发送给另一方，后者以同态方式评估交集电路，并将加密的结果发回给第一方进行解密。总的通信量只有
$$ 2 × \text {ciphertext expansion} × \text {size of the smaller set.} $$
然而，对上述想法的天真实施将导致一个非常低效的解决方案。原因是，对于所有已知的完全同态加密方案，计算成本不仅随着输入的大小（在这种情况下，两个集合大小的总和）而增长，而且还随着电路的深度而迅速增长。 因此，我们的主要挑战是提出各种优化方案，使该方案切实可行，甚至在许多情况下比最先进的协议更快。简而言之，我们将表明有可能构建一个快速的基于全同态加密的PSI协议，而且通信开销很低。
Meadows[44]提出了最早的安全PSI协议之一，后来Huberman、Franklin和Hogg在[34]中对其进行了全面描述。这种方法是基于公钥密码学，并利用了Diffie-Hellman密钥交换的乘法同构特性。虽然这些方案具有相对较好的通信成本，但由于需要对两个集合中的每一项进行多次的模块化指数化，当集合大小变得很大时，运行时间可能会很漫长。
自[34]以来，人们考虑了其他一些范式。Freedman等人[23]提出了一个基于遗忘多项式评估的协议。这种方法利用了部分同态加密，后来在[15, 31, 32]中被扩展到恶意设置。另一种方法是由Hazay等人[30]提出的，并基于所谓的遗忘式PRF。
最近，人们发明了基于不经意传输（OT）的更有前途的方法[35, 46]。当时，到目前为止，最有效的方案是由Pinkas等人提出的[49]，后来在[37, 46, 50]中得到改进。我们将用发送方和接收方来表示参与PSI协议的两方，并坚持认为在协议执行后，接收方会了解到集合的交集，而发送方则不会了解到任何信息。基于OT的协议的高层次想法是，接收方与发送方进行许多OT，并为其集合中的每个项目忘我地学习随机编码，而不透露哪些值被编码。然后，发送方可以对其项目进行本地编码，并将其发送给接收方，接收方在编码上计算出明文交集。由于编码是随机的，它们不会透露任何超出交集的信息。这种方法的一个固有属性是，由于需要对所有的编码进行编码和发送，通信在两个集合的大小上都是线性的。我们采取的方法是类似的，只是我们使用完全同态加密来代替遗忘传输。
然而，另一种基于OT的方法是由Dong等人引入的[18]，它建立在一个被称为布鲁姆过滤器的数据结构上。这种数据结构允许通过在一个长的位阵列中设置特定的位来进行有效的成员测试。重要的是，两个布隆过滤器的位和本身就是两个原始集合的交集的有效布隆过滤器。通过对这一想法进行一些修改，就可以构建一个安全的协议，允许其中一方通过使用OT来学习两个布隆过滤器的位-明智和。这种方法比Pinkas等人[49]介绍的方法需要更大的通信量，并且导致性能下降。
通常引用的PSI的解决方案是使用通用的安全多方计算协议来计算交集。Huang等人[33]是第一个使用乱码电路实现这种协议的人，后来[49]对此进行了改进，并提供了一个实现。他们表明，与基于OT的方法相比，乱码电路方法需要明显更多的通信。对于实际方法的更完整的调查，我们提请读者参考[50]。
Kamara等人也提出了一个非常有效的服务器辅助协议[36]。在这种情况下，假设存在一个非拥挤的服务器。其基本思想是，在双方之间取样一个随机函数，将其应用于各自集合中的元素。然后，这些编码被发送到服务器，由其报告相交情况。虽然在概念上很简单，而且非常有效，但对这种服务器的依赖是不可取的。此外，通信的复杂性在两个集合的大小上是线性的。
在上述所有协议中，都假定在协议开始时，集合的大小（或上界）是公开的。Ateniese等人[6]介绍了一个基于RSA累加器的协议[7]，它通过隐藏接收者的集合大小来放松这一假设。这个协议的工作原理是让接收方为其集合构建并发送一个RSA累加器。然后，发送方可以为其每个项目构建一个响应，这使得接收方可以测试它们是否包含在RSA累加器中。RSA累加器的一个重要属性是它的大小很小，而且与接收方的集合大小无关。因此，当接收方有一个比发送方大得多的集合时，这个协议是最有趣的。在后续工作中，Bradley等人[10]将该协议扩展到对累加器中的项目数量施加一个上限，从而防止接收方的所谓 "全域攻击"。