On the privacy of federated Clustering: A Cryptographic View

Qiongxiu Li, Lixia Luo

Abstract

The privacy concern in federated clustering has attracted considerable attention in past decades. Many privacy-preserving clustering algorithms leverage cryptographic techniques like homomorphic encryption or secure multiparty computation, to guarantee full privacy, i.e., no additional information is leaked other than the final output. However, given the iterative nature of clustering algorithms, consistently encrypting intermediate outputs, such as centroids, hampers efficiency. This paper delves into this intricate trade-off, questioning the necessity of continuous encryption in iterative algorithms. Using the federated K-means clustering as an example, we mathematically formulate the problem of reconstructing input private data from the intermediate centroids as a classical cryptographic problem called hidden subset sum problem (HSSP). Through an in-depth analysis, we show that existing lattice-based HSSP attacks fail in reconstructing the private data given the knowledge of intermediate centroids, thus it is secure to reveal them for the sake of efficiency.

Introduction

In federated clustering, multiple participants collaborate to group their data without sharing raw inputs. To ensure "full privacy," many existing methods use heavy-duty tools like Homomorphic Encryption (HE) or Secure Multi-Party Computation (SMPC) to hide every intermediate update, such as cluster centroids, during the iterative process. However, this "encrypt everything" approach is computationally expensive. This paper investigates whether revealing intermediate centroids inherently compromises privacy by asking: Can an honest-but-curious central server reconstruct private data points from the movement of centroids over time?

Methodology: Framing Privacy as HSSP

The authors bridge the gap between machine learning and cryptography by mathematically formulating the privacy risk as a Hidden Subset Sum Problem (HSSP). In this setup, the sum of data points in a cluster (derived from the centroid and cluster size) is treated as a hidden subset sum where both the data points (values) and cluster assignments (weights) are unknown to the attacker.

Theoretical comparison between Random and K-means HSSP formulations.

The study analyzes the Nguyen-Stern (NS) attack, a classic lattice-based method used to solve HSSPs. The core innovation lies in distinguishing between "random" HSSP instances and "K-means" HSSP instances. As shown in Table 1, K-means cluster assignments are not random; structural dependencies across iterations lead to a rank-deficient weight matrix, which fundamentally changes the attack's feasibility.

Key Insights: The "Structure" Shield

The research reveals that the inherent nature of clustering provides a natural defense against reconstruction:

  • Rank Deficiency: Unlike standard cryptographic attacks that rely on independent hidden weights, K-means weights are dependent because points rarely "jump" between clusters randomly. This results in $\text{Rank}(\mathbf{W}) \leq n$.
  • Short Vector Proliferation: Lattice attacks work by finding the shortest vectors in a lattice. In K-means, the dependencies create many "false" short vectors that are shorter than the actual data vectors, distracting the algorithm from the true private data.
  • Solution Ambiguity: Due to rank deficiency, even a correct guess of cluster assignments would yield infinitely many possible private data configurations for the same centroids.

Experimental Results

The theory was validated using the Iris dataset with 100 Monte Carlo runs. The NS attack successfully recovered hidden data in "random" HSSP scenarios but failed completely in "K-means" scenarios.

Comparison of attack performance on Random vs. K-means HSSP instances across recovered vector counts and L1 norms.

As illustrated in the experimental results, the number of true recovered vectors for K-means was zero (Figure 1c). Furthermore, the $L_1$ norm of recovered vectors for K-means deviated significantly from the true values (Figure 1b), whereas they matched perfectly in the random control group. These results suggest that disclosing intermediate centroids provides a massive speed boost without providing a clear path for reconstruction.

Conclusion and Future Work

This work demonstrates that the perceived trade-off between privacy and efficiency in federated K-means may be less severe than previously thought. While foundational lattice attacks fail, future research should explore a broader range of cryptographic or machine learning-based reconstruction attacks and test these findings on larger, higher-dimensional datasets. Additionally, the privacy profiles of other algorithms like DBSCAN or Gaussian Mixture Models remain an open area for investigation.

Summary updated

Abstract

The privacy concern in federated clustering has attracted considerable attention in past decades. Many privacy-preserving clustering algorithms leverage cryptographic techniques like homomorphic encryption or secure multiparty computation, to guarantee full privacy, i.e., no additional information is leaked other than the final output. However, given the iterative nature of clustering algorithms, consistently encrypting intermediate outputs, such as centroids, hampers efficiency. This paper delves into this intricate trade-off, questioning the necessity of continuous encryption in iterative algorithms. Using the federated K-means clustering as an example, we mathematically formulate the problem of reconstructing input private data from the intermediate centroids as a classical cryptographic problem called hidden subset sum problem (HSSP)-extended from an NP-complete problem called subset sum problem (SSP). Through an in-depth analysis, we show that existing lattice-based HSSP attacks fail in reconstructing the private data given the knowledge of intermediate centroids, thus it is secure to reveal them for the sake of efficiency. To the best of our knowledge, our work is the first to cast federated clustering's privacy concerns as a cryptographic problem HSSP such that a concrete and rigorous analysis can be conducted.
BibTeX
@inproceedings{li2024privacy,
  author = {Qiongxiu Li and Lixia Luo},
  title = {{On the privacy of federated Clustering: A Cryptographic View}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=XSlx2G9K5Z},
}
Figure