Faster Private Decision Tree Evaluation for Batched Input from Homomorphic Encryption

Privacy-preserving decision tree evaluation (PDTE) allows a client that holds feature vectors to perform inferences against a decision tree model on the server side without revealing feature vectors to the server. Our work focuses on the non-interactive batched setting where the client sends a batch of encrypted feature vectors and then obtains classifications, without any additional interaction. This is useful in privacy-preserving credit scoring, biometric authentication, and many more applications. In this paper, we propose two novel non-interactive batched PDTE protocols, \({{\,\mathrm{\textsf {BPDTE\_RCC}}\,}}\) and \({{\,\mathrm{\textsf {BPDTE\_CW}}\,}}\) , based on two batched ciphertext-plaintext comparison algorithms, our batched range cover comparison (RCC) comparator and the constant-weight (CW) piece-wise comparator, respectively. When comparing 16-bit batched encrypted values to a single plaintext value, our comparison algorithms show a speedup of up to \(72{\times }\) compared to the state-of-the-art \({{\,\mathrm{\textsf {Level Up}}\,}}\) (CCS’23). Moreover, we introduced a new tree traversal method called adapted \({{\,\mathrm{\textsf {SumPath}}\,}}\) , to achieve \(\mathcal {O}(1)\) complexity of the server’s response, whereas \({{\,\mathrm{\textsf {Level Up}}\,}}\) has \(\mathcal {O}(2^d)\) complexity for a depth-d tree and the client needs to look up classification values in a table. Overall, our PDTE protocols attain the optimal server-to-client communication complexity and are up to \(17{\times }\) faster than \({{\,\mathrm{\textsf {Level Up}}\,}}\) in batch size 16384.