# Deciphering the Interplay between Attack and Protection Complexity in Privacy-Preserving Federated Learning

arXiv: https://arxiv.org/abs/2508.11907 · HTML: https://mlsanity.com/paper/2508.11907/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 17 references that are in the map.
- First posted on arXiv 16 Aug 2025.

## Builds on (most cited first, 10 of 10)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [iDLG: Improved Deep Leakage from Gradients](https://mlsanity.com/paper/2001.02610/) (2020)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [Towards Achieving Near-optimal Utility for Privacy-Preserving Federated Learning via Data Generation and Parameter Distortion](https://mlsanity.com/paper/2305.04288/) (2023)
- [Theoretically Principled Federated Learning for Balancing Privacy and Utility](https://mlsanity.com/paper/2305.15148/) (2023)
- [A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning](https://mlsanity.com/paper/2305.18400/) (2023)
- [Context-aware Data Aggregation with Localized Information Privacy](https://mlsanity.com/paper/1804.02149/) (2018)

## Abstract (arXiv)

Federated learning (FL) offers a promising paradigm for collaborative model training while preserving data privacy. However, its susceptibility to gradient inversion attacks poses a significant challenge, necessitating robust privacy protection mechanisms. This paper introduces a novel theoretical framework to decipher the intricate interplay between attack and protection complexities in privacy-preserving FL. We formally define "Attack Complexity" as the minimum computational and data resources an adversary requires to reconstruct private data below a given error threshold, and "Protection Complexity" as the expected distortion introduced by privacy mechanisms. Leveraging Maximum Bayesian Privacy (MBP), we derive tight theoretical bounds for protection complexity, demonstrating its scaling with model dimensionality and privacy budget. Furthermore, we establish comprehensive bounds for attack complexity, revealing its dependence on privacy leakage, gradient distortion, model dimension, and the chosen privacy level. Our findings quantitatively illuminate the fundamental trade-offs between privacy guarantees, system utility, and the effort required for both attacking and defending. This framework provides critical insights for designing more secure and efficient federated learning systems.