## 3 PPDT Classification Model
### Proposed Protocol
8:\(P\gets P\setminus P_{i}\), \(V\gets V\setminus V_{i}\)
9:endif
10:endfor
11:return\(P\), \(V\)
12: Given encrypted path matrix \([\bar{\mathbf{P}}_{\bar{s}}]\) and classification result matrix \([\bar{\mathbf{V}}_{\bar{s}}]\) (Line 36 of Algorithm 1)  Client decrypts and obtains classification result (refer to Equations (19), (20) and (25)) \(\Rightarrow\) this process (Lines 11-21 bellow) replaces Lines 37-47 of Algorithm 1
13: Default class is \(C_{out}=C_{0}\)
14:for\(s=1\) to \(S\)do
15:\(\bar{\mathbf{P}}_{\bar{s}}\leftarrow\text{Dec}([\bar{\mathbf{P}}_{\bar{s}}],sk)\)
16:for\(k=1\) to \(m^{\prime}\)do
17:if\(\exists((k-1)(m+1)\)-th coefficients in \(P_{s}=0)\)then
18: computes \(\bar{\mathbf{V}}_{\bar{s}}\leftarrow\text{Dec}([\bar{\mathbf{V}}_{\bar{s}}],sk)\). 19:\(C_{out}\leftarrow\) the coefficient of \(x^{(k-1)(m+1)}\)
20:endif
21:endfor
22:endfor
23:return\(C_{out}\)
```

**Algorithm 2** Efficiency-Enhanced PPDT with LNP (Algorithm 1+LNP)

Note that the default class \(C_{0}\) must be securely shared in advance between the client and the model holder. Assigning the majority class as the default is generally more effective. The selection of the class excluded from computation depends on the classification task, as outlined below:

**Binary classification tasks**: (e.g., disease detection, abnormality detection): Only the decision path for class \(1\) (positive or anomalous) is evaluated. If the result is \(0\), class \(1\) is returned; otherwise, class \(0\) (negative or normal) is output. **Multi-class classification tasks:**: Only \(K-1\) classes are evaluated. If the dataset exhibits class imbalance (e.g., ImageNet), the majority class is assigned as the default. In the absence of such imbalance (e.g., MNIST), one class is randomly selected to serve as the default (i.e., the class not evaluated). We next use a simple example to illustrate homomorphic matrix multiplication and the leaf node pruning process based on Figure 1 to enhance clarity and aid in reader understanding. **Example 1**. : _Figure 1 shows a decision tree example that is for three classes \(\mathcal{C}=\{C_{0},C_{1},C_{2}\}\), in which the majority class \(C_{0}\) is assigned as the default. Feature vector \(X:=(X_{1},X_{2},X_{3})\), where \(X_{1}\), \(X_{2}\) and \(X_{3}\) denote height, weight, and age, respectively. For example, client [PERSON], whose feature vector \(X=(X_{1},X_{2},X_{3})=(150,64,32)\), tries to use the service to inference his health status. Decision tree \(\mathcal{T}\) has \(m=3\) nodes with threshold \((t_{1},t_{2},t_{3})=(170,60,25)\). In this case, the comparison result vector can be expressed as \(B=(1,b_{1},b_{2},b_{3})\).__From Figure 1, it can be easily seen that [PERSON]'s data should be classified to leaf node \(L_{2}\) by \(\mathsf{Path}_{2}\). In the following, we show how to perform classification inference using client [PERSON]'s data and the model holder's decision tree model while keeping them encrypted. According to Equations (2) and (19), we have_

\[ \begin{split}\mathsf{pc}_{1}&=\langle P_{1},B\rangle =\langle[1,-1,\ \ 0,\ \ 0],[1,b_{1},b_{2},b_{3}]\rangle,\\ \mathsf{pc}_{2}&=\langle P_{2},B\rangle=\langle[2,\ 1,-1,-1 ],[1,b_{1},b_{2},b_{3}]\rangle,\\ \mathsf{pc}_{3}&=\langle P_{3},B\rangle=\langle[1, \ 1,-1,\ \ 1],[1,b_{1},b_{2},b_{3}]\rangle,\\ \mathsf{pc}_{4}&=\langle P_{4},B\rangle=\langle[0, \ 1,\ \ 1,\ \ 0],[1,b_{1},b_{2},b_{3}]\rangle.\end{split}  \tag{30}\]

_Therefore,_

\[\mathbf{P}= \begin{bmatrix}P_{1}\\ P_{2}\\ P_{3}\\ P_{4}\end{bmatrix} = \begin{bmatrix}1&-1&0&0\\ 2&1&-1&-1\\ 1&1&-1&1\\ 0&1&1&0\end{bmatrix} . \tag{31}\]

**LNP process:**_Pruning the leaf nodes with class \(C_{0}\), i.e., \(L_{1}\) and \(L_{3}\), while multiplying \(P_{k}\) by a random non-zero numbers \(r_{k},r_{k}^{\prime}\in\mathbb{Z}_{p}^{*}(k=2,4)\), we obtain the path matrix_

\[\mathbf{P^{\prime}}= \begin{bmatrix}r_{2}P_{2}\\ r_{4}P_{4}\end{bmatrix} = \begin{bmatrix}P_{1}^{\prime}\\ P_{2}^{\prime}\end{bmatrix} = \begin{bmatrix}2r_{2}&r_{2}&-r_{2}&-r_{2}\\ 0&r_{4}&r_{4}&0\end{bmatrix}