SilentWood: Efficient Private Inference Over Gradient-Boosting Decision Forests

arXiv:2411.15494 · cs.CR, cs.DB · Submitted 2024-11-23 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "SilentWood: Efficient Private Inference Over Gradient-Boosting Decision Forests".

Elias: Gradient boosting decision forests offer higher accuracy and lower training times than decision trees for large datasets,

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: So, we're looking at the paper "SilentWood: Efficient Private Inference Over Gradient-Boosting Decision Forests," and it seems like the core issue they're tackling is how to run private inference on gradient boosting decision forests efficiently without making things take too long or use up too much resources.

Elias: Exactly, and what caught my eye in that summary was the two main challenges they identified: first, combining those decision tree results into a single prediction requires extra computation, which really hits protocols using homomorphic encryption hard because it increases the multiplication overhead significantly. Second, even running several independent private decision tree evaluations without combining them can exhaust the server's computing resources.

Priya: From a privacy and measurement standpoint, I'm interested in how these optimizations actually translate into real-world performance gains for someone running an inference job on a large dataset. The abstract mentions that the naive extension of private inference to decision forests leads to impractical running times, so what does SilentWood actually claim in terms of improvement over those naive methods?

Nadia: Well, the paper proposes SilentWood as a private decision inference protocol for gradient boosting that uses three novel techniques specifically designed to address these overheads. They claim this protocol achieves significant improvements in both communication and computation cost when compared to naive approaches by optimizing tree duplication.

Elias: That sounds like a lot of heavy lifting for the cryptographic side, Nadia, and I'm curious about those three specific techniques they introduced. The summary mentions "computation clustering," "blind code conversion (BCC)," and "ciphertext compression" as the novel approaches they propose.

Priya: I'm wondering what the actual mechanism behind those techniques is, especially since they are all aimed at reducing computational bottlenecks or communication costs. What does "computation clustering" actually mean in practice for a decision tree structure?

Nadia: Computation clustering is focused on reducing the high computation overhead caused by frequent homomorphic rotations in FHE-based private decision tree evaluation. They achieve this by grouping and weighted-averaging tree nodes that share similar thresholds, or by path clustering where they combine paths with the same path conditions. The goal is to eliminate redundant computations by only computing comparison results once for each distinct type of node, or replacing nodes with their weighted average when they have similar threshold values.

Elias: That sounds like a clever way to minimize the repeated homomorphic operations, which is usually where the runtime blows up in these kinds of protocols. But what about that Blind Code Conversion, or BCC? I saw it mentioned as something to address score aggregation incompatibility with protocols like SumPath.

Paper summary: Priya: So, if we think about the data flow, BCC sounds like it's a way to handle how the server aggregates scores from different trees without needing all that complex multiplication every time. What is the specific role of this blind conversion in making arithmetic compatible for score aggregation?

Nadia: BCC is described as a lightweight two-party protocol where the server pads and shuffles its intermediate ciphertext to make the plaintext contents look uniformly random from the user's perspective. The user then decrypts it blindly and converts it to help the server's subsequent computation of score aggregation. This ensures that the information in that intermediate ciphertext is inaccessible from both the client and the server, while still allowing for arithmetic compatibility during score aggregation.

Elias: The idea of blinding the intermediate data to make it look random is interesting, but I always have to check if those security assumptions hold up under real-world parameter choices. Are there any specific parameters in the FHE scheme that might break this protocol?

Priya: Looking at the compression technique, it sounds like they're focusing on reducing communication costs stemming from repetitive data encoding during FHE-based private decision tree evaluation. What’s the practical step-by-step process for this ciphertext compression?

Nadia: The protocol involves two steps for ciphertext compression. First, the client removes repetitive data encoding before encryption to generate size-reduced compact ciphertexts. Second, once the server receives them, it performs homomorphic decompression to restore the originally intended repetitions of data encoding. This process reduces the required number of ciphertexts by a factor related to that repetitive data encoding, which can significantly decrease communication size.

Elias: Reducing the number of ciphertexts sounds like a direct win for bandwidth, but I wonder about the computational cost of that homomorphic decompression step on the server side. How much overhead does that decompression introduce compared to just sending larger, uncompressed ciphertexts?

