Set intersection protocol with privacy preservation

Ivan D. Ioganson

2025 , VOLUME 25, NUMBER 4 ( july-august )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

doi: 10.17586/2226-1494-2025-25-4-703-709

Set intersection protocol with privacy preservation

I. D. Ioganson

Read the full article

Article in Russian

For citation:

Ioganson I.D. Set intersection protocol with privacy preservation. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2025, vol. 25, no. 4, pp. 703–709 (in Russian). doi: 10.17586/2226-1494-2025-25-4-703-709

Abstract

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.

Keywords: secure multi-party computations, cryptographic protocol, private set intersection, secret sharing

Acknowledgements. The research was carried out within the State Assignment (project No. FSER-2025-0003).

References

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. http://dx.doi.org/10.1561/3300000019
Falzon F., Markatou E.A. Re-visiting Authorized Private Set Intersection: a new privacy-preserving variant and two protocols. Proceedingson Privacy Enhancing Technologies, 2025, vol. 1, pp. 792–807. https://doi.org/10.56553/popets-2025-0041
Sun Z. Efficient multiparty private set intersection protocol based on function secret sharing. Proceedings of SPIE,2024, vol. 13175, pp. 1317505. https://doi.org/10.1117/12.3031902
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. https://doi.org/10.4018/IJCWT.2019040104
Ben-Efraim A., Nissenbaum O., Omri E., Paskin-Cherniavsky A. Psimple: Practical multiparty maliciously-secure private set intersection. Proc.of the ACM on Asia Conferenceon Computerand Communications Security, 2022, pp. 1098–1112. https://doi.org/10.1145/3488932.3523254
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. https://doi.org/10.1587/transfun.e95.a.1366
Bay A. New threshold private set intersection protocols. Mugla Journal of Science and Technology, 2024, vol. 10, no. 1, pp. 51–60. https://doi.org/10.22531/muglajsci.1387499
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. https://doi.org/10.56553/popets-2024-0041
Faber S. Variants of privacy preserving set intersection and their practical applications. Dissertation for the degree of PhDin Computer Science. Irvine,University of California, 2016, 192 p.
Li Y., Jiang Z.L., Yao L.,WangX., 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. https://doi.org/10.1007/s10586-017-1019-9
ShenL., 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. https://doi.org/10.1109/bibm.2018.8621291
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. https://doi.org/10.1186/s12920-017-0279-9
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. https://doi.org/10.31185/wjcm.52
CasacubertaS., HesseJ., LehmannA. SoK: oblivious pseudorandom functions. Proc. of theIEEE7^th EuropeanSymposiumonSecurityandPrivacy(EuroS&P), 2022, pp. 625–646. https://doi.org/10.1109/eurosp53844.2022.00045
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. https://doi.org/10.22531/muglajsci.1075788
ChaseM., MiaoP. Private set intersection in the internet setting from lightweight oblivious PRF. Lecture Notes in Computer Science, 2020, vol. 12172, pp. 34–63. https://doi.org/10.1007/978-3-030-56877-1_2
Kavousi A., Mohajeri J., Salmasizadeh M. Efficient scalable multi-party private set intersection using oblivious PRF. Lecture Notes in Computer Science,2021, vol. 13075, pp. 81–99. https://doi.org/10.1007/978-3-030-91859-0_5
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.
TangY., 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. https://doi.org/10.3390/e26090793
Kolesnikov V., Matania N., Pinkas B., Rosulek M., Trieu N. Practical multi-party private set intersection from symmetric-key techniques. Proc. of the ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1257–1272. https://doi.org/10.1145/3133956.3134065

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License