{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T05:23:05Z","timestamp":1761110585433,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T00:00:00Z","timestamp":1606262400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Foundation of National Natural Science of China under Grant","award":["61772147"],"award-info":[{"award-number":["61772147"]}]},{"name":"Guangdong Province Natural Science Foundation of major basic research and Cultivation project under Grant","award":["2015A030308016"],"award-info":[{"award-number":["2015A030308016"]}]},{"name":"Project of Ordinary University Innovation Team Construction of Guangdong Province under Grant","award":["2015KCXTD014"],"award-info":[{"award-number":["2015KCXTD014"]}]},{"name":"Basic Research Major Projects of Department of education of Guangdong Province under Grant","award":["2014KZDXM044"],"award-info":[{"award-number":["2014KZDXM044"]}]},{"name":"Collaborative Innovation Major Projects of Bureau of Education of Guangzhou City under Grant","award":["1201610005"],"award-info":[{"award-number":["1201610005"]}]},{"name":"Key-Area Research and Development Plan of Guangdong province under Grant","award":["2019B020215004"],"award-info":[{"award-number":["2019B020215004"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>A two-party private set intersection allows two parties, the client and the server, to compute an intersection over their private sets, without revealing any information beyond the intersecting elements. We present a novel private set intersection protocol based on Shuhong Gao\u2019s fully homomorphic encryption scheme and prove the security of the protocol in the semi-honest model. We also present a variant of the protocol which is a completely novel construction for computing the intersection based on Bloom filter and fully homomorphic encryption, and the protocol\u2019s complexity is independent of the set size of the client. The security of the protocols relies on the learning with errors and ring learning with error problems. Furthermore, in the cloud with malicious adversaries, the computation of the private set intersection can be outsourced to the cloud service provider without revealing any private information.<\/jats:p>","DOI":"10.3390\/e22121339","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T08:59:15Z","timestamp":1606294755000},"page":"1339","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Two-Party Privacy-Preserving Set Intersection with FHE"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4920-7523","authenticated-orcid":false,"given":"Yunlu","family":"Cai","sequence":"first","affiliation":[{"name":"School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China"}]},{"given":"Chunming","family":"Tang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China"},{"name":"State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China"}]},{"given":"Qiuxia","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Mathematics and Systems Science, Guangdong Polytechnic Normal University, Guangzhou 510665, China"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,25]]},"reference":[{"key":"ref_1","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Rvest","year":"1978","journal-title":"Found. Secur. Comput."},{"key":"ref_2","unstructured":"Craig, G. (June, January 31). Fully Homomorphic Encryption Using Ideal Lattices. Proceedings of the Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA."},{"key":"ref_3","unstructured":"Van Dijk, M., Gentry, C., Halevi, S., and Vaikuntanathan, V. (2009). Fully homomorphic encryp-tion over the integers. IACR Cryptol. Eprint Arch., 616."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1137\/120868669","article-title":"Efficient fully homomorphic encryption from (standard) LWE","volume":"43","author":"Brakerski","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2011, January 14\u201318). Fully homomorphic encryption from ring-LWE and security for key dependent messages. Proceedings of the Advances in Cryptology-CRYPTO 2011, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Gentry, C., Sahai, A., and Waters, B. (2013). Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Advances in Cryptology-CRYPTO 2013, Springer.","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"ref_7","unstructured":"Gao, S. (2020, October 28). Efficient Fully Homomorphic Encryption Scheme. Cryptology ePrint Archive: Report 2018\/637. Available online: https:\/\/eprint.iacr.org\/2018\/637."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., and Georgieva, M. (2020, October 28). Improving TFHE: Faster Packed Homomorphic Operations and Effcient Circuit Bootstrapping. Cryptology ePrint Archive: Report 2017\/ 430. Available online: https:\/\/eprint.iacr.org\/2017\/430.","DOI":"10.1007\/978-3-319-70694-8_14"},{"key":"ref_9","unstructured":"Oded, G., Micali, S., and Avi, W. (1987, January 25\u201327). How to play ANY mental game. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_10","unstructured":"Ion, M., Kreuter, B., and Nergiz, E. (2020, October 28). Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions. Cryptology ePrint Archive: Report 2017\/738. Available online: https:\/\/eprint.iacr.org\/2017\/738."},{"key":"ref_11","unstructured":"Ion, M., Kreuter, B., and Erhan, A. (2020, October 28). On Deploying Secure Computing Commercially: Private Intersection-Sum Protocols and their Business Applications. Cryptology ePrint Archive: Report 2019\/723. Available online: https:\/\/eprint.iacr.org\/2019\/723."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"37473","DOI":"10.1109\/ACCESS.2019.2902853","article-title":"A Note on Multiple Secret Sharing Using Chinese Remainder Theorem and Exclusive-OR","volume":"7","author":"Prasetyo","year":"2019","journal-title":"IEEE Access"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1109\/TIFS.2018.2868221","article-title":"MEG: Memory and Energy Efficient Garbled Circuit Evaluation on Smartphones","volume":"14","author":"Yang","year":"2019","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_14","first-page":"541","article-title":"Garbled Circuits and Indistinguishability Obfuscation","volume":"6","author":"Zhang","year":"2019","journal-title":"J. Cryptologic Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Qin, H., Wang, H., and Wei, X. (2019). Privacy-Preserving Wildcards Pattern Matching Protocol for IoT Applications. IEEE Access, 1.","DOI":"10.1109\/ACCESS.2019.2900519"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Gama, M., Mateus, P., and Souto, A. (2020). A Private Quantum Bit String Commitment. Entropy, 22.","DOI":"10.3390\/e22030272"},{"key":"ref_17","first-page":"194","article-title":"Advances in Practical Secure Two-party Computation and Its Application in Genomic Sequence Comparison","volume":"6","author":"Zhao","year":"2019","journal-title":"J. Cryptol. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/s00145-008-9034-x","article-title":"Efficient Protocols for Set Intersection and Pattern Matching with Security against Malicious and Covert Adversaries","volume":"23","author":"Hazay","year":"2010","journal-title":"J. Cryptol."},{"key":"ref_19","unstructured":"Cristofaro, E.D., Lu, E., and Tsudik, Y.A. (2020, October 28). Gene Efficient Techniques for Privacy-Preserving Sharing of Sensitive Information. Cryptology ePrint Archive: Report 2011\/113. Available online: https:\/\/eprint.iacr.org\/2011\/113."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.future.2019.05.010","article-title":"A novel approach to steganography based on the properties of Catalan numbers and Dyck words","volume":"100","author":"Saracevic","year":"2019","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.12700\/APH.15.7.2018.7.5","article-title":"Applications of Catalan numbers and Lattice Path combinatorial problem in cryptography","volume":"15","author":"Saracevic","year":"2018","journal-title":"Acta Polytech. Hung."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Coppolino, L., D\u2019Antonio, S., Formicola, V., Mazzeo, G., and Romano, L. (2020). VISE: Combining Intel SGX and Homomorphic Encryption for Cloud Industrial Control Systems. IEEE Trans. Comput., 99.","DOI":"10.1109\/TC.2020.2995638"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Lindell, Y., and Pinkas, B. (2009). Secure Multiparty Computation for Privacy-Preserving Data Mining. J. Priv. Confidentiality.","DOI":"10.29012\/jpc.v1i1.566"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Michael, L., Nejdl, W., Papapetrou, O., and Siberski, W. (2007, January 21\u201323). Improving Distributed Join Efficiency with Extended Bloom Filter Operations. Proceedings of the 21st International Conference on Advanced Networking and Applications, Niagara Falls, ON, Canada.","DOI":"10.1109\/AINA.2007.80"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Naor, M., and Pinkas, B. (1999, January 1\u20134). Oblivious Transfer and Polynomial Evaluation. Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, GA, USA.","DOI":"10.1145\/301250.301312"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Freedman, M.J., Ishai, Y., and Pinkas, B. (2005). Keyword Search and Oblivious Pseudorandom Functions. Second International Conference on Theory of Cryptography, Springer.","DOI":"10.1007\/978-3-540-30576-7_17"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Chaum, D., Rivest, R.L., and Sherman, A.T. (1983). Blind Signatures for Untraceable Payments. Adv. Cryptol.","DOI":"10.1007\/978-1-4757-0602-4_18"},{"key":"ref_28","unstructured":"Florian, K. (2012). Outsourced private set intersection using homomorphic encryption. ACM Symp. Inf., 85\u201386."},{"key":"ref_29","first-page":"131","article-title":"Cryptographically Secure Bloom-Filters","volume":"2","author":"Nojima","year":"2009","journal-title":"Trans. Data Priv."},{"key":"ref_30","first-page":"2153","article-title":"Survey on Private Preserving Set Intersection Technology","volume":"54","author":"Shen","year":"2017","journal-title":"J. Comput. Res. Dev."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Regev, O. (2005, January 22\u201324). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060603"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 34.","DOI":"10.1145\/1568318.1568324"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Peikert, C., and Regev, O. (2010). On ideal lattices and learning with errors over rings. Cryptology-EUROCRYPT 2010, Springer.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"ref_35","unstructured":"Bellovin, S., and Cheswick, W. (2020, October 28). Privacy-Enhanced Searches Using Encrypted Bloom Filters. Cryptology ePrint Archive: Report 2004\/022. Available online: https:\/\/eprint.iacr.org\/2004\/022."},{"key":"ref_36","unstructured":"Goh, E. (2020, October 28). Secure Indexes. Cryptology ePrint Archive: Report 2003\/216. Available online: https:\/\/eprint.iacr.org\/2003\/216."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Raykova, M., Vo, B., Bellovin, S., and Malkin, T. (2009, January 13). Secure Anonymous Database Search. Proceedings of the ACM Cloud Computing Security Workshop, Chicago, IL, USA.","DOI":"10.1145\/1655008.1655025"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10844-006-0018-8","article-title":"Preserving privacy in association rule mining with bloom filters","volume":"29","author":"Qiu","year":"2007","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_39","first-page":"209","article-title":"Secure and Efficient Private Set Intersection Cardinality Using Bloom Filter","volume":"9290","author":"Debnath","year":"2015","journal-title":"Int. Inf. Secur. Conf."},{"key":"ref_40","unstructured":"Changyu, D., Liqun, C., and Zikai, W. (2013, January 4\u20138). When private set intersection meets big data: An efficient and scalable protocol. Proceedings of the ACM Conference on Computer and Communications Security, Berlin, Germany."},{"key":"ref_41","first-page":"371","article-title":"Privately Computing Set-Union and Set-Intersection Cardinality via Bloom Filters","volume":"139","author":"Egert","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1007\/978-3-662-46800-5_24","article-title":"FHEW: Bootstrapping homomorphic encryption in less than a second","volume":"Volume 9056","author":"Ducas","year":"2015","journal-title":"Proceedings of the Advances in Cryptology-EUROCRYPT 2015"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-662-53887-6_1","article-title":"Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds","volume":"Volume 10031","author":"Chillotti","year":"2016","journal-title":"Proceedings of the Advances in Cryptology-ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/12\/1339\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:37:12Z","timestamp":1760179032000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/12\/1339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,25]]},"references-count":43,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["e22121339"],"URL":"https:\/\/doi.org\/10.3390\/e22121339","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,11,25]]}}}