Priya: The evaluation results are pretty telling here; they show that SilentWood is faster than baseline protocols, specifically stating its inference time is "faster than the baseline of parallel running the RCC-PDTE protocol by up to forty-two point five times" and "faster than Zama’s Concrete ML XGBoost by up to thirty-four point zero times". Furthermore, the speedup contributions are broken down, showing BCC contributed about nineteen point seven times on average, computation clustering next at one point five four times, and ciphertext compression last at about one point zero eight times.

Nadia: Those numbers really show the impact of the optimizations, Elias; it’s not just one technique doing all the work. The protocol achieves an average private XGBoost inference time that is "two point nine times ∼ twenty-eight point one times faster than state-of-the-art FHE or MPC-based protocols". That's a substantial difference in terms of practical application speed for those large datasets, Priya?

Paper summary: Elias: It is substantial, but we have to remember the proof assumes certain conditions for security. The security analysis shows it's proven secure against both semi-honest clients and malicious servers. Security against a corrupted client is shown by simulating the client's view using its own input, hyperparameters, and final class scores through a sanitization algorithm, and server security is modeled as a "client-aided outsourcing protocol" if instantiated with either a CPA-secure FHE scheme or if all ciphertexts are sanitized before being sent to the server.

Priya: So, what does this mean for the broader impact of these private inference techniques? If we can make running complex models like gradient boosting decision forests privately much faster and less communication-heavy, what kind of applications do you see being enabled by this work?

Nadia: I think the implication is that it makes deploying accurate machine learning models in privacy-preserving settings much more feasible for large datasets. If we can drastically cut down the inference time and communication overhead, we can start applying these private techniques to much larger and more complex predictive models that are currently too slow or resource-intensive for these protocols.

Elias: From a cryptographic angle, the comparison with MultiplyPath versus SumPath aggregation methods is also significant. SilentWood shows that BCC is superior to MultiplyPath because it avoids those "heavy multiplications" required by MultiplyPath, which needs as many homomorphic multiplications as the length of each path. That makes a real difference in complexity compared to the polynomial growth with tree depth that you see with MultiplyPath.

Priya: So, to wrap up on the research itself, the paper successfully demonstrates three distinct optimization pathways—clustering, BCC, and compression—and quantifies them against established baselines like parallel running RCC-PDTE and Zama’s Concrete ML XGBoost. This gives us a solid empirical foundation on how to tune these parameters for better performance.

Nadia: It really shows that combining these specific structural and cryptographic tricks addresses the core issues of runtime and communication overhead in this area. So, we've covered the summary, the conclusion, and touched on what these results actually mean for making private AI inference more practical.

Elias: Indeed, SilentWood provides a framework where structural changes to how we evaluate trees—like clustering—are combined with specific cryptographic tools like BCC and compression to yield tangible speedups. That's a solid piece of work in the field of private machine learning inference.

Conclusion: Nadia: So we've seen how SilentWood tackles the computational and communication hurdles of private inference for gradient boosting decision forests through its clustering, BCC, and compression techniques. Elias, looking at that title again—"SilentWood"—what does that name actually suggest about the protocol's behavior?

Elias: I think "SilentWood" implies a system where the heavy lifting happens internally without much noise getting out to the outside world, which fits perfectly with how they're optimizing those FHE operations. The authors are using these three specific mechanisms to keep the computation quiet and efficient.

Priya: From a measurement standpoint, what does that mean for the actual deployment of these models? Does this work move us closer to using complex AI on sensitive data in practical ways?

Nadia: It suggests we can finally make those large, accurate decision forest models usable privately without waiting for days to run them. The authors are showing that the inference time drops dramatically compared to what we're currently seeing in state-of-the-art FHE or MPC protocols.

Elias: I’m concerned about the security assumptions, though; we have to dig into whether those specific FHE schemes they use actually hold up against sophisticated attacks if someone tries to exploit a weakness in the clustering or compression steps.

Priya: And I want to know what the real-world data shows regarding those security models; are we talking about zero exploitable vulnerabilities, or are there specific parameter choices that might cause issues?

Nadia: We're looking at how cheaply someone could exploit it, Elias; if they can find a way around the sanitization algorithms they described, then the cost of breaking it would be significant.

Elias: The proof models it as a client-aided outsourcing protocol if you use CPA-secure FHE schemes, which means security hinges entirely on maintaining that specific level of FHE security throughout the process.

Priya: So what's the big picture implication for AI deployment? If we can make these models faster and more private, what kind of applications are suddenly possible that weren't before?

Nadia: We could see private inference applied to much bigger predictive models that are currently too slow or resource-intensive for any privacy-preserving setup. This opens the door for using complex AI on sensitive data in ways that were previously just theoretical possibilities.

Elias: I'm curious about the comparison they made with aggregation methods; how much more efficient is BCC compared to those heavy multiplication protocols we discussed earlier?

Priya: And the compression method seems quite clever by exploiting data repetition, which really shows a practical approach to reducing communication overhead for massive datasets.

Nadia: It seems like they've built a really comprehensive framework here, combining structural math with cryptographic tricks to get better performance metrics.

Elias: Indeed, SilentWood provides a concrete path forward by showing how these specific structural and cryptographic adjustments yield tangible speedups over the established baselines. We've seen how this work sets a new benchmark for efficiency in private machine learning inference.

Ronny Ko, Abdelkarim Kati, Robin Geelen, Rasoul Akhavan Mahdavi, Byoungwoo Yoon, Jongho Shin, Anton Jappinen, Igor Moroz

LG Electronics

cs.CR, cs.DB

Submitted: 2024-11-23

Updated: 2026-09-27

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: Gradient boosting decision forests offer higher accuracy and lower training times than decision trees for large datasets, but naively extending private inference protocols to these forests leads to

Key concepts

Computation Clustering: This technique reduces heavy computation by grouping tree nodes that share similar thresholds or path conditions. Instead of performing redundant calculations for every node, the protocol groups them and uses weighted averages or single comparisons to eliminate unnecessary computations while preserving the model's accuracy.
Blind Code Conversion (BCC): BCC solves a problem with score aggregation incompatibility. It is a lightweight two-party process where the server shuffles intermediate ciphertexts so that they look random to the client. The client then decrypts and converts this blinded data, allowing the server to correctly perform necessary arithmetic operations for aggregating scores.
Ciphertext Compression: This method cuts down communication overhead by exploiting patterns in data encoding within FHE-based decision tree evaluation. The client first removes repetitive encodings before encryption, resulting in smaller ciphertexts. The server then uses homomorphic decompression to restore these repetitions, drastically reducing the number of ciphertexts needed for transmission.

Terminology

Clustering — 71× in this paper · explained in 2 episodes
Accuracy — 29× in this paper · explained in 1 episode
Aggregation — 29× in this paper · explained in 1 episode
Elias — 16× in this paper · explained in 2 episodes
Decode — 14× in this paper · explained in 2 episodes
Nadia — 14× in this paper · explained in 2 episodes
Private Decision Tree Evaluation — 13× in this paper
Blind Code Conversion — 12× in this paper
Communication Overhead — 8× in this paper · explained in 2 episodes
Benchmark — 7× in this paper · explained in 2 episodes
Fully Homomorphic Encryption — 6× in this paper
Core — 5× in this paper · explained in 2 episodes
Pruning — 4× in this paper · explained in 4 episodes
Computational overhead — 3× in this paper · explained in 2 episodes
Ablation — 2× in this paper · explained in 1 episode
Ablation study — 2× in this paper · explained in 1 episode
Fully Homomorphic Encryption (FHE) — 2× in this paper · explained in 5 episodes
Activation Function — 1× in this paper · explained in 1 episode
Alignment — 1× in this paper · explained in 1 episode
Generalization — 1× in this paper · explained in 13 episodes
Information Gain — 1× in this paper · explained in 2 episodes
Interpretability — 1× in this paper · explained in 15 episodes
RAG — 1× in this paper · explained in 3 episodes
Regularization — 1× in this paper · explained in 3 episodes
Single Instruction Multiple Data — 1× in this paper

Summary

Gradient boosting decision forests offer higher accuracy and lower training times than decision trees for large datasets, but naively extending private inference protocols to these forests leads to impractical running times. This paper proposes SilentWood, an efficient private decision inference protocol using homomorphic encryption that achieves significant improvements in communication and computation cost over naive approaches by optimizing tree duplication.

