Secure k-means Clustering using Homomorphic Encryption

Machine Learning as a Service (MLaaS) enables users to outsource compute-intensive analytics, but processing sensitive data in clear on a cloud server raises strong privacy concerns. Fully Homomorphic Encryption (FHE) enables computations over encrypted data, yet implementing k-means under FHE is challenging because the assignment step requires repeated comparisons (argmin), while centroid updates involve divisions. We propose a TFHE-based privacy-preserving k-means protocol that performs the entire assignment step homomorphically. For each iteration, the cloud evaluates encrypted comparisons of squared Euclidean distance differences using TFHE programmable bootstrapping, and returns encrypted one-hot assignment vectors. The client decrypts only these assignment vectors once per iteration to update centroids in clear and sends the refreshed centroids back. This design eliminates any server-side decryption and avoids trusted third parties while keeping client work lightweight. We evaluate on several real datasets using ARI/NMI (when labels exist) and internal metrics (inertia/silhouette). The encrypted clustering closely matches plaintext Forgy k-means for moderate numbers of clusters, while runtime is dominated by bootstrapping operations and thus benefits from parallelization.