Argmax and XGBoost Training over Fully Homomorphic Encryption

Ramy Masalha (Paper author · IBM Research and University of Haifa), Adi Akavia (Paper author · University of Haifa), Allon Adir (Paper author · IBM Research), Ehud Aharoni (Paper author · IBM Research), Eyal Kushnir (Paper author · IBM Research)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 3 · Moose

Overview

This talk, presented by Ramy Masalha at PETS, delves into a significant advancement in privacy-preserving machine learning: the training of XGBoost models using Fully Homomorphic Encryption (FHE). The core problem addressed is the pervasive challenge of training machine learning models on sensitive, private data while leveraging powerful, potentially untrusted, cloud servers. Traditional approaches either compromise data privacy or incur prohibitive computational and communication costs. The research introduces a novel approach that drastically reduces the overhead associated with FHE-based training, specifically focusing on an optimized Argmax algorithm, a fundamental component of decision tree-based models like XGBoost.

Watch on YouTube · Slides

Visual summary for Argmax and XGBoost Training over Fully Homomorphic Encryption by Ramy Masalha, Adi Akavia, Allon Adir, Ehud Aharoni, Eyal Kushnir
Visual summary for Argmax and XGBoost Training over Fully Homomorphic Encryption by Ramy Masalha, Adi Akavia, Allon Adir, Ehud Aharoni, Eyal Kushnir

Key moments

  1. 0:00 Introduction to XGBoost over FHE
  2. 2:00 Achieving 360x speedup for FHE XGBoost
  3. 3:00 Why Argmax is crucial for XGBoost efficiency
  4. 5:00 Challenges: Comparison operations in FHE
  5. 6:00 Overview of existing Argmax algorithms
  6. 8:00 Our novel merged Argmax algorithm details
  7. 10:00 Argmax algorithm achieves 1.6x runtime improvement

Argmax and XGBoost Training over Fully Homomorphic Encryption

Speakers: Ramy Masalha (Paper author, IBM Research and University of Haifa); Adi Akavia (Paper author, University of Haifa); Allon Adir (Paper author, IBM Research); Ehud Aharoni (Paper author, IBM Research); Eyal Kushnir (Paper author, IBM Research)

Conference: PETS

YouTube: https://www.youtube.com/watch?v=9Q25IEEKQXk

Overview

This talk, presented by Ramy Masalha at PETS, delves into a significant advancement in privacy-preserving machine learning: the training of XGBoost models using Fully Homomorphic Encryption (FHE). The core problem addressed is the pervasive challenge of training machine learning models on sensitive, private data while leveraging powerful, potentially untrusted, cloud servers. Traditional approaches either compromise data privacy or incur prohibitive computational and communication costs. The research introduces a novel approach that drastically reduces the overhead associated with FHE-based training, specifically focusing on an optimized Argmax algorithm, a fundamental component of decision tree-based models like XGBoost.

The work is a collaborative effort by researchers from IBM Research and the University of Haifa, aiming to bridge the gap between theoretical privacy guarantees and practical applicability in real-world scenarios. By enabling efficient computation over encrypted data, this research paves the way for secure outsourcing of complex machine learning tasks, offering a robust solution for industries handling highly confidential information, such as healthcare or finance. The presented improvements represent a substantial leap forward, making privacy-preserving machine learning with FHE a more tangible reality.

The significance of this work lies in its direct attack on the performance bottlenecks that have historically plagued FHE. While FHE offers the ultimate privacy guarantee—computation on encrypted data without decryption—its computational intensity has limited its widespread adoption. By achieving a remarkable 360x speedup over prior state-of-the-art FHE solutions for XGBoost training, and a 1.6x improvement in the critical Argmax operation, the authors demonstrate that practical, privacy-preserving model training is increasingly within reach, thereby expanding the potential applications of machine learning in sensitive domains.

Background

▶ Watch: Introduction to XGBoost over FHE (0:00)

The scenario at the heart of this research is common in modern data science: an entity, Alice, possesses private data and wishes to train a sophisticated machine learning model, specifically an XGBoost model, to extract insights. However, Alice lacks the computational resources to train the model locally and must rely on a powerful, external server. The critical constraint is that Alice's data is private, and the server is considered semi-honest, meaning it will follow the protocol but may attempt to learn information from the data it processes. This necessitates a solution that preserves data privacy during the training process.

