XGT: Fast and Secure Decision Tree Training and Inference on GPUs

The decision tree (DT) model is widely usedin various applications due to its versatility, speed, and interpretability. However, outsourcing DT training and inference to cloud platforms raises data privacy concerns. While significant strides have been made in developing private DT training and inference using cryptography such as Secure Multi-Party Computation (MPC), the performance is still not ideal in real-world applications. Only a few recent works have explored using GPUs to enhance the performance of MPC-based deep learning. Nevertheless, data-dependent operations and the high communication costs inherent in MPC-based DT make the integration of GPUs a challenge. We introduce the eXpress GPU-based Tree (<i>XGT</i>), a fast MPC-based framework for private DT training and inference on GPUs. <i>XGT</i>converts the majority of operations in training and inference into parallelizable matrix operations, supplemented by various optimizations, including matrix dimension reductions. This innovative design leads to substantial reductions in communication overhead while maintaining the critical property of obliviousness. <i>XGT</i>also achieves a stronger security guarantee, where all data items, the tree shape, access patterns, and data distributions generated during the training and inference are protected. <i>XGT</i>only reveals the tree depth. The experimental results show that <i>XGT</i>is up to <inline-formula><tex-math notation="LaTeX">$278{\times }$</tex-math></inline-formula> faster than the previous most efficient CPU-based approach. <i>XGT</i>outperforms the latest GPU-based DT work by <inline-formula><tex-math notation="LaTeX">$41{\times }$</tex-math></inline-formula>. For inference, <i>XGT</i>is up to <inline-formula><tex-math notation="LaTeX">$2,800{\times }$</tex-math></inline-formula> faster than previous CPU-based inference schemes and at least <inline-formula><tex-math notation="LaTeX">$18 \times$</tex-math></inline-formula> faster than GPU-based.