Privacy-Preserving Vertical K-Means Clustering

Federico Mazzone, Trevor Brown, Florian Kerschbaum, Kevin H. Wilson, Maarten H. Everts, Florian Hahn, Andreas PeterarXiv 2025 · DOI · arXiv

Introduction

This paper presents a significant advancement in privacy-preserving machine learning, specifically targeting vertical k-means clustering. By integrating Homomorphic Encryption (HE) with Differential Privacy (DP), the authors have developed a solution that is orders of magnitude faster than traditional cryptographic methods while maintaining significantly higher accuracy than existing noise-based approaches.

In many collaborative data science scenarios, data is vertically partitioned. For instance, a hospital may hold a patient's medical records while an insurance company holds their claims history. To group these individuals into meaningful clusters, distances must be calculated using features from both parties. However, privacy regulations and competitive interests often prevent raw data sharing. Existing solutions like Multiparty Computation (MPC) are often too communication-intensive for practical use, while standard Differential Privacy methods can degrade data utility to the point of being unusable.

Proposed Protocol

The authors propose a hybrid protocol leveraging the CKKS Homomorphic Encryption scheme. HE allows mathematical operations to be performed on data while it remains encrypted, enabling a computing party to calculate distances without ever seeing the raw values.

The end-to-end protocol workflow between Alice and Bob, illustrating the integration of HE and DP.

The workflow, as illustrated in the protocol diagram, consists of several key stages:

  1. Secure Outsourcing: Bob encrypts his features and sends them to Alice.
  2. Distance and Cluster Computation: Alice computes squared Euclidean distances and performs the "argmin" operation to assign clusters.
  3. Within-Cluster Aggregation: Alice calculates the sums and counts for each cluster under encryption.
  4. Noise Injection: Differential Privacy noise is added to the aggregated sums and counts before they are decrypted.
  5. Centroid Update: The noisy aggregates are decrypted to update the centroids for the next iteration.

Technical Innovations

A core challenge in HE is the "argmin" operation (finding the closest cluster), which is non-polynomial and typically slow. The authors addressed this by developing a highly optimized encoding and SIMD (Single Instruction, Multiple Data) packing strategy.

Detailed view of the optimized distance computation using row and column encoding strategies.

By using smart matrix-to-vector encodings, the protocol can process thousands of data points in parallel within a single ciphertext. This optimization reduces the per-round communication cost from $O(nk)$ to $O(k)$, where $n$ is the number of points and $k$ is the number of clusters. For a dataset of 1 million points, this represents the difference between sending terabytes of data versus a few hundred megabytes.

Evaluation and Results

The protocol was evaluated on a variety of synthetic and real-world datasets, including loan records (60k), NYC taxi data (100k), and human activity recognition (10k).

Performance Benchmarks

On a 100Mbps network, clustering 100,000 points into 5 clusters took under 3 minutes. In contrast, state-of-the-art MPC solutions would require over 24 hours for the same task. Communication overhead was reduced by over 1,300x, requiring only 73MB compared to 101GB for leading MPC alternatives.

Accuracy and Utility

The protocol maintains high utility despite the addition of privacy noise. On the S1 dataset, it achieved 90.75% accuracy, nearly matching the plaintext baseline of 93.22% and far outperforming previous DP-only solutions (62.25%). Interestingly, the authors observed a "noise as regularizer" effect, where the DP noise occasionally helped the algorithm escape poor local minima, leading to better results than the plaintext version in some tests.

Conclusion and Future Work

This hybrid approach effectively breaks the performance bottleneck of privacy-preserving clustering. Future work may involve GPU acceleration—potentially reducing processing time for 1 million points to just 13 seconds—and the development of privacy-preserving convergence checks to allow the algorithm to stop dynamically when centroids stabilize.

Summary updated

Abstract

Clustering is a fundamental data processing task used for grouping records based on one or more features. In the vertically partitioned setting, data is distributed among entities, with each holding only a subset of those features. A key challenge in this scenario is that computing distances between records requires access to all distributed features, which may be privacy-sensitive and cannot be directly shared with other parties. The goal is to compute the joint clusters while preserving the privacy of each entity's dataset. Existing solutions using secret sharing or garbled circuits implement privacy-preserving variants of Lloyd's algorithm but incur high communication costs, scaling as O(nkt), where n is the number of data points, k the number of clusters, and t the number of rounds. These methods become impractical for large datasets or several parties, limiting their use to LAN settings only. On the other hand, a different line of solutions rely on differential privacy (DP) to outsource the local features of the parties to a central server. However, they often significantly degrade the utility of the clustering outcome due to excessive noise. In this work, we propose a novel solution based on homomorphic encryption and DP, reducing communication complexity to O(n+kt). In our method, parties securely outsource their features once, allowing a computing party to perform clustering operations under encryption. DP is applied only to the clusters' centroids, ensuring privacy with minimal impact on utility. Our solution clusters 100,000 two-dimensional points into five clusters using only 73MB of communication, compared to 101GB for existing works, and completes in just under 3 minutes on a 100Mbps network, whereas existing works take over 1 day. This makes our solution practical even for WAN deployments, all while maintaining accuracy comparable to plaintext k-means algorithms.
BibTeX
@misc{mazzone2025privacy,
  author = {Federico Mazzone and Trevor Brown and Florian Kerschbaum and Kevin H. Wilson and Maarten H. Everts and Florian Hahn and Andreas Peter},
  title = {{Privacy-Preserving Vertical K-Means Clustering}},
  year = {2025},
  eprint = {2504.07578},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.07578},
}
Figure