高性能两方隐私集合求交技术研究及应用探索*

雷术梅，张舒黎，彭夕茈，付 俊，谷 欣，洪 运

（1.中电科网络安全科技股份有限公司，四川 成都 610041；2.可信云计算与大数据四川省重点实验室，四川 成都 610041；3.中国星网网络创新研究院有限公司，北京 100029）

0 引言

随着信息技术的迅猛发展，个人隐私信息在互联网、社交媒体、电子商务等领域的泄露事件频频发生，在众多安全威胁中，数据泄露已成为全球范围高发的安全事件之一，且这个趋势仍在持续。因此，在数据共享流通的过程中，加强数据安全和隐私保护同等重要。2021 年国家相继通过了《数据安全法》和《中华人民共和国个人信息保护法》，对个人和企业隐私数据的保护的重视程度越来越高，数据隐私保护已成为业界关注的热点问题。

隐私计算是一种保护数据隐私的技术手段，在保证数据隐私的前提下实现数据的流通与共享，为数据安全和隐私保护提供了有力支撑。隐私集合求交（Private Set Intersection，PSI）作为隐私计算中的一项专用技术，允许互不信任的各方协同计算私有数据的交集，且不透露交集以外的任何信息。

近年来PSI 的理论研究活跃且应用广泛。早期的PSI 协议主要是基于公钥密码构造，根据实际应用的性能需求，新的技术手段和构造框架被提出，除了基于密码原语中的混淆电路（Garbled Circuit，GC）、不经意传输（Oblivious Transfer，OT）、同态加密（Homomorphic Encryption，HE）等技术，高性能OT 扩展（OT Extension，OTE）技术使PSI 效率大大提高。PSI 技术是多类隐私计算应用的先决步骤，如联合建模前需采用PSI 进行样本对齐，基于索引的安全查询前可采用PSI 进行索引获取等。PSI独立支撑了许多应用程序，包括隐私保护位置共享[1]、DNA 测试和模式匹配[2]、隐私通讯录查找[3]等。

现有的PSI 已经非常高效，但随着应用场景的多样化，在实际应用中仍然存在性能和安全问题。如新兴的卫星互联网，其网络和数据蕴藏着巨大的应用价值，可融合诸多行业应用充分挖掘数据价值，而研究更高性能和安全的PSI 对促进卫星互联网数据融合应用有很大的意义。

本文首先简要分析了PSI 的分类和设计框架，重点聚焦高性能两方PSI，详细梳理了涉及的密码技术和研究进展，分析和评估了业界先进的算法协议；其次以卫星互联网新型应用场景为例，探索提出高性能两方PSI 应用方案，实验测试不同数据类型在多种网络环境下的性能，给出新型场景下的PSI 实践范式；最后进行总结，给出了PSI 的发展思考与建议。

1 概述

PSI 是安全多方计算（Secure Multi-party Computation，MPC）的一类专用协议，传统的两方PSI 指互不信任的两个参与方分别持有各自的数据集X和Y，希望学习他们集合之间的交集X∩Y，而不透露任何额外的信息。为了满足不同实际场景的应用，除了传统的两方PSI，已衍生出了多种新型场景下的PSI协议。基于不同密码原语构建的PSI 协议的设计框架多种多样，经过广泛的理论和实验验证，基于不经意传输扩展（Oblivious Transfer Extension，OTE）的两方PSI 更高效。

1.1 PSI 的分类

为应对不同实际场景的需求，当前PSI 可从参与方数量、求交数据量差距、敌手行为和交集的重解释4 个方面进行分类，如表1 所示。从两方PSI到多方，若依旧使用传统PSI 两两求交以达到多方PSI 的功能，则存在多轮通信开销和合谋攻击的问题，目前较有效的技术框架是基于OTE 构造的可编程不经意伪随机函数（Oblivious Programmable Pseudo-Random Function，OPPRF）与零共享结合[4]。非平衡PSI 中两方数据量相差较大，若采用通用的平衡PSI 则存在小数据方的计算资源需求和消耗太大的问题。主流的非平衡PSI 主要采用全同态（Fully Homomorphic Encryption，FHE）技术且将大数据加密放在离线阶段[5]。恶意安全的PSI 更满足实际场景的安全需求，但相较于半诚实的开销更大，因此当前研究者倾向于探索安全性易扩展的PSI 框架，这种框架从半诚实到恶意安全仅需非常小的开销。门限PSI 是有条件的多方PSI，包括对元素出现次数的约束和对交集大小的约束两种情况。

