# Enhanced Outsourced and Secure Inference for Tall Sparse Decision Trees

arXiv: https://arxiv.org/abs/2505.02224 · HTML: https://mlsanity.com/paper/2505.02224/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 32 references that are in the map.
- First posted on arXiv 4 May 2025.

## Builds on (most cited first, 3 of 3)

- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Server-side Fingerprint-Based Indoor Localization Using Encrypted Sorting](https://mlsanity.com/paper/2008.11612/) (2020)

## Abstract (arXiv)

A decision tree is an easy-to-understand tool that has been widely used for classification tasks. On the one hand, due to privacy concerns, there has been an urgent need to create privacy-preserving classifiers that conceal the user's input from the classifier. On the other hand, with the rise of cloud computing, data owners are keen to reduce risk by outsourcing their model, but want security guarantees that third parties cannot steal their decision tree model. To address these issues, Joye and Salehi introduced a theoretical protocol that efficiently evaluates decision trees while maintaining privacy by leveraging their comparison protocol that is resistant to timing attacks. However, their approach was not only inefficient but also prone to side-channel attacks. Therefore, in this paper, we propose a new decision tree inference protocol in which the model is shared and evaluated among multiple entities. We partition our decision tree model by each level to be stored in a new entity we refer to as a "level-site." Utilizing this approach, we were able to gain improved average run time for classifier evaluation for a non-complete tree, while also having strong mitigations against side-channel attacks.