Paper 2024/662
Faster Private Decision Tree Evaluation for Batched Input from Homomorphic Encryption
Abstract
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, BPDTE_RCC and BPDTE_CW, based on two new ciphertext-plaintext comparison algorithms, the improved range cover comparison (RCC) comparator and the constant-weight (CW) piece-wise comparator, respectively. Compared to the current state-of-the-art Level Up (CCS'23), our comparison algorithms are up to $72\times$ faster for batched inputs of 16 bits. Moreover, we introduced a new tree traversal method called Adapted SumPath, to achieve $\mathcal{O}(1)$ complexity of the server's response, whereas Level Up has $\mathcal{O}(2^d)$ for a depth-$d$ tree where 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 Level Up in batch size 16384.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Machine learningPrivate Decision Tree EvaluationHomomorphic encryption
- Contact author(s)
-
kelong cong @ zama ai
jiayi kang @ esat kuleuven be
georgio nicolas @ esat kuleuven be
jeongeun park @ ntnu no - History
- 2024-05-02: approved
- 2024-04-29: received
- See all versions
- Short URL
- https://ia.cr/2024/662
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/662, author = {Kelong Cong and Jiayi Kang and Georgio Nicolas and Jeongeun Park}, title = {Faster Private Decision Tree Evaluation for Batched Input from Homomorphic Encryption}, howpublished = {Cryptology ePrint Archive, Paper 2024/662}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/662}}, url = {https://eprint.iacr.org/2024/662} }