EMPSI: Efficient multiparty private set intersection (with cardinality)

Abstract

Multiparty private set intersection (PSI) allows several parties, each holding a set of elements, to jointly compute the intersection without leaking any additional information. With the development of cloud computing, PSI has a wide range of applications in privacy protection. However, it is complex to build an efficient and reliable scheme to protect user privacy.

To address this issue, we propose EMPSI, an efficient PSI (with cardinality) protocol in a multiparty setting. EMPSI avoids using heavy cryptographic primitives (mainly rely on symmetric-key encryption) to achieve better performance. In addition, both PSI and PSI with the cardinality of EMPSI are secure against semi-honest adversaries and allow any number of colluding clients (at least one honest client). We also do experiments to compare EMPSI with some state-of-the-art works. The experimental results show that proposed EMPSI(-CA) has better performance and is scalable in the number of clients and the set size.

Graphical abstract

Yunbo Yang is a doctoral student in East China Normal University, China. His tutor is Xiaolei Dong and his main research direction is secure multiparty computation (MPC), searchable encryption (SE), and zero-knowledge proof (ZK). He also works as a cryptographic researcher in Shanghai Kunyao Network Technology Co., Ltd. and is responsible for the design of cryptographic algorithm

Xiaolei Dong received her PhD degree at Harbin Institute of Technology, China in 2001. She is a doctoral supervisor in East China Normal University, China. Her research interests include number theory, cryptography and network security (cloud computing, cloud processing security and privacy protection, big data security and privacy protection, etc.)

Zhenfu Cao is a doctoral supervisor in East China Normal University, China. His research interests include number theory, cryptography and new theories of network security (cloud computing, cloud processing security and privacy protection, big data security and privacy protection, etc.)

Jiachen Shen received his Bachelor degree at Shanghai Jiao Tong University, China in 2001, his Master and PhD degrees at University of Louisiana at Lafayette, USA in 2003 and 2008, respectively. He joined East China Normal University, China in 2015. His research interests include applied cryptography, cloud security, searchable encryption, and blockchains

Ruofan Li is a postgraduate student in East China Normal University, China. His tutor is Zhenfu Cao and he is co-author with Yunbo Yang. His research interest is multiparty computation (MPC), private set intersection (PSI), and searchable encryption (SE)

Yihao Yang is a postgraduate student in East China Normal University, China. He received his Bachelor degree in Shanghai Ocean University, China in 2020. His tutor is Xiaolei Dong. His research interest is multiparty computation (MPC), private set intersection (PSI), and searchable encryption (SE)

Shangmin Dou received his Bachelor degree of computer science in Shanghai Ocean University, China in 2020. He has a very solid development skill. He is now working as a tech lead in PwC

References

[1] Castelluccia C, Bielova N, Boutet A, Cunche M, Lauradoux C, Le Métayer D, Roca V. DESIRE: a third way for a European exposure notification system leveraging the best of centralized and decentralized systems. 2020, arXiv preprint arXiv: 2008.01621

[2] Madhusudan P, Ren L, Venkatakrishnan V N. ConTraIL: privacy-preserving secure contact tracing. 2020

[3] Chan J, Foster D, Gollakota S, Horvitz E, Jaeger J, Kakade S, Kohno T, Langford J, Larson J, Sharma P, Singanamalla S, Sunshine J, Tessaro S. PACT: privacy sensitive protocols and mechanisms for mobile contact tracing. 2020, arXiv preprint arXiv: 2004.03544

[4] Canetti R, Kalai Y T, Lysyanskaya A, Rivest R L, Shamir A, Shen E, Trachtenberg A, Varia M, Weitzner D J. Privacy-preserving automated exposure notification. Cryptology ePrint Archive, 2020

[5] Pinkas B, Schneider T, Zohner M . Scalable private set intersection based on OT extension. ACM Transactions on Privacy and Security, 2018, 21( 2): 7

[6] Pinkas B, Rosulek M, Trieu V, Yanai A. SpOT-light: lightweight private set intersection from sparse OT extension. In: Proceedings of the 39th Annual International Cryptology Conference. 2019, 401−431

[7] Chase M, Miao P. Private set intersection in the internet setting from lightweight oblivious PRF. In: Proceedings of the 40th Annual International Cryptology Conference. 2020, 34−63

[8] Rindal P, Rosulek M. Malicious-secure private set intersection via dual execution. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1229−1242

