{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T17:14:22Z","timestamp":1781370862821,"version":"3.54.1"},"reference-count":37,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772147"],"award-info":[{"award-number":["61772147"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Privacy-preserving machine learning has become an important study at present due to privacy policies. However, the efficiency gap between the plain-text algorithm and its privacy-preserving version still exists. In this paper, we focus on designing a novel secret-sharing-based K-means clustering algorithm. Particularly, we present an efficient privacy-preserving K-means clustering algorithm based on replicated secret sharing with honest-majority in the semi-honest model. More concretely, the clustering task is outsourced to three semi-honest computing servers. Theoretically, the proposed privacy-preserving scheme can be proven with full data privacy. Furthermore, the experimental results demonstrate that our proposed privacy version reaches the same accuracy as the plain-text one. Compared to the existing privacy-preserving scheme, our proposed protocol can achieve about 16.5\u00d7\u201325.2\u00d7 faster computation and 63.8\u00d7\u201368.0\u00d7 lower communication. Consequently, the proposed privacy-preserving scheme is suitable for secret-sharing-based secure outsourced computation.<\/jats:p>","DOI":"10.3390\/e24081145","type":"journal-article","created":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T21:39:21Z","timestamp":1660858761000},"page":"1145","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Efficient Privacy-Preserving K-Means Clustering from Secret-Sharing-Based Secure Three-Party Computation"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5259-8890","authenticated-orcid":false,"given":"Weiming","family":"Wei","sequence":"first","affiliation":[{"name":"School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chunming","family":"Tang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8883-0919","authenticated-orcid":false,"given":"Yucheng","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Mathematics, Jiaying University, Meizhou 514015, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s00145-001-0019-2","article-title":"Privacy Preserving Data Mining","volume":"15","author":"Lindell","year":"2002","journal-title":"J. Cryptol."},{"key":"ref_2","unstructured":"Tan, P.N., Steinbach, M., Karpatne, A., and Kumar, V. (2018). Introduction to Data Mining, Pearson. [2nd ed.]."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"225","DOI":"10.2478\/popets-2021-0068","article-title":"SoK: Efficient Privacy-Preserving Clustering","volume":"2021","author":"Hegde","year":"2021","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"107286","DOI":"10.1016\/j.sigpro.2019.107286","article-title":"Cryptanalysis and Improvement of Medical Image Encryption Using High-Speed Scrambling and Pixel Adaptive Diffusion","volume":"167","author":"Chen","year":"2020","journal-title":"Signal Process."},{"key":"ref_5","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Rivest","year":"1978","journal-title":"Found. Secur. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Gentry, C. (2009). A Fully Homomorphic Encryption Scheme. [Ph.D. Thesis, Stanford University].","DOI":"10.1145\/1536414.1536440"},{"key":"ref_7","unstructured":"Paillier, P. (1999, January 15\u201319). Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Proceedings of the Advances in Cryptology\u2014EUROCRYPT \u201999, Santa Barbara, CA, USA."},{"key":"ref_8","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_9","doi-asserted-by":"crossref","unstructured":"Vaidya, J., and Clifton, C. (2003, January 24\u201327). Privacy-Preserving k-Means Clustering over Vertically Partitioned Data. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956755.956776"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bunn, P., and Ostrovsky, R. (2007, January 28\u201331). Secure Two-Party k-Means Clustering. Proceedings of the 14th ACM Conference on Computer and Communications Security\u2014CCS \u201907, Alexandria, VA, USA.","DOI":"10.1145\/1315245.1315306"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Rao, F.Y., Samanthula, B.K., Bertino, E., Yi, X., and Liu, D. (2015, January 27\u201330). Privacy-Preserving and Outsourced Multi-User K-Means Clustering. Proceedings of the 2015 IEEE Conference on Collaboration and Internet Computing (CIC), Hangzhou, China.","DOI":"10.1109\/CIC.2015.20"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kim, H.J., and Chang, J.W. (2018, January 2\u20137). A Privacy-Preserving k-Means Clustering Algorithm Using Secure Comparison Protocol and Density-Based Center Point Selection. Proceedings of the 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), San Francisco, CA, USA.","DOI":"10.1109\/CLOUD.2018.00138"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"J\u00e4schke, A., and Armknecht, F. (2018, January 15\u201317). Unsupervised Machine Learning on Encrypted Data. Proceedings of the International Conference on Selected Areas in Cryptography, Calgary, AB, Canada.","DOI":"10.1007\/978-3-030-10970-7_21"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabach\u00e8ne, M. (2016, January 4\u20138). Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam.","DOI":"10.1007\/978-3-662-53887-6_1"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"e5473","DOI":"10.1002\/cpe.5473","article-title":"Privacy of Outsourced Two-party K-means Clustering","volume":"33","author":"Cai","year":"2021","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_16","first-page":"468","article-title":"Practical Fully Homomorphic Encryption without Noise Reduction","volume":"2015","author":"Liu","year":"2015","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_17","unstructured":"Wang, Y. (2022, June 18). Notes on Two Fully Homomorphic Encryption Schemes without Bootstrapping. Available online: https:\/\/eprint.iacr.org\/2015\/519."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Yao, A. (1982, January 3\u20135). Protocols for Secure Computations. Proceedings of the FOCS, Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., and Wigderson, A. (1987, January 25\u201327). How to Play Any Mental Game. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/28395.28420"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C. (1986, January 27\u201329). How to Generate and Exchange Secrets. Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Toronto, ON, Canada.","DOI":"10.1109\/SFCS.1986.25"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to Share a Secret","volume":"22","author":"Shamir","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Doganay, M.C., Pedersen, T.B., Saygin, Y., Sava\u015f, E., and Levi, A. (2008, January 29). Distributed Privacy Preserving K-Means Clustering with Additive Secret Sharing. Proceedings of the 2008 International Workshop on Privacy and Anonymity in Information Society, Nantes, France.","DOI":"10.1145\/1379287.1379291"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Patel, S., Garasia, S., and Jinwala, D. (2012, January 21\u201325). An Efficient Approach for Privacy Preserving Distributed K-Means Clustering Based on Shamir\u2019s Secret Sharing Scheme. Proceedings of the IFIP International Conference on Trust Management, Surat, India.","DOI":"10.1007\/978-3-642-29852-3_9"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Patel, S., Patel, V., and Jinwala, D. (2013, January 5\u20138). Privacy Preserving Distributed K-Means Clustering in Malicious Model Using Zero Knowledge Proof. Proceedings of the International Conference on Distributed Computing and Internet Technology, Bhubaneswar, India.","DOI":"10.1007\/978-3-642-36071-8_33"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Upmanyu, M., Namboodiri, A.M., Srinathan, K., and Jawahar, C.V. (2010, January 21). Efficient Privacy Preserving K-Means Clustering. Proceedings of the Pacific-Asia Workshop on Intelligence and Security Informatics, Hyderabad, India.","DOI":"10.1007\/978-3-642-13601-6_17"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Baby, V., and Chandra, N.S. (2016, January 21\u201324). Distributed Threshold K-Means Clustering for Privacy Preserving Data Mining. Proceedings of the 2016 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Jaipur, India.","DOI":"10.1109\/ICACCI.2016.7732393"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"414","DOI":"10.2478\/popets-2020-0080","article-title":"Practical Privacy-Preserving k-Means Clustering","volume":"2020","author":"Mohassel","year":"2020","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Araki, T., Furukawa, J., Lindell, Y., Nof, A., and Ohara, K. (2016, January 24\u201328). High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978331"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Canetti, R. (2001, January 14\u201317). Universally Composable Security: A New Paradigm for Cryptographic Protocols. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, Washington, DC, USA.","DOI":"10.1109\/SFCS.2001.959888"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Goldreich, O. (2004). The Foundations of Cryptography\u2014Volume 2: Basic Applications, Cambridge University Press.","DOI":"10.1017\/CBO9780511721656"},{"key":"ref_31","unstructured":"Mohassel, P., and Rindal, P. (2018, January 15\u201319). ABY3: A Mixed Protocol Framework for Machine Learning. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"188","DOI":"10.2478\/popets-2021-0011","article-title":"Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning","volume":"2021","author":"Wagh","year":"2021","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1002\/ecjc.4430720906","article-title":"Secret Sharing Scheme Realizing General Access Structure","volume":"72","author":"Ito","year":"1989","journal-title":"Electron. Commun. Jpn."},{"key":"ref_34","first-page":"35","article-title":"Secure Computation with Fixed-Point Numbers","volume":"Volume 6052","author":"Hutchison","year":"2010","journal-title":"Financial Cryptography and Data Security"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Beaver, D. (1995, January 27\u201331). Precomputing Oblivious Transfer. Proceedings of the Advances in Cryptology\u2014CRYPTO\u2019 95, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-44750-4_8"},{"key":"ref_36","unstructured":"Goldschmidt, R.E. (1964). Applications of Division by Convergence. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Pastro, V., Smart, N., and Zakarias, S. (2012, January 19\u201323). Multiparty Computation from Somewhat Homomorphic Encryption. Proceedings of the Advances in Cryptology\u2014CRYPTO 2012, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-32009-5_38"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/8\/1145\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:11:32Z","timestamp":1760141492000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/8\/1145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":37,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,8]]}},"alternative-id":["e24081145"],"URL":"https:\/\/doi.org\/10.3390\/e24081145","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,18]]}}}