完美体育官方网站隐私求交(Private Set Intersection, PSI)可能是被研究最多的具体的多方安全计算（Secure Multiparty Computation, MPC）协议。PSI本质上是一种特殊的多方安全计算协议：计算双方各自有一个集合，要求双方协作共同计算出两者集合的交集，计算过程中（除了交集部分）不泄露任何和各自集合相关的信息。

　　PSI属于一种特殊的多方安全计算，自然可以通过通用多方安全计算协议进行构造完美体育，但是效率通常不高[1]。目前效率比较好的PSI都是基于一些特殊技术。下面基于这些特殊技术对PSI进行一个分类。

　　最早的PSI协议就是建立在Diffie-Hellman密钥交换的基础上[2][3]，随后又被扩展到抵御恶意敌手攻击(malicious adversary attacks)[4][5]。另外这篇论文[6]提出一种利用RSA加密实现低通讯复杂度PSI的方法。 这类PSI的通讯复杂度较低，这是它的一大优势。缺陷主要是密钥交换相关操作计算复杂度高，因此当计算双方的集合较大时，PSI的计算效率较低。

　　这类分支是近几年提出的全新方法。它依赖于对计算方拥有的集合进行一种特殊编码,即OKVS，使得其拥有透明数据结构(oblivious data structures)。这类方法最开始使用多项式插值技术[16][17]导致计算效率偏低。后来[18]提出了PaXoS数据结构极大地提高了计算效率，直接导致了目前效率最高的OKVS-based PSI的诞生[20]。透明数据结构的概念和方法在[21]得到进一步总结。

　　这类分支是近几年提出的全新方法。他的构造依赖于VOLE。最早有[20]提出利用VOLE构造OPRF从而最终构造OPRF-PSI。

　　这类分支需要将计算方拥有的集合表示成多项式，并通过相应的多项式操作(主要是oblivious Polynomial evaluation, OPE)等价地进行集合运算[25][26][27][28][29][30][31][32]。这些方法通常较慢，但在其他方面也展现了一些优势。比如完美体育，可以在标准安全模型(standard model, 不依赖一些非标准安全假设，比如random oracle model)下论证安全性；可以提供除了求交集之外其他更丰富的计算功能(例如[31]提到的threshold PSI)；[33]提出使用全同态加密进行透明多项式估值。当计算双发集合大小差异很大时，该方法在通讯复杂度上有优势。[34]在[33]的基础上使用Paterson-Stockmeyer算法，postage stamp bases和Frobenius mapping进一步优化了计算和通讯开销。

　　这是新出现的，比较有意思的方法[35]，它的渐近线通讯度为\widetilde{\mathcal{O}}(∣Y ∣(\log \log ∣X∣)^2), 如果计算双方集合不相等时有优势。核心思路是将集合成员测试(membership test)变换成分支程序(Branching Program, BP)，并同态地执行该BP。这类方法原理上不仅仅可以计算PSI，而且可以方便计算基于PSI结果的各种运算(private computation on set intersection, PCI)。目前该方法只有理论构造和一些性能的理论估算。从这些估算结果判断，实际性能和其他的PSI方法比还有较大差距。

　　在很多应用场景下，我们并不需要完整的计算出交集或者交集的基数。这里举两个例子说明问题。第一个例子，例如在指纹识别中，计算双方分别是用户自己的指纹信息和服务器指纹数据库。用户的指纹信息包括若干个匹配点，如果指纹信息中匹配点匹配上的个数超过某个阈值认为该用户指纹匹配成功。这里用户关心的是匹配成功与否，而不是交集的内容又或是交集的大小。第二个例子完美体育，约会网站一对男女想了解彼此的兴趣爱好是否一致，如果兴趣爱好重合较多，那么双方有进一步的必要，否则彼此不应该透露兴趣爱好。这类问题现在被称之为Threshold PSI。抽象地讲，在Threshold PSI协议中，计算双方各自拥有大小为n的集合，如果交集的大小超过某个阈值(例如t)，那么协议完成时计算双方获得交集，否则获得空集。

　　Threshold PSI最近几年有一些新发展，主要工作包括：[45]在[31]的基础之上研究N方Threshold PSI，并得出它的通讯复杂度只和计算方的集合差异T有关，和集合大小无关。另外，[46]研究了N方下的一种另类Threshold PSI，即如果某个集合元素在N个计算方下的集合内出现k(kN)次则将其放入交集。这种另类Threshold PSI在[47]中被定义为quorum-PSI, 它和多方标准PSI之间有很密切的联系。

　　x\in X和元素y\in Y相等，那么这就是一次匹配且应该属于集合X\cap Y。 模糊PSI认为如何x和y的距离较近，则认为是一次匹配且应该属于集合X\cap Y。[52]首次提出模糊PSI并使用汉明距离来衡量元素和元素之间的距离，基于汉明距离的模糊PSI的核心计算部件就是阈值PSI。[53]同时给出了汉明距离和\ell_1距离下的fuzzy-PSI构造，统称为distance-aware PSI。