No More Guessing: a Verifiable Gradient Inversion Attack in Federated Learning

1. Problem Statement

Federated Learning (FL) allows distributed model training without sharing raw data, relying on the assumption that shared gradients do not reveal private inputs. However, Gradient Inversion Attacks (GIAs) have demonstrated that adversaries (specifically a malicious server) can reconstruct client training data from shared gradients.

The paper identifies a critical gap in existing GIAs, particularly for tabular data:

• Lack of Verifiability: Existing attacks (optimization-based, generative, or analytical) often produce reconstructions that are noisy or linear combinations of multiple samples. In vision and language tasks, attackers can use human inspection to judge plausibility. However, for numerical tabular data, there is no semantic way to verify if a reconstructed record is correct or a spurious artifact.
• Limitations of Current Analytical Attacks: The state-of-the-art analytical attack (CTP, Diana et al., 2025) uses a geometric approach to isolate samples but suffers from two main flaws:
  1. Unverifiability: It cannot certify if a reconstructed slice contains exactly one sample or multiple overlapping samples. It relies on a user-defined threshold ($\epsilon$) to stop searching, which is impossible to tune correctly without prior knowledge of the data distribution.
  2. Inadaptability: It blindly bisects all non-empty slices down to resolution $\epsilon$, wasting communication rounds on samples that were already isolated.

2. Methodology: Verifiable Gradient Inversion Attack (VGIA)

The authors propose VGIA, a novel analytical attack operating under a malicious server threat model. The server actively manipulates model parameters to force data leakage. The method consists of three core components:

A. Geometric Isolation with Algebraic Verification

VGIA builds on the observation that the activation boundary of a ReLU layer defines a hyperplane in the input space.

1. Hyperplane Probing: The server sets the weights of multiple neurons in the first layer to be identical ($W_a^i = w$) but assigns them different biases ($b_a^i$). This creates a series of parallel hyperplanes sweeping across the input space.
2. Slice Vectors: By querying gradients across consecutive hyperplanes, the server computes "slice vectors" ($s_k$), which represent the linear combination of samples falling between two hyperplanes.
3. The Verification Test (Proposition 4.1): This is the core innovation. If a slice contains a single sample, the slice vector from the current round must lie within the subspace spanned by the slice vectors of the next round (where the slice is further subdivided).
   • Mathematically, if $s_k \in \text{span}(s_{k}^{next}, s_{k+1}^{next}, \dots)$, the slice is certified to contain at most $q-2$ samples (where $q$ is the number of new hyperplanes).
   • If the condition holds and the slice is non-empty, the attacker can mathematically prove that the slice contains exactly one sample. This provides an explicit certificate of correctness, eliminating the need for heuristics or human inspection.

B. Adaptive Search Strategy

Unlike CTP, which bisects every slice until a fixed resolution $\epsilon$ is reached, VGIA is adaptive:

• Once a slice is certified to contain a single sample, it is removed from further search.
• Future hyperplane queries are allocated only to unexplored regions or slices that failed the verification test (indicating multiple samples).
• This significantly reduces the number of communication rounds required for full-batch reconstruction.

C. Analytical Reconstruction

Once a sample is isolated:

1. Input Recovery: The attacker recovers the input feature vector $x_k$ analytically by dividing the slice vector by a scaling factor derived from the loss gradient with respect to the bias.
2. Target Recovery: The attacker recovers the target label $y_k$ (even for continuous regression targets) by solving a lightweight univariate optimization problem that minimizes the difference between the observed gradient and the gradient computed with the recovered input.

3. Key Contributions

1. First Verifiable GIA for Tabular Data: VGIA is the first attack to provide an intrinsic, mathematical certificate that a reconstructed record is correct, addressing the "guessing" problem in tabular FL privacy.
2. Exact Recovery of Continuous Targets: The method proves the ability to recover continuous regression targets, a capability previously unproven in analytical attacks.
3. Adaptive Efficiency: By certifying isolation early, VGIA avoids unnecessary search rounds, outperforming previous geometric attacks in speed and resource efficiency.
4. Broad Applicability: The attack works on both tabular datasets (regression and classification) and image datasets (CIFAR10), demonstrating cross-domain applicability.

4. Experimental Results

The authors evaluated VGIA against the state-of-the-art CTP attack on four benchmarks: ACS Income (regression), King County Housing (regression), HARUS (classification), and CIFAR10 (images).

• Accuracy & Verifiability:
  • VGIA achieved exact reconstruction of all samples in the ACS Income dataset (size 2048) within 11 rounds.
  • Crucially, VGIA produced 0% spurious reconstructions (false positives). In contrast, CTP produced up to 30% spurious reconstructions in early rounds and could not distinguish them from true samples without ground truth.
• Efficiency:
  • VGIA required significantly fewer communication rounds to achieve full verifiability compared to CTP.
  • In scenarios where CTP failed to isolate samples due to poor $\epsilon$ tuning (e.g., $\epsilon > \epsilon_w$), VGIA continued searching until all samples were separated, eventually recovering 100% of the data.
• Robustness:
  • Under FedAvg (multiple local updates), VGIA maintained high accuracy (recovering >50% of samples in most settings), whereas CTP largely failed in regression scenarios due to its reliance on specific weight manipulations that drift with local updates.

5. Significance and Impact

• Privacy Risk Assessment: This work fundamentally changes how privacy risks in Federated Learning are assessed. It proves that tabular data is not inherently more secure than image data against malicious servers. The inability to verify reconstructions was a false sense of security; VGIA removes this uncertainty.
• Defense Implications: The existence of a verifiable attack implies that current FL defenses (like gradient compression or noise addition) must be rigorously tested against attacks that can mathematically certify success.
• Theoretical Advancement: The paper introduces a new algebraic framework for verifying sample isolation in high-dimensional spaces, moving the field from heuristic reconstruction to provable data recovery.

In conclusion, VGIA demonstrates that without specific privacy-preserving mechanisms, a malicious server can not only reconstruct private tabular records but also know with certainty that the reconstruction is correct, rendering the privacy guarantees of standard Federated Learning ineffective.