Paper 2020/1130
Secure training of decision trees with continuous attributes
Mark Abspoel, Daniel Escudero, and Nikolaj Volgushev
Abstract
We apply multiparty computation (MPC) techniques to show, given a database that is secret-shared among multiple mutually distrustful parties, how the parties may obliviously construct a decision tree based on the secret data.
We consider data with continuous attributes (i.e., coming from a large domain), and develop a secure version of a learning algorithm similar to the C4.5 or CART algorithms.
Previous MPC-based work only focused on decision tree learning with discrete attributes (De Hoogh et al. 2014).
Our starting point is to apply an existing generic MPC protocol to a standard decision tree learning algorithm, which we then optimize in several ways.
We exploit the fact that even if we allow the data to have continuous values, which a priori might require fixed or floating point representations, the output of the tree learning algorithm only depends on the relative ordering of the data.
By obliviously sorting the data we reduce the number of comparisons needed per node to
Note: Fixed acknowledgements
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Proceedings on Privacy Enhancing Technologies (PoPETs) 2021, Issue 1
- Keywords
- decision treesmultiparty computationprivacy-preserving machine learning
- Contact author(s)
-
abspoel @ cwi nl
escudero @ cs au dk - History
- 2021-06-20: revised
- 2020-09-21: received
- See all versions
- Short URL
- https://ia.cr/2020/1130
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1130, author = {Mark Abspoel and Daniel Escudero and Nikolaj Volgushev}, title = {Secure training of decision trees with continuous attributes}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1130}, year = {2020}, url = {https://eprint.iacr.org/2020/1130} }