Perfect Gradient Inversion in Federated Learning: A New Paradigm from the Hidden Subset Sum Problem

Qiongxiu Li, Lixia Luo, Agnese Gini, Changlong Ji, Zhanhao Hu, Xiao Li, Chengfang Fang, Jie Shi, Xiaolin HuarXiv 2024 · DOI · arXiv

Introduction

Federated Learning (FL) is often championed as a privacy-preserving framework because it allows multiple parties to train a shared model without ever exchanging raw data. Instead, participants share only model updates, such as gradients. However, the security of this approach relies on the assumption that gradients do not leak sensitive information.

While "Gradient Inversion Attacks" have previously demonstrated that data can be recovered from these updates, most existing methods rely on optimization-based heuristics. These methods often produce blurry reconstructions and struggle with large batch sizes. This paper introduces a paradigm shift, reframing gradient inversion as a cryptographic challenge: the Hidden Subset Sum Problem (HSSP). By moving from optimization to exact mathematical solvers, the authors achieve perfect data reconstruction and provide a rigorous theoretical foundation for FL privacy defenses.

The Limitations of Optimization-Based Inversion

Traditional attacks, such as Deep Leakage from Gradients (DLG), treat inversion as an optimization problem. An adversary starts with "dummy" data and iteratively updates it until the resulting gradients match the observed ones. While influential, these methods face several "real-world" hurdles:

  • Local Minima: Optimization can get stuck, leading to failed or noisy reconstructions.
  • Batch Constraints: Accuracy drops significantly as batch sizes increase or when a batch contains multiple samples from the same class.
  • Heuristic Nature: These attacks offer little insight into the fundamental limits of privacy or why certain defenses work.

Mapping Gradients to the Hidden Subset Sum Problem

The authors focus on Multi-Layer Perceptrons (MLPs) using ReLU activation. They demonstrate that the gradients of the first layer can be mathematically decomposed into a product of matrices involving the input data and a binary matrix representing the activation states.

This specific structure allows the attack to be mapped onto the Hidden Subset Sum Problem (HSSP), a classic problem in lattice-based cryptography. To solve this, the researchers employ three distinct cryptographic strategies:

  1. NS Attack (Nguyen-Stern): An orthogonal lattice-based approach.
  2. Multivariate Approach: Solving the problem through systems of quadratic polynomials.
  3. Statistical Approach: Utilizing a "learning a parallelepiped" technique.

By treating the gradient as a cryptographic ciphertext and the training data as the hidden key, the authors use lattice reduction algorithms (such as LLL and BKZ) to extract the exact original inputs.

Key Advantages: Precision and Robustness

This cryptographic approach offers several advantages over previous optimization-based methods:

Perfect Reconstruction

Unlike optimization attacks that produce "similar" images, the HSSP formulation allows for perfect reconstruction. When the lattice reduction succeeds, the result is bit-for-bit identical to the original data, achieving a Mean Squared Error (MSE) of 0 and a Structural Similarity Index (SSIM) of 1.

Label Diversity Independence

Many previous attacks required a batch to have diverse labels to distinguish between samples. Because this method analyzes the underlying linear algebra of the weights, it can perfectly reconstruct a batch even if every sample belongs to the same class (e.g., a batch consisting entirely of different "cat" images).

Efficiency via Subsampling

The researchers discovered that they do not need the entire gradient matrix to succeed. By subsampling a specific number of neurons ($m \approx 2B$, where $B$ is the batch size), they can significantly accelerate the attack without sacrificing accuracy.

The Computational Complexity of Privacy

One of the paper's most significant contributions is providing a mathematical explanation for the effectiveness of common FL defenses. The authors derive a theoretical time complexity for the attack of approximately $O(B^9)$.

This steep complexity curve explains why increasing the batch size is such an effective defense: doubling the batch size doesn't just double the difficulty; it increases the computational cost by a factor of over 500. Furthermore, when Secure Aggregation is used—where $N$ clients aggregate their gradients—the complexity jumps to $O(N^9 B^9)$. This provides a rigorous mathematical substantiation for why secure aggregation is a robust defense against gradient leakage.

Experimental Results

The authors validated their approach across diverse datasets, including MNIST, CIFAR-10, CIFAR-100, ImageNet, and the Purchase dataset (a tabular dataset of shopping histories). In experiments with a batch size of 10, all three HSSP-based attacks achieved perfect reconstruction across all data types. Empirical timing tests confirmed the $O(B^9)$ complexity, showing that while small batches are cracked in seconds, larger batches quickly become computationally prohibitive for standard hardware.

Conclusion and Future Work

By reframing gradient inversion as a cryptographic puzzle, this research moves the study of FL privacy from empirical observation to mathematical certainty. While the current HSSP formulation is tailored to MLPs with ReLU activations, it sets a new standard for what constitutes a "successful" attack.

Future work remains to extend this framework to more complex architectures like Convolutional Neural Networks (CNNs) or Transformers, where the spatial and attention-based abstractions make the simple matrix product model more difficult to apply. Additionally, the authors suggest that incorporating "bias" gradients, which were not fully utilized in this study, could further increase the potency of these cryptographic attacks.

Summary updated

Abstract

Federated Learning (FL) has emerged as a popular paradigm for collaborative learning among multiple parties. It is considered privacy-friendly because local data remains on personal devices, and only intermediate parameters -- such as gradients or model updates -- are shared. Although gradient inversion is widely viewed as a common attack method in FL, analytical research on reconstructing input training samples from shared gradients remains limited and is typically confined to constrained settings like small batch sizes. In this paper, we aim to overcome these limitations by addressing the problem from a cryptographic perspective. We mathematically formulate the input reconstruction problem using the gradient information shared in FL as the Hidden Subset Sum Problem (HSSP), an extension of the well-known NP-complete Subset Sum Problem (SSP). Leveraging this formulation allows us to achieve perfect input reconstruction, thereby mitigating issues such as dependence on label diversity and underperformance with large batch sizes that hinder existing empirical gradient inversion attacks. Moreover, our analysis provides insights into why empirical input reconstruction attacks degrade with larger batch sizes. By modeling the problem as HSSP, we demonstrate that the batch size \( B \) significantly affects attack complexity, with time complexity reaching \( \mathcal{O}(B^9) \). We further show that applying secure data aggregation techniques -- such as homomorphic encryption and secure multiparty computation -- provides a strong defense by increasing the time complexity to \( \mathcal{O}(N^9 B^9) \), where \( N \) is the number of local clients in FL. To the best of our knowledge, this is the first work to rigorously analyze privacy issues in FL by modeling them as HSSP, providing a concrete analytical foundation for further exploration and development of defense strategies.
BibTeX
@misc{li2024perfect,
  author = {Qiongxiu Li and Lixia Luo and Agnese Gini and Changlong Ji and Zhanhao Hu and Xiao Li and Chengfang Fang and Jie Shi and Xiaolin Hu},
  title = {{Perfect Gradient Inversion in Federated Learning: A New Paradigm from the Hidden Subset Sum Problem}},
  year = {2024},
  eprint = {2409.14260},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.14260},
}
Figure