XGBoost, short for eXtreme Gradient Boosting, is an ensemble machine learning algorithm that builds a strong predictive model from a series of weaker decision trees. It is widely used for its efficiency, flexibility, and high performance in various prediction tasks. Training an XGBoost model involves iteratively building decision trees, where each tree aims to correct the errors of the previous ones. A key operation within the construction of each decision tree is determining the optimal split point for data at each node, which often involves finding the maximum value (or minimum) and its corresponding index—an Argmax or Argmin operation.

Existing solutions for privacy-preserving machine learning primarily fall into two categories: Multi-Party Computation (MPC) and Fully Homomorphic Encryption (FHE). MPC solutions often involve multiple rounds of communication between Alice and the server. As the speaker highlights, some recent MPC papers require up to 60,000 rounds of communication to train just one decision tree, rendering them impractical for models with hundreds of trees. This heavy reliance on communication is a major bottleneck for scalability.

FHE, on the other hand, offers a more elegant solution by allowing computations directly on encrypted data without any interaction with Alice after the initial data upload. Alice encrypts her data and sends it to the server, which then performs all necessary computations on the ciphertext. The server returns the encrypted result to Alice, who can then decrypt it. While FHE theoretically eliminates communication rounds during computation, prior FHE solutions for XGBoost training have been notoriously slow. The state-of-the-art before this work reportedly took 7 hours to train just one XGBoost tree on a medium-large dataset. Given that typical XGBoost models comprise 100 trees, this translates to an unfeasible training time of 700 hours (nearly a month) for a full model. This significant performance gap is the problem this research aims to address, making FHE-based privacy-preserving machine learning more practical.

Key Findings

▶ Watch: Why Argmax is crucial for XGBoost efficiency (3:00)

The research presented by Ramy Masalha outlines two principal contributions that significantly advance the field of privacy-preserving machine learning with FHE. These findings directly tackle the performance limitations that have historically hindered the practical deployment of FHE for complex machine learning tasks.

The first and most prominent contribution is the development of a system for XGBoost training over FHE that achieves an unprecedented 360x speedup compared to the previous state-of-the-art FHE solutions. This dramatic reduction in training time transforms the feasibility of FHE-based XGBoost. Where previous methods took 7 hours to train a single tree, this new system can train an entire model of 100 trees in approximately 5 hours. This represents a monumental shift from a months-long computation to a matter of hours, making privacy-preserving XGBoost training a far more practical endeavor.

The second, and arguably more fundamental, contribution is the development of a novel Argmax algorithm over FHE. While the 360x speedup is an aggregate result, the optimized Argmax algorithm is a critical enabler. The speaker emphasizes this point, noting that the Argmax operation is repeatedly used throughout the XGBoost training process—on every node of every tree. A typical XGBoost model with 100 trees, each containing perhaps 16 nodes, implies thousands of Argmax computations. Therefore, any small efficiency gain in this specific operation scales up to a massive overall improvement. This new Argmax algorithm itself provides a 1.6x improvement in runtime over prior FHE-based Argmax methods. The speaker highlights that this algorithmic innovation is the primary focus of the presentation, underscoring its foundational role in the overall system's performance gains. This granular optimization, combined with other unmentioned "tricks" detailed in the full paper, culminates in the impressive end-to-end speedup for XGBoost training.

Technical Deep Dive

▶ Watch: Challenges: Comparison operations in FHE (5:00)

The core challenge in performing Argmax (finding the maximum value and its index) over Fully Homomorphic Encryption (FHE) schemes lies in the nature of FHE operations. Standard FHE schemes efficiently support arithmetic operations like addition and multiplication on encrypted numbers, meaning any polynomial computation can be performed. However, comparison operations, which are essential for determining a maximum value, are non-polynomial. To perform comparisons in FHE, they must be approximated using polynomial functions, which is computationally expensive and slow. Therefore, the primary goal of optimizing Argmax in FHE is to minimize the number of comparison operations required.

