Paper 2024/1077

Securely Training Decision Trees Efficiently

Abstract

Decision trees are an important class of supervised learning algorithms. When multiple entities contribute data to train a decision tree (e.g. for fraud detection in the financial sector), data privacy concerns necessitate the use of a privacy-enhancing technology such as secure multi-party computation (MPC) in order to secure the underlying training data. Prior state-of-the-art (Hamada et al.) construct an MPC protocol for decision tree training with a communication of $$, when building a decision tree of height $$ for a training dataset of $$ samples, each having $$ attributes. In this work, we significantly reduce the communication complexity of secure decision tree training. We construct a protocol with communication complexity $$, thereby achieving an improvement of $$ over Hamada et al. At the core of our technique is an improved protocol to regroup sorted private elements further into additional groups (according to a flag vector) while maintaining their relative ordering. We implement our protocol in the MP-SPDZ framework and show that it requires $$ lesser communication and is $$ faster than the state-of-the-art.