Enhanced Private Decision Trees using Secure Multiparty Computation and Differential Privacy

We address the problem of decision tree learning from data that may be distributed across multiple data owners while protecting the privacy of the training data and the model from each data owner. To protect the training data, Secure Multiparty Computation (MPC) provides a very promising privacy-preserving solution with none or minimum accuracy loss, but there is a potential privacy leakage on the training data during model prediction or inference. To this end, existing solutions use a hybrid framework that combines MPC and Differential Privacy (DP), where DP models are trained with MPC protocols. The existing approaches combine MPC and DP in a naive way and often lead to models with lower accuracy. In this work, to take the full advantage of MPC’s inherent security guarantee, we propose a novel way of utilizing both MPC and DP that can improve model accuracy while providing the same privacy guarantee. Our key design idea is to adopt MPC for building the entire model without leaking any intermediate results, and then carefully calibrated noise to enforce the DP guarantee (DP-noise) is only added at the leaf level to achieve the desired ϵ-DP. By doing so, less amount of noise is needed, and as a consequence, model accuracy can be significantly improved. We provide formal privacy proof of the proposed protocol and analyze the amount of required DP-noise. In addition, we implemented our protocol in a distributed environment, and our empirical results show that our approach can indeed improve model accuracy by up to 29% for the Adult dataset even with a small privacy budget of ϵ = 0.005 comparing to the existing solution. However, our solution is computationally more expensive, and it trades off between accuracy and computation cost.