隐私计算研习社

1

前言

在传统的数据共享和数据分析中，往往需要多个参与方共享他们的数据集以进行计算或分析。例如在社交网络中，两个用户希望找到他们之间的共同好友，而不想分享他们完整的好友列表。再比如市场调研中，两个公司希望比较他们的客户数据库中的共同客户，以了解他们之间的重叠。

然而，由于隐私和安全的考虑，参与方通常不希望直接将他们的数据集共享给其他方。因此，隐私求交（Private Set Intersection, PSI）应运而生，PSI可以用于在两个或多个数据集之间查找共同的元素，而不需要泄露数据集的详细信息。

目前，隐私求交被广泛应用于隐私保护场景下的数据共享和数据分析任务。为了增强隐私保护，隐私求交协议通常会使用加密技术和安全多方计算协议。这些技术确保了数据在传输和处理过程中的保密性和安全性，以防止未经授权的访问和信息泄露。

2023年5月21日，来自华东师范大学的在读博士研究生杨赟博详细介绍了隐私求交的关键路径及其应用。

2

PSI简介

本次课程将从以下几个方面进行讲解，如果本次课程无特殊说明均为半诚实模型，在半诚实模型下，参与方诚实地执行协议，但是想要去获得其他参与方的隐私数据。

在隐私求交协议中，有两个参与方，Bob和Alice，他们想要在不透露自己集合元素的情况下，求出交集信息，交集外的数据不能被另外一方获得。

PSI主要可以分为三个技术路径实现，分别为混淆电路，基于不经意传输构造的不经意的伪随机函数和全同态加密。

3

基于混淆电路的构造

首先，先介绍一下布隆过滤器，布隆过滤器可以将一系列的数据编码为一个比特向量，随后判断特定元素是否在布隆过滤器中。在初始化阶段，参与方选择两个哈希函数(映射函数)，并将相应的数据随机映射到随机的位置中。

预处理阶段时，生成一个长度为m的全0向量，即其中每个元素都是0，在插入阶段，首先计算x的两个哈希值，并对相应得到的结果置为1。比如将元素x哈希至如下两个位置，并在对应位置置为1。

随后我们介绍查询阶段，在查询阶段中，首先对元素进行哈希，然后取出相应位置的元素，如果所有位置均为1，那么该元素会以很大概率存在于布隆过滤器中，当任一位置为0时，那么说明该元素肯定不在布隆过滤器中。

接下来我们介绍一种基于混淆电路和布隆过滤器构造的隐私求交协议。首先双方各自根据自己的集合元素，生成相同长度的布隆过滤器。

随后两个参与方调用AND电路，计算仅含有交集的布隆过滤器，随后获得结果的参与方利用自己的集合元素，在结果中进行查询，输出交集。在协议执行过程中，双方构造的布隆过滤器都可以得到充分的保护。

4

基于全同态加密的构造

接下来，我们来讲一下基于全同态加密构造的隐私求交协议，首先各参与方先将各自的集合元素编码为一个多项式，每个元素都是这个多项式的一个根。

我们可以发现当x在交集时，那么x是两个多项式和的根，如果x不在交集时，那么x就不是两个多项式和的根。我们接下来可以使用同态加密，对其中一个参与方的系数进行加密，并将加密后的系数发送给另外一个参与方，计算加法。

得到加和多项式的一方，利用自己本地的数据代入，并判断是否是0的密文，如果是，则说明对应元素在交集中。当然该方案只是个框架，并不安全，协议执行过程中需要同步考虑使用掩码掩盖系数，以确保安全性。

4

各方案优缺点的比较

接下来我们比较一下这些技术路径，可以发现不经意的伪随机函数在通信复杂度和计算复杂度中达到了一个很好的平衡，并广泛用于隐私求交的构造中，接下来，我们重点基于不经意的伪随机函数构造的隐私求交协议。

下一节将整理基于不经意的伪随机函数构造的两方隐私求交协议。