[9] Kolesnikov V, Matania N, Pinkas B, Rosulek M, Trieu N. Practical multi-party private set intersection from symmetric-key techniques. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1257−1272

[10] Inbar R, Omri E, Pinkas B. Efficient scalable multiparty private set-intersection via garbled bloom filters. In: Proceedings of the 11th International Conference on Security and Cryptography for Networks. 2018, 235−252

[11] Dong C, Chen L, Wen Z. When private set intersection meets big data: an efficient and scalable protocol. In: Proceedings of 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 789−800

[12] Abadi A, Terzis S, Dong C. Feather: lightweight multi-party updatable delegated private set intersection. Cryptology ePrint Archive, 2020

[13] Abadi A, Terzis S, Dong C. O-PSI: delegated private set intersection on outsourced datasets. In: Proceedings of the 30th IFIP International Information Security and Privacy Conference. 2015, 3−17

[14] Abadi A, Terzis S, Dong C. VD-PSI: verifiable delegated private set intersection on outsourced private datasets. In: Proceedings of the 20th International Conference on Financial Cryptography and Data Security. 2016, 149−168

[15] Branco P, Döttling N, Pu S. Multiparty cardinality testing for threshold private intersection. In: Proceedings of the 24th IACR International Conference on Public-Key Cryptography. 2021, 32−60

[16] Yang X, Luo X, Wang X A, Zhang S . Improved outsourced private set intersection protocol based on polynomial interpolation. Concurrency and Computation: Practice and Experience, 2018, 30( 1): e4329

[17] Zhao Y, Chow S S M. Can you find the one for me?. In: Proceedings of 2018 Workshop on Privacy in the Electronic Society. 2018, 54−65

[18] Kissner L, Song D. Privacy-preserving set operations. In: Proceedings of the 25th Annual International Cryptology Conference. 2005, 241−257

[19] Duong T, Phan D H, Trieu N. Catalic: delegated psi cardinality with applications to contact tracing. In: Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. 2020, 870−899

[20] Shi R H . Quantum bloom filter and its applications. IEEE Transactions on Quantum Engineering, 2021, 2: 2100411

[21] Shi R H . Quantum multiparty privacy set intersection cardinality. IEEE Transactions on Circuits and Systems II: Express Briefs, 2021, 68( 4): 1203–1207

[22] Shi R H, Li Y F . Quantum private set intersection cardinality protocol with application to privacy-preserving condition query. IEEE Transactions on Circuits and Systems I: Regular Papers, 2022, 69( 6): 2399–2411

[23] Hazay C, Venkitasubramaniam M. Scalable multi-party private set-intersection. In: Proceedings of the 20th IACR International Workshop on Public Key Cryptography. 2017, 175−203

[24] Debnath S K, Stǎnicǎ P, Kundu N, Choudhury T . Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15( 2): 365–386

[25] Shamir A . How to share a secret. Communications of the ACM, 1979, 22( 11): 612–613

[26] Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, 2007

[27] Rabin M O. How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, 2005

[28] Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 54−70

[29] Freedman M J, Ishai Y, Pinkas B, Reingold O. Keyword search and oblivious pseudorandom functions. In: Proceedings of the 2nd Theory of Cryptography Conference. 2005, 303−324

[30] Kolesnikov V, Kumaresan R, Rosulek M, Trieu N. Efficient batched oblivious PRF with applications to private set intersection. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 818−829

[31] Jarecki S, Liu X. Fast secure computation of set intersection. In: Proceedings of the 7th International Conference on Security and Cryptography for Networks. 2010, 418−435

[32] Chandran N, Dasgupta N, Gupta D, Obbattu S L B, Sekar S, Shah A. Efficient linear multiparty PSI and extensions to circuit/quorum PSI. In: Proceedings of 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021, 1182−1204

[33] Bampoulidis A, Bruni A, Helminger L, Kales D, Rechberger C, Walch R . Privately connecting mobility to infectious diseases via applied cryptography. Proceedings on Privacy Enhancing Technologies, 2022, 2022( 1): 768–788

Acknowledgements

This work was supported in part by the National Key Research and Development Program of China (2020YFA0712300), in part by the National Natural Science Foundation of China (Grant Nos. 62172162, 62132005), and in part by the Shanghai Trusted Industry Internet Software Collaborative Innovation Center.

RIGHTS & PERMISSIONS

2024 Higher Education Press