# Non-Interactive Decision Trees and Applications with Multi-Bit TFHE
###### Abstract  
Machine learning classification algorithms, such as decision trees and random forests, are commonly used in many applications. Clients who want to classify their data send them to a server that performs their inference using a trained model. The client must trust the server and provide the data in plaintext. Moreover, if the classification is done at a third-party cloud service, the model owner also needs to trust the cloud service. In this paper, we propose a protocol for privately evaluating decision trees. The protocol uses a novel private comparison function based on fully homomorphic encryption over the torus (TFHE) scheme and a programmable bootstrapping technique. Our comparison function for 32-bit and 64-bit integers is 26% faster than the naive TFHE implementation. The protocol is designed to be non-interactive and is less complex than the existing interactive protocols. Our experiment results show that our technique scales linearly with the depth of the decision tree and efficiently evaluates large decision trees on real datasets. Compared with the state of the art, ours is the only non-interactive protocol to evaluate a decision tree with high precision on encrypted parameters. The final download bandwidth is also 50% lower than the state of the art. (fully) homomorphic encryption; machine learning classification; decision trees +
Footnote †: journal:  
0000-0001-9500-0001-9500]T.  
In this work, we focus on privacy-preserving classification using a decision tree. The secure evaluation of the decision tree involves the data owner, the model owner and a third-party evaluator, such as a cloud server. The model owner encrypts the model, and the data owner encrypts the feature vector. A third-party evaluator, such as a public cloud service, evaluates the query using the encrypted model parameters and returns the result, which the data owner decrypts, as shown in Figure 1. The main challenge in secure evaluation is to have an efficient way to compare the thresholds with the feature vector securely. We propose a secure comparison algorithm using fully homomorphic encryption (FHE) [2] and a decision tree evaluation protocol that preserves all the functionality without compromising the privacy of the data and model owners. This work aims to design and implement a private decision tree evaluation protocol that is both efficient and non-interactive. To this end, we propose a new non-interactive private comparison method that allows its output to be further used in the decision tree evaluation. This method can compare two encrypted integers, \(a\) and \(b\), and return a ciphertext that decrypts to 1 if \(a>b\) and 0 otherwise. We encrypt each nibble of integer \(a\) and \(b\) using the fully homomorphic encryption over the torus (TFHE) [3] scheme, and then we compare the encrypted nibbles using programmable bootstrapping [4]. Since the TFHE scheme supports bootstrapping, we can use the encrypted output in further homomorphic operations. This method's non-interactive property is used in the non-interactive private decision tree evaluation protocol. In this protocol, we use our private comparison method to compare the thresholds of the decision tree with the feature vector elements. Then, we use the output of the private comparison method to traverse the decision tree to evaluate the classification result. We implemented and conducted rigorous experiments to study the effect of different bit lengths to assess scalability. We also conducted experiments with decision trees trained with real datasets from the UCI machine learning repository [5] and compared them with the existing protocols. Existing approaches to the comparison of encrypted integers are not suitable for our purpose. The performance of bit-wise comparison operation using naive TFHE encryption is very slow and grows linearly with bit length. The state-of-the-art comparison operation using XCMP [6] only performs well for integers with a small bit length and grows exponentially with bit length.