最初的半诚实模型DH-PSI协议在1999年论文：Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities中提出，更早的思想可追溯到论文1986年的论文：C. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party.

ECDH-PSI协议的思想比较简单，整个过程如图1所示。

ECDH-PSI 协议开始前，Alice 和 Bob 对自己的数据进行随机乱序，协议流程如下：、

椭圆曲线群可以选择Curve25519，Secp256k1，SM2，FourQ等安全曲线。

（2）KKRT-PSI

KKRT基于 OT Extension, BaRK-OPRF 和 CuckooHash，该协议首次实现在在千万规模数据集上求交在1分钟之内完成，2016年论文：V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. Efficient batched oblivious PRF with applications to private set intersection。

在隐语 SPU PSI 中使用了2018年论文：B. Pinkas, T. Schneider, and M. Zohner. Scalable private set intersection based on ot extension中的3-way stash-less CuckooHash.

KKRT协议流程如下：

注意：在协议中，接收方执行Cuckoo哈希时，每个桶里的元素是只由一个哈希函数确定的位置，而在发送方这边是执行了三个哈希函数，每个元素都插入到了三个对应位置的桶里。这是因为发送方并不知道接收方是采用的哪一个哈希函数。Cuckoo哈希是降低后续元素比较次数的核心方法，将原来平方次的比较次数变成了线性次数的比较。

（3）BC22-PSI

伪随机相关生成器PCG(Pseudorandom Correlation Generator)是 Boyle等人引入的一种密码协议，优势在于可以将满足特定相关条件的随机数，在不影响安全的前提下进行压缩。

他们设计了一系列满足特定相关性的高效PCG协议, 例如: vector oblivious linear evaluation (VOLE) 或者batch oblivious linear evaluation (BOLE)。这些基础的密码原语是现代安全多方计算中的核心组件，可以显著降低通信量。基于LPN假设，PCG/VOLE 函数，Receiver 和Sender得到一组满足线性关系的分量，通信量是亚线性的。

BC22的2022年论文：Private Set Intersection from Pseudorandom Correlation Generators使用PCG加速PSI协议，减少计算量和通信量，在千万数据规模，长度128比特数据集上，求交时间在30秒左右，通信量是KKRT 的1/3.

流程如图所示：

协议流程描述如下：

其中论文[WYKW21]: C. Weng, K. Yang, J. Katz, and X. Wang. Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits, 2021.

（4）RR22-PSI

该技术来自于S.Raghuraman and P. Rindal的2022年论文：Blazing Fast PSI from Improved OKVS and Subfield VOLE，Blazing Fast PSI 由两个核心组件组成：OKVS 和 VOLE。

（5）性能比较

以上四楼主流的PSI协议的性能比较如下图（通信量和执行时间）

可以看出

KKRT 算法的运行时间较短，但通信量较大。
ECDH 算法的运行时间较长，但带宽较低。
Blazing Fast PSI 位于右下角的位置，即它在时间和通信量方面都具有较大的优势，能够满足不同场景下业务的应用需求。
在特定 2^24 大小的数据集进行求交，Blazing Fast PSI 性能已经基本与明文下的性能一致。

3、非平衡PSI协议

上面介绍的是通用的PSI协议，在数据量大小不同的场景下，即非平衡PSI有更专用的PSI协议，下面主要介绍两种非平衡PSI协议。

（1）EC-OPRF-PSI

论文RA18：Faster unbalanced private set intersection介绍了一种非平衡的PSI协议，协议分成两个阶段：离线预处理阶段和在线阶段，论文中引入了一些优化方法减少离线预处理阶段的计算和通信量。不经意伪随机函数(Oblivious Pseudorandom Function OPRF)是一个两方协议,客户端和服务端通过执行协议计算伪随机函数(Pseudorandom Function PRF)的结果。RFC 草案“Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups”基于素数阶群，给出了OPRF, VOPRF, and POPRF 的构造方案。

协议图示如下：

协议流程描述如下：

（2）FHE-PSI

利用同态加密算法来构造非平衡的PSI协议有几篇重要的论文：

CLR17：Fast Private Set Intersection from Homomorphic Encryption 给出了使用全同态(Level Full Homorphic Encryption) 构造PSI的方法，并给出了优化方法。
CHLR18：Labeled PSI from Fully Homomorphic Encryption with Malicious Security 中提出在预处理阶段使用不经意随机函数(OPRF)对原始数据进行安全加强。
CMGD+21：Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication 给出了具体的参数优化方法，减少了在线阶段计算和通信量，并给出了和RA18： Faster Unbalanced Private Set Intersection的性能对比。
FHE 的Unbalanced PSI 和[RA18] 中的Unbalanced PSI 相比，优势在于不需要传输大数据集的相关数据，在执行完不经意伪随机函数(OPRF)后，通过增加一轮查询交互，即FHE的查询密文和返回，得到交集。

基于FHE的 PSI流程如下图所示：

协议流程如下：

数据预处理阶段：

alice和bob在线执行OPRF协议，alice得到数据集X的的OPRF结果 $\widehat{x}={F_k(x)}$

在线求交阶段：

alice计算 $\{\widehat{x}\}$ 部分幂指数的FHE密文，发送给bob;
bob计算得到 $\{\widehat{x}\}$ 所有需要幂指数，计算插值多项式的密文结果 $\left \| z \right \|$ ，发送给alice；
alice对插值多项式 $\left \| z \right \|$ 的密文结果解密, 如果解密为0，则 $x\in X\cap Y$ .

4、下面分享Slides

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】