NEW THRESHOLD PRIVATE SET INTERSECTION PROTOCOLS

Year 2024, , 51 - 60, 30.06.2024

Aslı Bay

https://doi.org/10.22531/muglajsci.1387499

Abstract

With the rising amount of digital technologies that we use on a daily basis, it is more important than ever to handle and process private data securely. Research and academic communities are becoming increasingly interested in multi-party computation, with a focus on the field of Private Set Intersection (PSI). In this regard, this work introduces a novel technique that successfully converts the Cid-Davidson Private Set Intersection protocol into a Threshold Private Set Intersection. It achieves this conversion by introducing two new protocols, TPSI-1 and TPSI-2, and utilizing two previously developed methodologies while the Reed-Solomon codes and the Shamir-secret sharing scheme are the foundations of TPSI-1, whereas Secure Comparison Protocols serve as the foundation for TPSI-2. Specifically, our suggested protocols perform better asymptotically than previous threshold PSI protocols because they have a fixed number of rounds and linear communication and computation complexity that increase with data set size. This study adds to the continuous effort to strengthen the security and effectiveness of private data calculations, highlighting how safe data processing is changing in an era where digital technologies are ingrained in every aspect of our lives.

Keywords

Homomorphic Encryption, Multi-party Computation, Private Set Intersection, Secure Comparison Protocols, Secret Sharing

YENİ EŞİKLİ ÖZEL KÜME KESİŞİM PROTOKOLLERİ

Abstract

Günlük olarak kullandığımız dijital teknolojilerin miktarının artmasıyla birlikte, özel verilerin güvenli bir şekilde ele alınması ve işlenmesi her zamankinden daha önemlidir. Araştırma ve akademik topluluklar, Özel Küme Kesişimi (PSI) alanına odaklanarak çok partili hesaplamaya giderek daha fazla ilgi duymaktadır. Bu bağlamda, bu çalışma Cid-Davidson Özel Küme Kesişimi protokolünü başarılı bir şekilde Eşik Özel Küme Kesişimi'ne dönüştüren yeni bir teknik sunmaktadır. Bu dönüşümü, TPSI-1 ve TPSI-2 olmak üzere iki yeni protokol sunarak ve daha önce geliştirilmiş olan iki metodolojiyi kullanarak gerçekleştirmektedir, Reed-Solomon kodları ve Shamir-gizli paylaşım şeması TPSI-1'in temellerini oluştururken, Güvenli Karşılaştırma Protokolleri TPSI-2'nin temelini oluşturmaktadır. Özellikle, önerdiğimiz protokoller, sabit sayıda tura ve veri kümesi boyutuyla artan doğrusal iletişim ve hesaplama karmaşıklığına sahip oldukları için asimptotik olarak önceki eşik PSI protokollerinden daha iyi performans göstermektedir. Bu çalışma, özel veri hesaplamalarının güvenliğini ve etkinliğini güçlendirmeye yönelik sürekli çabalara katkıda bulunmakta ve dijital teknolojilerin hayatımızın her alanına girdiği bir çağda güvenli veri işlemenin nasıl değiştiğini vurgulamaktadır

Keywords

Homomorfik Şifreleme, Çok Taraflı Hesaplama, Özel Küme Kesişimi, Güvenli Karşılaştırma Protokolleri, Gizli Paylaşım

References

• “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, 2013. Accessed: 2021-11-25.
• Hallgren, P., Orlandi, C. and Sabelfeld, A., “Privatepool: Privacy-preserving ridesharing,” in 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 276–291, 2017.
• Sherif, A. B. T., Rabieh, K., Mahmoud, . M. E. A. and Liang, X., “Privacy-preserving ride sharing scheme for autonomous vehicles in big data era,” IEEE Internet of Things Journal, vol. 4, no. 2, pp. 611–618, 2017.
• Zhao, Y. and. Chow, S. S. M, “Can you find the one for me? privacy-preserving matchmaking via threshold psi.” Cryptology ePrint Archive, Report 2018/184, 2018. https://ia.cr/2018/ 184.
• Yao, A. C.-C. , “Protocols for secure computations (extended abstract),” in FOCS, pp. 160–164, IEEE Computer Society, 1982.
• Freedman, M. J. , Nissim, K. and Pinkas, B. , “Efficient private matching and set intersection,” in Advances in Cryptology- EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings(C.Cachin and J. Camenisch, eds.), vol. 3027 of Lecture Notes in Computer Science, pp. 1–19, Springer, 2004.
• Kissner, L. and Song, D. X., “Privacy-preserving set operations,” in Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings (V. Shoup, ed.), vol. 3621 of Lecture Notes in Computer Science, pp. 241–257, Springer, 2005.
• Camenisch, J., and Zaverucha, G. M., “Private intersection of certified sets,” in Financial Cryptography and Data Security (R. Dingledine and P. Golle, eds.), (Berlin, Heidelberg), pp. 108–127, Springer Berlin Heidelberg, 2009.
• Hazay, C., and Lindell, Y., “Efficient protocols for set intersection and pattern matching with Security against malicious and covert adversaries,” in Theory of Cryptography (R. Canetti, ed.),(Berlin, Heidelberg), pp. 155–175, Springer Berlin Heidelberg, 2008.
• Jarecki, S. and Liu, X., “Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection,” in Theory of Cryptography (O. Reingold, ed.), (Berlin, Heidelberg), pp. 577–594, Springer Berlin Heidelberg, 2009.
• Debnath, S. K. and Dutta, R.,“Towards fair mutual private set intersection with linear complexity,” Security and Communication Networks, vol. 9, no. 11, pp. 1589–1612, 2016.
• Burkhart, M. and Fontas, X. D. , “Fast private set operations with sepia,” 2012.
• Kerschbaum, F., “Outsourced private set intersection using homomorphic encryption,” in 7th ACM Symposium on Information, Compuer and Communications Security, ASIACCS ’12, Seoul, Korea, May 2-4, 2012 (H. Y. Youm and Y. Won, eds.), pp. 85–86, ACM, 2012.
• Goldwasser S. and Micali, S.,“Probabilistic encryption,” Journal of Computer and System Sciences vol. 28, no. 2, pp. 270–299, 1984.
• Dong, C., Chen, L. and Wen, Z. , “When private set intersection meets big data: an efficient and scalable protocol,” in 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013 (A. Sadeghi, V. D. Gligor, and M. Yung, eds.), pp. 789–800, ACM, 2013.
• Kiss, A., 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. 2017, no. 4, pp. 177–197, 2017.
• Debnath, S. K. and. Dutta, R ,“Efficient private set intersection cardinality in the presence of ma licious adversaries,” in Provable Security (M.-H. Au and A. Miyaji, eds.), (Cham), pp. 326–339, Springer International Publishing, 2015.
• Zhang, X, Zhu, H., Chen, M., Sun, M. , Liao, X. and Hu, L., “Outsourcing set intersection compu- tation based on bloom filter for privacy preservation in multimedia processing,” Secur. Commun. Networks, Hindawi, vol., 2018.
• Ruan, O., Wang, Z., Mi, J. and Zhang, M., “New approach to set representation and practical private set-intersection protocols,” IEEE Access, vol. 7, pp. 64897–64906, 2019.
• Huang, Y.,Evans, D. and Katz, J. “Private set intersection: Are garbled circuits better than custom protocols?,” in 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012, The Internet Society, 2012.
• Pinkas, B. , Schneider, T., Segev, G. and Zohner, M., “Phasing: Private set intersection using permutation-based hashing,” in 24th USENIX Security Symposium, USENIX Security 15, Washington, D.C., USA, August 12-14, 2015. (J. Jung and T. Holz, eds.), pp. 515–530, USENIX Association, 2015.
• Pinkas, B. , Schneider, T. , Weinert, C. and Wieder, U. , “Efficient circuit-based psi via cuckoo hashing,” in Advances in Cryptology – EUROCRYPT 2018 (J. B. Nielsen and V. Rijmen, eds.), (Cham), pp. 125–157, Springer International Publishing, 2018.
• Ruan, O. and Mao, H., “Efficient private set intersection using point-value polynomial representation,” Security and Communication Networks, vol. 2020, pp. 8890677:1–8890677:12, 2020.
• Ghosh, S. and Nilges, T., “An algebraic approach to maliciously secure private set intersection,” vol. 11478, pp. 154–185, 2019.
• Zhao, Y. and Chow, S. S. M. ,“Are you the one to share? secret transfer with access structure,” Proc. Priv. Enhancing Technol., vol. 2017, no. 1, pp. 149–169, 2017.
• Ghosh, S. And Nilges, T. ,“An algebraic approach to maliciously secure private set intersection.” Cryptology ePrint Archive, Report 2017/1064, 2017.
• Zhang, E. , Chang, J. and Li, Y. ,“Efficient threshold private set intersection,” IEEE Access, vol.9, pp. 6560–6570, 2021.
• Chandran, N., Gupta, D., and Shah, Akash, “Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF”, 22nd Privacy Enhancing Technologies Symposium (PETS 2022), 2022.
• Karakoç, F., Küpçü, A., “Enabling Two-Party Secure Computation on Set Intersection” IACR Cryptol. ePrint Arch. 2023: 609, 2023.
• Bay, A., Erkin, Z., Hoepman, J., Samardjiska, S. and Vos, J., “Practical multi-party private set intersection protocols,” IEEE Trans. Inf. Forensics Secur., vol. 17, pp. 1–15, 2022.
• Zhao, Y., and Chow, S. S., “Can you find the one for me?,” in Proceedings of the 2018 Workshop on Privacy in the Electronic Society, WPES’18, (New York, NY, USA), p. 54–65, Association for Computing Machinery, 2018.
• Bloom, B. H., “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, vol. 13, pp. 422–426, 1970.
• Bose, P. , Guo, H. , Kranakis, E. , Maheshwari, A. , Morin, P., Morrison, J., Smid, M. H. M. and. Tang, Y. “On the false-positive rate of bloom filters,” Inf. Process. Lett., vol. 108, no. 4, pp. 210–213, 2008.
• Davidson, A. and Cid, C., “An efficient toolkit for computing private set operations,” in Information Security and Privacy - 22nd Australasian Conference, ACISP 2017, Auckland, New Zealand, July 3-5, 2017, Proceedings, Part II (J. Pieprzyk and S. Suriadi, eds.), vol. 10343 of Lecture Notes in Computer Science, pp. 261–278, Springer, 2017.
• Shamir, A., “How to share a secret.,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979.
• Reed, I. S. and Solomon, “ G., Polynomial codes over certain finite fields,” vol. 8, no. 2, pp. 300–304, 1960.
• Gao, S. , “A New Algorithm for Decoding Reed-Solomon Codes”, pp. 55–68. Boston, MA: Springer, US, 2003.
• Yao, A. C., “Protocols for secure computations (extended abstract),” in 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pp. 160–164, IEEE Computer Society, 1982.
• Veugen, T., Blom, F., Hoogh, S. J. A. de and Erkin, Z., “Secure comparison protocols in the semi- honest model,” IEEE Journal of Selected Topics in Signal Processing, vol. 9, no. 7, pp. 1217–1228, 2015.
• Garay, J. A., Schoenmakers, B. and Villegas, J. “Practical and secure solutions for integer comparison,” in Public Key Cryptography - PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, April 16-20, 2007, Proceedings (T. Okamoto and X. Wang, eds.), vol. 4450 of Lecture Notes in Computer Science, pp. 330–342, Springer, 2007.
• Bellare, M., Desai, A. , Lokipii, E. and Rogaway, P. , “A concrete security treatment of symmetric encryption,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, (USA), p. 394, IEEE Computer Society, 1997.