# Non-Interactive Decision Trees and Applications with Multi-Bit TFHE
## 5 Applications of Private Integer Comparison: Decision Trees
### Private Evaluation of Decision Trees  
Recall from Figure 4 that evaluating the decision tree requires comparing each node threshold with one of the feature vector values. This comparison is made using our PvtCmp function, resulting in a tree with encrypted comparison results. For each node \(i\), we assign \(b_{i}\leftarrow\textsc{PvtCmp}(x_{\sigma(i)},\tau_{i})\).  
After computing all the decision values in the internal nodes, we assign a cost to each edge similar to [PERSON] et al. (2018), as shown in Figure 9. If the value of \(b_{i}\) is 1, then the path cost on its right edge will be 0, whereas the path cost on the left edge will be 1. In other words, the traversal will have a penalty of 1 for continuing on the left edge. Similarly, if the value of \(b_{i}\) is 0, then the path cost on its left edge will be 0, whereas the path cost on the right edge will be 1. The value \(1-b_{i}\) is computed using programmable bootstrapping with the function below, which inverts the input bit.  
\[f(x)=\begin{cases}1&x=0\\ 0&x\
eq 0\end{cases} \tag{11}\]  
For each leaf node, we construct a path from the root node consisting of all the edges from it to the leaf node. The cost of a path is computed by adding the path cost of all the edges in its path. We make use of our Parallel-Prefix-Sum algorithm to compute the path cost. If the length is less than \(2^{m}\), we append zero encryption to the path. If the length is greater than \(2^{m}\), then we split the path into chunks of size \(2^{m}\) and compute the path cost recursively by adding the path cost of the chunks. The paths of interest are those with a path cost of zero. Hence, we invert the path cost using a programmable bootstrapping function; the paths with zero path cost return one, and those with non-zero path cost return zero. The details of the algorithm are shown in Algorithm 4. The outputs of Is-Zero-Path-Cost are multiplied with the corresponding leaf value \(v_{i}\), and the terms are added to obtain the final output.  
Figure 10 shows the complete private decision tree evaluation. The client sends the encrypted integer as a sequence of encrypted nibble \([x_{1}],\ [x_{2}],\ \dots\ [x_{n}]\) to the server. The model owner also encrypts the decision tree thresholds \([\tau_{1}],[\tau_{2}],\dots\ [\tau_{m}]\) to the server. The server computes the private comparison values \([b_{1}],\ [b_{2}],\ \dots\ [b_{m}]\) for each of the \(m\) interior nodes. The server then computes the edge costs \([ec]\) of each node. For all the paths  
Figure 8: Encrypted 32-bit comparator circuit by cascading 4-bit encrypted comparator.  
where \(i\in\{1,m+1\}\) from root to the leaf node, we calculate its edge path cost \(pc_{i}\) using the Parallel-Prefix-Sum algorithm. The \(\widetilde{pc_{i}}\) is calculated by inverting the \(pc_{i}\) bit to indicate whether the path has zero edge path cost. The final result is obtained by pairwise multiplying \(\widetilde{pc_{i}}\) with \(v_{i}\) to obtain the final \(v\) value. The server sends the encrypted \([v]\) to the client, and the client decrypts the \([v]\) to obtain the final classification.  
```
Input: An encrypted bit array \(\mathbb{X}\in[\mathbb{B}]^{n}\), encryption of zero \([0]\) Output: An encrypted bit \(b\in[\mathbb{B}]\), such that \(b\leftarrow[1]\) if \([1]\in\mathbb{X}\)  Split the array \(\mathbb{X}\) into \(\mathbb{X}_{0},\mathbb{X}_{1},\ldots\in[\mathbb{B}]^{k}\), where \(k\leq n\) and \(k=2^{m}\). Append \([0]\) to the last split if \(k\
mid n\) for all\(\mathbb{X}_{i}\)do \(partial\_{sum}[i]\leftarrow\textsc{Parallel-Prefix-Sum}(\mathbb{X}_{i})\) \(partial\_{sum}[i]\leftarrow\textsc{Pbs}\Bigg{(}partial\_{sum}[i],\lambda(x)= \begin{cases}1&x=0\\ 0&x\
eq 0\end{cases}\) \(partial\_{sum}[i]\leftarrow\textsc{Ks}(partial\_{sum}[i])\) endfor if\(partial\_sum\) has more than one element then return Is-Zero-Path-Cost(\(partial\_sum\)) else return\(partial\_sum[0]\) endif
```  
**Algorithm 4** Is-Zero-Path-Cost