非平衡场景下的模糊隐私集合交集基数协议

doi:10.19678/j.issn.1000-3428.0070356

摘要/Abstract

摘要：

在接触者追踪应用场景中, 查询者与"敏感"人群的历史轨迹不完全相同, 导致隐私集合交集基数(PSI-CA)协议无法直接应用到接触者追踪这一场景。针对该问题, 提出一种非平衡模糊隐私集合交集基数(uFPSI-CA)协议。uFPSI-CA协议是隐私集合交集基数(PSI-CA)协议的一种变体, 该协议允许发送方和接收方通过交互共同计算其私有集合的交集的大小, 而不泄露其他任何信息。与PSI-CA协议不同的是, 双方的交集元素不完全相等, 而是有一定的相似性, 且发送方的集合大小远远大于接收方。为了将PSI-CA协议扩展到uFPSI-CA协议, 提出可分类洗牌的Diffie-Hellman不经意伪随机函数(CS-DH-OPRF)算法, 该算法在计算接收方的OPRF值时, 可以为同组数据添加一个常数的加密作为标签, 在后续计算过程中接收方按照标签对数据进行分类。uFPSI-CA协议将大量的计算交给作为服务器的发送方, 接收方仅做简单的元素加解密操作, 并且协议的总体通信开销与接收方的数据元素集合大小正相关。最后, 实现了uFPSI-CA协议, 在发送方集合大小为2¹⁸、接收方集合大小为2⁶时, 仅需4 s的在线时间及15 MB的通信开销, 证明了协议是高效的。

关键词: 非平衡, 模糊隐私集合交集基数, 全同态加密, 哈希技术, 多项式插值

Abstract:

In the contact tracing application scenario, the historical trajectories of the querier and the "sensitive" population are not completely identical, which makes the Private Set Intersection CArdinality (PSI-CA) protocol unable to be directly applied to this contact tracing scenario. To address this issue, an unbalanced fuzzy PSI-CA (uFPSI-CA) protocol is proposed. The uFPSI-CA protocol is a variant of the privacy-set intersection-cardinality protocol. This protocol allows the sender and receiver to jointly calculate the intersection size of their private sets via interactions, without revealing any other information. This protocol assigns many computations to the sender and behaves as a server. The receiver performs only simple element encryption and decryption. Additionally, the overall communication overhead of the protocol is positively correlated with the size of the receiver dataset. To extend PSI-CA to uFPSI-CA, a Classified Shuffle Diffie-Hellman oblivious Pseudo-Random Function (CS-DH-OPRF) algorithm is proposed. When computing the OPRF value of the receiver, the algorithm encrypts the same value for the same group of data as a label, and the receiver classifies the data according to the label in the subsequent calculation. Finally, the uFPSI-CA protocol is implemented. When the sender set size is 2¹⁸ and the receiver set size is 2⁶, only needs 4 s online time and 15 MB of communication overhead are required, which proves that the protocol is efficient.

Key words: unbalance, fuzzy Private Set Intersection CArdinality (PSI-CA), Fully Homomorphic Encryption (FHE), hash technology, polynomial interpolation

刘铭辉, 张恩, 王梦涛, 黄昱晨. 非平衡场景下的模糊隐私集合交集基数协议[J]. 计算机工程, 2026, 52(5): 281-292.

LIU Minghui, ZHANG En, WANG Mengtao, HUANG Yuchen. Fuzzy Private Set Intersection Cardinality Protocol in Unbalanced Scenarios[J]. Computer Engineering, 2026, 52(5): 281-292.

https://www.ecice06.com/CN/Y2026/V52/I5/281

图/表 9

图1 朴素哈希表与布谷鸟哈希表的对比方式

Fig.1 Comparison of simple hash table and cuckoo hash table

图2 多项式链接切片构造多项式流程

Fig.2 Procedure of polynomial link slicing constructs a polynomial

图3 uFPSI-CA协议整体流程图

Fig.3 The overall flow chart of the uFPSI-CA protocol

图4 发送方发送给接收方的数据量

Fig.4 The amount of data sent by the sender to the receiver

图5 接收方发送给发送方的数据量

Fig.5 The amount of data sent by the receiver to the sender

参考文献 30

1	张恩, 秦磊勇, 杨刃林, 等. 基于弹性秘密共享的多方门限隐私集合交集协议. 软件学报, 2023, 34 (11): 5424- 5441. doi: 10.13328/j.cnki.jos.006743
	ZHANG E , QIN L Y , YANG R L , et al. Multi-party threshold private set intersection protocol based on robust secret sharing. Journal of Software, 2023, 34 (11): 5424- 5441. doi: 10.13328/j.cnki.jos.006743
