SilentWood: Private Inference Over Gradient-Boosting Decision Forests

Ronny Ko, Abdelkarim Kati, Robin Geelen, Rasoul Akhavan Mahdavi, Byoungwoo Yoon, Jongho Shin, Igor Moroz, Anton Jappinen, Zhiqiang Lin, Makoto Onizuka, Florian Kerschbaum

TL;DR

SilentWood introduces a highly efficient private inference protocol for gradient-boosting decision forests (like XGBoost and AdaBoost) using Fully Homomorphic Encryption (FHE). By identifying and eliminating redundant computations across ensemble trees and compressing encrypted data, SilentWood achieves up to a 42.5× speedup and an 80% reduction in communication overhead compared to standard baselines, all while strictly preserving data and model privacy.

What Problem Does This Paper Address?

Machine Learning as a Service (MLaaS) allows users to leverage powerful, pre-trained models hosted in the cloud. However, this paradigm introduces severe privacy risks: users must upload potentially sensitive data (e.g., medical or financial records), and providers must protect their proprietary model parameters.

Cryptographic techniques like Fully Homomorphic Encryption (FHE) allow servers to process encrypted data without ever decrypting it. While Private Decision Tree Evaluation (PDTE) works reasonably well for a single decision tree, modern machine learning relies on ensembles of trees, such as gradient-boosting decision forests (XGBoost or AdaBoost), to achieve high accuracy. Naively replicating single-tree protocols across hundreds of trees causes exponential growth in computational complexity (due to expensive homomorphic rotations) and massive network communication overhead, making real-world deployment impractical.

Methods

SilentWood overcomes these bottlenecks through three novel core techniques:

  1. Computation Clustering:
  2. Node Clustering: The authors observed that different trees in a forest often evaluate very similar decision thresholds. SilentWood groups these similar thresholds across the entire forest and replaces them with their weighted average. This allows the server to perform the homomorphic comparison only once per cluster rather than for every single node. An accuracy-preserving merge algorithm ensures this optimization doesn't degrade model performance.
  3. Path Clustering: It identifies paths across different trees that share the exact same set of unordered conditions, combining them to eliminate redundant path evaluations.
  4. Blind Code Conversion (BCC): Evaluating tree paths typically uses either MultiplyPath (which requires deep, slow homomorphic multiplication chains) or SumPath (which is fast but outputs arithmetically incompatible values for final score aggregation). BCC introduces a lightweight, 1-round-trip-time (1-RTT) interactive protocol. The server pads and shuffles intermediate SumPath ciphertexts so they look uniformly random to the client. The client decrypts them, blindly flips the bits (converting 0s to 1s and non-zeros to 0s), re-encrypts, and sends them back. This allows the server to compute final scores using a single, efficient homomorphic multiplication.

  5. Ciphertext Compression: To enable Single Instruction Multiple Data (SIMD) operations, standard protocols repetitively encode feature bits into ciphertext slots, wasting massive amounts of space. SilentWood removes these repetitions on the client side before encryption, resulting in much smaller ciphertexts, and then homomorphically decompresses (restores) the required data format directly on the server.

Figure 3: An examples of node clustering

Datasets

The protocol was evaluated using 13 standard benchmarks from the UCI Machine Learning Repository, spanning various classification tasks:

  • Spam, Steel, Breast, Heart, Defect, Bank, PenDigits, Ailerons, Credit, Satellite, Elevators, Telescope, and MFeat.

These datasets represent a wide variety of feature dimensions (from 11 to 64) and sample sizes, providing a robust evaluation framework against existing state-of-the-art systems.

Key Insights and Ideas

  • Redundancy is an Asset: In trained decision forests, structural redundancy is incredibly common. Forcing slightly different thresholds to match via weighted averaging drastically reduces FHE rotation overhead without harming overall classification accuracy.
  • Breaking the Multiplication Depth Curse: By utilizing SumPath combined with BCC, SilentWood keeps the homomorphic circuit depth flat. The complexity of evaluating a path no longer scales poorly with the depth of the tree, which has historically been FHE's Achilles' heel.
  • Data-Agnostic Decompression: Unlike traditional compression algorithms (like Huffman or LZ77) that leak information about data distributions through codebooks, SilentWood’s compression is entirely structural and homomorphic, leaking absolutely zero plaintext information to the server.

Key Results

The authors evaluated SilentWood against several state-of-the-art baselines (including Zama's Concrete ML and SoK-GGG) using a 24-core CPU and an RTX 4090 GPU setup:

  • Speedups: On CPU-based FHE, SilentWood's end-to-end inference time is up to 42.5× faster than the parallelized baseline, 27.8× faster than Zama's Concrete ML, and 2.94× faster than the two-party garbled circuit protocol (SoK-GGG) under realistic network latencies (50ms RTT).
  • Communication Reduction: Ciphertext compression successfully reduced the client-to-server communication payload from an average of 85.75 MB down to 15.12 MB for 32-bit feature precision—roughly a 5× reduction.
  • Accuracy Preservation: Thanks to the validation-driven abort mechanism in the node clustering phase, the average model accuracy across all benchmarks remained stable at ~0.90, proving that the optimizations do not sacrifice model utility.

Limitations and Future Work

While SilentWood dramatically accelerates private inference, it transitions the protocol from a single-round non-interactive setup to a 2-round interactive protocol due to the Blind Code Conversion step. In environments with extremely high network latency, this single round-trip interaction could become a bottleneck, though the paper demonstrates that SilentWood still outperforms non-interactive alternatives in overall runtime.

Future work could explore completely non-interactive aggregation methods that match BCC's efficiency, or extending these clustering and compression frameworks to other ensemble methods like Random Forests.

Summary updated

Abstract

Gradient boosting decision forests, used by XGBoost or AdaBoost, offer higher accuracy and lower training times than decision trees for large datasets. Protocols for private inference over decision trees can be used to preserve the privacy of the input data as well as the privacy of the trees. However, naively extending private inference over decision trees to private inference over decision forests by replicating the protocols 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 then remove (approximate) duplication between the trees in a forest, thereby achieving significant improvements in communication and computation cost over the naive approach. To the best of our knowledge, we present the first private inference protocol for highly scalable gradient boosting decision forests. Our protocol's (SilentWood) inference time is faster than the baseline of parallel running the RCC-PDTE protocol by Mahdavi et al. by up to 42.5x, and faster than Zama's Concrete ML XGBoost by up to 27.8x, and faster than SoK-GGG's two-party garbled circuit protocol by 2.94x.
BibTeX
@misc{ko2024silentwood,
  author = {Ronny Ko and Abdelkarim Kati and Robin Geelen and Rasoul Akhavan Mahdavi and Byoungwoo Yoon and Jongho Shin and Igor Moroz and Anton Jappinen and Zhiqiang Lin and Makoto Onizuka and Florian Kerschbaum},
  title = {{SilentWood: Private Inference Over Gradient-Boosting Decision Forests}},
  year = {2024},
  eprint = {2411.15494},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.15494},
}
Figure