Page 379 - 《软件学报》2026年第4期

1820 软件学报 2026 年第 37 卷第 4 期

obtain the intersection. To address these issues, this study proposes a threshold testing method based on robust secret sharing (RSS) and a
TMP-PSI scheme combined with oblivious key-value store (OKVS), which effectively reduces both computational overhead and the
number of communication rounds. To meet the demand for multiple participants to access the intersection information from their private
sets, this study also proposes a second extended threshold multi-party private set intersection (ETMP-PSI) protocol, which modifies the
share distribution method. Compared to the first scheme, the secret distributor and secret reconstructor do not incur additional
communication rounds or computational complexity, allowing multiple participants to obtain the intersection elements from their private
sets. The proposed protocol runs in 6.4 seconds (TMP-PSI) and 8.7 seconds (ETMP-PSI) in a three-party scenario with a dataset size of
16
n=2 . Compared to existing threshold multi-party private set intersection protocols, the communication complexity between the
reconstructor and distributor is reduced from O(nNtlognλ) to O(bNλ).
Key words: threshold multi-party private set intersection (TMP-PSI) protocol; communication round; computational overhead; robust secret
sharing; oblivious key-value store (OKVS)
数字技术作为世界科技革命和产业变革的先机, 日益融入经济社会发展各领域全过程, 数据资源已经成为数
字经济时代的基础性生产要素. 为了保护用户隐私信息在数据交互过程中的安全, 研究人员提出了各种隐私保护
方法, 其中安全多方计算是保护隐私的有效手段之一. 隐私集合交集 (private set intersection, PSI) [1−14] 作为安全多方
计算的一个重要应用, 与其他隐私保护框架 [15,16] 被广泛应用于医疗、金融和社交网络等领域.
隐私集合交集协议允许各个参与方之间执行协议获得所有参与方持有数据元素的交集, 但不泄露除了交集以
外的任何信息. 隐私集合交集技术在数据交互的过程中, 发挥了保护个人隐私的关键作用, 允许不同实体在共享数
据时保护数据的隐私, 同时允许参与者在不暴露私有信息的情况下进行集合运算.
但是标准隐私集合交集协议在现实生活中的某些场景并不适用, 例如议案投票时, 投票支持人数超过一定数
量即可, 并不需要全部投票人员都支持才通过议案. 此外可用于金融机构协作识别交易威胁: 某个金融机构 A 需
要检测用户账户是否存在交易威胁且不泄露金融机构的隐私信息, 假设采用多方隐私集合交集协议 (multi-party
private set intersection, MP-PSI) [17−25] , 将金融机构 A 中的异常用户与其他金融中心进行联合筛查, 一旦金融机构 A
中的异常用户在其他金融机构都存在异常交易行为, 就标记为交易威胁, 并上传至监管名单, 但该交易威胁的设置
过于严格, 因为用户不一定在全部金融机构都存在异常交易行为. 此场景可以采用门限多方隐私集合交集协议判
断交易威胁, 设置预警阈值 t, 在检测时间段内, 金融中心 A 的异常交易用户, 在其余 t −1 个金融中心中存在异常
t 个网络中心受到攻
交易行为, 将被标记存在交易威胁. 此协议同样适用于网络操作中心协作识别常见威胁, 只要
击, 就被设置为常见威胁 [26] .
针对问题, Bay 等人 [17] 提出了门限多方隐私集合交集协议 (TMP-PSI) 的概念, 允许一个服务器端 P 1 和多个客
,
户端 P 2 ,...,P N , 输入他们的私有数据集 X 1 ,...,X N N 个参与方共同计算服务器端数据集 X 1 中, 哪些数据元素是至
少 t (t < N) 个参与方共同拥有的, 并且除了服务器端以外, 其他参与方不知道任何信息, 如图 1 所示.

服务器

X s ={1,2,3,4} {1,2}

X 1 ={1,2,3,6} X 4 ={4,5,6,7}
T=3
用户 1 用户 4
X 2 ={1,2,5,7} X 3 ={2,5,6,7}

用户 2 用户 3
图 1 门限多方 PSI 示意图