基于加性秘密分享的可扩展的多方阈值秘密集合交集方法

《Journal of Information Security and Applications》：Scalable multiparty threshold private set intersection based on additive secret sharing

　　**摘要**

多方私有集合交集（MTPSI）是一种特殊的安全多方计算形式，其中每个参与者都拥有一个集合，并在集合的交集基数大于某个阈值时计算该交集。如果交集基数小于阈值，则参与者不会获得任何关于交集的信息。尽管TPSI协议在现实世界中有许多应用，例如在线拼车、联系人发现、机器学习等，但目前的大多数研究都集中在两方设置上，对多方设置关注较少。此外，现有的TPSI协议存在计算开销高、交集基数泄露、在大型集合（例如2^20）上运行效率低下以及无法扩展到更多参与者（例如15方）等问题。为了解决这些问题，本文提出了一种基于多点无知 Prisoner-Point Function (PRF)、无知键值存储（OKVS）、Cuckoo哈希和加法秘密共享的多方私有成员测试（MPMT）协议。然后，我们使用向量无知匹配测试（VOMT）和MPMT协议实现了该协议，其运行时间优于之前的工作，并在半诚实模型下证明了其安全性。我们用C++实现了该协议，并在不同的集合大小和参与者数量设置下对其进行了评估。实验结果表明，当集合大小为2^11且参与者有2方时（阈值t=0.5×2^11），我们的协议运行时间为0.766秒，而之前的最新TPSI协议则需要700秒。另外，在集合大小为2^20且参与者有15方的设置下，我们的协议运行时间为268.788秒。我们的MTPSI协议是一个实用的解决方案，能够在具有大型数据集和多个参与者的场景中高效运行。

**引言**

私有集合交集（PSI）是多方计算（MPC）的一种特殊情况，它允许参与者联合计算他们集合的交集，而无需泄露超出交集的信息。在过去十年中，PSI得到了广泛研究并取得了很大进展[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]，随着2018年5月欧盟引入的通用数据保护条例（GDPR），PSI获得了更多的关注。它在许多场景中都非常高效，并在现实中得到了广泛应用，例如联系人发现、测量广告转化率和人类基因组研究。然而，标准的PSI在某些特殊情况下并不适用。例如，在保护隐私的数据挖掘和机器学习中，当数据在多个参与者之间垂直分割时，只有当他们的数据集交集足够大时，参与者才有合作的动机[12]。如果他们的集合交集太小，那么交集对他们来说可能没有意义。同样，在一个保护隐私的拼车应用[13]中，乘客只有在大多数行程相同时才会选择共用一辆车。因此，Freedman等人[14]提出了阈值私有集合交集（TPSI）的概念。在这里，两个不信任的参与者分别拥有集合X和Y，并希望在|X∩Y|达到阈值t时了解交集。特别是，当|X∩Y|小于阈值t时，任何一方都不应知道X∩Y的大小。当|X∩Y|大于阈值t时，拥有X的参与者（接收者）不应知道关于Y的任何信息，除了X∩Y之外。同样，拥有Y的参与者（发送者）也不应知道关于X的任何信息。

在多方阈值私有集合交集（MTPSI）协议中，N个参与者拥有集合X1,…,XN。只有当交集基数|X1∩XN|大于阈值t时，每个参与者才能获得交集I=∩i=1NXi；否则，每个参与者都无法获得关于交集I的任何信息。

**挑战**

TPSI问题的难点在于在交集基数小于阈值时进行交集基数测试，同时确保不泄露任何关于交集的信息。现有的TPSI解决方案使用了诸如通用安全计算、同态加密和鲁棒秘密共享等算法，因此计算开销很大。例如，当直接使用通用安全计算框架实现TPSI协议时，协议的计算复杂性为O(n^2)。如果输入集合是排序的，协议的计算复杂性可以降低到O(nlogn)。然而，对于排序的输入，这可能会泄露来自其他参与者的信息（即输出是有序的）。如果我们直接使用通用安全计算框架来实现MTPSI协议，协议的计算复杂性会更大（即O(N^n^2)）。当协议使用鲁棒秘密共享进行交集基数测试时，插值多项式的次数与集合的大小成正比。因此，当集合大小很大（例如2^18）时，协议的计算开销也非常大。

**两方设置**

这是我们在现有方案中能找到的唯一实现设置。然而，这种解决方案仅适用于小型输入集合，目前尚不清楚它们的方法是否可以扩展以处理更大的输入，例如2^18。

**多方设置**

