Let’s Stride Blindfolded in a Forest: Sublinear Multi-Client Decision Trees Evaluation
Jack P. K. Ma, Raymond K. H. Tai, Yongjun Zhao, Sherman S. M. Chow · 2021
Decision trees are popular machine-learning classification models due to their simplicity and effectiveness.Tai et al. (ESORICS '17) propose a privacy-preserving decision-tree evaluation protocol purely based on additive homomorphic encryption, without introducing dummy nodes for hiding the tree structure, but it runs a secure comparison for each decision node, resulting in linear complexity.Later protocols (DBSEC '18, PETS '19) achieve sublinear (client-side) complexity, yet the server-side path evaluation requires oblivious transfer among 2 d real and dummy nodes even for a sparse tree of depth d to hide the tree structure.This paper aims for the best of both worlds and hence the most lightweight protocol to date.Our complete-tree protocol can be easily extended to the sparse-tree setting and the reusable outsourcing setting: a model owner (resp.client) can outsource the decision tree (resp.attributes) to two non-colluding servers for classifications.The outsourced extension supports multi-client joint evaluation, which is the first of its kind without using multikey fully-homomorphic encryption (TDSC '19).We also extend our protocol for achieving privacy against malicious adversaries.Our experiments compare in various network settings our offline and online communication costs and the online computation time with the prior sublinear protocol of Tueno et al. (PETS '19) and O(1)-round linear protocols of Kiss et al. (PETS '19), which can be seen as garbled circuit variants of Tai et al.'s.Our protocols are shown to be desirable for IoT-like scenarios with weak clients and big-data scenarios with high-dimensional feature vectors.This work aims to make privacy-preserving inference more usable in practice.Technically, we propose a baseline protocol that achieves the best of two existing paradigms, namely, sublinear client-side computation complexity, without incurring an exponential blow-up in server-side complexity.Not only this improves the state-of-the-art on the foundational level, but this design is also easily extensible to the outsourced setting, saving us the ad-hoc efforts in customizing yet another protocol.We also extend it to achieve privacy against malicious adversaries.