Протокол пересечения множеств с сохранением конфиденциальности K-sparse энкодер для эффективного информационного поиска

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

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

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

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

1. Evans 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/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. V. 1. P. 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. V. 13175. P. 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. V. 9. N 2. P. 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. P. 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. V. E95.A. N 8. P. 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. V. 10. N 1. P. 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. V. 2024. N 2. P. 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. V. 22. Suppl. 1. P. 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. P. 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. V. 10. P. 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. V. 1. N 3. P. 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. P. 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. V. 8. N 1. P. 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. V. 12172. P. 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. V. 13075. P. 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. P. 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. V. 26. N 9. P. 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. P. 1257–1272. doi: 10.1145/3133956.3134065