Privacy-preserving outsourcing decision tree evaluation from homomorphic encryption

A decision tree is a common algorithm in machine learning, which performs classification prediction based on a tree structure. In real-world scenarios, input attribute values may be sensitive and tree models are usually private, thus the computation potentially incurs security and privacy risks. In this paper, we focus on how to retain privacy when outsourcing decision tree evaluation. Leveraging homomorphic encryption, our construction achieves data confidentiality against semi-honest adversaries while enabling both the client (who provides the attributes) and the model holder to be offline during evaluation. Based on an unbalanced computational-ability two-server model, we achieve single-branch evaluation, which is exponentially less computation than previous schemes that evaluated the entire decision tree. A proof-of-concept implementation demonstrates this. Additionally, with multi-key encryption and joint decryption, our protocol easily supports multi-client scenarios.

Automated summary

This paper focuses on maintaining privacy during decision tree evaluation by using homomorphic encryption, providing data confidentiality against semi-honest adversaries. The proposed construction allows both the client and the model holder to be offline during evaluation, achieving single-branch evaluation with significantly less computation compared to previous schemes. A proof-of-concept implementation demonstrates the effectiveness, and multi-key encryption and joint decryption support multi-client scenarios.