表1 PSI 分类

1.2 PSI 的设计框架

两方PSI 的性能优化主要依赖底层密码原语的发展，根据密码原语的不同可划分为4 种设计框架。

（1）基于公钥密码的设计框架。主要采用椭圆曲线迪菲-赫尔曼密钥交换（Elliptic Curve Diffie-Hellman Key Exchange，ECDH）和RSA 技术构造PSI 协议，基于ECDH 采用椭圆曲线上的倍点运算效率更高，协议易于理解、实现简单且对网络带宽不敏感，目前工业界仍广泛使用ECDH-PSI。

（2）基于混淆电路（Garbled Circuit，GC）的设计框架。此类协议基于GC 的通用特性，对构造可计算交集结果的PSI 比较友好。由于电路构造和深度复杂、比较次数大，此类协议的开销昂贵。

（3）基于HE 的设计框架。利用HE 密文运算和明文运算等价的特点实现PSI 功能，构造通用的PSI 计算量大，常用于非平衡场景。

（4）基于OT 的设计框架。使用传统的OT 技术给PSI 带来了很大的通信开销，随着OTE 技术的发展，基于OTE 的PSI 性能突出，被业界广泛研究和实际应用。本文重点研究基于OTE 设计框架的高性能两方PSI。

1.3 密码技术

1.3.1 不经意传输扩展

OT 由Rabin[6]于1981 年提出，是一个安全的两方通信协议，指发送方有多个输入值，接收方希望得到其中某一个值，与此同时需保证发送方不知道接收方的选择信息，且接收方除了得到自己选择的值，不知道其他输入值的相关信息。OT 是MPC中最重要的原语之一，可被应用到许多密码学协议的构造中，目前业界高性能的PSI 协议主要依赖OT 的构造，对PSI 性能的提升直接转化为对OT 协议的改进。

OT 协议性能的优化主要是从“base OT”到OTE 的发展，如表2 所示。“base OT”主要基于公钥密码技术构造，在具体实现时表现为计算效率低、通信开销大，可通过椭圆曲线上的倍点运算和多线程技术进行性能优化。OTE 的提出是为了解决“base OT”的开销问题，核心思想是参与方交互式获取“种子信息”，然后使用高效的对称密码原语在没有交互的情况下扩展种子，以获取大量的OT 实例。OTE 从构造方式的角度又分为IKNP-OTE 和Silent-OTE，前者计算效率高、通信开销大，后者是前者的改进，旨在降低通信开销且寻求计算和通信的最佳平衡。

表2 OT 发展及特点

Ishai 等人[7]于2003 年提出的IKNP 协议是OTE 的突破性工作，基于矩阵变换的思想采用少量的“base OT”加对称加密获得几乎任意数量的OT实例，后续有很多基于IKNP 协议的改进性研究[8-9]，此类协议最大的瓶颈是通信。基于伪随机相关发生器（Pseudorandom Correlation Generator，PCG）构造的Silent-OTE[10-13]优化了通信开销，其Silent 特性根据PCG 的性质，经过一次廉价的交互后，双方可以存储小的密钥种子，这些种子可以离线本地生成大量OT 实例，通信和计算开销基本上独立于OT的目标数量。2019 年Boyle 等人[10]基于对偶一带噪声学习奇偶校验（dual-Learning Parity with Noise，dual-LPN）假设和函数秘密共享（Function Secret Sharing，FSS）技术提出Silent-OTE，但在密钥建立和dual-LPN 计算上复杂度高。为了降低Silent-OTE 的计算开销，后续的研究改用支持高效编码的原始-LPN（primal-LPN）假设[11-12]或低密度奇偶校验码（Low-Density Parity-Check Codes，LDPC）进行构造[13]。

1.3.2 向量不经意线性评估

不经意线性评估（Oblivious Linear Evaluation，OLE）是一种使参与双方能够获得相关输出的功能。一方输入值u和v，另一方输入值x且获得输出w=ux+v。向量不经意线性评估（Vector OLE，VOLE）是OLE 的一个向量化变体，更具体地说，发送方持有向量u和v，接收方有值x。该协议的目的是使接收方能够学习w=ux+v，而不向任何一方透露进一步的信息。VOLE 协议隐含了一个伪随机变体，如图1 所示，其中向量u和v是伪随机的，并在协议执行过程中随机生成，作为输出到达发送方。伪随机VOLE 是MPC 的一个基础构件，被广泛用于构造当前高性能的PSI 协议。

图1 伪随机VOLE

VOLE 与Silent-OTE 有深刻的联系，相互之间可以构造转化。因此，VOLE 的发展同Silent-OTE。

1.3.3 不经意键值存储

2 高性能两方PSI

早期提出的基于朴素哈希的PSI 方案存在暴力破解的风险，后续为解决这个问题提出了不经意伪随机函数（Oblivious Pseudo-Random Function，OPRF）的PSI 构造范式，其成为实现隐私性和高性能两方PSI 的核心。当前OPRF 高效的实例化主要分为两条技术路线：（1）将IKNP-OTE 解释为OPRF；（2）结合VOLE 和OKVS 构造OPRF。通过以上两种实例化的OPRF 构建的PSI 分别为IKNP-OTE PSI 协议和VOLE-OTE PSI 协议。

2.1 不经意伪随机函数

如图2 所示，运行OPRF 协议之后，发送方可获得一个伪随机函数F的密钥k，接收方可以得到一系列伪随机函数的计算结果，同时，发送方不知道接收方的输入，接收方也不知道发送方获得的密钥k。OPRF 协议保证了发送方无法反推输入，同时接收方没有密钥k，也无法得到结果后暴力搜索。

图2 OPRF 范式

2.2 IKNP-OTE PSI

IKNP-OTE PSI 技术发展如图3 所示，核心思想是对基于公钥密码的“base OT”技术扩展为高效的OTE，然后将OTE 解释为OPRF，由OPRF 构建PSI 协议。随着OT 技术的提出，Pinkas 等人提出的PSSZ15 协议[14]及许多衍生协议[9,15-16]发起了对IKNP-OTE 新协议族的研究，这类协议以增加通信为代价提高了效率。

图3 IKNP-OTE PSI 技术发展

2013 年Ishai 等人[7]基于矩阵转置提出突破性的1-out-of-2 IKNP03-OTE 工作，Kolesnikov 等人[8]指出IKNP-OTE 使用了一个编码方案，存在对选择比特ri∈{0,1}重复编码的问题。因此，使用一定码字长的ℓ维线性纠错码，构造出1-out-of-2ℓ的KK13-OTE 协议。2016 年Kolesnikov 等人[9]指出PSSZ15 隐私相等性检测协议执行OT 次数依赖于集合元素的比特长度，计算和通信开销非常大。为了移除上述依赖关系，作者改进KK13-OTE 协议，使用伪随机函数替换线性纠错码构造出1-outof-∞的KKRT16-OTE 协议。后续将OTE 解释为批量密钥相关的OPRF（Batched Related-key OPRF，BaRK-OPRF），OPRF 则可很容易构建PSI 协议。此外，融入了Cuckoo hash 技术将集合映射到hash表中，确保双方相同的数据必定在同一箱中，降低比较次数且减少OPRF 实例的计算而减少了通信开销。鉴于KKRT 协议对每个元素需执行多个单点OPRF 操作，Pinkas 等人[15]从通信负载上，采用多项式插值技术改进IKNP03-OTE，实现了多点OPRF且允许每个元素只计算一个OPRF 实例，降低了通信开销，但高阶多项式插值产生了较高的计算开销。2020 年Chase 等人[16]从通信和计算平衡的角度，仅采用OT、对称密码和伪随机函数设计出多点OPRF，实现了通信和计算开销平衡的PSI 协议。

