ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2025-25-4-703-709ntv-495Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEПротокол пересечения множеств с сохранением конфиденциальностиSet intersection protocol with privacy preservationhttps://orcid.org/0000-0002-0856-2249ИогансонИ. Д.IogansonI. D.

Иван Дмитриевич Иогансон, аспирант

197101; Санкт-Петербург

sc 57883504800

Ivan D. Ioganson, PhD Student

197101; Saint Petersburg

sc 57883504800

ivan.ioganson@yandex.ruУниверситет ИТМОРоссияITMO UniversityRussian Federation202529082025254703709Copyright © Иогансон И.Д., 20252025Иогансон И.Д.Ioganson I.D.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/495   Введение

   Введение. Протокол пересечения закрытых множеств (Private Set Intersection, PSI) является одним из фундаментальных примитивов конфиденциальных вычислений. Данный примитив позволяет нескольким сторонам, которые не доверяют друг другу, совместными усилиями вычислить пересечение их секретных множеств без разглашения при этом дополнительной информации об этих множествах. Это позволяет пользователям совместно проводить анализ данных без раскрытия конфиденциальной информации друг другу.

   Метод

   Метод. В работе представлен новый протокол пересечения закрытых множеств для трех и более участников. Протокол работает в сети с топологией типа «кольцо». Это минимизирует количество необходимых каналов связи между пользователями. Протокол основан на идее условного разделения нуля, позволяющей использовать схему разделения секрета для определения принадлежности элемента множества всем пользователям. Для оценки быстродействия нового решения предложена программная реализация протокола на языке С++.

   Основные результаты

   Основные результаты. Показана безопасность разработанного протокола для трех и более пользователей при условии, что пользователи не будут сговариваться друг с другом для «Honest-But-Curious» модели злоумышленника. Предложенная модель подразумевает, что злоумышленником является один из участников протокола, который корректно выполняет протокол, но может анализировать полученную в ходе этого информацию для извлечения выгоды. Безопасность протокола основывается только на предположении о недостатке у злоумышленника информации для получения каких-либо полезных данных из полученных во время выполнения протокола сообщений. Таким образом, этот протокол обладает информационно-теоретической стойкостью.

   Обсуждение

   Обсуждение. Представленный протокол может быть использован для конфиденциального анализа данных, например при обмене несколькими компаниями информацией об общих клиентах. Протокол позволяет трем пользователям найти пересечение множеств размера 106 примерно за 42 с. В настоящей реализации существует возможность добавления многопоточности или перенос вычислений больших матриц с процессора на графический ускоритель.

   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.

конфиденциальные вычислениякриптографический протоколпересечение закрытых множествразделение секретаsecure multi-party computationscryptographic protocolprivate set intersectionsecret sharingРабота выполнена в рамках государственного задания (проект № FSER-2025-0003)The research was carried out within the State Assignment (project No. FSER-2025-0003)ReferencesEvans D., Kolesnikov V., Rosulek M. A pragmatic introduction to secure multi-party computation // Foundations and Trends in Privacy and Security. 2018. V. 2. N 2-3. P. 70–246. doi: 10.1561/3300000019Evans 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/3300000019Falzon F., Markatou E.A. Re-visiting Authorized Private Set Intersection: a new privacy-preserving variant and two protocols // Proceedings on Privacy Enhancing Technologies. 2025. V. 1. P. 792–807. doi: 10.56553/popets-2025-0041Falzon 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-0041Sun Z. Efficient multiparty private set intersection protocol based on function secret sharing // Proceedings of SPIE. 2024. V. 13175. P. 1317505. doi: 10.1117/12.3031902Sun Z. Efficient multiparty private set intersection protocol based on function secret sharing. Proceedings of SPIE, 2024, vol. 13175, pp. 1317505. doi: 10.1117/12.3031902Debnath S.K. Provably Secure Private Set Intersection With Constant Communication Complexity // International Journal of Cyber Warfare and Terrorism. 2019. V. 9. N 2. P. 39–64. doi: 10.4018/IJCWT.2019040104Debnath 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.2019040104Ben-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. P. 1098–1112. doi: 10.1145/3488932.3523254Ben-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.3523254Cheon 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. V. E95.A. N 8. P. 1366–1378. doi: 10.1587/transfun.e95.a.1366Cheon 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.1366Bay A. New threshold private set intersection protocols // Mugla Journal of Science and Technology. 2024. V. 10. N 1. P. 51–60. doi: 10.22531/muglajsci.1387499Bay 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.1387499Gao J., Trieu N., Yanai A. Multiparty private set intersection cardinality and its applications // Proceedings on Privacy Enhancing Technologies. 2024. V. 2024. N 2. P. 73–90. doi: 10.56553/popets-2024-0041Gao 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-0041Faber 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.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.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. V. 22. Suppl. 1. P. 1581–1593. doi: 10.1007/s10586-017-1019-9LiY., 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-9Shen 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. P. 761–764. doi: 10.1109/bibm.2018.8621291Shen 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.8621291Aziz M.M.A., Alhadidi D., Mohammed N. Secure approximation of edit distance on genomic data // BMC Medical Genomics. 2017. V. 10. P. 55–67. doi: 10.1186/s12920-017-0279-9Aziz 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-9Hasan 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. V. 1. N 3. P. 75–88. doi: 10.31185/wjcm.52Hasan 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.52Casacuberta S., Hesse J., Lehmann A. SoK: oblivious pseudorandom functions // Proc. of the IEEE 7<sup>th</sup> European Symposium on Security and Privacy (EuroS&P). 2022. P. 625–646. doi: 10.1109/eurosp53844.2022.00045Casacuberta S., Hesse J., Lehmann A. SoK: oblivious pseudorandom functions. Proc. of the IEEE 7<sup>th</sup> European Symposium on Security and Privacy (EuroS&P), 2022, pp. 625–646. doi: 10.1109/eurosp53844.2022.00045Bay A., Kayan A. A new multi-party private set intersection protocol based on OPRFs // Mugla Journal of Science and Technology. 2022. V. 8. N 1. P. 69–75. doi: 10.22531/muglajsci.1075788Bay 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.1075788Chase M., Miao P. Private set intersection in the internet setting from lightweight oblivious PRF // Lecture Notes in Computer Science. 2020. V. 12172. P. 34–63. doi: 10.1007/978-3-030-56877-1_2Chase 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_2Kavousi A., Mohajeri J., Salmasizadeh M. Efficient scalable multiparty private set intersection using oblivious PRF // Lecture Notes in Computer Science. 2021. V. 13075. P. 81–99. doi: 10.1007/978-3-030-91859-0_5Kavousi 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_5Pinkas B., Schneider T., Zohner M. Faster private set intersection based on OT extension // Proc. of the 23<sup>rd</sup> Usenix Security Symposium. 2014. P. 797–812.Pinkas B., Schneider T., Zohner M. Faster private set intersection based on OT extension. Proc. of the 23<sup>rd</sup> Usenix Security Symposium, 2014, pp. 797–812.Tang Y., Guo M., Huo Y., Zhao Z., Yu J., Qin B. An MLWE-based cut-and-choose oblivious transfer protocol // Entropy. 2024. V. 26. N 9. P. 793. doi: 10.3390/e26090793Tang 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/e26090793Kolesnikov 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. P. 1257–1272. doi: 10.1145/3133956.3134065Kolesnikov 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

The authors declare that there are no conflicts of interest present.