LEA: Label Enumeration Attack in Vertical Federated Learning

This paper introduces LEA, a novel and practical Label Enumeration Attack in Vertical Federated Learning that bypasses the need for auxiliary data by utilizing clustering and first-round loss gradient similarity to efficiently enumerate label mappings, while overcoming computational bottlenecks through a Binary-LEA optimization that reduces complexity from $n!$ to $n^3$ and remains effective against common defense mechanisms.

The Gist

Imagine a group of friends trying to solve a mystery together, but they are all in different rooms and can't share their full notebooks. This is Vertical Federated Learning (VFL).

• The Setup: Everyone has different clues about the same set of suspects (samples).
  • Friend A (The Active Party): Has the "Answer Key" (the labels, like "Guilty" or "Innocent"), but no other clues.
  • Friend B (The Passive Party): Has a bunch of clues (features like height, shoe size, alibi), but no answer key.
• The Goal: They want to build a super-smart detective AI together without Friend A ever showing the Answer Key to Friend B, and without Friend B showing their raw clues to Friend A.

The Problem: The Sneaky Spy

The paper introduces a new trick called LEA (Label Enumeration Attack). It's like a spy (Friend B) trying to figure out the Answer Key just by watching how the group solves the puzzle, without ever seeing the key itself.

Previous spy tricks had a big flaw: the spy needed to have a copy of the Answer Key for a few suspects beforehand to make the guess work. If the spy had zero prior knowledge, they were stuck.

LEA changes the game. The spy doesn't need any prior knowledge. They just need to be smart about how they group the suspects.

How the Attack Works (The "Guessing Game" Analogy)

Imagine the suspects are people at a party, and the Answer Key is their favorite ice cream flavor (Chocolate, Vanilla, or Strawberry). The spy (Passive Party) sees everyone's outfits but doesn't know their flavors.

Step 1: The Grouping (Clustering)
The spy looks at the outfits and says, "Okay, these 10 people are wearing all black, these 10 are in bright neon, and these 10 are in suits." They group them into three piles.

• The Spy's Intuition: "People who dress similarly probably like the same ice cream."

Step 2: The "What If" Simulation (Enumeration)
Now, the spy plays a massive game of "What If."

• Scenario A: Maybe the Black pile likes Chocolate, Neon likes Vanilla, Suits like Strawberry.
• Scenario B: Maybe Black likes Vanilla, Neon likes Strawberry, Suits like Chocolate.
• ...and so on.

If there are 10 flavors, there are millions of ways to assign flavors to these piles. The spy creates a million "fake detectives" (simulated models), each one assuming a different flavor assignment.

Step 3: The "First Step" Test (The Secret Sauce)
Here is the clever part. The spy doesn't wait for the fake detectives to finish their whole training (which would take forever). They just watch them take one single step of learning.

• The spy watches the real group take one step.
• The spy watches all the fake groups take one step.
• The Magic: The fake detective whose "one step" looks most similar to the real group's step is the winner!

Why? Because if the spy guessed the ice cream flavors correctly, that fake detective will react to the clues in the exact same way the real detective does. If the guess is wrong, the reaction will be totally different.

Step 4: The Win
The spy picks the winning fake detective. Now, the spy has a model that knows the ice cream flavors. They can look at any new person and say, "That person is wearing a suit, so they must like Strawberry!" The spy has stolen the secret labels without ever asking for them.

The "Binary" Shortcut (Binary-LEA)

If there are 10 ice cream flavors, checking every single combination is like trying to find a needle in a haystack the size of a city. It takes too long.

The authors invented Binary-LEA. Instead of guessing all 10 flavors at once, the spy plays a simpler game:

• "Is this person Chocolate OR Vanilla?" (Ignore the rest).
• "Is this person Strawberry OR Mint?"
• They break the big, impossible puzzle into many small, easy puzzles. This makes the attack 100,000 times faster and much more practical.

Can You Stop It? (The Defenses)

The paper tested common security shields:

1. Adding Noise (Static): Imagine the group adds random static to their conversation. The spy found that even with static, they could still hear the "rhythm" of the correct guess.
2. Compressing Data (Summarizing): Imagine the group only sends the most important words. The spy found that even with fewer words, the pattern was still clear enough to guess the answer.
3. The "Code Book" (Label Mapping): The authors suggested a new defense: The Answer Key holder changes the names of the flavors (e.g., "Guilty" becomes "X", "Innocent" becomes "Y") before sharing.
   • Does it work? Yes, but only if the spy has no outside help. If the spy has even a tiny bit of outside info (like knowing one person is definitely "Guilty"), they can crack the code book and win again.

The Big Takeaway

This paper shows that in Vertical Federated Learning, just having your own data isn't enough to keep your secrets safe. Even if you don't have the labels, if you can group your data smartly and watch how the model learns, you can reverse-engineer the secrets.

It's like realizing that even if you don't have the answer key, you can figure out the answers just by watching how the teacher grades the test, provided you know how the students are sitting in the room.

Technical Summary

1. Problem Statement

Vertical Federated Learning (VFL) allows multiple parties to collaboratively train a model where each party holds different features for the same set of samples, but only one party (the Active Party) holds the labels. While VFL is designed to protect data privacy, the Passive Parties (who hold features but no labels) are vulnerable to Label Inference Attacks.

Existing label inference attacks suffer from significant limitations:

