Introduction
Federated Learning (FL) has emerged as a cornerstone of privacy-preserving machine learning, allowing multiple parties to collaboratively train models without sharing their raw data. By only exchanging model updates, such as gradients, FL aims to mitigate the risks associated with centralized data storage. To further bolster security, techniques like Additive Homomorphic Encryption (HE) are often employed to protect these gradients during transit.
However, recent research has begun to challenge the assumption that gradients are inherently safe. While complex architectures like Convolutional Neural Networks (CNNs) have been shown to leak information, simpler models like Logistic Regression were often perceived as more secure. This paper investigates the vulnerability of Federated Approximated Logistic Regression, particularly when dealing with binary-encoded data, and demonstrates that an "honest-but-curious" participant can mathematically reconstruct a partner's private dataset.
The Vulnerability of Approximated Logistic Regression
Logistic Regression typically utilizes the sigmoid function, which is non-linear and computationally expensive to evaluate within Homomorphic Encryption frameworks. Consequently, researchers often use polynomial approximations of the sigmoid function. This paper explores whether these approximations, combined with the structural simplicity of the model, create a backdoor for data reconstruction.
The authors focus on scenarios where training data is binary—a common format in sensitive fields such as genomics (presence/absence of genetic markers) and financial risk analysis (binary flags for credit history). In these cases, the input features $x$ satisfy the property $x^2 = x$. This mathematical identity is pivotal, as it allows for the simplification of complex gradient equations.
Attack Methodology: Linear Programming for Binary Data
The core of the proposed attack involves treating the shared gradient as a system of equations where the training samples are the unknowns. The authors analyze two primary training configurations:
- Synchronized Case: A participant computes and shares gradients immediately after processing a single batch of data.
- Asynchronized Case: A participant aggregates gradients over multiple batches before pushing an update.
In the synchronized setting, the quadratic equations governing the gradient can be collapsed into a Linear Programming (LP) problem due to the binary nature of the data. By solving this LP problem, an attacker can efficiently recover the original training bits. The authors prove that if the number of observed gradients is at least equal to the number of features ($d$), complete reconstruction is possible.
Experimental Evaluation
To assess the practical feasibility of this attack, the authors implemented the reconstruction process using the pulp Python library on a standard consumer-grade CPU (Intel i5-8500). The results, summarized in Table 1, demonstrate that reconstruction is computationally "cheap" for small to medium-sized batches.
As shown in the table, a batch of 5 samples with 20 features can be reconstructed in less than 2 seconds. Even as the batch size ($m$) and feature count ($d$) increase, the time remains manageable; for instance, a batch of 11 samples with 20 features takes approximately 27 minutes (1634.821 seconds). This highlights that the "honest-but-curious" threat is not merely theoretical but a practical concern for real-world FL deployments.
Discussion: Synchronized vs. Asynchronized Settings
The paper provides a rigorous mathematical foundation for these vulnerabilities. Theorem 1 establishes the leakage in asynchronized settings, while Theorem 2 reveals a critical defense mechanism: asynchronized updates using multiple batches can result in an "infinite" number of possible solutions for the underlying data. This makes exact reconstruction significantly more difficult compared to the synchronized case, where updates are frequent and granular.
However, the authors caution that even if exact reconstruction is thwarted, partial leakage may still occur. In synchronized settings, adding more participants does not necessarily enhance privacy; it may simply increase the effective batch size, which an attacker can still navigate if the underlying mathematical conditions for the LP attack are met.
Conclusion and Future Directions
This research underscores a significant privacy gap in Federated Learning for simple models. The binary vulnerability allows attackers to bypass traditional protections by solving linear systems derived from gradients.
Future work is needed to quantify "partial leakage"—determining how much information an attacker can infer even when an exact solution is unavailable. Potential defenses include shuffling data sequences, selective gradient pushing, or introducing differential privacy noise. As FL continues to be adopted in sensitive domains, understanding and mitigating these reconstruction attacks is paramount for maintaining data sovereignty.
Summary updated