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.
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