1. 引言
隐私集合求交(Private Set Intersection, PSI)源于密码学与安全多方计算(Secure Multi-party Computation, SMC),旨在在不泄露各方输入集合的前提下安全计算交集。Meadows等人基于Diffie-Hellman协议提出的两种方案首次系统性地引入了这一问题,为后续PSI研究奠定了基础[1]。随着数字经济与电子商务的发展,跨平台、跨部门、跨机构的数据协作需求日益突出:一方面,电商平台需在账户风控、黑产治理、刷单/羊毛党识别、商家准入与跨境合规等业务中对齐风险标识;另一方面,在网络营销、数据库营销及
联动等场景中也存在协同匹配需求。
也存在对“屏蔽名单/重复触达用户/异常流量设备”等标识进行交叉匹配的现实需求[2]。在这些场景下,直接共享用户标识、设备指纹或商家风险名单不仅涉及合规与隐私保护,还可能暴露商业敏感策略与运营数据,从而制约了跨域协作的深度与效率[1]-[4]。
早期PSI协议主要依赖公钥加密与SMC技术,通过加密、混淆以及不经意传输(Oblivious Transfer, OT)实现安全集合比较[3];随后研究进一步整合同态加密与Bloom过滤器,在保障安全性的同时提升计算与通信效率[4]。近年来,PSI也与区块链、可信执行环境(Trusted Execution Environments, TEEs)等技术结合,形成2-PSI、MP-PSI等多种变体,并在云端协同计算环境中得到更广泛讨论[5]-[7]。面向电商业务的大规模数据处理与快速响应需求,云辅助PSI为提升可扩展性提供了工程可行路径;但由于云环境可能不完全可信,云侧计算与中间结果仍可能带来隐私与策略泄露风险,使得安全的云端PSI成为关键挑战[8]。
在电子商务协同中,很多匹配任务并不需要“每次都输出精确交集”。例如,跨平台风控联动往往更关心“疑似重叠是否达到需要联动处置的规模”,数据库营销也常需要先判断“重复触达用户是否足以触发联合策略”。因此,为满足现实业务中“先评估价值、再决定是否深度协同”的需求,阈值PSI (Threshold PSI)逐渐受到关注:仅当交集规模超过预设阈值时才执行后续的精确求交流程,从而避免低收益协作带来的不必要开销[9]。然而,现有阈值PSI方案仍存在明显局限。多数方案在协议层仍近似采用“无条件执行”或高成本判定流程,即使在交集稀疏的电商场景下(例如平台用户群差异显著、风险标识较稀疏)也需承担较高的计算与通信开销[10]。这种强制执行不仅降低风控链路的实时性与系统吞吐,还可能引入时序、路径等侧信道泄露风险,违背“最小披露”原则。同时,在云辅助架构下,不可信基础设施带来的新型威胁进一步放大了上述问题。因此,如何在保证阈值判断与PSI执行安全性的前提下,实现更贴合电商业务的高效协同机制,是当前亟待解决的关键问题。
针对传统多方隐私集合求交(MP-PSI)在稀疏交集场景下仍需“无条件执行”而导致的高开销与隐私冗余问题,本文提出一种两阶段阈值门控多方PSI方案(Threshold-Gated Multi-Party PSI, TG-MPSI),在不破坏PSI安全性的前提下实现“先判断是否值得计算,再决定是否执行”的自适应计算模式。本文主要贡献如下:
(1) 提出阈值触发的两阶段PSI框架,在多方PSI中引入可配置的交集基数阈值门控机制:当估计的交集规模未达到阈值时终止协议,从而避免电商跨平台协同中稀疏交集带来的无效计算与额外隐私暴露,实现“按需执行”的协同风控与联合治理模式。
(2) 设计基于同态加密与Bloom过滤器结合的安全阈值判定与条件PSI执行机制:云侧完成加密域聚合,领导者仅基于解密后的槽位统计进行基数估计,并结合Chernoff界实现阈值判定;在触发条件满足时,进一步结合零共享与混淆布隆过滤器(GBF)结构完成安全交集计算,适配电商场景下的云端可扩展部署。
(3) 在半诚实模型下给出基于仿真的安全性论证,保障输入隐私、输出正确性与阈值判定准确性。实验结果表明,在交集规模低于阈值时,TG-MPSI相较无门控方案平均减少通信开销30%~45%,在线延迟降低25%~35%;当达到阈值时,整体性能与标准PSI同属一个量级,验证了方案在电商协同风控与数据协作中的可用性与扩展性。
本文其余部分组织如下:第2节概述相关工作;第3节介绍TG-MPSI的预备知识与问题定义;第4节描述系统模型与安全模型;第5节给出方案设计与正确性分析;第6节进行工程化落地;第7节总结全文并讨论后续工作。
2. 相关工作
现有PSI研究可概括为三条主线。
(1) 基于密码学原语的PSI:利用OT扩展与同态加密实现大规模集合比较,代表性协议在通信与计算复杂度上持续优化[11]。这类方案安全表达能力强,但在多方云环境下的工程成本与运维复杂度仍需权衡。
(2) 基于数据结构的高效PSI:Bloom过滤器及其派生结构通过常数时间的插入与查询支持高效匹配。GBF/OBF通过混淆、随机填充与路径隐藏等机制提升对抗侧信道的能力,并进一步扩展到并集/交集基数计算与多方场景[12] [13]。这类方法更贴近企业信息化中的高并发匹配需求,但需谨慎处理泄露边界与业务语义之间的平衡。
(3) 云辅助与阈值/门限PSI:云计算为企业提供弹性算力,但不可信基础设施引入新的隐私风险与治理挑战[8] [14] [15]。阈值PSI将“是否执行”与阈值判断结合,适用于风控触发、合规核验与营销触达等业务逻辑,代表性方案结合Paillier、阈值投票与零知识证明实现门限判定[16] [17]。但在企业常见的稀疏负载下,部分方案仍缺少稳定的“按需降本”效果,或因证明链路较重而增加系统集成成本。
针对电商稀疏匹配的真实负载特征,本文提出TG-MPSI,以轻量的云端基数判定作为门控层,在不影响触发场景求交能力的前提下显著降低未触发场景的通信与在线计算,并提供企业信息化集成与可运维部署路径。
3. 预备知识与符号
3.1. 符号约定
本文常用符号及含义如表1所示。
Table 1. Table of protocol notation
表1. 符号表
符号 |
含义 |
|
第
个参与方 |
|
参与方集合,
为参与方数量 |
|
云服务器(提供聚合与并行计算能力) |
|
参与方
的私有集合(电商风险标识集) |
|
安全参数/字符串长度(bit) |
|
哈希函数个数 |
|
个独立哈希函数集合 |
|
Bloom/GBF的长度(槽位数) |
|
触发阈值(门控条件) |
/
|
同态加密/解密算法 |
|
触发标志(是否进入第二阶段) |
|
安全证明中的模拟器 |
3.2. Bloom过滤器与混淆布隆过滤器(GBF)
Bloom过滤器是一种空间高效的概率型数据结构,可用于快速判定元素
是否属于集合。其由长度为
的比特数组
和
个相互独立的哈希函数
组成,其中
。初始化时
全为0。插入元素
时,对每个
置位
。查询
时,若存在某个
使得
,则
一定不在集合中;若所有对应位均为1,则判定
可能在集合中(存在误报概率),该误报概率通常随
、
以及集合规模变化,但在合理参数下可控制在较低水平。
混淆布隆过滤器(Garbled Bloom Filter, GBF),GBF是在Bloom过滤器基础上引入“混淆编码”的结构化PSI构件[18]。与仅存储比特不同,GBF维护长度为
的字符串数组
,每个槽位存放
比特串。对元素
(可视为
比特串),令其索引集合为
。编码时在
对应的
个槽位写入
份随机份额,使得这些份额按XOR还原为
,即满足:
(1)
加法同态加密本文第一阶段的阈值判定采用加法同态加密以支持“加密域聚合、明文端判定”的计算模式。以Paillier方案为例,其满足对明文加法的同态性:对任意明文
,有
(2)
并且对任意常数
,
(3)
其中,
为Paillier公钥模数,
与幂运算在密文群中进行。该性质使云端能够对密文进行加和聚合,而不直接接触各方输入,符合电商跨域协作中最小披露、可扩展计算的工程要求。
4. 模型描述
本节面向电子商务协作场景,给出阈值触发TG-MPSI的系统模型、输入输出、通信架构与阶段划分,并据此定义安全模型。在电商C2C/B2B业务中,多平台需对风险标识集合进行交叉核验以支撑联防联控、黑产治理、营销去重与商家准入,但直接共享名单易带来合规与商业敏感信息泄露风险。为此,TG-MPSI采用两阶段门控机制:阶段一对交集规模进行隐私保护估计,未达阈值则终止;达到阈值时触发阶段二输出真实交集,从而在保障隐私的同时降低稀疏交集下的冗余开销。
系统由两类实体构成:
电商参与方:记为
。参与方
持有私有集合
,其中元素
为标准化编码的电商风险标识(账号ID、设备指纹、商家ID等)。可执行本地哈希映射、GBF/Bloom编码及加解密等操作。
云服务器:记为
。负责执行与阈值判定相关的结构化计算与密文域聚合。考虑到电商协作中云基础设施可能属于第三方服务商或多租户环境,本文将
建模为半诚实(semi-honest):遵循协议但可能试图从所见消息中推断额外信息。
为便于工程实现,指定某一参与方
为领导者(Leader),负责收集来自云端的阈值判定结果、在触发条件满足时协调第二阶段PSI的执行并分发最终交集结果。
云辅助多方隐私集合求交协议:
输入:
个参与方的私有集合
以及阈值
。
输出:触发标志
与条件输出结果
:
若
,输出真实交集
;
若
,输出
(表示不触发精确求交)。
传统MPSI系统模型如图1所示。
Figure 1. Traditional MPSI system model
图1. 传统MPSI系统模型
半诚实安全的TG-MPSI
本文在半诚实模型下分析TG-MPSI的安全性。攻击者可腐化云服务器
或腐化部分参与方,但腐化实体在执行过程中均按协议发送消息,只是试图从交互视图中获取额外信息。为满足电商协作中“只泄露必要业务信号”的要求,本文主要关注如下安全目标:
输入隐私:除协议允许泄露的输出(触发标志
与在
时的交集
)外,任意被腐化实体不应获得关于诚实方输入集合
的额外信息(例如非交集元素、集合规模细节、结构性特征等)。
输出正确性:协议输出应与理想功能一致,即当满足触发条件时输出真实交集,否则输出
。
阈值判定最小披露:阶段I仅允许输出触发判定所必需的信息(如
或与阈值比较等价的最小统计量),避免在稀疏交集下暴露不必要的中间结构与路径信息。
TG-MPSI系统模型如图2所示。
Figure 2. TG-MPSI system model diagram
图2. TG-MPSI系统模型图
给定协议
与理想功能
,若对任意PPT半诚实攻击者
,存在PPT模拟器
,使得对任意输入向量
有:
(4)
则称协议
在半诚实模型下安全。其中
表示计算不可区分,即对任意PPT区分器
:
(5)
该定义保证,在电商协作场景中,除“是否触发深度协作”与“触发后的交集结果”之外,云端或被腐化参与方无法从协议交互中推断更多关于其他平台风险标识集合的内容。
5. 阈值触发多方隐私集合求交
本节介绍TG-MPSI在半诚实模型下的协议流程。方案面向电子商务跨域协作:多平台在不共享原始名单的前提下,对风控标识集合进行交叉核验。考虑到联防并非每次都需输出精确交集,TG-MPSI采用两阶段门控设计:阶段I在云端进行隐私保护的交集规模估计,仅输出触发标志
(可选输出估计值)以判断是否启动深度协作;阶段II仅在
(估计交集规模达到业务阈值
)时执行MP-PSI输出真实交集,用于联合封禁、联合拦截或营销去重触达等联动处置。
5.1. 阶段I:交集基数门控
阶段I的目标是判断真实交集规模
是否达到阈值
,并输出触发标志
,同时尽量不泄露除触发判定所需之外的任何信息。
(1) Bloom结构构造与加密上传
各参与方
选取
个公开哈希函数
,对其本地风险标识集合
中的元素
计算哈希位置:
(6)
初始化比特向量
,并对每个
置位
。随后,Leader生成Paillier密钥对:
(7)
并将公钥
分发给所有参与方与云服务器
,私钥
仅由Leader持有。参与方对每个槽位加密:
(8)
并将密文向量
上传至云服务器。
(2) 云端同态聚合与“全1槽位”构造
云服务器对每个槽位
在密文域做同态加和聚合:
(9)
为判定槽位
是否为全1插槽,云端进一步构造:
(10)
将
发送给Leader解密。
(3) Leader解密判定与基数估计
Leader解密得到每个槽位的明文差值并判定是否“全1”:
(11)
其中
表示第
个槽位在所有参与方中均为1。令全1槽位总数为
(12)
基于Bloom过滤器的标准估计式,可得到交集基数估计值:
(13)
最后进行阈值门控,若
,则置
并进入阶段 II;否则置
,协议终止并输出
。
5.2. 阶段II:触发后精确求交
当且仅当
时,执行阶段II输出真实交集元素,用于跨平台协同风控处置或营销去重。
(1) 离线阶段:GBF构造与混淆
各参与方基于其集合
构造混淆布隆过滤器
。对每个元素
,计算索引集合
,并生成
份XOR份额写入对应槽位,使得满足:
(14)
对未赋值的槽位用随机串填充。为隐藏结构与访问模式,可进一步采用随机化/路径隐藏等混淆策略,使云端难以从槽位分布推断元素位置。
(2) 在线阶段:云端XOR聚合与OT受控解码
云服务器接收所有
后,对每个槽位做按位XOR聚合:
(15)
随后,Leader与云端执行1-out-of-2 OT机制,使Leader只能按其本地索引集合查询必要槽位而不暴露查询位置。对任意候选元素
(Leader本地集合),若满足:
(16)
则判定
,并输出为交集元素。Leader汇总交集结果并分发给其余参与方,用于电商联防/协同治理任务。
5.3. 正确性分析
定理 1 (阈值判定的正确性)
在Bloom参数
合理配置、误差概率受控的条件下,阶段I基于全1槽位数
计算得到的
能以高概率正确反映交集规模是否超过阈值
。当真实交集规模较小(典型电商稀疏重叠场景)时,方案以高概率输出
并提前终止;当交集规模达到业务阈值时,以高概率输出
触发阶段II。
记真实交集规模为
,则全1槽位计数
的期望近似为
(17)
阈值
在
域对应:
(18)
在独立哈希近似下,
满足Chernoff集中界,从而第一类错误(误触发)与第二类错误(漏触发)分别满足
(19)
(20)
式(19)~(20)表明:当
远离
时误判概率随
指数下降;当
时误判更敏感,需通过增大
、合理选择
或设置阈值提升门控稳定性。
定理 2 (阶段II交集恢复的正确性)
当
时,所有参与方对交集元素的GBF份额在云端XOR聚合后满足式(16)的零判定条件,从而Leader可正确恢复真实交集
。当
时,协议不进入阶段II,输出
,符合门控语义。
5.4. 安全性分析
本节在第3章安全模型基础上,说明TG-MPSI在静态半诚实对手下满足输入隐私与最小披露原则,适用于电商多方协作的合规与商业敏感约束。
(1) 阶段I:密文聚合的隐私性
仅Leader持有Paillier私钥
,云服务器与其他参与方无法解密任意
、
、
。云端观察到的仅为Paillier密文,结合IND-CPA安全性,无法推断任意参与方Bloom位向量的具体分布,更无法恢复电商风险标识集合内容。
(2) 最小披露与门控输出
阶段I对外仅公开触发标志
(以及可选的估计值
)。当
时协议终止,避免在“交集很小但仍强行做PSI”时产生的额外交互与潜在侧信道泄露;这与电商风控链路“低价值不联动”的业务逻辑一致。
(3) 阶段II:GBF混淆 + OT的访问模式保护
在阶段II中,云端仅看到经混淆的GBF槽位与XOR聚合结果;Leader的槽位查询通过1-out-of-2 OT完成,使云端难以获知Leader具体查询的槽位位置,从而隐藏访问模式,降低由查询路径推断元素的风险。
定理 3 (半诚实安全性)
若Paillier满足IND-CPA安全性,OT协议在半诚实模型下安全,哈希函数与PRF满足伪随机性,且GBF混淆使单方视图与随机串不可区分,则TG-MPSI在第3章定义的半诚实模型下安全,为进一步降低
与
被单点掌握带来的合谋风险,可将阶段I的Paillier解密从“Leader单点解密”升级为
阈值解密,即使Leader与云服务器
合谋,只要其腐化的解密份额数小于
,除允许泄露的
与在
时的交集结果外,攻击者无法获得关于诚实方输入集合及
的额外信息。
6. 工程化落地
将参与方平台记为
,云侧聚合服务记为
。各平台仅上传经加密、混淆后的Bloom/GBF结构,禁止上传原始风险名单;密钥与解密能力集中于Leader (或合规托管模块),云端仅执行密文聚合与结构化计算。对异常请求(高频触发、重复提交、参数越界)进行限流与风控拦截,避免通过调用频率推断业务策略。
对关键操作,如:KeyGen、上传、聚合、解密、触发判定、OT交互,记录不可抵赖审计日志,包含请求ID、时间戳、参数摘要与签名链路;对flag触发与交集下发设置双人复核或策略审批,支持事后追责与合规核查。必要时将日志摘要周期性锚定到独立存储以提升防篡改能力。
默认仅输出触发标志
;仅在
且满足业务授权策略时输出交集元素。交集结果以“最小字段集”形式下发(如标准化ID/哈希标识),并采用分级权限控制与到期回收机制;对跨境/跨主体协作场景,按数据最小化与目的限定原则配置阈值
与输出粒度,确保“可用、可控、可审计”。
7. 结论及展望
本文面向电商跨平台风控与协同治理中“交集稀疏但频繁比对”的需求,针对传统多方PSI无条件执行带来的通信与在线时延冗余及隐私暴露问题,提出阈值门控TG-MPSI。方案在云端对加密Bloom过滤器进行安全聚合以估计交集基数,仅输出1比特触发标志;仅当估计规模达到阈值时,才启动基于GBF与OT的多方PSI输出交集用于联动处置,实现按需协作。在半诚实模型下,方案满足输入隐私与输出正确性。实验表明,在不同参与方数量、集合规模与阈值配置下,TG-MPSI可在大量未触发场景显著降低总通信开销与在线延迟,适用于电商风控联防、营销去重与商家治理等业务链路。未来可扩展至恶意安全与可验证计算,引入更细粒度门控与功能负载,并结合更轻量的基数估计、TEE或差分隐私提升鲁棒性与可用性。
基金项目
国家自然科学基金联合基金重点项目(U24A20241);贵州省重大专项(黔科合重大专项字[2024]014,黔科合重大专项字[2024]003);现代商贸深度融合新零售电商数字经济平台关键技术研究(合同编号:黔科合支撑[2023]一般231)。
NOTES
*通讯作者。