2	魏立斐, 刘纪海, 张蕾, 等. 双云辅助的超阈值多方隐私集合交集计算协议. 软件学报, 2023, 34 (11): 5442- 5456.
	WEI L F , LIU J H , ZHANG L , et al. Two cloud-assisted over-threshold multi-party private set intersection calculation protocol. Journal of Software, 2023, 34 (11): 5442- 5456.
3	张蕾, 贺崇德, 魏立斐. 高效且恶意安全的三方小集合隐私交集计算协议. 计算机研究与发展, 2022, 59 (10): 2286- 2298. doi: 10.7544/issn1000-1239.20220471
	ZHANG L , HE C D , WEI L F . Efficient and malicious secure three-party private set intersection computation protocols for small sets. Journal of Computer Research and Development, 2022, 59 (10): 2286- 2298. doi: 10.7544/issn1000-1239.20220471
4	UZUN E, CHUNG S P, KOLESNIKOV V, et al. Fuzzy labeled private set intersection with applications to private real-time biometric search[C]//Proceedings of the 30th USENIX Security Symposium. [S. l. ]: USENIX, 2021: 911-928.
5	MEADOWS C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//Proceedings of the IEEE Symposium on Security and Privacy. Oakland, USA: IEEE Press, 1986: 134-134.
6	RINDAL P, SCHOPPMANN P. VOLE-PSI: fast OPRF and circuit-PSI from vector-OLE[C]//Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2021: 901-930.
7	RAGHURAMAN S, RINDAL P. Blazing fast PSI from improved OKVS and subfield VOLE[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM Press, 2022: 2505-2517.
8	LIU F H, ZHANG E, QIN L Y. Efficient multiparty probabilistic threshold private set intersection[C]//Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM Press, 2023: 2188-2201.
9	FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]//Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer. 2004. 1-19.
10	CHMIELEWSKI L, HOEPMAN J H. Fuzzy private matching[C]//Proceedings of the 3rd International Conference on Availability. Barcelona, Spain: IEEE Press, 2008, 327-334.
11	YE Q S, STEINFELD R, PIEPRZYK J, et al. Efficient fuzzy matching and intersection on private datasets[C]//Proceedings of Conference on Information Security and Cryptology. Berlin, Germany: Springer, 2009: 211-228.
12	李婷. 基于大数据平台支持任意计算和模糊匹配的隐私保护集合交集方案[D]. 西安: 西安电子科技大学, 2024.
	LI T. Private set intersection scheme based on big data platform supporting full computation and fuzzy matching[D]. Xi'an: Xidian University, 2024. (in Chinese)
