Privacy Preserving Outsourced K-means Clustering Using Kd-tree | SpringerLink
Skip to main content
Springer Nature Link
Log in

Privacy Preserving Outsourced K-means Clustering Using Kd-tree

  • Conference paper
  • First Online:
Provable and Practical Security (ProvSec 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14217))

Included in the following conference series:

  • 495 Accesses

Abstract

Nowadays, more and more resource-constrained individuals and corporations tend to outsource their data and machine learning tasks to cloud servers, enjoying high-quality data storage and computing services ubiquitously. However, outsourcing sensitive data can bring data security and privacy issues, arousing public concerns. In this work, we propose an efficient privacy-preserving outsourced scheme of K-means clustering on encrypted data in the twin-cloud model using the paradigm of secret sharing. The state-of-the-art outsourced K-means clustering scheme using fully homomorphic encryption is efficient but not secure enough. To better solve this problem, we utilize the kd-tree data structure and design a set of secure protocols, presenting a new scheme that is almost as efficient as the state-of-the-art schemes but more secure. In our scheme, the clustering process is performed by two cloud servers without leaking any intermediate information. We provide formal security analyses and evaluate the performance of our scheme on both synthetic and real-world datasets. The experiment results show that our scheme is efficient and practical.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8464
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Masulli, F., Schenone, A.: A fuzzy clustering based segmentation system as support to diagnosis in medical imaging. Artif. Intell. Med. 16(2), 129–147 (1999)

    Article  Google Scholar 

  2. Chaturvedi, A., Carroll, J.D., Green, P.E., Rotondo, J.A.: A feature-based approach to market segmentation via overlapping k-centroids clustering. J. Mark. Res. 34(3), 370–377 (1997)

    Article  Google Scholar 

  3. Wu, W., Liu, J., Wang, H., Hao, J., Xian, M.: Secure and efficient outsourced k-means clustering using fully homomorphic encryption with ciphertext packing technique. IEEE Trans. Knowl. Data Eng. 33(10), 3424–3437 (2020)

    Article  Google Scholar 

  4. Mohassel, P., Rosulek, M., Trieu, N.: Practical privacy-preserving k-means clustering. Proc. Priv. Enh. Technol. 2020(4), 414–433 (2020)

    Google Scholar 

  5. Naeem, M., Asghar, S.: KEGG metabolic reaction network data set. The UCI KDD Archive (2011)

    Google Scholar 

  6. Rong, H., Wang, H., Liu, J., Hao, J., Xian, M.: Privacy-preserving-means clustering under multiowner setting in distributed cloud environments. Secur. Commun. Netw. 2017 (2017)

    Google Scholar 

  7. Rao, F.-Y., Samanthula, B.K., Bertino, E., Yi, X., Liu, D.: Privacy-preserving and outsourced multi-user k-means clustering. In: 2015 IEEE Conference on Collaboration and Internet Computing (CIC), pp. 80–89. IEEE (2015)

    Google Scholar 

  8. Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881–892 (2002)

    Article  MATH  Google Scholar 

  9. Rathee, D., et al.: Cryptflow2: practical 2-party secure inference. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 325–342 (2020)

    Google Scholar 

  10. Gheid, Z., Challal, Y.: Efficient and privacy-preserving k-means clustering for big data mining. In: 2016 IEEE Trustcom/BigDataSE/ISPA, pp. 791–798. IEEE (2016)

    Google Scholar 

  11. Jäschke, A., Armknecht, F.: Unsupervised machine learning on encrypted data. In: Cid, C., Jacobson, M., Jr. (eds.) SAC 2018. LNCS, vol. 11349, pp. 453–478. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_21

    Chapter  Google Scholar 

  12. Liu, X., et al.: Outsourcing two-party privacy preserving k-means clustering protocol in wireless sensor networks. In: 2015 11th International Conference on Mobile Ad-hoc and Sensor Networks (MSN), pp. 124–133. IEEE (2015)

    Google Scholar 

  13. Liu, D., Bertino, E., Yi, X.: Privacy of outsourced k-means clustering. In: Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, pp. 123–134 (2014)

    Google Scholar 

  14. Kim, H.-J., Chang, J.-W.: A privacy-preserving k-means clustering algorithm using secure comparison protocol and density-based center point selection. In: 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), pp. 928–931. IEEE (2018)

    Google Scholar 

  15. Kargupta, H., Datta, S., Wang, Q., Sivakumar, K.: On the privacy preserving properties of random data perturbation techniques. In: Third IEEE International Conference on Data Mining, pp. 99–106. IEEE (2003)

    Google Scholar 

  16. Doganay, M.C., Pedersen, T.B., Saygin, Y., Savaş, E., Levi, A.: Distributed privacy preserving k-means clustering with additive secret sharing. In: Proceedings of the 2008 International Workshop on Privacy and Anonymity in Information Society, pp. 3–11 (2008)

    Google Scholar 

  17. Lin, Z., Jaromczyk, J.W.: Privacy preserving two-party k-means clustering over vertically partitioned dataset. In: Proceedings of 2011 IEEE International Conference on Intelligence and Security Informatics, pp. 187–191. IEEE (2011)

    Google Scholar 

  18. Patel, S.J., Punjani, D., Jinwala, D.C.: An efficient approach for privacy preserving distributed clustering in semi-honest model using elliptic curve cryptography. Int. J. Netw. Secur. 17(3), 328–339 (2015)

    Google Scholar 

  19. Chen, X.: Introduction to secure outsourcing computation. Synth. Lect. Inf. Secur. Priv. Trust 8(2), 1–93 (2016)

    Google Scholar 

  20. Goldreich, O.: Encryption schemes. The foundations of cryptography, vol. 2 (2004)

    Google Scholar 

  21. Bogdanov, D., Laur, S., Willemson, J.: Sharemind: a framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88313-5_13

    Chapter  Google Scholar 

  22. Bogdanov, D., Niitsoo, M., Toft, T., Willemson, J.: High-performance secure multi-party computation for data mining applications. Int. J. Inf. Secur. 11(6), 403–418 (2012)

    Article  Google Scholar 

  23. Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34

    Chapter  Google Scholar 

  24. El Malki, N., Ravat, F., Teste, O.: KD-means: clustering method for massive data based on KD-tree. In: 22nd International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data-DOLAP 2020, vol. 2572. CEUR-WS (2020)

    Google Scholar 

  25. Cover, T., Hart, P.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967)

    Article  MATH  Google Scholar 

  26. Liu, L., et al.: Toward highly secure yet efficient KNN classification scheme on outsourced cloud data. IEEE Internet Things J. 6(6), 9841–9852 (2019)

    Article  Google Scholar 

  27. Cheng, K., Hou, Y., Wang, L.: Secure similar sequence query on outsourced genomic data. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security, pp. 237–251 (2018)

    Google Scholar 

  28. Liu, X., Deng, R.H., Choo, K.-K.R., Weng, J.: An efficient privacy-preserving outsourced calculation toolkit with multiple keys. IEEE Trans. Inf. Forensics Secur. 11(11), 2401–2414 (2016)

    Article  Google Scholar 

  29. Fränti, P., Sieranoja, S.: K-means properties on six clustering benchmark datasets. Appl. Intell. 48(12), 4743–4759 (2018)

    Article  MATH  Google Scholar 

  30. Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20901-7_2

    Chapter  Google Scholar 

  31. Papernot, N., McDaniel, P., Sinha, A., Wellman, M.P.: SoK: security and privacy in machine learning. In: 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 399–414. IEEE (2018)

    Google Scholar 

  32. Xu, R., Wunsch, D.: Survey of clustering algorithms. IEEE Trans. Neural Networks 16(3), 645–678 (2005)

    Article  Google Scholar 

  33. Hegde, A., Möllering, H., Schneider, T., Yalame, H.: SoK: efficient privacy-preserving clustering. Proc. Priv. Enh. Technol. 2021(4), 225–248 (2021)

    Google Scholar 

  34. Bozdemir, B., Canard, S., Ermis, O., Möllering, H., Önen, M., Schneider, T.: Privacy-preserving density-based clustering. In: Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pp. 658–671 (2021)

    Google Scholar 

  35. Boldyreva, A., Tang, T.: Privacy-preserving approximate k-nearest-neighbors search that hides access, query and volume patterns. Cryptology ePrint Archive (2021)

    Google Scholar 