Proposal of SilentWood

SilentWood is a private decision inference protocol for gradient boosting models that utilizes three novel techniques: computation clustering, blind code conversion (BCC), and ciphertext compression. These optimizations are designed to address the challenges arising from combining multiple decision trees into a final model prediction, specifically reducing the overhead caused by frequent homomorphic rotations in FHE-based protocols, addressing score aggregation incompatibility, and minimizing communication costs from repetitive data encoding.

Computation Clustering

The first technique introduced is node clustering, which aims to reduce the high computation overhead caused by frequent homomorphic rotations in FHE-based PDTE (private decision tree evaluation). This is achieved by grouping and weighted-averaging tree nodes having similar thresholds and path clustering, which involves combining tree paths having the same path conditions. The goal is to eliminate redundant computations by computing comparison results only once for each distinct type of node, or by replacing nodes with their weighted average when they have similar threshold values. This process is controlled by a learnable clustering intensity parameter and includes techniques like weighted averaging, leaf value re-optimization, and accuracy-preserving merge to ensure model correctness is maintained during the clustering process.

Blind Code Conversion (BCC)

To address the incompatibility of protocols like SumPath for score aggregation, SilentWood proposes the Blind Code Conversion (BCC) protocol. This is a lightweight two-party protocol in which the server pads and shuffles its intermediate ciphertext to make the plaintext contents appear uniformly random from the user’s perspective. The user's role is to decrypt it and convert it blindly to help the server's subsequent computation of score aggregation. This ensures that the information in the intermediate ciphertext to be inaccessible from both the client and server, while realizing arithmetic compatibility of the server’s score aggregation.

Ciphertext Compression

The third technique focuses on reducing communication overhead caused by repetitive data encoding in FHE-based PDTE. The protocol involves two steps: (1) the client removes repetitive data encoding before encryption and generates size-reduced compact ciphertexts; and (2) once the server receives them, it performs homomorphic decompression to restore the originally intended repetitions of data encoding. This process reduces the required number of ciphertexts by a factor related to repetitive data encoding, which can significantly decrease communication size.

Performance and Evaluation

The paper presents evaluation results demonstrating that SilentWood is faster than baseline protocols. The protocol’s inference time is faster than the baseline of parallel running the RCC-PDTE protocol by up to 42.5x, and faster than Zama’s Concrete ML XGBoost by up to 34.0x. Furthermore, the evaluation shows that SilentWood's speedup contributions are: BCC contributed about 19.7x on average, computation clustering next (1.54x), and ciphertext compression last (about 1.08x). The protocol achieves an average private XGBoost inference time of 2.9x ∼ 28.1x faster than state-of-the-art FHE or MPC-based protocols.

Security Analysis

The protocol is proven secure against both semi-honest clients and malicious servers. Security against a corrupted client is demonstrated by showing that the client's view can be simulated using its own input, hyperparameters, and final class scores through a sanitization algorithm. Security against a corrupted server is shown by modeling SilentWood as a client-aided outsourcing protocol, proving privacy if the scheme is instantiated with either a CPA-secure FHE scheme or if all ciphertexts are sanitized before being sent to the server. The client learns only the inference scores/probabilities for each class and hyperparameters, while the server learns nothing about the client’s features.

Comparison of Aggregation Methods

The paper compares score aggregation methods, showing that BCC is superior to MultiplyPath because it avoids heavy multiplications required by MultiplyPath, which requires as many homomorphic multiplications as the length of each path. The critical path for BCC is dominated by log N Rotate operations, which are fixed and small in practice, whereas the critical path for MultiplyPath involves 2l − 1 ciphertext–to-ciphertext multiplications, which grows polynomially with tree depth, making it computationally expensive.

Comparison of Compression Methods

Ciphertext compression is shown to be effective because it reduces the number of required ciphertexts by exploiting repetitive data encoding.

Improvements for AI systems

As a fastidious researcher, I have analyzed SilentWood: Efficient Private Inference Over Gradient Boosting Decision Forests and identified several specific, high-impact improvements for existing AI systems, particularly those utilizing complex ensemble models like XGBoost or random forests in privacy-sensitive environments (MLaaS).