The authors assume the use of an FHE scheme that supports Single Instruction, Multiple Data (SIMD) computation. SIMD allows the FHE scheme to perform the same operation (e.g., addition or multiplication) simultaneously on vectors containing thousands of encrypted numbers. This parallel processing capability is crucial for efficiency, and any optimized algorithm must leverage SIMD to its fullest extent. The problem with existing Argmax algorithms, particularly in their later stages, is that they fail to fully utilize this SIMD capability.

The talk outlines two traditional approaches to Argmax:

  1. Tournament Method: This method proceeds in rounds, similar to a sports tournament bracket. If we have n values, in the first round, adjacent pairs are compared, yielding n/2 maximums. This process repeats, halving the number of values in each round, until a single maximum is found. This requires log n rounds of comparisons. For example, with 100 numbers, it takes 10 rounds. While the number of rounds is logarithmic, the issue arises in later rounds where fewer comparisons are performed. If the SIMD vector can handle 1,000 numbers, but only two values are being compared in the final round, a significant portion of the SIMD slots remain unused, leading to computational waste.
  1. League Method: This approach, conceptually, compares every value with every other value. If there are n values, an n x n matrix of comparisons is generated. For each row (representing a value), if it is the maximum, all its comparisons against other values will result in '1' (or true). If it's not the maximum, at least one comparison will yield '0' (or false) because it's smaller than some other value. Multiplying the comparison results across each row reveals the maximum (the row with all ones). The major drawback here is the sheer number of comparisons: n^2. For 100 numbers, this means 10,000 comparisons, which is prohibitively expensive in FHE.

The innovation proposed by Masalha and his team is a hybrid approach that merges the strengths of both the League and Tournament methods while mitigating their weaknesses, specifically tailored for FHE with SIMD. The core idea is to perform repeated rounds that combine elements of both.

The new algorithm starts with a few rounds of tournament-like comparisons. For instance, it might initially find the maximum within small blocks of numbers (e.g., m1 as the maximum of the first four values, m2 for the next four, and so on). The crucial step then is to aggregate these local maximums and apply a "core league round" on them. Instead of a full n x n league, they perform a league comparison on a smaller, fixed size block. For example, if they have four local maximums, they perform a 4 x 4 league comparison to find the maximum among these 4 values, which effectively gives the maximum of the initial 16 values (4 blocks of 4).

This process is then repeated iteratively. Each subsequent "core league round" operates on the maximums found in the previous step, effectively squaring the number of values being compared. If k values were compared in the previous step, the next step compares k values using a k x k league, finding the maximum among k^2 original values. This means at step i, they compute the league on 2^(2^i) values. This exponential growth in the scope of comparison with each step leads to a highly efficient logarithmic reduction in the number of rounds required. Instead of log n comparison rounds as in the tournament method, this hybrid approach requires only log log n comparison nodes. This dramatically reduces the number of expensive FHE comparison operations, making the Argmax computation significantly faster.

The result of this optimized Argmax algorithm is a 1.6x improvement in runtime for the Argmax operation itself. This seemingly modest factor, when multiplied by the thousands of times Argmax is invoked during XGBoost training, becomes a critical component of the overall 360x speedup achieved for the entire FHE-based XGBoost training system. By intelligently combining techniques and leveraging SIMD, the researchers have found a way to make a fundamental, non-polynomial operation significantly more efficient within the FHE paradigm.

Demo / Proof of Concept

▶ Watch: Our novel merged Argmax algorithm details (8:00)

While the talk focuses on the algorithmic innovations and performance metrics, it describes the development of a complete system for XGBoost training over FHE. The presentation highlights the achieved speedups and performance gains through empirical results, comparing their system's runtime against previous state-of-the-art solutions. The speaker presents a graph showing their system's performance (in blue) against the previous benchmark, demonstrating the 1.6x improvement specifically for the Argmax operation. The primary evidence of the "proof of concept" is the reported 360x speedup in training a 100-tree XGBoost model in 5 hours, a direct result of the implemented algorithms and system optimizations, rather than a live, interactive demonstration during the talk.

Defensive Implications

▶ Watch: Argmax algorithm achieves 1.6x runtime improvement (10:00)

The advancements in privacy-preserving machine learning, particularly the efficient training of XGBoost models using Fully Homomorphic Encryption (FHE), carry profound defensive implications for organizations dealing with sensitive data. The ability to perform complex machine learning tasks on encrypted data fundamentally changes the security posture for data processing in several critical ways.

