Private Set Intersection Cardinality Protocol for Supporting Set  Dynamic Updating

Journal of Information Security Reserach ›› 2025, Vol. 11 ›› Issue (12): 1099-.

Private Set Intersection Cardinality Protocol for Supporting Set Dynamic Updating

Dong Xuanyan, Gao Yanan, Guan Cong, Wang Juntian, Pang Xiaoqiong, and Yu Xiaoqing

(School of Computer Science and Technology, North University of China, Taiyuan 030051)

Online:2025-12-12 Published:2025-12-03

支持集合动态更新的隐私集合交集基数协议

董轩言高亚楠关聪王俊添庞晓琼郁晓庆

(中北大学计算机科学与技术学院太原030051)

通讯作者: 庞晓琼博士，副教授.主要研究方向为信息安全与密码学. xqpang@nuc.edu.cn
作者简介:董轩言硕士研究生.主要研究方向为信息安全与密码学. 1473798150@qq.com 高亚楠硕士.主要研究方向为信息安全与密码学. 18863922670@163.com 关聪硕士研究生.主要研究方向为信息安全与密码学. 1466079620@qq.com 王俊添硕士研究生.主要研究方向为信息安全与密码学. 2249056978@qq.com 庞晓琼博士，副教授.主要研究方向为信息安全与密码学. xqpang@nuc.edu.cn 郁晓庆博士，副教授.主要研究方向为网络安全、计算机视觉. yuxiaoqing2006@163.com

基金资助:

山西省重点研发计划项目(202102010101011)；研究生教育创新计划项目(2024AL20)

Abstract

Abstract: The private set intersection cardinality (PSICA) enables each participant to obtain only the intersection size while keeping other information private. For instance, when it comes to measuring the ad conversion rates, the number of ad viewers on the ad platform is much smaller than the number of service subscribers of the service provider, and the set owned by the service provider is constantly changing. However, the majority of the existing PSICA protocols do not suppport the dynamic updating of sets. To this end, this paper proposes a PSICA protocol based on switched encryption and dynamic Bloom filters for nonequilibrium scenarios and supports dynamic updating of ensembles. The security proof shows that the protocol can be proven to be secure under the random oracle model. The performance analysis and simulation experimental results indicate that the protocol is able to achieve the intersection base computation with acceptable overhead and the misclassification rate of the dynamic Bloom filter is maintained at a low level.

Key words: private set intersection cardinality, dynamic Bloom filter, commutative encryption, set dynamic updating, unbalanced

摘要： 隐私集合交集基数(private set intersection cardinality, PSICA)协议允许各参与方仅获知交集大小而不暴露其他信息.以测量广告转换率为例，广告平台的广告浏览者数量远少于服务提供商的服务订阅者数量，且服务提供商的用户集合不断变化.然而，大多数现有PSICA协议不支持集合的动态更新.为此，提出了一种基于交换加密和动态布隆过滤器的PSICA协议，适用于非平衡场景，并支持集合动态更新.安全性证明表明，该协议在随机谕言机模型下是可证明安全的；性能分析和仿真实验结果表明，该协议能够以可接受的开销实现交集基数的计算，且动态布隆过滤器的误判率控制在较低水平.

关键词: 隐私集合交集基数, 动态布隆过滤器, 交换加密, 集合动态更新, 非平衡

CLC Number:

TP309

董轩言, 高亚楠, 关聪, 王俊添, 庞晓琼, 郁晓庆, . 支持集合动态更新的隐私集合交集基数协议[J]. 信息安全研究, 2025, 11(12): 1099-.

References

［1］钱文君, 沈晴霓, 吴鹏飞, 等. 大数据计算环境下的隐私保护技术研究进展［J］. 计算机学报, 2022, 45(4): 669701［2］Narayanan A, Thiagarajan N, Lakhani M, et al. Location privacy via private proximity testing［COL］ Proc of the 18th Symp on Network and Distributed System Security(NDSS 2011). 2011 ［20251108］. https:crypto.stanford.edu~dabopubspaperslocpriv.pdf［3］Pinkas B, Schneider T, Segev G, et al. Phasing: Private set intersection using permutationbased hashing［C］ Proc of the 24th USENIX Security Symposium (USENIX Security 15). Berkeley, CA: USENIX Association, 2015: 515530［4］Baldi P, Baronio R, Cristofaro E D, et al. Countering GATTACA: Efficient and secure testing of fullysequenced human genomes［C］ Proc of the 18th ACM Conf on Computer and Communications Security. New York: ACM, 2011: 691702［5］Ion M, Kreuter B, Nergiz A E, et al. On deploying secure computing: Private intersectionsumwithcardinality［C］ Proc of the 2020 IEEE European Symp on Security and Privacy (EuroS&P). Piscataway, NJ: IEEE, 2020: 370389［6］Gao J, Trieu N, Yanai A. Multiparty private set intersection cardinality and its applications［J］. Proceedings on Privacy Enhancing Technologies, 2024, 41(2): 7390［7］Agrawal R, Evfimievski A, Srikant R. Information sharing across private databases［C］ Proc of the 2003 ACM SIGMOD Int Conf on Management of Data(SIGMOD’03). New York: ACM, 2003: 8697［8］Hohenberger S, Weis S A. Honestverifier private disjointness testing without random oracles［C］ Proc of Int Workshop on Privacy Enhancing Technologies. Berlin: Springer, 2006: 277294［9］Many D, BurkhartM, Dimitropoulos X. Fast private set operations with sepia, TIKReport NO.345,2012［ROL］.［20251120］. https:tikold.ee.ethz.chfile0fb77d633e8f0 ca674cd79d1a6bb03e3TIKReport345.pdf［10］Cristofaro E D, Gasti P, Tsudik G. Fast and private computation of cardinality of set intersection and union［C］ Proc of the Int Conf on Cryptology and Network Security. Berlin: Springer, 2012: 218231［11］Debnath S K, Dutta R. Secure and efficient private set intersection cardinality using Bloom filter［C］ Proc of the Int Conf on Information Security. Berlin: Springer, 2015: 209226［12］Dong C, Loukides G. Approximating private set unionintersection cardinality with logarithmic complexity［J］. IEEE Trans on Information Forensics and Security, 2017, 12(11): 27922806［13］Egert R, Fischlin M, Gens D, et al. Privately computing setunion and setintersection cardinality via Bloom filters［C］ Proc of the 20th Australasian Conf on Information Security and Privacy. Berlin: Springer, 2015: 413430［14］Ashok V G, Mukkamala R. A scalable and efficient privacy preserving global itemset support approximation using Bloom filters［C］ Proc of IFIP Annual Conf on Data and Applications Security and Privacy. Berlin: Springer, 2014: 382389［15］Lv S, Ye J, Yin S, et al. Unbalanced private set intersection cardinality protocol with low communication cost［J］. Future Generation Computer Systems, 2020, 102: 10541061［16］Duong T, Phan D H, Trieu N. Catalic: Delegated PSI cardinality with applications to contact tracing［C］ Proc of the Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2020: 870899［17］Li H, Gao Y. Efficient private set intersection cardinality protocol in the reverse unbalanced setting［C］ Proc of the Int Conf on Information Security. Berlin: Springer, 2022: 2039［18］Tu B, Zhang X, Bai Y, et al. Fast unbalanced private computing on (labeled) set intersection with cardinality［JOL］. Cryptology ePrint Archive, 2023 ［20251108］. https:eprint.iacr.org20231015［19］Wu M, Yuen T H. Efficient unbalanced private set intersection cardinality and userfriendly privacypreserving contact tracing［C］ Proc of the 32nd USENIX Security Symp (USENIX Security 23). Berkeley, CA: USENIX Association, 2023: 283300［20］Guo D, Wu J, Chen H, et al. The dynamic Bloom filters［J］. IEEE Trans on Knowledge and Data Engineering, 2010, 22(1): 120133［21］Bloom B H. Spacetime tradeoffs in hash coding with allowable errors［J］. Communications of the ACM, 1970, 13(7): 422426［22］王瀚橙, 戴海鹏, 陈树森, 等. 过滤器数据结构研究综述［J］. 计算机科学, 2024, 51(1): 3540［23］Huang K, Tso R. A commutative encryption scheme based on ElGamal encryption［C］ Proc of the 2012 Int Conf on Information Security and Intelligent Control. Piscataway, NJ: IEEE, 2012: 156159