Breaking Privacy in Federated Clustering: Perfect Input Reconstruction via Temporal Correlations

Guang Yang, Lixia Luo, Qiongxiu LiarXiv 2025 · DOI · arXiv

Introduction

Federated $k$-means clustering is a popular technique allowing multiple parties to collaboratively group their data without sharing raw samples. To maintain efficiency, many protocols require clients to share intermediate statistics, such as cluster centroids or sums, with a central server. For years, this practice was considered relatively safe, based on the assumption that the underlying "Hidden Subset Sum Problem" (HSSP) was mathematically intractable. It was believed that because the number of data points typically far exceeds the number of clusters, an attacker could not work backward from aggregate sums to individual private inputs.

This paper challenges that assumption by introducing Trajectory-Aware Reconstruction (TAR), an attack that exploits temporal correlations in how data points move between clusters to achieve perfect, bit-for-bit reconstruction of private user data.

Methodology: Trajectory-Aware Reconstruction (TAR)

Unlike previous privacy attacks that analyzed clustering iterations in isolation, TAR focuses on the path or trajectory a data point takes across different clusters over time. The attack follows a structured five-step process:

  1. Difference Analysis: Calculating changes in cluster sums between iterations to identify mass movement.
  2. Template Building: Creating blocks that represent possible switching patterns (e.g., a point moving from Cluster A to Cluster B).
  3. Recursive Combination: Constructing a global assignment matrix ($W^\star$) that captures all observed trajectories across all time steps.
  4. Stationary Accounting: Adding identity blocks to account for data points that remain in the same cluster.
  5. RREF Leakage Test: Applying Reduced Row Echelon Form (RREF) to the resulting system of equations.

The core insight is that even in an underdetermined system, if the RREF version of the matrix contains a row with exactly one non-zero entry, that specific data point is uniquely determined. This allows for the exact reconstruction of individual samples even if the entire dataset cannot be solved.

Key Results

The researchers validated the TAR attack across synthetic, tabular (Iris), and high-dimensional image datasets. The results were particularly devastating for image data, where the high dimensionality was previously thought to provide a layer of protection.

Visual comparison of original faces (top row) and reconstructed faces (bottom row) using the TAR attack on the Olivetti Faces dataset, demonstrating perfect visual reconstruction.

On the Olivetti Faces dataset ($n=400, d=4096$), the attack achieved a 77% success rate. As shown in the figure above, the reconstructed images are visually indistinguishable from the originals, representing a total privacy breach. In synthetic and tabular tests, the attack maintained a success rate between 43% and 51%.

Discussion and Insights

Several critical vulnerabilities were identified through this research:

  • Temporal Regularity as a Liability: In $k$-means, points do not move randomly; they follow predictable trajectories that drastically reduce the search space for an attacker.
  • The Truncation Paradox: Releasing only the final iterations of centroids can actually make the attack more successful. Late-stage iterations have more stable cluster assignments, leading to a sparser assignment matrix that is easier to solve via RREF.
  • Dimensionality is Not a Defense: While HSSP is harder in high dimensions, TAR's exploitation of temporal paths remains effective even on complex image data with thousands of features.

Conclusion and Future Work

The TAR attack demonstrates a fundamental tension between the efficiency of federated learning and the privacy of user data. While Differential Privacy (DP) can mitigate these algebraic attacks by injecting noise, it often comes at the cost of clustering accuracy. This work serves as a call to the research community to move beyond the perceived hardness of HSSP and adopt more robust cryptographic defenses, such as Secure Multi-Party Computation (SMPC) or Homomorphic Encryption (HE), to ensure true data privacy in federated environments.

Summary updated

Abstract

Federated clustering allows multiple parties to discover patterns in distributed data without sharing raw samples. To reduce overhead, many protocols disclose intermediate centroids during training. While often treated as harmless for efficiency, whether such disclosure compromises privacy remains an open question. Prior analyses modeled the problem as a so-called Hidden Subset Sum Problem (HSSP) and argued that centroid release may be safe, since classical HSSP attacks fail to recover inputs. We revisit this question and uncover a new leakage mechanism: temporal regularities in $k$-means iterations create exploitable structure that enables perfect input reconstruction. Building on this insight, we propose Trajectory-Aware Reconstruction (TAR), an attack that combines temporal assignment information with algebraic analysis to recover exact original inputs. Our findings provide the first rigorous evidence, supported by a practical attack, that centroid disclosure in federated clustering significantly compromises privacy, exposing a fundamental tension between privacy and efficiency.
BibTeX
@misc{yang2025breaking,
  author = {Guang Yang and Lixia Luo and Qiongxiu Li},
  title = {{Breaking Privacy in Federated Clustering: Perfect Input Reconstruction via Temporal Correlations}},
  year = {2025},
  eprint = {2511.07073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.07073},
}
Figure