Download references

Acknowledgment

This work is supported by the National Nature Science Foundation of China (No. 62102429, No. 62072466, No. 62102430, No. 62102440), Natural Science Foundation of Hunan Province, China (Grant No. 2021JJ40688), the NUDT Grants (No. ZK19-38, No. ZK22-50).

Author information

Authors and Affiliations

  1. College of Computer, National University of Defense Technology, Changsha, China

    Yanxiang Deng, Lin Liu, Shaojing Fu, Yuchuan Luo & Wei Wu

  2. Academy of Military Sciences, Beijing, China

    Shixiong Wang

Authors
  1. Yanxiang Deng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shaojing Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yuchuan Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Wei Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Shixiong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yanxiang Deng .

Editor information

Editors and Affiliations

  1. Hubei University of Technology, Wuhan, China

    Mingwu Zhang

  2. Hong Kong Polytechnic University, Kowloon, Hong Kong

    Man Ho Au

  3. University of Wollongong, Wollongong, NSW, Australia

    Yudi Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Deng, Y., Liu, L., Fu, S., Luo, Y., Wu, W., Wang, S. (2023). Privacy Preserving Outsourced K-means Clustering Using Kd-tree. In: Zhang, M., Au, M.H., Zhang, Y. (eds) Provable and Practical Security. ProvSec 2023. Lecture Notes in Computer Science, vol 14217. Springer, Cham. https://doi.org/10.1007/978-3-031-45513-1_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-45513-1_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45512-4

  • Online ISBN: 978-3-031-45513-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation