## 3 PPDT Classification Model
### Proposed Protocol
\begin{split}\llbracket\tilde{\mathbf{P}}_{\tilde{\mathbf{S}}}\rrbracket& =\llbracket\mathbf{P}_{s}^{\prime}\rrbracket_{mat}\otimes\mathsf{poly}_{t }(B),\\ \llbracket\tilde{\mathbf{V}}_{\tilde{\mathbf{s}}}\rrbracket& =\llbracket\mathbf{V}_{\tilde{\mathbf{s}}}\rrbracket_{mat}\otimes\mathsf{poly}_{t }(B)\end{split}  \tag{29}\]  
for \(s=1,\ldots,S\) and sends \((\llbracket\tilde{\mathbf{P}}_{\tilde{\mathbf{S}}}\rrbracket,\llbracket\tilde{\mathbf{V}}_ {\tilde{\mathbf{S}}}\rrbracket)\) to the client. **Step 8 (client):**: The client obtains the number of path matrix \(S=\lceil(m+1)/m^{\prime}\rceil\) using Equation (21), where \(m^{\prime}=\lfloor n/(m+1)\rfloor\). Then, for \(s=1,\ldots,S\), it decrypts \(\llbracket\mathbf{P}_{s}\rrbracket\) to obtain a polynomial with randomized non-zero coefficients for the path matrix \(\tilde{\mathbf{P}}_{s}\), in which coefficients of \(x^{(k-1)(m+1)}\) are \(k\)-th path cost \(\mathsf{pc}_{k}\cdot r_{k}\) according to Equations (19) and (20). Since \(\mathsf{pc}_{k}\cdot r_{k}=0\iff\mathsf{pc}_{k}=0\), then it is verified whether any \((k-1)(m+1)\)-th term for \(k=1,\ldots,m^{\prime}\) is \(0\), which implies the corresponding path cost \(\mathsf{pc}_{k}=0\). If so, the corresponding leaf of \(\mathcal{T}\) is the classification result according to Equation (25), and the client decrypts \(\llbracket\tilde{\mathbf{V}}_{\tilde{\mathbf{s}}}\rrbracket\) and obtains \(C_{out}\) from the coefficient of \(x^{(k-1)(m+1)}\). ```
0:\(X=(X_{1},\ldots,X_{N})\): \(X_{i}\) denotes the \(i\)-th feature vector of data \(X\) with \(N\) features, and \(\mathcal{T}=(t_{1},\ldots,t_{m})\): \(t_{j}\) denotes the \(j\)-th threshold of decision tree \(\mathcal{T}\) with \(m\) decision nodes. \(n\): degree of polynomial, \(S\): number of path matrices, \(\mu\): maximum bit length of \(X_{i}\) and \(t_{j}\). 0: Classification result \(C_{out}\)
1: Client generates a secret-public key pair \((sk,pk)\) and sends \(pk\) to the model holder and server. Client encrypts each feature vector of data \(X\) (refer to Equation (22))
2:for\(i=1\) to \(N\)do
3:\(\llbracket X_{i}\rrbracket_{1}\leftarrow\mathsf{Enc}(pk,\mathsf{poly}_{1}(x_{ i}^{\mathsf{b}}))\), \(\llbracket X_{i}\rrbracket_{2}\leftarrow\mathsf{Enc}(pk,\mathsf{poly}_{2}(x_{ i}^{\mathsf{b}}))\). 4:endfor
5:return\(\llbracket X\rrbracket=\{(\llbracket X_{i}\rrbracket_{1},\llbracket X_{i} \rrbracket_{2})\}_{1}^{N}\), sends \(\llbracket X\rrbracket\) to Model holder. Model holder encrypts threshold \(t_{j}\) (refer to Equation (23))
6:for\(j=1\) to \(m\)do
7:\(\llbracket t_{j}\rrbracket_{1}\leftarrow\mathsf{Enc}(pk,\mathsf{poly}_{1}(t_{ j}^{\mathsf{b}}))\), \(\llbracket t_{j}\rrbracket_{2}\leftarrow\mathsf{Enc}(pk,\mathsf{poly}_{2}(t_{ j}^{\mathsf{b}}))\). 8:endfor
9:return\(\llbracket t\rrbracket=\{\llbracket t_{j}\rrbracket_{1},\llbracket t_{j} \rrbracket_{2}\}\) _Model holder generates path matrix \(P\) and classification result matrix \(V\) (refer to Equations (24) and (25))_
10:for\(k=1\) to \(m+1\)do
11: generate \(P_{k}\), select \(r_{k},r_{k}^{\prime}\in\mathbb{Z}_{p}^{*}\), compute \(P_{k}^{\prime}\gets r_{k}\cdot P_{k}\), \(V_{k}:=r_{k}^{\prime}\cdot P_{k}+[\mathsf{score}(L_{k}),0,\ldots,0]\). 12:endfor
13:return\(P,V\) is divided into \(S\) matrices \(P_{1},\ldots,P_{S}\) and \(V_{1},\ldots,V_{S}\), as shown in Equation (21). The Model Holder encrypts path matrices and classification result matrices (refer to Equations (16) and (26))
14:for\(s=1\) to \(S\)do
15:\(\llbracket P_{s}\rrbracket_{mat}\leftarrow\mathsf{Enc}(pk,\mathsf{poly}_{mat}(P _{s}))\), \(\llbracket V_{s}\rrbracket_{mat}\leftarrow\mathsf{Enc}(pk,\mathsf{poly}_{mat}(V _{s}))\). 16:endfor
17:return\(\llbracket P\rrbracket=\{\llbracket P_{s}\rrbracket\}\), \(\llbracket V\rrbracket=\{\llbracket V_{s}\rrbracket\}\), and sends \(\llbracket X\rrbracket\), \(\llbracket t\rrbracket\), \(\llbracket P\rrbracket\), \(\llbracket V\rrbracket\) to Cloud Server.