A NEW MULTI-PARTY PRIVATE SET INTERSECTION PROTOCOL BASED on OPRFs

Abstract

In many crucial real-world applications, parties must jointly perform some secure multi-party computation (MPC) while keeping their inputs hidden from other parties. Private Set Intersection (PSI), the specific area of Multi-Party Computation, let the parties learn the intersection of their private data sets without sharing their secret data with others. For instance, a smartphone user downloads a messaging application, naturally, he wants to discover who are the other contacts that are using the same application. The naive and insecure solution is to send all contacts to the server to discover them. However, the user does not want to share his contacts with the application for privacy issues. To handle this, in recent years, companies and organizations start to use PSI to enhance privacy and security with a little cost of communication and computation. In this paper, we introduce a novel method to compute Private Set Intersection with multi parties where there are at least three or more parties participating in the protocol. By employing the Zero-Secret Sharing scheme and Oblivious Pseudo-Random Functions (OPRFs), parties securely calculate the intersection with computational and communication complexities which are both linear in the number of parties.

Keywords

• : Private set intersection
• multi-party private set intersection
• multi-party computation
• oblivious transfer
• oblivious pseudorandom function
• zero sharing

References

1. Pinkas, B., Schneider, T. and Zohner, M., “Faster private set intersection based on {OT} extension”, 23rd USENIX Security Symposium (USENIX Security 14), 2014, 797-812.
2. Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., and Trieu, N., “Practical multi-party private set intersection from symmetric-key techniques”, 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, 1257-1272.
3. Chase, M., and Miao, P.,“Private set intersection in the internet setting from lightweight oblivious PRF”, Annual International Cryptology Conference, 2020, 34-63.
4. Kolesnikov, V., Kumaresan, R., Rosulek, M., and Trieu, N., ”Efficient batched oblivious PRF with applications to private set intersection”, 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016, 818-829.
5. Pinkas, B., Schneider, T., Segev, G., and Zohner, M., “Phasing: Private set intersection using permutation-based hashing”, 24th USENIX Security Symposium (USENIX Security 15), 2015, 515-530.
6. Pinkas, B., Rosulek, M., Trieu, N. and Yanai, A., “PSI from PaXoS: fast, malicious private set intersection”, Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2020, 739-767.
7. Trieu, N., Shehata, K., Saxena, P., Shokri, R. and Song, D., “Epione: Lightweight contact tracing with strong privacy”. arXiv preprint arXiv:2004.13293., 2020.
8. Thomas, K., Pullman, J., Yeo, K., Raghunathan, A., Kelley, P. G., Invernizzi, L., ... and Bursztein, E., “Protecting accounts from credential stuffing with password breach alerting”, 28th USENIX Security Symposium (USENIX Security 19), 2019, 1556-1571.

9. Internet: K. Opsahl, R. Reitman, The Disconcerting Details: How Facebook Teams Up With Data Brokers to Show You Targeted Ads, https://www.eff.org/deeplinks/2013/04/disconcerting-details-how-facebook-teams-data-brokers-show-you-targeted-ads , 03.02.2022
10. Shen, L., Chen, X., Wang, D., Fang, B. and Dong, Y., “Efficient and private set intersection of human genomes”, 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2018, 761-764.
11. Freedman, M. J., Nissim, K. and Pinkas, B., “Efficient private matching and set intersection”. International Conference on the Theory and Applications of Cryptographic Techniques, 2004, 1-19.
12. De Cristofaro, E. and Tsudik, G., “Experimenting with fast private set intersection”, International Conference on Trust and Trustworthy, 2012, 55-73.
13. Sang, Y. and Shen, H., ”Privacy preserving set intersection based on bilinear groups”, The Thirty-first Australasian conference on Computer science, 2008, 47-54.
14. Huang, Y., Evans, D. and Katz, J., “Private set intersection: Are garbled circuits better than custom protocols?”, NDSS. 19th Annual Network & Distributed System Security Symposium, 2012.
15. Yao, A. C. C., “How to generate and exchange secrets”, 27th Annual Symposium on Foundations of Computer Science, 1986, 162-167.
16. Kiss, Á., Liu, J., Schneider, T., Asokan, N. and Pinkas, B., “Private Set Intersection for Unequal Set Sizes with Mobile Applications”, Proceedings on Privacy Enhancing Technologies, Vol. 4, 177-197, 2017.
17. Inbar, R., Omri, E. and Pinkas, B., “Efficient scalable multiparty private set-intersection via garbled bloom filters”. International Conference on Security and Cryptography for Networks, 2018, 235-252.
18. Debnath, S. K. and Dutta, R., “Secure and efficient private set intersection cardinality using bloom filter, International Conference on Information Security, 2015, 209-226.
19. Pinkas, B., Schneider, T., Tkachenko, O. and Yanai, A., “Efficient circuit-based PSI with linear communication”, Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2019, 122-153.
20. Freedman, M. J., Nissim, K. and Pinkas, B., “Efficient private matching and set intersection”. International Conference on the Theory and Applications of Cryptographic Techniques, 2004, 1-19.
21. Kissner, L. and Song, D., “Privacy-preserving set operations”, Annual International Cryptology Conference, 2005, 241-257.
22. Hazay, C. and Venkitasubramaniam, M., “Scalable multi-party private set-intersection”. IACR International Workshop on Public Key Cryptography, 2017, 175-203.
23. Goldreich O., "Secure multi-party computation", Manuscript. Preliminary version 78, 1998.
24. Miyaji, A., Nakasho, K. and Nishida, S., “Privacy-preserving integration of medical data”, Journal of Medical Systems, Vol. 41(3), 1-10, 2017.
25. Binu V. P. and Sreekumar A., "Simple and efficient secret sharing schemes for sharing data and image.", International Journal of Computer Science and Information Technologies, Vol. 6 (1), 404-409, 2015.
26. M. O. Rabin, "How To Exchange Secrets with Oblivious Transfer." IACR Eprint archive 2005/187, 2005.
27. Kolesnikov, V. and Kumaresan, R., “Improved OT extension for transferring short secrets”, Annual Cryptology Conference, 2013, 54-70.
28. Pinkas, B., Rosulek, M., Trieu, N. and Yanai, A., “SpOT-light: lightweight private set intersection from sparse OT extension”, Annual International Cryptology Conference, 2019, 401-431.
29. Alireza K., Mohajeri J. and Mahmoud S., "Efficient scalable multi-party private set intersection using oblivious prf", International Workshop on Security and Trust Management, 2021, 81-99.
30. Cheon, J. H., Jarecki, S. and Seo, J. H., “Multi-party privacy-preserving set intersection with quasi-linear complexity”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 95(8), 1366-1378, 2012.
31. Ishai, Y., Kilian, J., Nissim, K. and Petrank, E.. “Extending oblivious transfers efficiently”, Annual International Cryptology Conference, 2013, 145-161.
32. Internet: P. Rindal, A fast, portable, and easy to use Oblivious Transfer Library, https://github.com/osu-crypto/libOTe, 01.02.2022.