Technical Summary: SilentWood – Efficient Private Inference Over Gradient Boosting Decision Forests

Problem Statement

Gradient Boosting Decision Forests (e.g., XGBoost, AdaBoost) offer superior accuracy and training efficiency for large datasets compared to single decision trees, while maintaining model interpretability. However, deploying these models in a "Machine Learning as a Service" (MLaaS) context raises significant privacy concerns: users are reluctant to reveal sensitive input data, and service providers wish to protect their proprietary model parameters.

While private inference protocols exist for single decision trees using Fully Homomorphic Encryption (FHE) or Two-Party Computation (2PC), naively extending these to decision forests is impractical. The paper identifies three primary challenges:

1. Computational Overhead (C1): Private Decision Tree Evaluation (PDTE) requires homomorphic comparisons at every node. In a forest with hundreds of trees, the number of unique [feature, threshold] pairs necessitates excessive homomorphic rotations and ciphertext cloning to align data for SIMD (Single Instruction Multiple Data) operations.
2. Score Aggregation Incompatibility (C2): Aggregating results from multiple trees requires summing leaf values of "true" paths. Existing FHE-based PDTE methods face a dilemma: SumPath (efficient addition) produces outputs (0 for true, random non-zero for false) that cannot be arithmetically converted to leaf scores without complex logic; MultiplyPath (multiplication) allows direct scoring but incurs prohibitive multiplication depth and cost.
3. Communication Cost (C3): Standard PDTE protocols often require repetitive data encoding (e.g., repeating feature inputs for every comparison) to enable SIMD operations, leading to massive ciphertext sizes (e.g., >85 MB for 32-bit features) and network bottlenecks.

Methodology: SilentWood

SilentWood is a private inference protocol designed specifically for gradient boosting forests, leveraging FHE (specifically the BFV scheme) and introducing three novel optimization techniques to address the challenges above.

1. Computation Clustering

To reduce the overhead of homomorphic rotations and comparisons, SilentWood clusters redundant computations across the forest:

• Node Clustering: Nodes across different trees that share the same feature name and have similar threshold values are grouped. Instead of computing comparisons for each node individually, the protocol computes a weighted average of the thresholds (weighted by tree and node importance) and updates the model. This reduces the number of unique comparisons. The process includes a "leaf value re-optimization" step to adjust leaf scores based on the new thresholds, ensuring model accuracy is preserved. A validation check aborts any merge that degrades accuracy.
• Path Clustering: Paths with identical sets of unordered node conditions (e.g., A > 5 AND B > 10 vs. B > 10 AND A > 5) are identified. Since the result is order-insensitive, the protocol computes the path evaluation (SumPath) only once for the unique set of conditions, reusing the result for all matching paths.

2. Blind Code Conversion (BCC)

To solve the score aggregation dilemma (C2), SilentWood introduces a lightweight two-party protocol that bridges the gap between efficient SumPath evaluation and arithmetic score aggregation:

• Process: The server homomorphically shuffles and pads the SumPath ciphertexts (which contain 0s for true paths and random non-zeros for false paths) to create a uniformly random distribution. This ciphertext is sent to the client.
• Client Role: The client decrypts the data, converts 0s to 1s and non-zeros to 0s (blindly flipping the values), re-encrypts the result, and sends it back.
• Server Role: The server receives the converted ciphertext (now containing 1s for true paths and 0s for false paths) and performs a single homomorphic multiplication with the plaintext leaf scores. This effectively selects the correct leaf values without requiring deep multiplication chains.
• Security: The shuffling ensures the client learns nothing about the specific path outcomes, and the server learns nothing about the intermediate values during the client's conversion.

3. Ciphertext Compression

To address communication overhead (C3), SilentWood optimizes the client's initial query:

• Mechanism: Instead of repetitively encoding feature inputs for every comparison slot (as required by standard SIMD alignment), the client removes these repetitions before encryption, creating a compact ciphertext.
• Decompression: Upon receipt, the server performs a homomorphic decompression (using rotations and additions) to restore the original repetitive data format required for SIMD comparisons.
• Benefit: This reduces the client-to-server communication size significantly (e.g., from ~85 MB to ~15 MB for 32-bit features) without leaking plaintext information during the decompression process.

Key Contributions

The paper presents the following contributions:

1. Protocol Design: The proposal of SilentWood, the first private inference protocol specifically optimized for highly scalable gradient boosting decision forests.
2. Optimization Techniques: The introduction of three specific techniques:
   • Computation Clustering: Node and path clustering to eliminate redundant homomorphic operations.
   • Blind Code Conversion (BCC): A protocol enabling efficient arithmetic aggregation of tree scores using SumPath without high multiplication costs.
   • Ciphertext Compression: A method to reduce client query size by removing repetitive data encoding prior to encryption.
3. Implementation & Evaluation: A C++ prototype implementation and extensive evaluation across 13 UCI datasets, comparing performance against state-of-the-art baselines.

Results

The authors evaluated SilentWood against three baselines:

• Baseline: RCC-PDTE (a state-of-the-art FHE protocol) with naive MultiplyPath aggregation.
• Zama Concrete ML: A TFHE-based implementation.
• SoK-GGG: A state-of-the-art 2-party Garbled Circuit (GC) protocol.

Performance Metrics (CPU-FHE, 32-bit features, 100 trees):

• Speedup over Baseline: SilentWood is up to 42.5x faster (average 32.7x).
• Speedup over Zama: SilentWood is up to 27.8x faster (average 27.8x).
• Speedup over SoK-GGG: SilentWood is up to 2.94x faster (average 2.2x).
• Communication: SilentWood reduces client-server communication size by approximately 5x compared to the baseline (e.g., 15.12 MB vs 85.7 MB for 32-bit data).

Ablation Study:

• BCC provided the largest speedup contribution (~19.7x), primarily by avoiding expensive multiplication chains.
• Computation Clustering contributed a ~1.54x speedup.
• Ciphertext Compression contributed a ~1.08x speedup in low-latency settings, but its benefit grows significantly as network Round-Trip Time (RTT) increases.

Accuracy: The node clustering technique preserves model accuracy, with average accuracy remaining at 0.90 across various clustering intensities and tree configurations.

Significance

The paper claims that SilentWood represents a significant advancement in making private inference for gradient boosting models practical. By addressing the specific inefficiencies of scaling PDTE from single trees to forests—specifically the explosion of rotations, the incompatibility of aggregation methods, and communication bloat—SilentWood achieves inference times that are orders of magnitude faster than existing FHE approaches and competitive with (or faster than) MPC-based approaches. The authors emphasize that this enables the deployment of high-accuracy, explainable gradient boosting models in privacy-sensitive MLaaS environments where previous protocols were prohibitively slow or communication-heavy.