Low-Complexity Private Decision Tree Evaluation over Homomorphic Encryption

As machine-learning-as-a-service (MLaaS) becomes ubiquitous, protecting model queries via private inference is increasingly critical. Existing homomorphic encryption (HE)-based protocols for Private Decision Tree Evaluation (PDTE) have server complexity that scales at least as 𝑂 (2 𝐷 ) in the tree depth 𝐷, so the cost of evaluating each tree grows exponentially with depth; in gradient boosted decision tree (GBDT) ensembles, where predictions aggregate the outputs of many trees, this per-tree cost is directly amplified. In this paper, we present a non-interactive HE-based PDTE protocol built on the CKKS scheme with an end-to-end complexity of 𝑂 (𝑝 √ 2 𝐷 ), where 𝑝 is the input bit-length. To the best of our knowledge, this is the first HE-based PDTE scheme that asymptotically improves over the 𝑂 (2 𝐷 ) dependence on 𝐷 while remaining non-interactive. We address two depth-driven sources of 𝑂 (2 𝐷 ) dependence in existing protocols: we use the One-Branch-Only (OBO) paradigm from PROBONITE for comparisons, and we design the Baby-Step Giant-Step based Branch Selection algorithm for traversal. To further exploit the structure of GBDT ensembles, we deploy the batched bootstrapping technique by applying level-major tree evaluation. Our experimental results show that, at depth 𝐷 = 12, our protocol reduces communication by 8.38× and runtime by 7.74× compared to FASTER, which is the fastest prior HE-based non-interactive PDTE baseline in our amortized setting, and the advantage increases as 𝐷 grows. These results suggest that our design provides a practical path toward depth-scalable HE-based PDTE for large boosted ensembles. CCS Concepts • Security and privacy → Privacy-preserving protocols; Cryptography.