{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,25]],"date-time":"2025-12-25T07:21:10Z","timestamp":1766647270055,"version":"build-2065373602"},"reference-count":50,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T00:00:00Z","timestamp":1760918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Crystals-Kyber and Classic-McEliece are two prominent post-quantum key encapsulation mechanisms (KEMs) designed to address the challenges posed by quantum computing to classical cryptographic schemes. While the former has been standardized by the National Institute of Standards and Technology (NIST), the latter is well-known for its exceptional robustness and as one of the finalists of the fourth round of post-quantum cryptography standardization. Private set intersection (PSI) is a privacy-preserving technique that enables two parties, each possessing a dataset, to compute the intersection of their sets without revealing anything else. This can be achieved thanks to homomorphic encryption (HE), which allows computations on encrypted data. In this paper, firstly, we study Kyber and McEliece, apart from being KEMs, as post-quantum public key encryption (PKE), and examine their homomorphic properties. Secondly, we design two different two-party PSI protocols that utilize the homomorphic capabilities of Kyber and McEliece. Thirdly, a practical performance evaluation under NIST\u2019s security levels 1, 3, and 5 is conducted, focusing on three key metrics: storage overhead, communication overhead, and computation cost. Insights indicate that the Kyber-based PSI Protocol, which utilizes the multiplicative homomorphic property, is secure but less efficient. In contrast, the McEliece-based PSI protocol, while efficient in practice, raises concerns regarding its security as a homomorphic encryption scheme.<\/jats:p>","DOI":"10.3390\/cryptography9040066","type":"journal-article","created":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T13:54:41Z","timestamp":1760968481000},"page":"66","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Homomorphic Properties of Kyber and McEliece with Application to Post-Quantum Private Set Intersection"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9425-3671","authenticated-orcid":false,"given":"Anas A.","family":"Abudaqa","sequence":"first","affiliation":[{"name":"Department of Computer Science, College of Engineering and Information Technology, Onaizah Colleges (OC), Qassim 56447, Saudi Arabia"}]},{"given":"Khaled","family":"Alshehri","sequence":"additional","affiliation":[{"name":"Mathematics & Statistics Department, King Fahd University of Petroleum and Minerals (KFUPM), Dhahran 31261, Saudi Arabia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6414-3391","authenticated-orcid":false,"given":"Muhamad","family":"Felemban","sequence":"additional","affiliation":[{"name":"Interdisciplinary Research Center of Intelligent Secure Systems, King Fahd University of Petroleum and Minerals (KFUPM), Dhahran 31261, Saudi Arabia"},{"name":"Computer Engineering Department, King Fahd University of Petroleum and Minerals (KFUPM), Dhahran 31261, Saudi Arabia"},{"name":"Information and Computer Science Department, King Fahd University of Petroleum and Minerals (KFUPM), Dhahran 31261, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Rev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and cryptography","volume":"56","author":"Regev","year":"2009","journal-title":"J. ACM (JACM)"},{"key":"ref_3","unstructured":"Chou, T., Cid, C., UiB, S., Gilcher, J., Lange, T., Maram, V., Misoczki, R., Niederhagen, R., Paterson, K., and Persichetti, E. (2025, October 01). Classic McEliece: Conservative Code-Based Cryptography, 10 October 2020. Available online: https:\/\/cryptojedi.org\/papers\/mceliecenistr3-20201010.pdf."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., and Stehl\u00e9, D. (2018, January 24\u201326). CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. Proceedings of the 2018 IEEE European Symposium on Security and Privacy (EuroS&P), London, UK.","DOI":"10.1109\/EuroSP.2018.00032"},{"key":"ref_5","unstructured":"Albrecht, M.R., Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., Von Maurich, I., Misoczki, R., and Niederhagen, R. (2025, October 01). Classic McEliece: Conservative Code-Based Cryptography. Available online: https:\/\/cr.yp.to\/talks\/2024.09.17\/slides-djb-20240917-mceliece-16x9.pdf."},{"key":"ref_6","first-page":"114","article-title":"A public-key cryptosystem based on algebraic coding theory","volume":"4244","author":"McEliece","year":"1978","journal-title":"Coding Thv"},{"key":"ref_7","first-page":"157","article-title":"Knapsack-type cryptosystems and algebraic coding theory","volume":"15","author":"Niederreiter","year":"1986","journal-title":"Prob. Contr. Inform. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Wang, W., Szefer, J., and Niederhagen, R. (2017, January 17\u201319). FPGA-based key generator for the Niederreiter cryptosystem using binary Goppa codes. Proceedings of the International Conference on Cryptographic Hardware and Embedded Systems, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-319-66787-4_13"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Freedman, M.J., Nissim, K., and Pinkas, B. (2004, January 2\u20136). Efficient private matching and set intersection. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland.","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"ref_10","unstructured":"Chen, L., Li, Z., Chen, Z., and Liu, Y. (2018, January 18). Two anti-quantum attack protocols for secure multiparty computation. Proceedings of the Trusted Computing and Information Security: 12th Chinese Conference, CTCIS 2018, Wuhan, China. Revised Selected Papers 12."},{"key":"ref_11","unstructured":"Paillier, P. (1999, January 2\u20136). Public-key cryptosystems based on composite degree residuosity classes. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Prague, Czech Republic."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic encryption","volume":"28","author":"Goldwasser","year":"1984","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","author":"ElGamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Naccache, D., and Stern, J. (1998, January 3\u20135). A new public key cryptosystem based on higher residues. Proceedings of the 5th ACM Conference on Computer and Communications Security, Francisco, CA, USA.","DOI":"10.1145\/288090.288106"},{"key":"ref_16","unstructured":"Benaloh, J. (1994, January 5\u20136). Dense probabilistic encryption. Proceedings of the Workshop on Selected Areas of Cryptography, Kingston, ON, Canada."},{"key":"ref_17","unstructured":"Okamoto, T., and Uchiyama, S. (June, January 31). A new public-key cryptosystem as secure as factoring. Proceedings of the Advances in Cryptology\u2014EUROCRYPT\u201998: International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland. Proceedings 17."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Boneh, D., Goh, E.J., and Nissim, K. (2005, January 10\u201312). Evaluating 2-DNF formulas on ciphertexts. Proceedings of the Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA. Proceedings 2.","DOI":"10.1007\/978-3-540-30576-7_18"},{"key":"ref_19","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_20","unstructured":"Sander, T., Young, A., and Yung, M. (1999, January 17\u201318). Non-interactive cryptocomputing for nc\/sup 1. Proceedings of the 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), New York, NY, USA."},{"key":"ref_21","unstructured":"Ishai, Y., and Paskin, A. (2007, January 21\u201324). Evaluating branching programs on encrypted data. Proceedings of the Theory of Cryptography Conference, Amsterdam, The Netherlands."},{"key":"ref_22","unstructured":"Gentry, C. (June, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Brakerski, Z. (2012, January 19\u201323). Fully homomorphic encryption without modulus switching from classical GapSVP. Proceedings of the Annual Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-32009-5_50"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2633600","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","author":"Brakerski","year":"2014","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"ref_25","unstructured":"Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017, January 3\u20137). Homomorphic encryption for arithmetic of approximate numbers. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China. Proceedings, Part I 23."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabachene, M. (2016, January 4\u20138). Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam. Proceedings, Part I 22.","DOI":"10.1007\/978-3-662-53887-6_1"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","article-title":"Worst-case to average-case reductions for module lattices","volume":"75","author":"Langlois","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Peikert, C., and Regev, O. (June, January 30). On ideal lattices and learning with errors over rings. Proceedings of the Advances in Cryptology\u2013EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France. Proceedings 29.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"ref_29","first-page":"1","article-title":"CRYSTALS-Kyber algorithm specifications and supporting documentation","volume":"2","author":"Avanzi","year":"2019","journal-title":"NIST PQC Round"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"\u00d6zeren, S., and Yayla, O. (2023, January 18\u201319). Methods for masking crystals-kyber against side-channel attacks. Proceedings of the 2023 16th International Conference on Information Security and Cryptology (ISCT\u00fcrkiye), Ankara, Turkiye.","DOI":"10.1109\/ISCTrkiye61151.2023.10336068"},{"key":"ref_31","unstructured":"Mukherjee, A., Aikata, A., Mert, A.C., Lee, Y., Kwon, S., Deryabin, M., and Roy, S.S. (2025, February 10). ModHE: Modular Homomorphic Encryption Using Module Lattices: Potentials and Limitations. Cryptology ePrint Archive. Available online: https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/11261\/10803\/11220."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Zhao, C.-C., Yang, Y.-T., and Li, Z.-C. (2012, January 2\u20134). The homomorphic properties of McEliece public-key cryptosystem. Proceedings of the 2012 Fourth International Conference on Multimedia Information Networking and Security, Nanjing, China.","DOI":"10.1109\/MINES.2012.228"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"100567","DOI":"10.1016\/j.cosrev.2023.100567","article-title":"Private set intersection: A systematic literature review","volume":"49","author":"Morales","year":"2023","journal-title":"Comput. Sci. Rev."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1049\/iet-ifs.2019.0315","article-title":"Post-quantum protocol for computing set intersection cardinality with linear complexity","volume":"14","author":"Debnath","year":"2020","journal-title":"IET Inf. Secur."},{"key":"ref_35","first-page":"102731","article-title":"Post-quantum secure multi-party private set-intersection in star network topology","volume":"58","author":"Debnath","year":"2021","journal-title":"J. Inf. Secur. Appl."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Cai, Y., Tang, C., and Xu, Q. (2020). Two-party privacy-preserving set intersection with FHE. Entropy, 22.","DOI":"10.3390\/e22121339"},{"key":"ref_37","unstructured":"Gao, S. (2025, June 06). Efficient Fully Homomorphic Encryption Scheme. Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2018\/637."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Camenisch, J., and Zaverucha, G.M. (2009, January 23\u201326). Private intersection of certified sets. Proceedings of the Financial Cryptography and Data Security: 13th International Conference, FC 2009, Accra Beach, Barbados. Revised Selected Papers 13.","DOI":"10.1007\/978-3-642-03549-4_7"},{"key":"ref_39","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_40","doi-asserted-by":"crossref","unstructured":"Kerschbaum, F. (2012, January 2\u20134). Outsourced private set intersection using homomorphic encryption. Proceedings of the Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, Seoul, Republic of Korea.","DOI":"10.1145\/2414456.2414506"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"6672","DOI":"10.1109\/TIT.2012.2203582","article-title":"A CCA2 secure variant of the McEliece cryptosystem","volume":"58","author":"Dottling","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_42","unstructured":"Rastaghi, R. (2013). An efficient CCA2-secure variant of the McEliece cryptosystem in the standard model. arXiv."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s10623-008-9175-9","article-title":"Semantic security for the McEliece cryptosystem without random oracles","volume":"49","author":"Nojima","year":"2008","journal-title":"Des. Codes Cryptogr."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/18.651067","article-title":"A new algorithm for finding minimum-weight words in a linear code: Application to McEliece\u2019s cryptosystem and to narrow-sense BCH codes of length 511","volume":"44","author":"Canteaut","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Horlemann, A.L., Puchinger, S., Renner, J., Schamberger, T., and Wachter-Zeh, A. (2021, January 21\u201322). Information-set decoding with hints. Proceedings of the Code-Based Cryptography Workshop, Munich, Germany.","DOI":"10.1007\/978-3-030-98365-9_4"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIFS.2021.3118879","article-title":"Practical multi-party private set intersection protocols","volume":"17","author":"Bay","year":"2021","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Davidson, A., and Cid, C. (2017, January 3\u20135). An efficient toolkit for computing private set operations. Proceedings of the Australasian Conference on Information Security and Privacy, Auckland, New Zealand.","DOI":"10.1007\/978-3-319-59870-3_15"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Nita, S.L., and Mihailescu, M.I. (2022). Jdk 17: New features. Cryptography and Cryptanalysis in Java: Creating and Programming Advanced Algorithms with Java SE 17 LTS and Jakarta EE 10, Springer.","DOI":"10.1007\/978-1-4842-8105-5_2"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Kostaras, I., Drabo, C., Juneau, J., Reimers, S., Schr\u00f6der, M., Wielenga, G., Kostaras, I., Drabo, C., Juneau, J., and Reimers, S. (2020). What Is Apache NetBeans. Pro Apache NetBeans: Building Applications on the Rich Client Platform, Springer.","DOI":"10.1007\/978-1-4842-5370-0"},{"key":"ref_50","unstructured":"(2024, May 11). Bouncy Castle Crypto Library. Available online: https:\/\/www.bouncycastle.org."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/4\/66\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T04:15:32Z","timestamp":1761106532000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/4\/66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,20]]},"references-count":50,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["cryptography9040066"],"URL":"https:\/\/doi.org\/10.3390\/cryptography9040066","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2025,10,20]]}}}