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 workflow, as illustrated in the protocol diagram, consists of several key stages:
- Secure Outsourcing: Bob encrypts his features and sends them to Alice.
- Distance and Cluster Computation: Alice computes squared Euclidean distances and performs the "argmin" operation to assign clusters.
- Within-Cluster Aggregation: Alice calculates the sums and counts for each cluster under encryption.
- Noise Injection: Differential Privacy noise is added to the aggregated sums and counts before they are decrypted.
- 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.
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