之前的研究都是理论性的，我们不知道有任何具有实际实现的方案。这些工作使用了加法/完全同态加密或依赖于需要大量多项式插值的算法。因此，这些方案的实现是一个重大挑战。我们将在第1.3节详细描述这些工作。

**我们的目标**

我们的目标是设计一种可扩展且实用的多方阈值私有集合交集协议，避免使用计算成本高昂的算法，如同态加密和多项式插值。为了实现这一目标，我们设计了一种新的MTPSI协议，具体贡献如下：
- 我们提出了一种新的MTPSI协议构造，将加法秘密共享与无知键值存储（OKVS）相结合。在OKVS方案中，加法秘密共享的共享值被用作键值对的值。在重构阶段，如果秘密能够成功重构，则相应的键属于交集。
- 我们提出了一种避免使用计算成本高昂的算法（如同态加密和鲁棒秘密共享）的MTPSI协议。我们的协议仅需要对称密钥技术和计算复杂性为O(n)的两方安全计算。
- 我们设计了一种具有良好可扩展性的MTPSI协议，从3方扩展到10方只需要少量的额外开销。
- 我们的MTPSI协议可以在15方和2^20大小的数据集设置中高效运行。我们的协议在运行时间方面优于之前的工作。

本文的结构如下：第1节描述了技术概述和相关工作。第2节介绍了基础知识。第3节详细介绍了我们的新MPSI协议，第4节证明了协议的正确性和安全性。第5节我们展示了协议的计算复杂性和运行时间，并将其与现有最佳方案进行了比较。最后，我们在第6节总结了本文。

我们遵循了之前工作[8],[13],[14],[15],[16],[17],[18],[19]中使用的设计思想。我们设计的初衷是用计算复杂度较低的通用安全计算替换计算成本高昂的算法（如多项式插值、同态加密等），从而提高协议的效率。然而，如果直接使用通用安全计算来解决TPSI问题，开销也会非常大。如上所述，直接使用通用安全计算实现TPSI协议的计算复杂性为O(n^2)。在这项工作中，我们在ABY[20]中实现了TPSI功能，并展示了不同集合大小的运行时间，作为与之前工作的比较热身。我们的实验表明，ABY协议对于小型输入表现良好，但对于大型输入的扩展性不佳，如表1所示。

为了解决这个问题，我们构建了一种新的MPMT（多方私有成员测试）协议。我们在第2.3节定义了MPMT协议的理想功能。通过MPMT协议构建MTPSI协议的方法如图1所示。首先，我们描述了在两方设置中的协议构造，然后展示了如何将两方设置扩展到多方设置。为了说明这一点，我们使用了一个具体的例子来解释我们的协议设计，如图2和图3所示。

**两方设置**

我们假设接收者拥有集合Y={y1,…,y7}，发送者拥有集合X，其中x*∈X。接收者通过3个哈希函数将集合Y插入Cuckoo哈希表中。Cuckoo哈希表有10个桶。发送者使用相同的哈希函数将集合X插入简单哈希表中。我们的协议工作原理如下：
- 接收者使用Cuckoo哈希将Y分配到10个桶中，并用虚拟元素u填充空位置。我们用CTY表示Cuckoo哈希表。然后接收者将每个元素与其映射到桶的哈希函数索引连接起来，即h2(y4)=1且YC[1]=y4∥2。
- 发送者以相同的方式将集合X插入简单哈希表，并用u将每个桶填充到最大值bmax。
- 接收者将Cuckoo哈希表CTY作为输入传递给FOPRF，然后接收者收到F(·,…)的密钥k，并且接收者学习{F(k,CTY[1]),…,F(k,CTY[10])}。
- 发送者选择10个秘密，秘密值的数量等于Cuckoo哈希表的长度。
- 发送者将每个桶中的元素与其对应的秘密组成键值对，例如((F(k,STX[1][1]),r1),…,(F(k,STX[1][bmax]),r1))。如图2所示，如果集合Y中的元素等于x*，那么该元素必须映射到CTY[2], CTY[5], 和 CTY[8]。因此，发送者为每个桶中的元素和秘密组成键值对。然后发送者将键值对集编码成数据结构D并发送给接收者。