• Dependency on Auxiliary Data: Most state-of-the-art attacks (e.g., Passive Model Completion) require the attacker to possess a small portion of labeled auxiliary data to function effectively.
• Scenario Limitations: Many attacks are restricted to specific VFL architectures (e.g., only SplitVFL or only AggVFL) or specific model types.
• Practicality: In real-world scenarios, obtaining auxiliary labeled data is often impossible, rendering existing attacks impractical.

The paper addresses the critical gap: How can a passive party infer the active party's private labels without any auxiliary labeled data and across diverse VFL settings?

2. Methodology: Label Enumeration Attack (LEA)

The authors propose LEA, a novel attack based on the intuition that a passive party's local data is inherently classifiable. The attack proceeds in three main phases:

A. Clustering and Enumeration

1. Clustering: The adversary performs unsupervised clustering on their local feature data to group samples into $n$ clusters (where $n$ is the number of label classes).
2. Label Permutation: The adversary generates all possible permutations of the $n$ labels ($n!$ permutations).
3. Simulation: For each permutation, the adversary assigns the permuted labels to the $n$ clusters, creating $n!$ "simulated datasets."
4. Model Training: The adversary replicates their local model $n!$ times. Each simulated model is trained for one round on its corresponding simulated dataset using the local features.

B. Model Similarity Assessment (The Core Innovation)

To identify which simulated model corresponds to the true label mapping, the adversary compares the simulated models against the model trained during the actual joint VFL process.

• Challenge: Comparing final model parameters is unreliable because neural networks can converge to different local optima even with identical data.
• Solution: The authors propose comparing the cosine similarity of the first-round loss gradients.
  • If the simulated label mapping matches the true labels, the direction of the gradient update will align closely with the gradient received from the active party during joint training.
  • The simulated model yielding the highest cosine similarity with the real training gradient is identified as the Attack Model.

C. Binary-LEA (Optimization)

Training $n!$ models is computationally prohibitive for large $n$ (e.g., $10! \approx 3.6$ million). To solve this, the authors introduce Binary-LEA:

• Strategy: Decompose the $n$-class problem into $\lfloor n/2 \rfloor$ binary classification tasks.
• Process: The adversary selects two clusters at a time and enumerates permutations only for those two labels.
• Complexity Reduction: This reduces the computational complexity from $O(n!)$ to $O(n^3)$, making the attack feasible for multi-class tasks.

3. Key Contributions

1. Auxiliary-Data-Free Attack: LEA is the first label inference attack that requires no auxiliary labeled data, relying solely on the passive party's local features and unsupervised clustering.
2. General Applicability: The attack works across both AggVFL (aggregation-based) and SplitVFL (split-model) scenarios and supports both Logistic Regression and Neural Network models.
3. Gradient-Based Similarity Metric: The paper establishes that comparing first-round loss gradients is superior to comparing final parameters for identifying the correct label mapping, offering higher precision and efficiency.
4. Binary-LEA Optimization: The introduction of Binary-LEA drastically reduces the computational burden, enabling attacks on high-cardinality classification tasks.
5. Defense Evaluation: The paper evaluates common defenses (Gradient Noise, Gradient Compression) and finds them largely ineffective against LEA. It proposes a Label Mapping Table defense but notes its limitations.

4. Experimental Results

The authors evaluated LEA on three real-world datasets: Breast Cancer (binary), Give-me-some-credit (binary), and MNIST (multi-class: 3, 5, and 10 classes).

• Attack Accuracy:
  • In the absence of auxiliary data, LEA achieved 50% to 90% higher accuracy than existing state-of-the-art attacks (like Passive Model Completion).
  • Binary Tasks: Attack Success Rate (ASR) exceeded 90% on Breast Cancer and Give-me-some-credit datasets.
  • Multi-class Tasks: On MNIST-10, LEA achieved an ASR of 82.8% (SplitVFL) and 94.0% (AggVFL).
• Correlation with Clustering: The attack success rate is directly proportional to the Cluster Accuracy (CA). Even with limited features (e.g., 10% of features in Breast Cancer), if clustering is accurate, the attack succeeds.
• Efficiency: Binary-LEA reduced the number of simulated models from millions to hundreds. For MNIST-10, LEA would take ~3 years to compute, whereas Binary-LEA took ~4,900 seconds.
• Defense Resilience:
  • Gradient Noise: Adding Laplace noise did not significantly degrade LEA's accuracy unless the noise was excessive enough to disrupt the original task.
  • Gradient Compression: LEA remained effective even with high compression ratios.
  • Label Mapping Table: This defense failed if the adversary had even a small amount of auxiliary data or if the label distribution was highly imbalanced (allowing the attacker to guess based on cluster size).

5. Significance and Implications

• Security Vulnerability: LEA reveals a fundamental privacy flaw in VFL: even without auxiliary data, the structural relationship between features and labels can be reverse-engineered through enumeration and gradient analysis.
• Redefining Threat Models: The paper forces a re-evaluation of VFL security assumptions. The "honest-but-curious" passive party is a far greater threat than previously modeled, as they do not need external data to compromise privacy.
• Defense Challenges: The ineffectiveness of standard gradient perturbation and compression techniques suggests that current VFL defenses are insufficient against enumeration-based attacks. Future research must focus on mechanisms that break the correlation between local feature clustering and global label inference, such as the proposed (but imperfect) label mapping tables or more robust cryptographic protocols.

In conclusion, LEA demonstrates that label privacy in VFL is fragile and that existing defenses are inadequate against sophisticated enumeration attacks that leverage unsupervised learning and gradient analysis.