Welcome to the resource topic for 2024/1077
Title:
Securely Training Decision Trees Efficiently
Authors: Divyanshu Bhardwaj, Sandhya Saravanan, Nishanth Chandran, Divya Gupta
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 \mathcal{O}(hmN\log N), when building a decision tree of height h for a training dataset of N samples, each having m attributes.
In this work, we significantly reduce the communication complexity of secure decision tree training.
We construct a protocol with communication complexity \mathcal{O}(mN\log N + hmN + hN\log N), thereby achieving an improvement of \approx \mathsf{min}(h, m, \log N) 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 10\times lesser communication and is 9\times faster than the state-of-the-art.
ePrint: https://eprint.iacr.org/2024/1077
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .