Welcome to the resource topic for 2024/662
Title:
Faster Private Decision Tree Evaluation for Batched Input from Homomorphic Encryption
Authors: Kelong Cong, Jiayi Kang, Georgio Nicolas, Jeongeun Park
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.
ePrint: https://eprint.iacr.org/2024/662
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .