# Non-Interactive Decision Trees and Applications with Multi-Bit TFHE
## 6 Evaluation
### Experimental Results  
We implemented the comparison function and the classifiers in Rust using the concrete ([[https://github.com/zama-ai/concrete/tree/concrete-0.1.11](https://github.com/zama-ai/concrete/tree/concrete-0.1.11)]([https://github.com/zama-ai/concrete/tree/concrete-0.1.11](https://github.com/zama-ai/concrete/tree/concrete-0.1.11)) (accessed on 4 August 2022)) library [23] for the TFHE implementation. Our performance evaluations were run on a server with Intel Xeon Platinum 8170 (64-bit) processors running at 3.7 GHz and 192 GB RAM. We chose the statistical security parameter \(\lambda\) to be 128 and instantiated the TFHE scheme with the following parameters by the LWE estimator [24]. We used the default value for \(q=2^{64}\) given by the library. The number of padding bits \(\tilde{\omega}\) was set to 4 while encoding the 4-bit integers. Hence, the value of \(p=2^{4+4}\), i.e., uses 4-bits precision for representing the number and another 4-bits for padding. The LWE key has a dimension of 750 and a noise with a standard deviation of \(2^{-18}\). For the RLWE key, we used a polynomial of size 2048 and a standard deviation of \(2^{-52}\). The bootstrapping key has base \(2^{7}\) and level 3. The key-switching key has base \(2^{2}\) and level 7. We ran benchmarks for the performance of our comparison function and XCMP [6] non-interactive private method. Specifically, we measured the computation time for evaluating comparison, excluding the encryption and decryption time. The integer input size varied from 12 bits to 32 bits. The value of bit length for XCMP could only be measured to 19 bits because of the constraints of HElib [25]. The rest of the values for XCMP were extrapolated for higher bit length. The results are shown in Figure 12. Our comparison function for 32-bit and 64-bit integers is 26% faster than the naive TFHE implementation. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Protocol**} & \multicolumn{2}{c}{**Complexity**} & \multirow{2}{*}{**Rounds**} & \multirow{2}{*}{**Scheme**} & \multicolumn{2}{c}{**Leakage**} \\  & **Client** & & & & **Client** & **Server** \\ \hline [PERSON] et al. [19] & \(O((n+m)t)\) & \(O(mt)\) & \(\geq\)6 & Levelled-FHE & None & \(m\) \\ [PERSON] et al. [22] & \(O((n+m)t+d)\) & \(O(mt+2^{d})\) & 6 & AHE & None & \(m,d\) \\ [PERSON] et al. [21] & \(O((n+m)t)\) & \(O(mt)\) & 4 & AHE & None & \(m\) \\ This work & \(O(n\times\lceil t/4\rceil)\) & \(O(m\times\lceil t/4\rceil)\) & 2 & TFHE w PBS & None & None \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Computational complexity summary. A more efficient version of XCMP was mentioned in [26], but we could not compare its performance since its source code is not open sourced. We measured the path cost computation time for long paths to see the impact on evaluation trees with high depth. The computation time grows linearly with the length of the path in every step of 4. The results are shown in Figure 13.  
We trained our decision tree models on real datasets from the UCI repository [5] using the scikit-learn library [27]. The training phase was done on plain data without any encryption. The number of features, decision nodes and the depth of the trained models are summarized in Table 2. We measured the performance of our secure evaluation after both the client's input and the decision tree thresholds were encrypted. The performance gain achieved by the XCMP protocol is hindered by the fact that the feature vectors and decision tree thresholds cannot be more than 13 bits long. The work  
Figure 12: Evaluation time of our comparison method, TFHE [3] and XCMP [6], for comparing two encrypted value aspects to various bit lengths. Figure 13: Time taken for path cost calculation. of [PERSON] et al. [21], on the other hand, is an interactive protocol where the server needs to communicate with the client to determine the result. The final LWE encrypted classification result is serialized and sent to the client.