Privacy-preserving decision tree training facilitates multiple parties to jointly train a decision tree model, whilst preserving the confidentiality of their individual data. Pivot [1] (VLDB’ 20) is by far the most advanced generic and scalable PDTT protocol, while more recent works Squirrel [2] (USENIX’ 23) and Ham-ada et al. [3] (PETS’ 23) achieve better performance in particular settings ([2] concentrating on 2-party setting) or functionalities ([3] honing on classification tree with continuous attributes). A critical limitation of Pivot is its dependency on vertical federated learning, which mandates that a single party possesses all the record values for a particular feature. This assumption allows vertical federated learning approaches to compute the evaluation function in plaintext. In this paper, we proposed KOG, a novel scalable privacy-preserving decision trees training framework with pure secure multiparty computation (MPC), in which all computations in training are performed under secret shares. KOG is adaptable, catering to both regression and classification aims of decision trees, with the ability to handle both continuous and discrete inputs. Notably, KOG’s computational complexity is proportional to the depth of the tree. We also extend our solution and implement random forest (RF) and gradient boosting decision tree (GBDT). Besides supporting non-vertical decision tree, KOG as an MPC based solution, also outperforms the federated learning based Pivot by 10X-100X in efficiency.