2.3 VOLE-OTE PSI

VOLE-OTE PSI 协议主要采用VOLE 和OKVS技术构造OPRF 实例，比对OPRF 实例即可获取交集结果。2020 年Pinkas 等人[17]首次将OKVS 数据结构融入PSI 中，使用一个Cuckoo 图来实现PaXoS（probe-and-XOR of strings），它提供了一个非常高效和便捷的方法来表示集合X和Y，作者将他们的OKVS 和文献[15]的PSI 协议结合起来，以获得当时最高效的PSI 协议之一。Rindal 等人[18]观察到OKVS 可以更有效地与VOLE[11]相结合，以获得更高效的PSI 协议，还提出了改进的XoPaXoS（X-oblivious PaXoS）以构造OPPRF，使用OPPRF以很小的开销实现恶意安全的PSI。与此同时，Garimella 等人[19]通过放大技术验证OKVS 随机构造的失败概率在一个相对较高的上界，改进的OKVS 使文献[15]的PSI 协议通信效率提高。到目前为止，基于IKNP-OTE 的KKRT 协议仍然是计算效率最高的，文献[18]是通信效率最高的，而文献[19]是两者之间的折中方案。2022 年Rindal 等人[20]基于文献[18]的PSI 框架，对OKVS 进行了颠覆性的改进，基于高维线性方程求解的思想，采用简化矩阵下三角和分块聚类的方法，可有效并行化OKVS 编码，并且将VOLE 扩展成子域-VOLE（subfield-OKVS）[13]降低通信量。同年，Bui 等人[21]提出了一个相似贡献的PSI 协议，采用的是hash 和VOLE 技术。

总的来说，VOLE-OTE PSI 框架如图4 所示，分为OKVS 编码、OPRF 密钥生成和OKVS 解码并获得交集3 个阶段。假设发送方有数据集Y={y1,y2,…,yn}，接收方有数据集X={x1,x2,…,xn}，双方提前协商两个hash 函数，即HF:{0,1}*→F，H*:{0,1}→{0,1}out，参数m为OKVS 编码输出向量的维度，m＞n。

图4 VOLE-OTE PSI 框架

（1）OKVS 编码。接收方采样随机值r并发送给发送方，接收方本地执行OKVS 编码过程，输入数据是关于集合数据的 (xi,HF(xi,r))，获得输出向量P∈Fm。

（2）OPRF 密钥生成。发送方和接收方交互式地进行VOLE 过程，发送方获得有限域整数Δ∈F，向量B∈Fm，接收方获得向量A∈Fm和C∈Fm，其中C=ΔA+B。接收方计算A+P并发送给发送方，然后发送方计算OPRF 密钥K=B+Δ(A+P)。

（3）OKVS 解码并获得交集。接收方对每个数据xi进行OKVS 解码Decode(C,xi)，并对其计算hash 值H*(Decode(C,xi))。发送方对每个数据yi进行OKVS 解码Decode(K,yi)，然后计算H*(Decode(K,yi)-ΔHF(yi,r))，并将所计算的hash 结果发送给接收方。最后，接收方比对两个OPRF 集合获得最终的交集。

此外，基于VOLE 和OKVS 技术实现的PSI提供了一个非常优秀的范式，既可以为半诚实安全又可抗恶意安全。PSI 的安全级别依赖于VOLE 和OKVS 实例化的OPRF 输出长度out，当out=λ+log2(nxny)时达到半诚实安全，当out=κ时达到抗恶意安全，其中λ和κ分别为统计安全参数和计算安全参数，且相对于半诚实到恶意安全仅需非常小的开销。

3 面向卫星互联网的PSI 应用方案及实验分析

3.1 面向卫星互联网的PSI 应用方案设计

卫星互联网作为新型战略基础设施，其网络和数据蕴藏着巨大的应用价值。不同于传统通信网络，卫星互联网具备“天—地”一体化组网、多源信息融合等新特性，典型的卫星互联网场景如图5 所示。

图5 卫星互联网场景

卫星互联网数据涵盖网络运行、测试控制、行业应用、个人增值、物联网（Internet of Things，IoT）等多元信息，数据种类多、时空尺度大、覆盖范围广、数据价值高，可作为重要的数据来源支撑其他行业的数据融合应用。比如，卫星互联网的高价值测绘、遥感等数据可为环境、旅游等行业提供数据支撑；卫星互联网多维度的网络流量数据可与传统运营商互补，以更好地刻画用户行为和分析业务情况等。本文以卫星互联网新型场景为背景，提出卫星互联网和地面运营商的高性能PSI 应用解决方案，探索PSI 技术如何在新型场景落地，赋能行业应用。方案整体框架见图6。

卫星互联网和地面运营商数据融合的PSI 应用方案主要包含数据准备、元信息共享、数据预处理、安全求交4 个阶段。

（1）数据准备阶段。卫星互联网业务平台采集网络数据、用户信息、流量数据等，并将业务平台的数据接入隐私计算节点，节点将对用户、业务的原始数据（或数据表）进行管理，如元信息的展示和统计分析等。同样地，地面运营商业务平台在本地隐私计算节点形成自身的原始数据及相应的元信息。

（2）元信息共享阶段。卫星互联网和地面运营商作为隐私计算的两个独立节点，先确定待融合应用的样本数据，然后通过原始数据隔离、元数据共享的安全业务模式，交互式确定需对齐的ID信息，如用户身份证号、业务ID 等。

（3）数据预处理阶段。双方对确定的ID 信息本地预处理，包括数据去重和数据标准化。ID 信息进行本地数据去重，海量数据可采用BloomFilter 方式，针对一般量级的数据可借助K-V 数据库进行去重，或采用朴素HashSet 的方式。对于ID 信息的本地数据标准化，双方提前协商规则进行数据填充和清洗。

（4）安全求交阶段。双方根据场景需求选择PSI 协议并运行，结合实际需求设置一方或者两方获取交集结果，但不能获得交集以外的任何信息。PSI 协议执行的对比分析见3.2 节。

3.2 对比实验

本文主要对业界关注度比较高且广泛用于实际场景的4 个PSI 算法进行实验分析，包括基于公钥密码的ECDH-PSI[22]、IKNP-OTE 的KKRT[9]、VOLE-OTE 的BC22[21]和RR22[20]，前3 个算法是基于隐语的安全处理单元（Secure Processing Unit，SPU）平台[23]实现的，最后一个算法是基于文献对应的开源库Vole-PSI[20]实现的，该库是跨平台的（win，linux，mac），依赖于libOTe（大量OTE 算法实现库）、sparsehash（hash 映射库）和Coproto（基于协程的跨平台协议框架）。实验环境为两台Intel至强5218@2.3 GHz 服务器上的CentOS7.6-x64 虚拟机（16 GB 内存、251 GB 硬盘），在两台物理机上分布式地运行PSI 任务。

针对实际应用，设置两项细分场景进行实验分析。一是面向用户行为分析的海量用户ID 求交，二是面向业务逻辑分析的小批量业务ID 求交。

3.2.1 用户ID 求交

4 种PSI 算法的性能统计如表3 所示，测试数据量两方均为1 亿条（ID 为18 位十进制字符），交集结果为5 000 万条，分别在100 Mbit/s、500 Mbit/s 和1 000 Mbit/s 三种网络带宽下的统计结果。从表中可知：（1）ECDH-PSI 对网络配置不敏感，对计算资源敏感；（2）IKNP-OTE PSI 受带宽影响较大，计算性能较好；（3）VOLE-OTE PSI 是通信和计算的平衡，性能开销上表现更好，亿级数据的求交可在10 min 内完成。

表3 基于用户ID 的安全求交

3.2.2 业务ID 求交

使用“设备ID－网络情况－业务信息”模拟30 字符的业务ID，双方数据量分别为100 万条，交集结果为50 万条，在低带宽10 Mbit/s 的网络环境下，4 种PSI 算法的性能统计如表4 所示。实验数据表明，在低带宽网络环境下，ECDH 和VOLEOTE（RR22）的PSI 算法性能较好，运行速度是KKRT 和BC22 的2～3 倍。

表4 10 Mbit/s 带宽下基于业务ID 的安全求交

由表4 可知RR22 算法性能最好，表5 展示了在多个参数优化下的性能统计。设置较大的聚类分块参数（mBinSize）和较小的统计安全参数（mSsp），降低了总体通信量且可进行多线程运算。此外，在局域网下的运行速度是广域网下的3～15 倍。

表5 不同参数下基于RR22 算法的安全求交

3.3 对比结论

基于公钥密码技术的ECDH-PSI 协议简单，易于理解和实现，且易于扩展为非平衡和多方的PSI 场景，具有低通信量和中计算量的特性。基于矩阵变换的IKNP-OTE 类PSI 协议具有最佳的计算效率，但通信开销为该类方案在广域网场景下的主要瓶颈。基于VOLE 和OKVS 构造的VOLE-OTE 类PSI 协议在通信和计算效率上做到了较好的平衡，在广域网下性能具有优势。此外，VOLE 和OKVS 技术为PSI 提供了一个优秀的范式，可很容易从半诚实安全转化为恶意安全，开销非常小。VOLE-OTE 类PSI 协议的局限性是依赖的基础技术理解和实现层面都有一定难度。

在卫星互联网场景，在计算资源允许的情况下推荐采用RR22 协议构建高性能PSI 应用方案，此外海量数据高带宽下可选用KKRT 协议，少量样本低带宽下可选用ECDH 方案。针对RR22 协议，需进一步优化OKVS 聚类分块大小、安全参数和线程数等协议参数以取得最优性能。在实际应用中，可结合数据样本大小和网络、计算资源选择算法，以达到最优性能。

4 结语

在政策和个人意识的推动下隐私保护需求愈加强烈，数据隐私保护已成为业界关注的热点问题。隐私计算是一种保护数据隐私的技术手段，PSI 作为隐私计算中的一项专用技术，是促进数据融合应用的先决步骤，在保证数据隐私的前提下推动了数据的流通与共享。然而，在多样性的实际场景下，现有的PSI 协议仍存在高效性、安全性和适用性等方面的问题，有待进一步探索和突破，如下文所述。

（1）提高PSI 协议的性能。密码技术的性能瓶颈是其与实际业务相结合的一大难点，相较于明文计算慢几个数量级。一直以来，PSI 协议的性能都是计算和通信开销的博弈，基于VOLE-OTE 的PSI 协议在计算和通信开销上做到了较好的平衡，但在低网络带宽下海量数据求交的性能仍然不理想。因此，基于VOLE-OTE PSI 的范式，可进一步改进底层OKVS 和VOLE 的计算和通信性能。

（2）研究高安全性的PSI 方案。当前绝大部分的PSI 方案仅抵御半诚实攻击，但抗恶意安全更具有实用性。从一般的半诚实安全协议扩展到恶意安全，往往需要更高的开销，在满足实际可用的情况下高安全性的PSI 协议需进一步研究。

（3）构建新型场景的PSI 协议。为应对不同实际场景的需求，通用的PSI 协议并不能适用于所有的业务场景，如参与方数据不平衡的场景，通用的方案导致小数据方的计算资源需求和消耗太大；某些交集结果仍是敏感的特定场景，如电子医疗的病患数据，通用方案则会泄露交集结果。因此，需根据实际情况构造满足场景需求的PSI 协议。