Paper 2025/1447
A New Paradigm for Privacy-Preserving Decision Tree Evaluation
Abstract
Privacy-preserving decision tree inference is a fundamental primitive in privacy-critical applications such as healthcare and finance, yet existing protocols rely heavily on secure selection, which accounts for more than half of the total cost. We introduce a new paradigm that eliminates this limitation by replacing multiple secure selections with a single permutation, whose cost is comparable to that of a single secure selection. Our scheme significantly reduces both computation and communication overhead compared to SOTA. Comprehensive benchmarks show an 86 % reduction in model evaluation versus the state-of-the-art FSS protocol by Ji et al., and a 99.9 % reduction versus the OT-based protocol of Ma et al. Overall, our benchmark shows that our protocol achieves a performance improvement of 20 tiems over Ma et al.’s scheme and 4.5 times over Ji et al.’s scheme.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- secure permutationdecision treesecure multiparty computation
- Contact author(s)
-
lutianpei @ zju edu cn
bingsheng @ zju edu cn
22321050 @ zju edu cn
kuiren @ zju edu cn - History
- 2025-12-04: revised
- 2025-08-09: received
- See all versions
- Short URL
- https://ia.cr/2025/1447
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1447,
author = {Tianpei Lu and Bingsheng Zhang and Hao Li and Kui Ren},
title = {A New Paradigm for Privacy-Preserving Decision Tree Evaluation},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1447},
year = {2025},
url = {https://eprint.iacr.org/2025/1447}
}
