An Efficient Learning Framework For Federated XGBoost Using Secret Sharing And Distributed Optimization

This paper proposes a secure, lossless, and efficient multi-party federated XGBoost framework that utilizes secret sharing and distributed optimization to overcome data isolation issues and outperform existing state-of-the-art models in both security and performance.

The Gist

Imagine a group of banks, hospitals, and retail stores who all want to build a super-smart AI to predict credit card fraud or disease outbreaks. They have a problem: they can't share their data.

• Bank A has your spending history but no medical records.
• Hospital B has your health data but no spending history.
• Store C has your shopping habits but nothing else.

If they combined all their data in one giant database, they could build a much better AI. But laws and privacy rules say they can't do that. They need a way to train a model together without ever seeing each other's raw data. This is called Federated Learning.

This paper introduces a new, super-efficient way to do this specifically for a powerful AI tool called XGBoost. The authors call their solution MP-FedXGB.

Here is the breakdown using simple analogies:

1. The Problem: The "Secret Recipe" Dilemma

XGBoost is like a master chef who builds a decision tree to make predictions. To build this tree, the chef needs to ask questions like: "Is the customer's income over $50k?" or "Is the patient's blood pressure high?"

To find the best question, the chef has to do some heavy math involving division (splitting numbers) and finding the maximum (picking the best option).

• The Old Way (Homomorphic Encryption): Imagine the chef tries to cook while wearing thick, heavy oven mitts. He can stir the pot, but he can't feel the heat or taste the food easily. It works, but it's incredibly slow and exhausting.
• The Previous "Secret Sharing" Way: Imagine the chef asks two assistants to hold parts of the recipe. They can add and subtract numbers easily. But when the recipe requires division (cutting a cake into exact fractions) or finding the best option among many, the assistants get stuck. They have to play a complex game of "bit-by-bit" comparison that only works if there are exactly two people. If you add a third or fourth person, the game breaks.

2. The Solution: The "Magic Math" Trick

The authors, Xie and his team, invented a new framework that solves these math problems without ever revealing the actual data. They use a technique called Secret Sharing.

Think of Secret Sharing like a puzzle.

• You have a secret number (e.g., 10).
• You cut it into 4 pieces: 3, 2, 4, and 1.
• You give one piece to Bank A, one to Hospital B, etc.
• No one knows the number 10. They only know their own piece.
• But if they add their pieces together, they get 10 back.

The magic of this paper is how they handle the difficult math (division and finding the maximum) using only these puzzle pieces.

Analogy A: The "Common Denominator" Trick (Solving the Division Problem)

In the old method, to compare two fractions (like 3/4 vs. 5/8), you had to actually divide the numbers to see which is bigger. In the secret world, you can't divide.

The authors' trick is like this:
Instead of asking "Which fraction is bigger?", they ask: "If we multiply both fractions by the same giant number (the common denominator), which numerator is bigger?"

• Old Way: Calculate 3 ÷ 4 and 5 ÷ 8. (Hard to do with puzzle pieces).
• New Way: Multiply 3 by 8 and 5 by 4. Now you just compare 24 vs. 20.
• Why it matters: Multiplication is easy to do with puzzle pieces. Division is hard. By turning the division problem into a multiplication problem, they make the calculation fast and secure.

Analogy B: The "Gradient Descent" (Solving the Leaf Weight Problem)

At the end of the tree, the AI needs to assign a "weight" (a final score) to a leaf node. The formula for this usually requires division.

The authors realized this is like trying to find the bottom of a valley in the dark.

