Level Up: Private Non-Interactive Decision Tree Evaluation using Levelled Homomorphic Encryption

Rasoul Akhavan Mahdavi, Haoyan Ni, Dimitry Linkov, Florian Kerschbaum

Abstract

Private Decision Tree Evaluation (PDTE) is a critical component of privacy-preserving Machine Learning as a Service (MLaaS), enabling a server to evaluate a decision tree on a client's encrypted data without compromising the client's privacy or the server's proprietary model. Historically, non-interactive PDTE protocols have struggled with high latency or restricted bit-precision. This paper presents two novel protocols, XXCMP-PDTE and RCC-PDTE, which leverage Levelled Homomorphic Encryption (LHE) and optimized comparison operators to achieve high-performance evaluation. By decoupling computational depth from bit-precision, these protocols can evaluate trees with over 1,000 nodes and 16-bit precision in under two seconds, representing a significant improvement over previous state-of-the-art methods.

Introduction

As Machine Learning as a Service (MLaaS) becomes ubiquitous, the tension between data privacy and intellectual property protection intensifies. Clients require that their sensitive input data remains confidential, while service providers seek to protect their proprietary models. Private Decision Tree Evaluation (PDTE) offers a solution by allowing a server to execute a decision tree model on encrypted client data.

Existing PDTE solutions generally fall into two categories: interactive and non-interactive. Interactive protocols based on Multi-Party Computation (MPC) are often fast but require multiple rounds of communication, making them unsuitable for high-latency environments or "send-and-forget" scenarios where the client goes offline. Conversely, non-interactive protocols based on Fully Homomorphic Encryption (FHE) allow for single-round communication but have traditionally been slow or limited to low bit-precision (typically 11–13 bits). This paper introduces high-performance non-interactive protocols that support high-precision inputs without the typical performance penalties.

Methodology

The proposed protocols are built upon the Fan-Vercauteren (FV) homomorphic encryption scheme and introduce several key innovations to optimize performance and precision.

Comparison Operators

The authors propose two distinct protocols based on different comparison strategies:

  • XXCMP-PDTE (Extended XCMP): This protocol extends the existing XCMP method to support arbitrary bit-precision. It represents large numbers in base-$N$ and performs comparisons by evaluating high-order digits first, allowing for more flexible precision handling.
  • RCC-PDTE (Range Cover Comparison): This more scalable approach utilizes One-sided Uniform Range Covers (OURC) combined with constant-weight equality operators. A major advantage of this operator is that its multiplicative depth depends on the Hamming weight of the code rather than the bit-precision of the numbers, allowing for high-precision comparisons (e.g., 32-bit or 64-bit) with minimal depth increase.

Tree Traversal and Optimization

To navigate the decision tree efficiently within the constraints of LHE, the authors employ the SumPath Traversal algorithm. Unlike traditional methods that multiply edge values—which rapidly exhausts the encryption "noise budget"—SumPath uses additions to identify the correct leaf node. This keeps the circuit depth shallow and the computation fast.

Furthermore, the protocols utilize SIMD (Single Instruction, Multiple Data) Optimization. Rather than using batching solely to process multiple users, the authors use it to parallelize the internal comparisons of a single inference task, drastically reducing overall latency.

Experimental Evaluation

The researchers evaluated the protocols using both real-world and synthetic datasets:

  1. UCI Machine Learning Repository: Four standard datasets—Breast Cancer, Steel Plates Faults, Heart Disease, and Spam—were used to benchmark performance on practical classification tasks.
  2. Synthetic Decision Trees: To test scalability, the authors generated balanced trees with depths up to 10 (1,023 nodes), varying bit-precisions (8, 16, and 26 bits), and attribute counts (up to 100).

Key Results and Insights

The experimental results demonstrate that the proposed protocols significantly outperform existing non-interactive solutions:

  • High Speed and Low Latency: The RCC operator can compare two 32-bit numbers in less than 10 milliseconds. In full tree evaluations, RCC-PDTE processed a tree with 1,023 nodes and 16-bit precision in under 2 seconds. For context, the previous state-of-the-art, SortingHats, required over 10 seconds for a similar tree with only 11-bit precision.
  • Decoupled Precision: By using constant-weight codes, the authors successfully decoupled computational cost from bit-length. This allows the system to handle 32-bit or 64-bit inputs without the exponential slowdown typically associated with LHE-based comparisons.
  • Structural Independence: In the RCC-PDTE protocol, the multiplicative depth of the evaluation is independent of the tree's depth or the number of attributes. This makes it uniquely capable of handling "deep" trees that would otherwise exceed the noise budget of standard LHE systems.
  • Throughput: On UCI datasets, the new protocols achieved up to a 5x speedup over SortingHats. While RCC-PDTE has higher initial communication overhead for models with few attributes, it becomes more efficient than alternatives as the number of client attributes exceeds 40.

Conclusion

This work demonstrates that non-interactive Private Decision Tree Evaluation can be both high-precision and high-performance. By optimizing comparison operators and tree traversal logic, the authors have removed the precision bottleneck that previously limited LHE-based PDTE. Future research may focus on refining data "packing" strategies to further reduce communication overhead for single-inference queries and adapting these high-efficiency comparison operators to other forms of private computation.

Summary updated

BibTeX
@inproceedings{mahdavi2023level,
  author = {Rasoul Akhavan Mahdavi and Haoyan Ni and Dimitry Linkov and Florian Kerschbaum},
  title = {{Level Up: Private Non-Interactive Decision Tree Evaluation using Levelled Homomorphic Encryption}},
  booktitle = {CCS},
  year = {2023},
  doi = {10.1145/3576915.3623095},
}
Figure