Secure Decision Trees

The core mechanism for choosing split points without exposing raw data. Protocols use secure comparison and argmax operations over secret-shared values to determine the optimal feature and threshold.

• Gini impurity or information gain computed entirely in the encrypted domain
• Uses oblivious selection to hide which feature was chosen
• Prevents leakage of marginal distributions across parties

During inference, the evaluation path through the tree must remain hidden to prevent the computing parties from inferring the input. Oblivious evaluation ensures every possible path is traversed, with only the correct result selected.

• Implements conditional selection using cryptographic multiplexers
• Prevents timing side-channels that could leak decision boundaries
• Essential for model privacy when the tree structure is proprietary

Continuous features are discretized into bins before secure computation to dramatically reduce the number of comparisons. This preprocessing step converts expensive secure comparisons into cheaper secure equality checks or table lookups.

• Reduces circuit depth for garbled circuit implementations
• Enables efficient oblivious transfer-based evaluation
• Typical bin counts range from 8 to 256 per feature

Modern secure decision trees combine multiple cryptographic primitives to optimize for different operations. Arithmetic sharing handles aggregation, while boolean sharing or garbled circuits manage comparisons.

• Secret sharing for linear operations and weight sums
• Garbled circuits for non-linear threshold comparisons
• Oblivious transfer for leaf-level lookups
• Protocol switching occurs at predetermined circuit boundaries

Finding exact median or quantile splits securely is prohibitively expensive. Instead, protocols use distributed quantile sketching algorithms like t-digest or Greenwald-Khanna summaries to approximate split points with bounded error.

• Communication complexity reduced from quadratic to near-linear
• Approximation error typically bounded to ε < 0.01
• Enables practical training on datasets with millions of records

To maintain practical performance, secure training often restricts tree depth to 4-8 levels. Each additional level adds cryptographic overhead, so shallow trees with higher leaf cardinality are preferred over deep, narrow structures.

• XGBoost-style boosting adapts well to depth constraints
• Ensemble methods compensate for individual tree shallowness
• Typical secure random forests use 50-100 shallow trees

The foundational protocol introduced by Andrew Yao that enables secure two-party computation of any boolean circuit. In the context of decision trees, each comparison node (e.g., feature_x < threshold) is represented as a boolean gate. The tree evaluation is compiled into a circuit where garbled truth tables are exchanged, allowing parties to traverse the tree without revealing their input vector or the tree structure. Modern optimizations like Free-XOR and Half-Gates make this the dominant approach for private inference.

A fundamental primitive where a sender inputs two messages and a receiver selects one, with the sender learning nothing about the choice and the receiver learning nothing about the unselected message. In secure decision trees, OT is the core engine for evaluating garbled circuit gates. The receiver's input bits select the correct garbled row without the sender knowing which path was taken. OT Extension protocols amplify a few base OTs into millions of efficient transfers using only symmetric cryptography.

A method for distributing a secret value among parties such that no single party can reconstruct it. In arithmetic-based secure decision tree protocols, input features and model parameters are additively shared. Computations like secure comparison and threshold evaluation are performed interactively on shares. Schemes like Shamir's Secret Sharing provide threshold properties, while replicated secret sharing in the 3-party honest-majority setting enables extremely fast, communication-efficient tree evaluation.

The critical bottleneck in private decision tree evaluation. At each internal node, the parties must jointly compute x < t without revealing the feature value x or the threshold t. Efficient protocols use DReLU (derivative of ReLU) circuits, bit-decomposition of shared values, or specialized comparison garbled circuits. The CrypTFlow2 framework demonstrated that optimized secure comparison can evaluate complex tree ensembles over encrypted data in under a second.

A cryptographic technique that hides memory access patterns from an observer. In decision tree evaluation, the path taken through the tree leaks information about the input. ORAM ensures that each node access appears random and independent of the actual decision path. While computationally expensive, circuit ORAM constructions can be integrated into secure tree protocols to provide access-pattern hiding, preventing leakage of the tree traversal route to the server holding the model.