FSS-DT: Secure Division-free Decision Tree Training and Inference via Function Secret Sharing
- 21 May 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. PP (15455971) , 1-15
Abstract
Decision tree (DT), an efficient and interpretable machine learning algorithm, has been widely used in numerous industrial applications. As the demand for higher performance grows, there is increasing interest in cross-domain collaboration for training DTs using vertical datasets, where different owners hold distinct features but share the same set of samples. Due to privacy concerns, leveraging secure multi-party computation (MPC) to train DTs jointly has gained significant attention. Although promising, deploying these approaches across large scale vertical datasets presents formidable challenges for two bottlenecks: divisions and comparisons. MPC is not friendly to process divisions, whereas DT training algorithms involve division to evaluate each feature split for each tree node. DT training and inference also involve numerous comparisons, yet existing secure comparisons are still not efficient enough. We propose FSS-DT, a highly efficient two-party framework for secure DT training and inference on vertically distributed datasets. The efficiency of FSS-DT is achieved by designing a division-free MPC-friendly DT algorithm. Moreover, we present a lightweight secure comparison protocol using our optimized distributed comparison function (DCF), an instance of function secret sharing, via “0/1-encoding” and “early termination” techniques. We have implemented a prototype of FSS-DT. Extensive experiments demonstrate that FSS-DT achieves the same accu racy as models trained in plaintext and outperforms the state-of the-art Pivot and PriVDT. Specifically, for training on LAN and WAN over the large UCI dataset, FSS-DT is 17.5× and 51.1× faster than Pivot, and about 8.4× and 8.8× faster than Swan, respectively.Keywords
Funding Information
- National Natural Science Foundation of China (62402358)
- National Key Research and Development Program of China (2023YFB3107500)
- Young Elite Scientist Sponsorship Program by CAST (YESS20240717)
- Young Talent Fund of Association for Science and Technology in Shaanxi, China (20240138)
- “Pioneer” and “Leading Goose” R&D Program of Zhejiang (2026SDXT014)
- Key Research and Development Projects of Shaanxi Province (2025PT-ZCK-52)
- Open Topics from The Lion Rock Labs of Cyberspace Security (#LRL24004)
- Fundamental Research Funds for the Central Universities (ZDRC2202)
- Xidian University Specially Funded Project for Interdisciplinary Exploration (TZJHF202502)
- China Scholarship Council
This publication has 44 references indexed in Scilit:
- Communication-Efficient Secure Neural Network via Key-Reduced Distributed Comparison Function2025
- Computation Efficient Structure-Aware PSI from Incremental Function Secret Sharing2024
- Half-Tree: Halving the Cost of Tree Expansion in COT and DPF2023
- Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation2021
- Function Secret Sharing2015
- Improved Garbled Circuit: Free XOR Gates and Applications2008
- An Efficient Solution to the Millionaires’ Problem Based on Homomorphic Encryption2005
- Privacy Preserving Data Mining2000
- General Secure Multi-party Computation from any Linear Secret-Sharing Scheme2000
- Security and Composition of Multiparty Cryptographic ProtocolsJournal of Cryptology, 2000