• Old Way: Try to calculate the exact bottom using a complex map (division).
• New Way: Just take a few steps downhill. Since the "valley" is shaped perfectly (it's a convex curve), you don't need to calculate the exact bottom instantly. You just take a few smart steps, and you land right on the answer.
• They turned the division problem into a simple "step-by-step" walking problem that everyone can solve together without revealing their location.

3. The "First-Layer Mask" (The Security Guard)

There was one tiny risk: If the very first split of the tree was done by a specific hospital, that hospital might learn exactly which patients were in the "sick" group vs. the "healthy" group just by looking at the tree structure.

To fix this, the authors added a First-Layer Mask.

• The Rule: The very first split of the tree must be done by the person who holds the labels (the "Active Participant," like the bank with the fraud data).
• The Result: This acts like a security guard at the door. It scrambles the data right at the start so that no other participant can ever trace a specific path back to a specific individual's data. It's like shuffling the deck of cards before dealing the first hand.

4. Why is this a Big Deal?

• Speed: The old methods were like walking through molasses. This new method is like running on a track. It's much faster because it avoids the heavy "division" math.
• Scalability: The old secret-sharing methods only worked well with two people. This new method works perfectly with 4, 5, or even 100 organizations collaborating.
• Accuracy: They proved that their "puzzle piece" math gives the exact same results as the "raw data" math. No accuracy is lost.

Summary

Imagine a group of detectives trying to solve a crime.

• Detective A has the fingerprints.
• Detective B has the witness statements.
• Detective C has the CCTV footage.

They can't show their evidence to each other.

• Old Method: They try to whisper clues through a thick wall. It takes forever, and they can only do it in pairs.
• This Paper's Method: They use a special code (Secret Sharing) where they can combine their clues mathematically without ever speaking the actual words. They found a clever way to do the hard math (division) by turning it into easy math (multiplication).

The result? They solve the crime (build the AI model) together, fast and securely, without anyone ever seeing the others' private evidence.

Technical Summary

Here is a detailed technical summary of the paper "An Efficient Learning Framework For Federated XGBoost Using Secret Sharing And Distributed Optimization" by Xie et al.

1. Problem Statement

The paper addresses the challenge of training XGBoost models in a Vertical Federated Learning (VFL) setting.

• Context: In VFL, different data holders (participants) possess different feature sets for the same set of entities (samples). The goal is to build a joint model without sharing raw data due to privacy regulations and commercial competition.
• Limitations of Existing Solutions:
  • Homomorphic Encryption (HE) based approaches (e.g., SecureBoost): While they prevent raw data leakage, they often leak intermediate information (e.g., instance counts in buckets) and suffer from extremely high computational and communication overheads, making them inefficient for large-scale data.
  • Secret Sharing (SS) based approaches (e.g., Fang et al.): These offer better privacy but are currently limited to two-party settings. They struggle with multi-party scenarios because XGBoost requires non-linear operations (specifically argmax for split selection and division for leaf weight calculation) which are not natively supported by standard SS primitives (addition, subtraction, multiplication). Existing SS methods approximate division using iterative algorithms, leading to massive computational complexity.

Core Challenge: How to design a lossless, secure, and efficient multi-party federated XGBoost framework under the Secret Sharing setting that avoids division operations and supports more than two participants.

2. Methodology: MP-FedXGB

The authors propose MP-FedXGB, a multi-party federated XGBoost framework. The system involves $M$ participants ($P_1$ is the active participant holding labels, $P_2 \dots P_M$ are auxiliary participants holding features) and a Coordinator ($C$).

A. Secure Training Framework

The training follows the standard XGBoost additive training process but operates on secret shares (denoted as $\langle \cdot \rangle$) rather than raw data.

• Data Representation: Gradients ($g_i$) and Hessians ($h_i$) are shared among participants.
• Tree Construction: Participants recursively build the tree. At each node, they compute the sum of gradients and Hessians for the current instance set using secret shares.

B. Key Technical Innovations

1. SecureArgmax: Reshaping Split Criterion Calculation

• Problem: Finding the best split requires comparing loss reductions ($L_{split}$) of candidates. $L_{split}$ involves fractions (division). In SS, comparing shares of fractions directly is difficult and requires expensive division approximations.
• Solution: The authors mathematically reshape the comparison of two loss reductions ($L_1$ vs $L_2$).
  • Instead of calculating $L_1$ and $L_2$ directly, they analyze the difference $L_{diff} = L_1 - L_2$.
  • By reducing fractions to a common denominator, the difference is expressed as a single fraction: $L_{diff} = \frac{G}{H}$.
  • The sign of $L_{diff}$ is determined by the signs of the numerator ($G$) and denominator ($H$) separately.
  • Protocol: $P_1$ restores $H$ and $P_2$ restores $G$. They independently judge the signs and communicate the result to determine the sign of the fraction.
  • Benefit: This completely eliminates the need for division operations and complex bit-by-bit comparisons (multiplexers) used in previous two-party SS methods, making it scalable to $M$ parties.

2. SecureLeafWeight: Distributed Optimization for Leaf Weights

• Problem: Leaf weight calculation ($w = -\frac{\sum g_i}{\sum h_i + \lambda}$) requires division.
• Solution: The authors reformulate the leaf weight calculation as a convex quadratic optimization problem.
  • The problem is transformed into minimizing a function: $\min_w \frac{1}{2} (\sum \langle a \rangle_m) w^2 + (\sum \langle b \rangle_m) w$.
  • They solve this using a distributed gradient descent algorithm.
  • To protect the sensitivity of the denominator (which reveals instance counts), they introduce a small positive perturbation ($\sigma$) to the step-size calculation.
  • Benefit: This avoids direct division and iterative approximation, converging to the exact solution in a single step (or a few steps with perturbation) while maintaining privacy.

3. First-Layer-Mask (Security Enhancement)

• Problem: In standard tree building, if a specific participant owns the features used for the root split, they might infer the exact instance space (subset of data) belonging to that node, potentially leaking label information.
• Solution: The framework enforces that the root node split must always be performed by the active participant ($P_1$).
• Benefit: This breaks the direct path from the root to the leaves for auxiliary participants, ensuring they only receive coarse-grained indicator vectors, thereby preventing instance space leakage.

3. Key Contributions

1. First Multi-Party SS-based FedXGB: Proposes the first lossless, multi-party federated XGBoost framework under the Secret Sharing setting, overcoming the two-party limitation of prior work.
2. Computation Reshaping: Introduces novel mathematical transformations for Split Criterion (SecureArgmax) and Leaf Weight (SecureLeafWeight) that eliminate division operations, drastically reducing computational complexity.
3. Enhanced Security: Proposes the First-Layer-Mask mechanism to prevent instance space leakage, a vulnerability in previous VFL tree-based models.
4. Theoretical & Empirical Validation: Provides a rigorous security analysis under the semi-honest adversary model and demonstrates superior efficiency compared to HE-based methods.

4. Experimental Results

The authors evaluated MP-FedXGB on benchmark datasets (GiveMeSomeCredit and Adult) against Vanilla XGBoost and theoretical HE-based models.

• Efficiency:
  • Computation: MP-FedXGB is significantly faster than HE-based methods (e.g., SecureBoost). In a simulated scenario with 4 participants and 10k instances, MP-FedXGB took 44.52s compared to 599s for the HE approach.
  • Complexity: The proposed SecureArgmax reduces the number of multiplication operations (MULs) from thousands (in division approximation methods) to hundreds (e.g., 468 vs 10,496 for specific parameters).
• Accuracy:
  • MP-FedXGB achieves comparable or slightly better performance (Accuracy, F1, AUC) than centralized Vanilla XGBoost.
  • The First-Layer-Mask mechanism introduces negligible performance loss, confirming that forcing $P_1$ to split the root does not significantly degrade model quality.
• Scalability: Runtime scales linearly with the number of trees and features, and exponentially with tree depth (consistent with standard XGBoost behavior), proving the framework is viable for large-scale data.

5. Significance

This paper bridges a critical gap in privacy-preserving machine learning. By enabling efficient multi-party collaboration for one of the industry's most powerful algorithms (XGBoost) without relying on heavy Homomorphic Encryption, it makes secure vertical federated learning practical for real-world applications involving multiple organizations (e.g., banks, hospitals, and retailers). The elimination of division operations via distributed optimization and fraction reshaping offers a new paradigm for designing secure non-linear machine learning models under secret sharing.