LAUSR

Privacy-preserving decision trees (DTs) in vertical federated learning are one of the most effective tools to facilitate various privacy-critical applications in reality. However, the main bottleneck of current solutions is their huge overhead, mainly due to the adoption of communication-heavy bit decomposition to realize complex non-linear operations, such as comparison and division. In this paper, we present PriVDT, an efficient two-party framework for private vertical DT training and inference in the offline/online paradigm. Specifically, we customize several cryptographic building blocks based on an advanced primitive, Function Secret Sharing (FSS). First, we construct an optimized comparison protocol to improve the efficiency via reducing the invocation of FSS evaluations. Second, we devise an efficient and privacy-enhanced division protocol without revealing the range of divisors, which utilizes the above comparison protocol and more importantly new designed FSS-based secure range and digital decomposition protocols. Besides, we further reduce the overhead of linear operations by employing lightweight pseudorandom function-based Beaver’s triple techniques. Building on the above efficient components, we implement the PriVDT framework and evaluate it on 5 real-world datasets on both LAN and WAN. Experimental results show that the end-to-end runtime of PriVDT outperforms the prior art by $42 \sim 510\times $ on LAN and $16 \sim 70\times $ on WAN. Moreover, PriVDT provides comparable accuracy to the non-private setting.