Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Looking Back—My Life as a Mathematician and Cryptographer Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

Towards a Practical Cluster Analysis over Encrypted Data

verfasst von : Jung Hee Cheon, Duhyeong Kim, Jai Hyun Park

Erschienen in: Selected Areas in Cryptography – SAC 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Cluster analysis is one of the most significant unsupervised machine learning methods, and it is being utilized in various fields associated with privacy issues including bioinformatics, finance and image processing. In this paper, we propose a practical solution for privacy-preserving cluster analysis based on homomorphic encryption (HE). Our work is the first HE solution for the mean-shift clustering algorithm. To reduce the super-linear complexity of the original mean-shift algorithm, we adopt a novel random sampling method called dust sampling approach, which perfectly suits with HE and achieves the linear complexity. We also substitute non-polynomial kernels by a new polynomial kernel so that it can be efficiently computed in HE.
The HE implementation of our modified mean-shift clustering algorithm based on the approximate HE scheme HEAAN shows prominent performance in terms of speed and accuracy. It takes approx. 30 min with \(99\%\) accuracy over several public datasets with hundreds of data, and even for the dataset with 262, 144 data, it takes 82 min only when SIMD operations in HEAAN is applied. Our results outperform the previously best known result (SAC 2018) by over 400 times.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel A General Framework for the Related-Key Linear Attack Against Block Ciphers with Linear Key Schedules
Nächstes Kapitel Breaking the Bluetooth Pairing – The Fixed Coordinate Invalid Curve Attack
Literatur
1.
2.
3.
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef
4.
Almutairi, N., Coenen, F., Dures, K.: K-means clustering using homomorphic encryption and an updatable distance matrix: secure third party data clustering with limited data owner interaction. In: Bellatreche, L., Chakravarthy, S. (eds.) DaWaK 2017. LNCS, vol. 10440, pp. 274–285. Springer, Cham (2017). https://​doi.​org/​10.​1007/​978-3-319-64283-3_​20CrossRef
5.
6.
7.
Bunn, P., Ostrovsky, R.: Secure two-party k-means clustering. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS 2007, New York, NY, USA, pp. 486–497. ACM (2007)
8.
9.
10.
11.
Cheon, J.H., et al.: Toward a secure drone system: flying with real-time homomorphic authenticated encryption. IEEE Access 6, 24325–24339 (2018)CrossRef
12.
13.
14.
Cheon, J.H., Kim, D., Kim, D., Lee, H.H., Lee, K.: Numerical methods for comparison on homomorphically encrypted numbers. Cryptology ePrint Archive, Report 2019/417 (2019). https://​eprint.​iacr.​org/​2019/​417, To appear ASIACRYPT 2019
15.
Cheon, J.H., Kim, D., Kim, Y., Song, Y.: Ensemble method for privacy-preserving logistic regression based on homomorphic encryption. IEEE Access 6, 46938–46948 (2018)CrossRef
16.
17.
18.
Cho, H., Wu, D.J., Berger, B.: Secure genome-wide association analysis using multiparty computation. Nat. Biotechnol. 36(6), 547 (2018)CrossRef
19.
Crawford, J.L., Gentry, C., Halevi, S., Platt, D., Shoup, V.: Doing real work with FHE: the case of logistic regression (2018)
20.
Dhillon, I.S., Marcotte, E.M., Roshan, U.: Diametrical clustering for identifying anti-correlated gene clusters. Bioinformatics 19(13), 1612–1619 (2003)CrossRef
21.
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, PAIS 2008, New York, NY, USA, pp. 3–11. ACM (2008)
22.
Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. Wiley, Hoboken (2012)MATH
23.
Freedman, D., Kisilev, P.: Fast mean shift by compact density representation. In: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1818–1825. IEEE (2009)
24.
25.
Gilad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: CryptoNets: applying neural networks to encrypted data with high throughput and accuracy. In: International Conference on Machine Learning, pp. 201–210 (2016)
26.
Goldschmidt, R.E.: Applications of division by convergence. Ph.D. thesis, Massachusetts Institute of Technology (1964)
27.
Han, K., Hong, S., Cheon, J.H., Park, D.: Logistic regression on homomorphic encrypted data at scale (2019)CrossRef
28.
Jagannathan, G., Wright, R.N.: Privacy-preserving distributed k-means clustering over arbitrarily partitioned data. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD 2005, New York, NY, USA, pp. 593–599. ACM (2005)
29.
30.
Kim, A., Song, Y., Kim, M., Lee, K., Cheon, J.H.: Logistic regression model training based on the approximate homomorphic encryption. BMC Med. Genomics 11(4), 83 (2018)CrossRef
31.
Kim, M., Song, Y., Wang, S., Xia, Y., Jiang, X.: Secure logistic regression based on homomorphic encryption: design and evaluation. JMIR Med. Inform. 6(2), e19 (2018)CrossRef
32.
33.
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)
34.
Malik, M.B., Ghazi, M.A., Ali, R.: Privacy preserving data mining techniques: current scenario and future prospects. In: 2012 Third International Conference on Computer and Communication Technology (ICCCT), pp. 26–32. IEEE (2012)
35.
Meskine, F., Nait-Bahloul, S.: Privacy preserving k-means clustering: a survey research. Int. Arab J. Inf. Technol. 9, 03 (2012)
36.
Pouget, F., Dacier, M., et al.: Honeypot-based forensics. In: AusCERT Asia Pacific Information Technology Security Conference (2004)
37.
Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987)CrossRef
38.
39.
Samet, S., Miri, A., Orozco-Barbosa, L.: Privacy preserving k-means clustering in multi-party environment, January 2007
40.
Su, C., Bao, F., Zhou, J., Takagi, T., Sakurai, K.: Privacy-preserving two-party k-means clustering via secure approximation. In: Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops - Volume 01, AINAW 2007, Washington, DC, USA, pp. 385–391. IEEE Computer Society (2007)
41.
Sugar, C.A., James, G.M.: Finding the number of clusters in a dataset: an information-theoretic approach. J. Am. Stat. Assoc. 98(463), 750–763 (2003)MathSciNetCrossRef
42.
43.
Vaidya, J., Clifton, C.: Privacy-preserving k-means clustering over vertically partitioned data. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2003, New York, NY, USA, pp. 206–215. ACM (2003)
44.
Vinoth, K.J., Santhi, V.: A brief survey on privacy preserving techniques in data mining. IOSR J. Comput. Eng. (IOSR-JCE) 18, 47–51 (2016)
45.
Wang, S., et al.: HEALER: homomorphic computation of exact logistic regression for secure rare disease variants analysis in GWAS. Bioinformatics 32(2), 211–218 (2016)
46.
Wang, Y.: Notes on two fully homomorphic encryption schemes without bootstrapping. IACR Cryptology ePrint Archive, 2015:519 (2015)
Metadaten
Titel
Towards a Practical Cluster Analysis over Encrypted Data
verfasst von
Jung Hee Cheon
Duhyeong Kim
Jai Hyun Park
Copyright-Jahr
2020
Buch
Selected Areas in Cryptography – SAC 2019

Print ISBN: 978-3-030-38470-8

Electronic ISBN: 978-3-030-38471-5

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-38471-5_10

Premium Partner

    Bildnachweise