Set intersection protocol with privacy preservation

   The Private Set Intersection Protocol (PSI) is one of the fundamental primitives of secure multi-party computations. This primitive allows several parties who do not trust each other to work together to calculate the intersection of their secret sets without disclosing additional information about these sets. This allows users to jointly analyze data without revealing confidential information to each other. This paper describes a new protocol for the intersection of private sets for 3 or more participants. The protocol works in a network with a “ring” type topology which minimizes the number of necessary communication channels between users. The protocol is based on the idea of conditional zero-sharing which allows using a secret sharing scheme to determine whether an element of the set belongs to all users or not. To evaluate the performance of the proposed solution, a software implementation of the protocol in C++ is proposed. The security of the developed protocol for three or more users is shown, provided that users do not conspire with each other for an “Honest-But-Curious” attacker model. Proposed model implies that the attacker is one of the protocol participants who performs the protocol correctly, but can analyse the information obtained during this process to gain benefits. The security of the protocol is based only on the assumption that the attacker lacks information to obtain any useful data from the messages received during the protocol execution. Thus, this protocol is information-theoretically secure. The presented protocol can be used for confidential data analysis, for example, when several companies exchange information about common customers. The protocol allows three users to find the intersection of sets of sizes 106 in about 42 s. In the present implementation, it is possible to add multithreading or transfer large matrix calculations from the processor to the GPU.

1. Evans D., Kolesnikov V., Rosulek M. A pragmatic introduction to secure multi-party computation. Foundations and Trends in Privacy and Security, 2018, vol. 2, no. 2-3, pp. 70–246. doi: 10.1561/3300000019

2. Falzon F., Markatou E.A. Re-visiting Authorized Private Set Intersection: a new privacy-preserving variant and two protocols. Proceedings on Privacy Enhancing Technologies, 2025, vol. 1, pp. 792–807. doi: 10.56553/popets-2025-0041

3. Sun Z. Efficient multiparty private set intersection protocol based on function secret sharing. Proceedings of SPIE, 2024, vol. 13175, pp. 1317505. doi: 10.1117/12.3031902

4. Debnath S.K. Provably Secure Private Set Intersection With Constant Communication Complexity. International Journal of Cyber Warfare and Terrorism, 2019, vol. 9, no. 2, pp. 39–64. doi: 10.4018/IJCWT.2019040104

5. Ben-Efraim A., Nissenbaum O., Omri E., Paskin-Cherniavsky A. Psimple: Practical multiparty maliciously-secure private set intersection. Proc. of the ACM on Asia Conference on Computer and Communications Security, 2022, pp. 1098–1112. doi: 10.1145/3488932.3523254

6. Cheon J.H., Jarecki S., Seo J.H. Multi-party privacy-preserving set intersection with quasi-linear complexity. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012, vol. E95.A, no. 8, pp. 1366–1378. doi: 10.1587/transfun.e95.a.1366

7. Bay A. New threshold private set intersection protocols. Mugla Journal of Science and Technology, 2024, vol. 10, no. 1, pp. 51–60. doi: 10.22531/muglajsci.1387499

8. Gao J., Trieu N., Yanai A. Multiparty private set intersection cardinality and its applications. Proceedings on Privacy Enhancing Technologies, 2024, vol. 2024, no. 2, pp. 73–90. doi: 10.56553/popets-2024-0041

9. Faber S. Variants of privacy preserving set intersection and their practical applications. Dissertation for the degree of PhD in Computer Science. Irvine, University of California, 2016, 192 p.

10. LiY., Jiang Z.L., Yao L., Wang X., Yiu S.M., Huang Z. Outsourced privacy-preserving C4.5 decision tree algorithm over horizontally and vertically partitioned dataset among multiple parties. Cluster Computing, 2019, vol. 22, suppl. 1, pp. 1581–1593. doi: 10.1007/s10586-017-1019-9

11. Shen L., Chen X., Wang D., Fang B., Dong Y. Efficient and private set intersection of human genomes. Proc. of the IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2018, pp. 761–764. doi: 10.1109/bibm.2018.8621291

12. Aziz M.M.A., Alhadidi D., Mohammed N. Secure approximation of edit distance on genomic data. BMC Medical Genomics, 2017, vol. 10, pp. 55–67. doi: 10.1186/s12920-017-0279-9

13. Hasan H.A., Al-Layla H.F., Ibraheem F.N. A review of hash function types and their applications. Wasit Journal of Computer and Mathematics Science, 2022, vol. 1, no. 3, pp. 75–88. doi: 10.31185/wjcm.52

14. Casacuberta S., Hesse J., Lehmann A. SoK: oblivious pseudorandom functions. Proc. of the IEEE 7^th European Symposium on Security and Privacy (EuroS&P), 2022, pp. 625–646. doi: 10.1109/eurosp53844.2022.00045

15. Bay A., Kayan A. A new multi-party private set intersection protocol based on OPRFs. Mugla Journal of Science and Technology, 2022, vol. 8, no. 1, pp. 69–75. doi: 10.22531/muglajsci.1075788

16. Chase M., Miao P. Private set intersection in the internet setting from lightweight oblivious PRF. Lecture Notes in Computer Science, 2020, vol. 12172, pp. 34–63. doi: 10.1007/978-3-030-56877-1_2

17. Kavousi A., Mohajeri J., Salmasizadeh M. Efficient scalable multiparty private set intersection using oblivious PRF. Lecture Notes in Computer Science, 2021, vol. 13075, pp. 81–99. doi: 10.1007/978-3-030-91859-0_5

18. Pinkas B., Schneider T., Zohner M. Faster private set intersection based on OT extension. Proc. of the 23^rd Usenix Security Symposium, 2014, pp. 797–812.

19. Tang Y., Guo M., Huo Y., Zhao Z., Yu J., Qin B. An MLWE-based cut-and-choose oblivious transfer protocol. Entropy, 2024, vol. 26, no. 9, pp. 793. doi: 10.3390/e26090793

20. Kolesnikov V., Matania N., Pinkas B., Rosulek M., Trieu N. Practical multiparty private set intersection from symmetric-key techniques. Proc. of the ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1257–1272. doi: 10.1145/3133956.3134065