{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:25:15Z","timestamp":1760145915806,"version":"build-2065373602"},"reference-count":62,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T00:00:00Z","timestamp":1725840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Guangdong Key Laboratory of Data Security and Privacy Preserving","award":["2023B1212060036"],"award-info":[{"award-number":["2023B1212060036"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Private Set Intersection (PSI) is a cryptographic method in secure multi-party computation that allows entities to identify common elements in their datasets without revealing their private data. Traditional approaches assume similar-sized datasets and equal computational power, overlooking practical imbalances. In real-world applications, dataset sizes and computational capacities often vary, particularly in the Internet of Things and mobile scenarios where device limitations restrict computational types. Traditional PSI protocols are inefficient here, as computational and communication complexities correlate with the size of larger datasets. Thus, adapting PSI protocols to these imbalances is crucial. This paper explores unbalanced PSI scenarios where one party (the receiver) has a relatively small dataset and limited computational power, while the other party (the sender) has a large amount of data and strong computational capabilities. It introduces three innovative solutions for unbalanced PSI: an unbalanced PSI protocol based on the Cuckoo filter, an unbalanced PSI protocol based on single-cloud assistance, and an unbalanced PSI protocol based on dual-cloud assistance, with each subsequent solution addressing the shortcomings of the previous one. Depending on performance and security needs, different protocols can be employed for applications such as private contact discovery.<\/jats:p>","DOI":"10.3390\/info15090554","type":"journal-article","created":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T10:42:22Z","timestamp":1725878542000},"page":"554","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Cryptographic Solutions for Unbalanced Private Set Intersection in Mobile Communication"],"prefix":"10.3390","volume":"15","author":[{"given":"Qian","family":"Feng","sequence":"first","affiliation":[{"name":"College of Cyber Security, Jinan University, Guangzhou 510632, China"},{"name":"Guangdong Key Laboratory of Data Security and Privacy Preserving, Guangzhou 510632, China"}]},{"given":"Shenglong","family":"Du","sequence":"additional","affiliation":[{"name":"College of Cyber Security, Jinan University, Guangzhou 510632, China"},{"name":"Guangdong Key Laboratory of Data Security and Privacy Preserving, Guangzhou 510632, China"}]},{"given":"Wuzheng","family":"Tan","sequence":"additional","affiliation":[{"name":"College of Cyber Security, Jinan University, Guangzhou 510632, China"},{"name":"Guangdong Key Laboratory of Data Security and Privacy Preserving, Guangzhou 510632, China"}]},{"given":"Jian","family":"Weng","sequence":"additional","affiliation":[{"name":"College of Cyber Security, Jinan University, Guangzhou 510632, China"},{"name":"Guangdong Key Laboratory of Data Security and Privacy Preserving, Guangzhou 510632, China"}]}],"member":"1968","published-online":{"date-parts":[[2024,9,9]]},"reference":[{"key":"ref_1","first-page":"7","article-title":"Efficient and secure testing of fully-sequenced human genomes","volume":"470","author":"Bald","year":"2000","journal-title":"Biol. Sci. Initiat."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chen, H., Laine, K., and Rindal, P. (November, January 30). Fast private set intersection from homomorphic encryption. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA.","DOI":"10.1145\/3133956.3134061"},{"key":"ref_3","unstructured":"Nagaraja, S., Mittal, P., Hong, C.Y., Caesar, M., and Borisov, N. (2010, January 11\u201313). BotGrep: Finding P2P Bots with Structured Graph Analysis. Proceedings of the 19th USENIX Security Symposium (USENIX Security 10), Washington, DC, USA."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chen, H., Huang, Z., Laine, K., and Rindal, P. (2018, January 15\u201319). Labeled PSI from fully homomorphic encryption with malicious security. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada.","DOI":"10.1145\/3243734.3243836"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kamara, S., Mohassel, P., Raykova, M., and Sadeghian, S. (2014, January 3\u20137). Scaling private set intersection to billion-element sets. Proceedings of the Financial Cryptography and Data Security: 18th International Conference, FC 2014, Christ Church, Barbados. Revised Selected Papers.","DOI":"10.1007\/978-3-662-45472-5_13"},{"key":"ref_6","unstructured":"Pinkas, B., Schneider, T., Weinert, C., and Wieder, U. (2019, January 19\u201323). Efficient circuit-based PSI via cuckoo hashing. Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany."},{"key":"ref_7","first-page":"1782","article-title":"A Survey on Set Intersection Computation for Privacy Protection","volume":"59","author":"Li","year":"2022","journal-title":"J. Comput. Res. Dev."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Meadows, C. (1986, January 7\u20139). A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. Proceedings of the 7th IEEE Symposium on Security and Privacy, Los Alamitos, CA, USA.","DOI":"10.1109\/SP.1986.10022"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Huberman, B., Franklin, M., and Hogg, T. (1999, January 3\u20135). Enhancing Privacy and Trust in Electronic Communities. Proceedings of the 1st ACM Conference on Electronic Commerce, Denver, CO, USA.","DOI":"10.1145\/336992.337012"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"DeCristofaro, E., and Tsudik, G. (2012). Experimenting with Fast Private Set Intersection. International Conference on Trust and Trustworthy Computing, Springer.","DOI":"10.1007\/978-3-642-30921-2_4"},{"key":"ref_11","unstructured":"Pinkas, B., Schneider, T., and Zohner, M. (2014, January 20\u201322). Faster Private Set Intersection Based on OT Extension. Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA."},{"key":"ref_12","unstructured":"Freedman, M., Nissim, K., and Pinkas, B. (2004, January 2\u20136). Efficient Private Matching and Set Intersection. Proceedings of the 23rd International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00145-014-9190-0","article-title":"Efficient Set Intersection with Simulation-Based Security","volume":"29","author":"Freedman","year":"2016","journal-title":"J. Cryptol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Abadi, A., Terzis, S., and Dong, C. (2015, January 26\u201328). O-PSI: Delegated Private Set Intersection on Outsourced Datasets. Proceedings of the 30th IFIP International Information Security and Privacy Conference, Hamburg, Germany.","DOI":"10.1007\/978-3-319-18467-8_1"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Kissner, L., and Song, D. (2005, January 14\u201318). Privacy-Preserving Set Operations. Proceedings of the 25th Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.21236\/ADA457144"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Jarecki, S., and Liu, X. (2009, January 15\u201317). Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection. Proceedings of the LNCS 5444: 6th Theory of Cryptography Conference, San Francisco, CA, USA.","DOI":"10.1007\/978-3-642-00457-5_34"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Hazay, C., and Venkitasubramaniam, M. (2017, January 28\u201331). Scalable Multi-party Private Set-Intersection. Proceedings of the 20th IACR International Workshop on Public Key Cryptography, Amsterdam, The Netherlands.","DOI":"10.1007\/978-3-662-54365-8_8"},{"key":"ref_18","first-page":"1397","article-title":"Efficient and Secure Calculation of Two-Party Sets in the Field of Rational Numbers","volume":"43","author":"Dou","year":"2020","journal-title":"Chin. J. Comput."},{"key":"ref_19","unstructured":"Safavi-Naini, R., and Canetti, R. (2012, January 19\u201323). Multiparty Computation from Somewhat Homomorphic Encryption. Proceedings of the 32nd Annual Cryptology Conference, Santa Barbara, CA, USA. Lecture Notes in Computer Science."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Yao, A.C. (1982, January 3\u20135). Protocols for Secure Computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Micali, S., Goldreich, O., and Wigderson, A. (1987, January 25\u201327). How to Play Any Mental Game. Proceedings of the 19th ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/28395.28420"},{"key":"ref_22","unstructured":"Pinkas, B., Schneider, T., Segev, G., and Zohner, M. (2015, January 12\u201314). Phasing: Privateset intersectionusing permutation-basedhashing. Proceedings of the 24th USENIX Security Symposium, Washington, DC, USA."},{"key":"ref_23","unstructured":"Pinkas, B., Schneider, T., Tkachenko, O., and Yanai, A. (2020, January 10\u201314). Efficient circuit-based PSI with linear communication. Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia."},{"key":"ref_24","unstructured":"Huang, Y., Evans, D., and Katz, J. (2012, January 5\u20138). Private Set Intersection: Are Garbled Circuits Better Than Custom Protocols?. Proceedings of the 19th Network and Distributed System Security Symposium, San Diego, CA, USA."},{"key":"ref_25","unstructured":"Naor, M., and Pinkas, B. (2001, January 7\u20139). Efficient oblivious transfer protocols. Proceedings of the SODA, Washington, DC, USA."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Dong, C., Chen, L., and Wen, Z. (2013, January 4\u20138). When private set intersection meets big data: An efficient and scalable protocol. Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, Berlin, Germany.","DOI":"10.1145\/2508859.2516701"},{"key":"ref_27","unstructured":"Rindal, P., and Rosulek, M. (May, January 30). Improved private set intersection against malicious adversaries. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Zhang, E., Liu, F.H., Lai, Q., Jin, G., and Li, Y. (2019, January 11). Efficient multi-party private set intersection against malicious adversaries. Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, London, UK.","DOI":"10.1145\/3338466.3358927"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Pinkas, B., Rosulek, M., Trieu, N., and Yanai, A. (2020, January 10\u201314). PSI from PaXoS: Fast, malicious private set intersection. Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia.","DOI":"10.1007\/978-3-030-45724-2_25"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Orr\u00f9, M., Orsini, E., and Scholl, P. (2017, January 14\u201317). Actively secure 1-out-of-n OT extension with application to private set intersection. Proceedings of the Cryptographers\u2019 Track at the RSA Conference, San Francisco, CA, USA.","DOI":"10.1007\/978-3-319-52153-4_22"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Rindal, P., and Schoppmann, P. (2024, April 22). VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE. IACR Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2021\/266.","DOI":"10.1007\/978-3-030-77886-6_31"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Schoppmann, P., Gasc\u00f3n, A., Reichert, L., and Raykova, M. (2019, January 11\u201315). Distributed vector-OLE: Improved constructions and implementation. Proceedings of the 26th ACM SIGSAC Conference on Computer and Communications Security, London, UK.","DOI":"10.1145\/3319535.3363228"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Weng, C., Yang, K., Katz, J., and Wang, X. (2024, April 22). Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits. Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2020\/925.","DOI":"10.1109\/SP40001.2021.00056"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Wang, Z., and Ma, X. (2024). Blockchain-Based Unbalanced PSI with Public Verification and Financial Security. Mathematics, 12.","DOI":"10.3390\/math12101544"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"6052651","DOI":"10.1049\/2024\/6052651","article-title":"Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private Sets","volume":"2024","author":"Ning","year":"2024","journal-title":"IET Inf. Secur."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11432-022-3717-9","article-title":"Unbalanced private set intersection with linear communication complexity","volume":"67","author":"Zhao","year":"2024","journal-title":"Sci. China Inf. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Tan, W., Du, S., and Weng, J. (2024). Efficient Cryptographic Solutions for Unbalanced Private Set Intersection in Mobile Communication. Preprints.","DOI":"10.20944\/preprints202404.1701.v1"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Yang, X., Cai, L., Wang, Y., Sun, L., and Hu, J. (Cryptol. Eprint Arch., 2024). Efficient Unbalanced Quorum PSI from Homomorphic Encryption, Cryptol. Eprint Arch., preprint.","DOI":"10.1145\/3634737.3657001"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1109\/TCC.2024.3360098","article-title":"Efficient Verifiable Cloud-Assisted PSI Cardinality for Privacy-Preserving Contact Tracing","volume":"12","author":"Chen","year":"2024","journal-title":"IEEE Trans. Cloud Comput."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Van Baarsen, A., and Stevens, M. (Cryptol. Eprint Arch., 2024). Amortizing Circuit-PSI in the Multiple Sender\/Receiver Setting, Cryptol. Eprint Arch., preprint.","DOI":"10.62056\/a0fhsgvtw"},{"key":"ref_41","unstructured":"Bienstock, A., Patel, S., Seo, J.Y., and Yeo, K. (Cryptol. Eprint Arch., 2024). Batch PIR and Labeled PSI with Oblivious Ciphertext Compression, Cryptol. Eprint Arch., preprint."},{"key":"ref_42","unstructured":"Hao, M., Liu, W., Peng, L., Li, H., Zhang, C., Chen, H., and Zhang, T. (Cryptol. Eprint Arch., 2023). Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval, Cryptol. Eprint Arch., preprint."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Son, Y., and Jeong, J. (2023, January 10\u201314). PSI with computation or Circuit-PSI for Unbalanced Sets from Homomorphic Encryption. Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, Melbourne, Australia.","DOI":"10.1145\/3579856.3582817"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Yang, Y., Dong, X., Shen, J., Cao, Z., Yang, Y., Zhou, J., Fang, L., Liu, Z., Ge, C., and Su, C. (2023, January 21\u201323). MDPPC: Efficient Scalable Multiparty Delegated PSI and PSI Cardinality. Proceedings of the 2023 20th Annual International Conference on Privacy, Security and Trust (PST), Copenhagen, Denmark.","DOI":"10.1109\/PST58708.2023.10320155"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s11071-022-07837-1","article-title":"Optimizing energy dissipation in gas foil bearings to eliminate bifurcations of limit cycles in unbalanced rotor systems","volume":"111","author":"Papafragkos","year":"2023","journal-title":"Nonlinear Dyn."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/00051144.2022.2095829","article-title":"Angular symmetrical components-based anti-islanding method for solar photovoltaic-integrated microgrid","volume":"64","author":"Arivumani","year":"2023","journal-title":"Automatika"},{"key":"ref_47","unstructured":"Berenjian, S. (2023). Encryption-Based Secure Protocol Design for Networks. [Ph.D. Thesis, Stevens Institute of Technology]."},{"key":"ref_48","unstructured":"Hill, K. (2024, April 22). Facebook Figured Out My Family Secrets, And It Won\u2019t Tell Me How. Gizmodo 2017. Published on 25 August 2017. Available online: https:\/\/gizmodo.com\/facebook-figured-out-my-family-secrets-and-it-wont-tel-1797696163."},{"key":"ref_49","unstructured":"Marlinspike, M. (2017, September 26). Private Contact Discovery for Signal. Available online: https:\/\/signal.org\/blog\/private-contact-discovery."},{"key":"ref_50","unstructured":"Mittal, P., Papamanthou, C., and Song, D. (2013, January 24\u201327). Preserving Link Privacy in Social Network Based Systems. Proceedings of the NDSS, San Diego, CA, USA."},{"key":"ref_51","unstructured":"Abebe, R., and Nakos, V. (2014). Private Link Prediction in Social Networks, Harvard University. Technical Report."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.14778\/3402707.3402749","article-title":"Private Analysis of Graph Structure","volume":"4","author":"Karwa","year":"2011","journal-title":"Proc. VLDB Endow."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1866739.1866758","article-title":"A Firm Foundation for Private Data Analysis","volume":"54","author":"Dwork","year":"2011","journal-title":"Commun. ACM"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Pihur, V., and Korolova, A. (2014, January 3\u20137). RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. Proceedings of the ACM Conference on Computer and Communications Security (CCS), Scottsdale, AZ, USA.","DOI":"10.1145\/2660267.2660348"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Brendel, W., Han, F., Marujo, L., Jie, L., and Korolova, A. (June, January 27). Practical privacy-preserving friend recommendations on social networks. Proceedings of the Companion Proceedings of the The Web Conference 2018, Gothenburg, Sweden.","DOI":"10.1145\/3184558.3186954"},{"key":"ref_56","first-page":"19","article-title":"A Survey on Secure Multi-party Computation Technology and Applications","volume":"5","author":"Su","year":"2019","journal-title":"Inf. Commun. Technol. Policy"},{"key":"ref_57","first-page":"35","article-title":"A Survey of Filter Data Structures","volume":"51","author":"Wang","year":"2024","journal-title":"Comput. Sci."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Yu, M., Fabrikant, A., and Rexford, J. (2009, January 1\u20134). BUFFALO: Bloom filter forwarding architecture for large organizations. Proceedings of the International Conference on Emerging Networking Experiments and Technologies, Rome, Italy.","DOI":"10.1145\/1658939.1658975"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1080\/17445760.2019.1599889","article-title":"Cluster-based distributed dynamic cuckoo filter system for Redis","volume":"35","author":"Li","year":"2020","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Wang, F., Chen, H., Liao, L., Zhang, F., and Jin, H. (2019, January 7\u20139). The power of better choice: Reducing relocations in cuckoo filter. Proceedings of the International Conference on Distributed Computing Systems, Dallas, TX, USA.","DOI":"10.1109\/ICDCS.2019.00043"},{"key":"ref_61","unstructured":"Gu, R., Li, S., Dai, H., Wang, H., Luo, Y., Fan, B., Basat, R.B., Wang, K., Song, Z., and Chen, S. (2023, January 10\u201312). Adaptive online cache capacity optimization via lightweight working set size estimation at scale. Proceedings of the USENIX Annual Technical Conference, Boston, MA, USA."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"2690","DOI":"10.1109\/TNSM.2020.3024680","article-title":"Cuckoo Filters and Bloom Filters: Comparison and Application to Packet Classification","volume":"17","author":"Reviriego","year":"2020","journal-title":"IEEE Trans. Netw. Serv. Manag."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/9\/554\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:52:23Z","timestamp":1760111543000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/9\/554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,9]]},"references-count":62,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["info15090554"],"URL":"https:\/\/doi.org\/10.3390\/info15090554","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2024,9,9]]}}}