13	INDYK P, WOODRUFF D. Polylogarithmic private approximations and efficient matching[C]//Proceedings of the 3rd Theory of Cryptography Conference. Berlin, Germany: Springer, 2006: 245-264.
14	CHAKRABORTI A, FANTI G, REITER M K. Distance-aware private set intersection[C]//Proceedings of the 32nd USENIX Security Symposium. Anaheim, USA: USENIX, 2023: 319-336.
15	GARIMELLA G, ROSULEK M, SINGH J. Structure-aware private set intersection. with applications to fuzzy matching[C]//Proceedings of the 42nd Annual International Cryptology Conference. Berlin, Germany: Springer, 2022: 323-352.
16	GARIMELLA G, ROSULEK M, SINGH J. Malicious secure, structure-aware private set intersection[C]//Proceedings of the 43rd Annual International Cryptology Conference. Berlin, Germany: Springer, 2023: 577-610.
17	BAARSEN A, PU S H. Fuzzy private set intersection withLarge hyperballs[C]//Proceedings of the 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2024: 340-369.
18	CRISTOFARO E, GASTI P, TSUDIK G. Fast and private computation of cardinality of set intersection and union[C]//Proceedings of International Conference on Cryptology and Network Security. Berlin, Germany: Springer, 2012: 218-231.
19	DEBNATH S K, DUTTA R. Secure and efficient private set intersection cardinality using bloom filter[C]//Proceedings of the 18th International Conference on Information Security. Berlin, Germany: Springer, 2015: 209-226.
20	YANG Y B , DONG X L , CAO Z F , et al. EMPSI: efficient multiparty private set intersection (with cardinality). Frontiers of Computer Science, 2023, 18 (1): 181804. doi: 10.1007/s11704-022-2269-0
21	YANG X Y , ZHAO Y Q , ZHOU S F , et al. A lightweight delegated private set intersection cardinality protocol. Computer Standards & Interfaces, 2024, 87, 103760. URL
22	CHEN Y F , WU A X , YANG Y E , et al. Efficient verifiable cloud-assisted PSI cardinality for privacy-preserving contact tracing. IEEE Transactions on Cloud Computing, 2024, 12 (1): 251- 263. doi: 10.1109/TCC.2024.3360098
23	DUONG T, PHAN D H, TRIEU N. Catalic: delegated PSI cardinality with applications to contact tracing[C]//Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Germany: Springer, 2020: 870-899.
24	WU M, YUEN T H. Efficient unbalanced private set intersection cardinality and user-friendly privacy-preserving contact tracing[C]//Proceedings of the 32nd USENIX Security Symposium. Anaheim, USA: USENIX, 2023: 283-300.
25	PINKAS B, SCHNEIDER T, TKACHENKO O, et al. Efficient circuit-based PSI with linear communication[C]//Advances in Cryptology-EUROCRYPT 2019. Berlin, Germany: Springer, 2019: 122-153.
26	PINKAS B, SCHNEIDER T, WEINERT C, et al. Efficient circuit-based PSI via cuckoo hashing[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2018: 125-157.
27	CHEN H, HUANG Z, LAINE K, et al. Labeled PSI from fully homomorphic encryption with malicious security[C]//Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM, 2018: 1223-1237.
28	CHEN H, LAINE K, RINDAL P. Fast private set intersection from homomorphic encryption[C]//Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, USA: ACM Press, 2017: 1243-1255.
29	CONG K, MORENO R C, GAMA M B, et al. Labeled PSI from homomorphic encryption with reduced computation and communication[C]//Proceedings of 2021 ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM Press, 2021: 1135-1150.
30	ZHANG C, CHEN Y, LIU W, et al. Linear private set union from multi-query reverse private membership test[C]//Proceedings of the 32nd USENIX Security Symposium. Anaheim, USA: USENIX, 2023: 337-354.

[1]	高改梅, 邸国霞, 刘春霞, 杨玉丽, 党伟超, 张爱贞. 基于全同态加密的区块链电子投票方案[J]. 计算机工程, 2026, 52(4): 313-326.
[2]	唐莹莹, 陈玉玲, 罗运, 李再东. 基于全同态加密的可验证多关键词密文检索方案[J]. 计算机工程, 2025, 51(4): 188-197.
[3]	徐红, 矫桂娥, 张文俊, 陈一民. 基于卷积神经网络的结构化非平衡数据分类算法[J]. 计算机工程, 2023, 49(2): 81-89.
[4]	吕芳, 汤丰赫, 黄俊恒, 王佰玲. 面向非平衡数据集的金融欺诈账户检测研究[J]. 计算机工程, 2021, 47(6): 312-320.
[5]	李秋贤, 周全兴, 王振龙, 丁红发, 潘齐欣. 基于隐私保护的可证明安全委托计算协议[J]. 计算机工程, 2021, 47(5): 131-137.
[6]	苗立志, 白瑞思蒙, 刘成良, 翟月昊. 面向非平衡数据的癌症患者生存预测分析[J]. 计算机工程, 2021, 47(12): 316-320.
[7]	张月平, 李茹, 王元龙, 柴清华, 武宇娟, 关勇. 汉语语篇零形式识别与填充方法研究[J]. 计算机工程, 2020, 46(3): 79-86.
[8]	刘文超, 潘峰, 杨晓元, 周潭平, 涂广升. 基于cuFHE的同态比较运算器[J]. 计算机工程, 2019, 45(9): 143-146,152.
[9]	牛壮,李凤莲,张雪英,樊宇宙,魏鑫. 改进欠抽样方法及其在非平衡数据集分类中的应用[J]. 计算机工程, 2019, 45(6): 218-224.
[10]	王彩芬,赵冰,刘超,成玉丹,许钦百. 基于整数多项式环的多对一全同态加密算法[J]. 计算机工程, 2019, 45(4): 130-135.
[11]	孙霓刚,朱浩然,陈宣任. 一种缩短公钥尺寸的整数上全同态加密方案[J]. 计算机工程, 2018, 44(9): 149-152.
[12]	王彩芬,成玉丹,刘超. 基于WSN的全同态数据加密聚合方案[J]. 计算机工程, 2018, 44(12): 190-195.
[13]	汤全有，马传贵. 针对全同态加密体制的反馈攻击[J]. 计算机工程, 2014, 40(6): 79-84.
[14]	赵程程, 杨亚涛, 李子臣, 阎晓姮. 基于McEliece公钥密码体制的盲签名算法[J]. 计算机工程, 2013, 39(6): 146-149.
[15]	彭永供, 邱桃荣, 林于渊, 黄海泉. 基于哈夫曼树的雷电数据采样算法[J]. 计算机工程, 2013, 39(5): 174-177,182.

选择文件类型/文献管理软件名称

选择包含的内容