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

• URL: http://arxiv.org/abs/2409.14260v1
• Date: Sat, 21 Sep 2024 23:01:33 GMT
• Title: Perfect Gradient Inversion in Federated Learning: A New Paradigm from the Hidden Subset Sum Problem
• Authors: Qiongxiu Li, Lixia Luo, Agnese Gini, Changlong Ji, Zhanhao Hu, Xiao Li, Chengfang Fang, Jie Shi, Xiaolin Hu,
• Abstract summary: Federated Learning (FL) has emerged as a popular paradigm for collaborative learning among multiple parties. We formulate the input reconstruction problem using the gradient information shared in FL as the Hidden Subset Sum Problem. Our analysis provides insights into why empirical input reconstruction attacks degrade with larger batch sizes.
• Score: 21.546869377126125
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning [48.41770886055744]
  Federated Learning has seen an increased deployment in real-world scenarios recently.<n>The introduction of the so-called gradient inversion attacks has challenged its privacy-preserving properties.<n>We introduce SPEAR, which is based on a theoretical analysis of the gradients of linear layers with ReLU activations.<n>Our new attack, SPEAR++, retains all desirable properties of SPEAR, such as robustness to DP noise and FedAvg aggregation.
  arXiv  Detail & Related papers  (2025-10-28T09:06:19Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture. Non-smooth regularization is often incorporated into machine learning tasks. We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Privacy-Preserving Distributed Learning for Residential Short-Term Load Forecasting [11.185176107646956]
  Power system load data can inadvertently reveal the daily routines of residential users, posing a risk to their property security. We introduce a Markovian Switching-based distributed training framework, the convergence of which is substantiated through rigorous theoretical analysis. Case studies employing real-world power system load data validate the efficacy of our proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-02T16:39:08Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• GIFD: A Generative Gradient Inversion Method with Feature Domain Optimization [52.55628139825667]
  Federated Learning (FL) has emerged as a promising distributed machine learning framework to preserve clients' privacy. Recent studies find that an attacker can invert the shared gradients and recover sensitive data against an FL system by leveraging pre-trained generative adversarial networks (GAN) as prior knowledge. We propose textbfGradient textbfInversion over textbfFeature textbfDomains (GIFD), which disassembles the GAN model and searches the feature domains of the intermediate layers.
  arXiv  Detail & Related papers  (2023-08-09T04:34:21Z)
• Mixed Precision Quantization to Tackle Gradient Leakage Attacks in Federated Learning [1.7205106391379026]
  Federated Learning (FL) enables collaborative model building among a large number of participants without the need for explicit data sharing. This approach shows vulnerabilities when privacy inference attacks are applied to it. In particular, in the event of a gradient leakage attack, which has a higher success rate in retrieving sensitive data from the model gradients, FL models are at higher risk due to the presence of communication in their inherent architecture.
  arXiv  Detail & Related papers  (2022-10-22T04:24:32Z)
• Feature Reconstruction Attacks and Countermeasures of DNN training in Vertical Federated Learning [39.85691324350159]
  Federated learning (FL) has increasingly been deployed, in its vertical form, among organizations to facilitate secure collaborative training over siloed data. Despite the increasing adoption of VFL, it remains largely unknown if and how the active party can extract feature data from the passive party. This paper makes the first attempt to study the feature security problem of DNN training in VFL.
  arXiv  Detail & Related papers  (2022-10-13T06:23:47Z)
• Cocktail Party Attack: Breaking Aggregation-Based Privacy in Federated Learning using Independent Component Analysis [26.233860960220483]
  Federated learning (FL) aims to perform privacy-preserving machine learning on distributed data held by multiple data owners. To this end, FL requires the data owners to perform training locally and share the gradient updates with the central server, which are then securely aggregated over multiple data owners. Although aggregation by itself does not provably offer privacy protection, prior work showed that it may suffice if the batch size is sufficiently large.
  arXiv  Detail & Related papers  (2022-09-12T20:01:53Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Do Gradient Inversion Attacks Make Federated Learning Unsafe? [70.0231254112197]
  Federated learning (FL) allows the collaborative training of AI models without needing to share raw data. Recent works on the inversion of deep neural networks from model gradients raised concerns about the security of FL in preventing the leakage of training data. In this work, we show that these attacks presented in the literature are impractical in real FL use-cases and provide a new baseline attack.
  arXiv  Detail & Related papers  (2022-02-14T18:33:12Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Local Learning Matters: Rethinking Data Heterogeneity in Federated Learning [61.488646649045215]
  Federated learning (FL) is a promising strategy for performing privacy-preserving, distributed learning with a network of clients (i.e., edge devices)
  arXiv  Detail & Related papers  (2021-11-28T19:03:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.