## 3 PPDT Classification Model
### Proposed Protocol
Server calculates \(d\) via one-round communication with the Client refer to Equation (10)
```
18 for\(j=1\) to \(S\)do
19 computes \([\![d_{j}]\!]\leftarrow([\![t_{j}]\!]_{1}\odot[\![X_{\lambda}]\!]_{1})\otimes([\! [t_ {j}]\!]_{2}\odot[\![X_{\lambda}]\! ]_{2}\oplus\mathsf{poly}_{1\to 3})\oplus \widetilde{\mathsf{poly}}(\mathbf{1})\). 20 selects \(\gamma_{j}\in\mathcal{Z}_{p}\), computes \([\![d^{\prime}_{j}]\!]\leftarrow[\![d_{j}]\! ]\oplus\gamma_{j}\), and sends \([\![d^{\prime}_{j}]\! ]\) to Client. 21 endfor
22 return\([\![d^{\prime}]\!]=\{[\![d^{\prime}_{j}]\! ]\}\), and sends \([\![d^{\prime}]\! ]\) to Client. 23 Client decrypts \(d^{\prime}\leftarrow\mathsf{Dec}([\![d^{\prime}]\! ],sk)\) and sends it to Server. 34 Server computes the comparison result vector \(B\) (refer to Equation (13))
35 for\(j=1\) to \(m\)do
36 for\(i=0\) to \(\mu-1\)do
37 let\(b_{j}=0\)
38 if\(\exists\)\(i\)-th coefficient in \(d_{j}=0\)then
39\(b_{j}\gets b_{j}+1\)
40 endif
410 endfor
42
43 endfor
44 endfor
45 return\(B=[1,b_{1},\ldots,b_{m}]\)Server computes encrypted path and classification result matrices (refer to Equations (14) and (29))
46 for\(s=1\) to \(S\)do
47\([\![\tilde{P}_{s}]\!]\leftarrow[\![P^{\prime}_{s}]\! ]_{mat}\otimes\mathsf{poly }_{t}(B)\), \([\![\tilde{V}_{s}]\!]\leftarrow[\![V_{s}]\!]_{mat}\otimes\mathsf{poly}_{t}(B)\). 48 endfor
49 return\(([\![\tilde{P}_{s}]\!],[\![\tilde{V}_{s}]\! ])\) and sends to Client. 50 Client decrypts and obtains the classification result (refer to Equations (19), (20) and (25))
51 The default class is \(C_{out}=\emptyset\)
52 for\(s=1\) to \(S\)do
53\(\tilde{P}_{s}\leftarrow\mathsf{Dec}([\![P_{s}]\! ],sk)\)
54 for\(k=1\) to \(m^{\prime}\)do
55 if\(\exists((k-1)(m+1)\)-th coefficients in \(P_{s}=0)\)then
56 computes \(\tilde{V}_{s}\leftarrow\mathsf{Dec}([\![\tilde{V}_{s}]\!],sk)\). 57\(C_{out}\leftarrow\) the coefficient of \(x^{(k-1)(m+1)}\)
58 endif
59 endfor
600 endfor
611 return\(C_{out}\)
```
**Algorithm 1**_Cont._

### Leaf Node Pruning (LNP)

In this subsection, we describe how to reduce the number of path costs to be calculated. Let the number of leaf nodes of decision tree \(\mathcal{T}\) be \(m+1\) and the number of classes to be classified be \(K=|\mathcal{C}|\). In this case, we do not calculate the path cost for one class (e.g., \(C_{0}\)) but only the path cost for the other \(K-1\) items. We compute the path cost corresponding to \(K-1\) classes, and if any of them is \(0\), the output is the class corresponding to the path. If none of them is \(0\), the output is class \(C_{0}\) corresponding to the uncalculated path. The detailed procedure is illustrated in Algorithm 2. ```
1:\(X=(X_{1},\dots,X_{N})\): \(X_{i}\) denotes the \(i\)-th feature vector of data \(X\) with \(N\) features, and \(\mathcal{T}=(t_{1},\dots,t_{m})\): \(t_{j}\) denotes the \(j\)-th threshold of decision tree \(\mathcal{T}\) with \(m\) nodes. \(n\): degree of polynomial, \(S\): number of path matrices, \(\mu\): maximum bit length of \(X_{i}\) and \(t_{j}\) \(K=|\mathcal{C}|\): number of classes \(\mathcal{C}=\{C_{0},C_{1},\dots,C_{K-1}\}\)
2:Classification result \(C_{out}\)
3: Given path matrix \(P\) and classification result matrix \(V\) for \(\mathcal{T}\) with \(m+1\) leaf nodes. Model holder prunes leaf nodes that result to the default class \(\Rightarrow\) this process (Lines 2-9 fellow) being inserted between Line 12 and Line 13 of Algorithm 1
4:for\(i=1\) to \(m+1\)do
5: checks classification value score on leaf node \(L_{i}\) of \(\mathcal{T}\),
6:if\((\text{score}(L_{i})=C_{0})\)then
7: deletes \(P_{i}\) and \(V_{i}\) from \(P\) and \(V\), respectively.