Firstly, this technology enables organizations to leverage the vast computational power of cloud providers without exposing their raw, private data. Traditionally, migrating data to the cloud for machine learning training would require either decrypting the data, thus making it vulnerable to the cloud provider or other actors, or using less powerful on-premise infrastructure. With efficient FHE, organizations can encrypt their datasets (e.g., patient health records, financial transactions, proprietary business intelligence) and outsource the computationally intensive XGBoost training to a cloud server. The server computes directly on the ciphertexts, and only the encrypted model or prediction is returned. This eliminates the risk of data breaches or unauthorized access to sensitive information by the cloud provider or during transit, significantly enhancing data confidentiality.

Secondly, this research fosters compliance with stringent data privacy regulations such as GDPR, HIPAA, and CCPA. These regulations mandate robust protection of personal and sensitive data. FHE-based machine learning provides a strong cryptographic guarantee that data remains private throughout its lifecycle, including during computation. This allows organizations to build and deploy powerful predictive models for fraud detection, medical diagnosis, or personalized services without violating privacy laws or incurring the ethical dilemmas associated with using raw sensitive data. It democratizes access to advanced analytics for sectors previously constrained by privacy concerns.

Finally, the substantial performance improvements demonstrated in this work make FHE a more viable and practical defensive tool. The shift from months to hours for training a full XGBoost model means that privacy-preserving analytics can be integrated into operational workflows for real-time threat intelligence, anomaly detection, or secure collaborative AI. Defenders can train models on aggregated data from multiple sources, each contributing encrypted inputs, without any single party revealing their raw data. This facilitates shared intelligence and collective defense mechanisms, strengthening the overall security posture against sophisticated cyber threats while upholding individual and organizational privacy.

Key Takeaways

  • Practical FHE for XGBoost: The research achieves a groundbreaking 360x speedup in training XGBoost models over Fully Homomorphic Encryption (FHE), reducing training time for a 100-tree model from potentially months to approximately 5 hours.
  • Optimized Argmax Algorithm: A key enabler for this speedup is a novel Argmax algorithm specifically designed for FHE, which provides a 1.6x runtime improvement for this frequently used operation.
  • Reduced Comparison Operations: The core technical innovation lies in minimizing the number of expensive non-polynomial comparison operations in FHE by combining aspects of the Tournament and League methods, resulting in log log n comparison nodes.
  • Leveraging SIMD: The algorithm efficiently utilizes SIMD computation in FHE schemes, ensuring parallel processing of encrypted data vectors to maximize throughput.
  • Enhanced Data Privacy: This work enables organizations to train powerful machine learning models on sensitive data using untrusted cloud servers without compromising data privacy, offering a robust solution for industries like healthcare and finance.
  • Scalability for Privacy-Preserving ML: The significant performance gains push FHE-based machine learning closer to practical scalability, making privacy-preserving analytics a more feasible and deployable technology for real-world applications.

About the Speaker(s)

The talk was presented by Ramy Masalha, who is one of the paper's authors, affiliated with both IBM Research and the University of Haifa. He is part of a collaborative team that includes Adi Akavia (University of Haifa), Allon Adir (IBM Research), Ehud Aharoni (IBM Research), and Eyal Kushnir (IBM Research). Their collective expertise spans advanced cryptography, machine learning, and secure computation, focusing on bridging the gap between theoretical privacy-preserving techniques and their practical application in real-world systems.

Reviews

Dr. Zero (Offensive Security Researcher) — MUST SEE

FHE has always been the holy grail that nobody could actually lift because the compute overhead is crushing. Masalha and the IBM Research crew just made XGBoost over FHE mathematically viable by brutally optimizing the Argmax bottlenecks. Dropping a 700-hour compute to 5 hours isn't an iteration; it's a rescue mission for privacy-preserving ML.

Heather Calloway (CISO) — SOLID

This research demonstrates a 360x speedup in training XGBoost models over Fully Homomorphic Encryption (FHE), bringing a 700-hour compute job down to five hours. It crosses the threshold from academic novelty to practical business utility. If your data science teams are blocked from using cloud ML due to data residency or privacy regulations, this is the math that will eventually unblock them.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026