Here are the specific improvements and what the enhanced system can achieve:

)1. Computation Clustering (Node & Path Clustering)

The system should implement a dynamic, learnable clustering mechanism to group decision tree nodes and paths that share similar threshold values or structural conditions across different trees in a forest.

How it works: Instead of performing an FHE comparison for every unique [feature type, threshold value] pair at every node (Challenge C1), the system should use the Weighted Threshold Average technique (Algorithm 1). This replaces many individual comparisons with a single homomorphic comparison for clustered nodes. Furthermore, path clustering groups paths that share identical unordered sets of node conditions (e.g., one path is "age > 45 AND sleep > 8 and another is sleep > 8 AND age > 45").
What the improved system can do: This drastically reduces the number of homomorphic rotations and comparisons required during inference. For a model with thousands of trees, this results in speedups up to 27.8x over baseline protocols like RCC-PDTE, allowing for real-time (or near real-time) inference on large ensemble models without prohibitive latency or computational cost increases associated with naive replication.

)2. Blind Code Conversion (BCC) Protocol

The system must integrate a two-party protocol to handle the aggregation of leaf scores from multiple trees efficiently, specifically addressing the incompatibility between SumPath/MultiplyPath outputs and final score summation (Challenge C2).

How it works: The server should use BCC to send intermediate ciphertext containing padded, uniformly shuffled SumPath values to the client. The client decrypts these, transforms them (flipping 0s to 1s and non-zeros to 0s), and re-encrypt. This allows the server to perform a single homomorphic multiplication with the plaintext leaf score array aligned with the SumPath values, effectively filtering out false paths while preserving arithmetic compatibility for true paths.
What the improved system can do: This eliminates the need for computationally expensive multiplications required by MultiplyPath protocols (which scale polynomially with tree depth) and avoids complex non-arithmetic logic required by SumPath aggregation. It enables faster, more scalable score aggregation in gradient boosting models while maintaining strong privacy guarantees against both semi-honest and malicious servers.

)3. Ciphertext Compression

The system needs a client-side mechanism to compress the input feature encodings before encryption, followed by a server-side homomorphic decompression.

How it works: Instead of sending repetitive data encodings (e.g., encoding the same feature bit multiple times across different nodes) as in standard FHE protocols, the client removes these repetitions before encryption (Algorithm 4). The server then uses a homomorphic decompression operation to restore the intended repetitions during computation.
What the improved system can do: This significantly reduces communication overhead (Challenge C3), potentially decreasing ciphertext size by factors of up to 5x for 32-bit data, thereby minimizing network latency—which is often the dominant runtime factor in MLaaS scenarios.

)4. Overall System Capability

The resulting AI system will be a highly efficient, privacy-preserving inference engine capable of:

Providing real-time private predictions on complex ensemble models (XGBoost/AdaBoost) on resource-constrained devices or cloud environments where traditional two-party computation (MPC) is too slow due to high communication costs.
Achieving massive speedups (up to 34x for Zama's Concrete ML baseline) while maintaining a model accuracy of >0.9 across diverse benchmarks, making it viable for high-throughput MLaaS applications like real-time recommendation systems or fraud detection where input data must remain confidential.
Operating robustly under varying model complexity (depth and tree count) by using clustering to manage complexity without sacrificing the privacy guarantees or model correctness through iterative validation.

Abstract

Gradient boosting decision forests, used by XGBoost or AdaBoost, offer higher accuracy and lower training times than decision trees on large datasets. Private inference protocols for decision trees can preserve both input and tree privacy. However, naively extending them to decision forests by replication leads to impractical running times. In this paper, we propose an efficient private decision inference protocol using homomorphic encryption. We present several optimizations that identify and remove (approximate) duplication between trees, significantly reducing communication and computation costs over the naive approach. We present the private inference protocol for highly scalable gradient boosting decision forests. Our protocol SilentWood is faster than parallel RCC-PDTE by up to 42.5x, Zama's Concrete ML XGBoost by up to 27.8x, and SoK-GGG's two-party garbled circuit protocol by 2.94x.