GTree: GPU-friendly Privacy-preserving Decision Tree Training and Inference

Outsourcing Decision tree (DT) training and inference to cloud platforms raises privacy concerns. Recent Secure Multi-Party Computation (MPC)-based methods are hindered by heavy overhead. Few recent studies explored GPUs to improve MPC-protected deep learning, yet integrating GPUs into MPC-protected DT with massive data-dependent operations remains challenging, raising question: can MPC-protected DT training and inference fully leverage GPUs for optimal performance?We present GTree, the first scheme that exploits GPU to accelerate MPC-protected secure DT training and inference. GTree is built across 3 parties who jointly perform DT training and inference with GPUs. GTree is secure against semi-honest adversaries, ensuring that no sensitive information is disclosed. GTree offers enhanced security than prior solutions, which only reveal tree depth and data size while prior solutions also leak tree structure. With our oblivious array access, access patterns on GPU are also protected. To harness the full potential of GPUs, we design a novel tree encoding method and craft our MPC protocols into GPU-friendly versions. GTree achieves ~11× and ~21× improvements in training SPECT and Adult datasets, compared to prior most efficient CPU-based work. For inference, GTree outperforms the prior most efficient work by 126× when inferring 10<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> instances with a 7-level tree.