A New Paradigm for Privacy-Preserving Decision Tree Evaluation

Introduction

Decision trees are widely used for their interpretability and efficiency. However, deploying them on sensitive data—such as medical records or financial history—requires robust privacy guarantees for both the user's input and the model itself. Existing Privacy-Preserving Decision Tree (PPDT) evaluation protocols often struggle with high communication overhead and latency.

The primary bottleneck in current state-of-the-art (SOTA) methods is the reliance on secure selection. In a typical level-by-level tree traversal, a party must cryptographically select the next node without knowing which path was taken. For a tree of depth $d$, this necessitates $d$ rounds of interaction. These operations, often based on Oblivious Transfer (OT) or Function Secret Sharing (FSS), scale poorly with the number of nodes or security parameters, accounting for over half of the total evaluation cost.

The "Shuffle-then-Evaluate" Paradigm

To overcome these limitations, the authors propose a shift from "select-as-you-go" to a "shuffle-then-evaluate" approach. Operating within a 3-party replicated secret sharing (3PC) framework in a semi-honest setting, the protocol moves the heavy lifting to an offline phase. By shuffling the tree structure and features before evaluation, the system achieves an 86% reduction in communication and up to a 20× speedup over previous protocols.

Key Innovations

1. Secure Permutation over Selection: Instead of $d$ sequential secure selections, the parties perform a single secure permutation to shuffle the entire tree structure and feature list. Once shuffled, indices can be revealed in plaintext during evaluation without leaking the tree's structure or the specific path.
2. New Tree Representation: The model owner represents the tree using two permutations ($ζ, σ$) and a threshold list. This allows computing parties to generate a "one-time use" shuffled tree efficiently.
3. Oblivious Vector Expansion (OVE): Since a single feature or node might be referenced multiple times, the authors introduced OVE. This primitive allows for repeating items at specific indices in a secret-shared list without revealing the duplication pattern.
4. Structural Hiding: To prevent leakage via path length, all paths are padded to a maximum depth $d$ using dummy nodes and features.

Expand

Source, p. 6

Experimental Evaluation

The protocol was evaluated using eight standard datasets from the UCI Machine Learning Repository, including Iris, Breast Cancer, and Spambase. These datasets varied in complexity, with feature counts up to 57 and tree depths up to 30.

Performance Results

The benchmarks demonstrate significant improvements over existing SOTA protocols:

• Communication Efficiency: The protocol achieves an 86% reduction in communication compared to FSS-based methods (Ji et al.) and a 99.9% reduction compared to OT-based methods (Ma et al.).
• Speed: Overall performance improved by up to 20× over Ma et al. and 4.5× over Ji et al.
• Latency: In LAN environments, online latency remained stable between 15ms and 40ms.
• Scalability: For batch processing (e.g., 1000 queries), the protocol achieved a 50× speedup in the online phase by effectively amortizing costs.

Expand

Source, p. 2

Conclusion and Future Work

By replacing repeated secure selections with a single oblivious permutation, this work sets a new performance standard for PPDT. While the current model assumes a semi-honest, 3-party setting, it demonstrates that structural shuffling is a powerful tool for privacy-preserving inference. Future research may explore extending this paradigm to handle malicious adversaries or more complex model architectures beyond decision trees.