**D=[?row(F(k,STX[1][1]))???row(F(k,STX[1][bmax]))???row(F(k,STX[10][1]))???row(F(k,STX[10][bmax]))?]?1×[r1?r1?r10?r10]**
- 通过这种方式，接收者在解码集合元素时可以获得正确的秘密。
- 接收者使用伪随机值解码OKVS数据结构D，例如{Decode(D,F(k,CTY[1]),…,Decode(D,F(k,CTY[10]))}={r′1,…,r′10}。
- 最后，接收者和发送者分别使用解码后的值{r1′,…,r10′}和秘密{r1,…,r10}调用FVOMT。在FVOMT中，它们只需要按顺序逐一比较（即计算复杂性为O(n)）。如果{r1′,…,r10′}和{r1,…,r10}之间的交集大于t，则意味着集合交集大于阈值t。如果交集大于阈值t，接收者得到交集I，否则得到⊥。

通过上述过程，我们可以构建一个两方TPSI协议。在这里，我们使用OKVS和Cuckoo哈希将两方安全计算的计算复杂性从O(n^2)降低到O(n)，并使用OPRF方案防止接收者了解有关随机秘密的更多信息。

**扩展到多方**

我们展示了如何将我们的构造从两方设置扩展到多方设置。我们还用一个具体的例子来说明我们的设计，如图3所示。有n个参与者P1,…,PN，每个参与者都拥有集合X1,…,XN。P1使用Cuckoo哈希将集合X插入表CTX1中，而P2,…,PN将集合插入简单哈希表中，我们将其表示为STX2,…,STXN。插入方法与两方设置相同。后续过程如下：
- P1将CTX1作为输入传递给FOPRF并学习{F(k,CTX1[1]),…,F(k,CTX1[b])}。然后P2获得F(·,…)的密钥k。
- P2随机抽取一组秘密{r1,…,r10}，然后执行FASS将每个秘密分成N?1个秘密共享{r12,…,r102},…,{r1N,…,r10N}，满足r1=⊕i=2^n。
- P2,…,PN使用简单哈希表中的每个元素及其对应的秘密共享组成一组键值对。然后，他们使用OKVS方案对这些集合进行编码，并将编码后的数据结构D2,…,DN发送给P1。如果P1在P2,…,PN中有交集元素，P1可以通过解码获得正确的秘密共享。
- 接收D,{F(k,CTX1[1]),…,F(k,CTX1[b])}来解码D2,…,DN，分别得到{d12,…,d102}, …,{d1N,…,d10N}。然后，P1执行FASS的秘密重构阶段并重构秘密{r′1,…,r′10}（即r′1=⊕i=2^n）。如果CTX1[1]中的元素属于交集，则r′1=r1。(5)最后，P1和P2分别输入{r1′,…,r10′}和{r1,…,r10}来执行FVOMT。如果秘密之间的交集大于阈值t，则P1获得交集I，否则获得⊥。FASS的属性保证只有当元素属于交集时，P1才能正确重建秘密。此外，在P1看来，重构的秘密是随机的（即，不知道哪个秘密值是正确的）。通过这种方式，FVOMT可以保护交集的基数并实现MTPSI的功能。当扩展到更多方时，只需要增加FASS分发份额的数量和生成的OKVS数据结构的数量，因此该协议具有良好的可扩展性。然而，本文在多方设置中仍存在一些限制。具体来说，本文无法防止P1和P2之间的勾结，其原因将在4.2节中描述。Freedman等人[14]提出了TPSI协议，它是标准PSI协议的一个变体。在这里，当交集大小达到阈值时，各方可以获得交集，否则什么也得不到。然后他们设计了一个基于平衡哈希和同态加密的隐私保护协议，可以计算交集大小。Zhao和Chow[21]提出了一种基于秘密共享和半同态加密技术的阈值秘密传输方案，可以实现两方TPSI协议。该协议计算211个大小、128位长度的集合交集需要769.7秒。但此协议会泄露交集的基数。Ghosh和Nilges[17]提出了一种评估随机线性函数的工具，并基于鲁棒秘密共享（RSS）和代数技术构建了两方TPSI协议。然而，代数技术需要大量的插值操作，导致协议的通信开销较大。此外，RSS解码（即Reed-Solomon码）的计算复杂度为O(n3)。因此，该协议无法在大型集合上运行。Hallgren等人[13]设计了一种基于出行轨迹的两方TPSI协议，并将其应用于具有隐私保护的拼车应用。这使得乘客可以在不泄露行程隐私的情况下进行拼车。但该协议的计算复杂度为O(n3)，通信复杂度为O(n2)，并在212大小的数据集上运行需要5267秒。Zhao和Chow等人[16]基于加法同态加密和不相关多项式构建了两种两方TPSI协议。一种是在交集基数大于阈值时输出交集，另一种是在交集基数小于阈值时输出交集。他们的实验提到，计算大小为100的小集合的交集需要222.306秒。Pinkas等人[15]基于二维Cuckoo哈希的变体设计了一种电路PSI协议，将使用的门的数量从O(nlogn)减少到ω(n)。他们的PSI-CAT电路协议可以扩展以实现两方TPSI协议。Satrejit Ghosh等人[22]研究了TPSI的通信复杂度，并指出通信的下限至少为O(t)，其中t是集合差。他们设计了一种基于加法同态加密的TPSI协议，将协议的通信复杂度降低到O(t2)。然而，当集合差t较大时，协议的通信复杂度将变得非常大，O(t2)≈O(n2)。Badrinarayanan等人[23]扩展了[22]并设计了基于完全同态加密的两方TPSI协议。但目前尚不清楚该协议是否能够实现。Chandran和Dasgupta等人[24]设计了一种多方PSI协议，并将其扩展到多方电路PSI。理论上它可以实现MTPSI的功能，但在实现MTPSI时需要调用多方通用安全计算。目前，我们还没有找到该协议的确切运行时间和协议代码，因此无法得到该方案的确切效率。Pedro Branco等人[25]设计了一种安全基数测试协议，并构建了一种多方TSPI协议。该协议的通信复杂度为O(Nt2)，其中t是阈值。与[22]中的方案类似，当阈值t较大（例如t=O(n)）时，该协议的通信开销较大，O(Nt2)=O(Nn2)。Rindal和Schoppmann[8]设计了一种基于Vole的遗忘PRF（OPRF）协议，并构建了一种电路PSI协议，可用于解决TPSI问题，但它无法扩展到多方。Raghuraman和Rindal[6]设计了一种新的遗忘键值存储（OKVS）方案，并将其应用于[8]中的电路PSI协议，进一步提高了协议的通信和计算开销。该协议可以用来实现TPSI协议，但仍然无法扩展到多方。Liu等人[26]首次提出了概率阈值私有集合交集（pTPSI）协议的概念。每个方获得交集的概率根据交集基数的大小而变化。他们基于Goldwasser-Sipser证明系统设计了一种多方概率交集基数测试协议，然后基于此协议设计了一种概率多方阈值私有集合交集（pMTPSI）协议。该协议可以绕过标准MTPSI协议的通信下限，并大大降低MTPSI协议的开销。

### 协议片段
#### 安全模型
我们在半诚实模型下证明协议的安全性。在这个模型中，腐败方严格遵循协议规范。然而，他们可能试图了解其他方的更多输入信息。有关定义和模型的信息，请参考[27]。

#### N方协议π计算一个函数f，该函数将一组输入映射到一组输出，其中f=(f1,…,fn)。f:{0,1}1*×···×{0,1}n*→{0,1}1*×···×{0,1}n*。对于每一组输入{x1,…,xn}∈{0,1}*，输出是一个随机变量(f1(xˉ),…,fn(xˉ))，其中xˉ

#### 主要构造
我们在半诚实模型下实现图4中的功能，并展示我们协议的主要构造。

#### 安全性证明
假设P2没有与P1勾结，图9中的协议实现了FMTPSI功能，并且可以在混合模型中抵御任意数量的半诚实对手。

#### 复杂性分析
给定统计安全参数和计算安全参数分别为λ和κ。根据[30]的分析，在Cuckoo哈希方案中，我们设置b=ε·n个桶，k个哈希函数，以及s=0。哈希阶段的计算复杂度为O(Nkn)，与哈希函数的数量和参与方的数量有关。OKVS编码和解码算法阶段的计算复杂度分别为O(N(εn+λ))和O(εn)。

#### 结论
在本文中，我们实现了一种多方阈值私有集合交集协议。根据实验数据，我们的协议在多方和大型数据集的设置中是高效的。此外，如图5所示，我们协议的大部分开销在FVOMT阶段。如果有一种更高效的安全阈值测试方法，该协议的效率将进一步提高。

#### 我们的未来工作将集中在抵抗恶意对手方面。

#### 作者贡献声明
En Zhang：写作 – 审稿和编辑、验证、方法论、概念化。Zhengkun Jia：写作 – 原始草案、可视化。Yuchen Huang：调查。

#### 利益冲突声明
作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。

En Zhang于2013年从北京工业大学获得博士学位。2014年至2016年，他在中国科学院信息工程研究所担任博士后研究员。他目前是河南师范大学的教授。他的研究兴趣包括密码学和信息安全。

En Zhang | Zhengkun Jia | Yuchen Huang
河南师范大学计算机与信息工程学院，新乡，453007，中国