## 3 PPDT Classification Model
### Proposed Protocol
\begin{split}&\mathsf{Enc}\big{(}\mathsf{poly}_{mat}(P^{ \prime})\big{)}\otimes\mathsf{poly}_{1}(B)\\ &=\mathsf{Enc}\Big{(}(2r_{2}x^{0}+r_{2}x-r_{2}x^{2}-r_{2}x^{3}+r _{4}x^{5}+r_{4}x^{6})(1-x^{n-3}-x^{n-2})\Big{)}\\ &=\mathsf{Enc}\Big{(}0\cdot x^{0}+r_{4}x^{4}+\mathsf{otherterms} \Big{)}\\ &=\mathsf{Enc}(F_{\mathsf{path}}(x)),\\ &\mathsf{Enc}(\mathsf{poly}_{mat}(V^{\prime}))\otimes\mathsf{ poly}_{7}(B)\\ &=\mathsf{Enc}\Big{(}\big{(}(2r_{2}^{2}+C_{1})+r_{2}^{\prime}x-r_ {2}^{\prime}x^{2}-r_{2}^{\prime}x^{3}+C_{2}x^{4}+r_{4}^{\prime}x^{5}+r_{4}^{ \prime}x^{6}\big{)}(1-x^{n-3}-x^{n-2})\Big{)}\\ &=\mathsf{Enc}\big{(}C_{1}x^{0}+(r_{4}+C_{2})x^{4}+\mathsf{otherterms }\Big{)}\\ &=\mathsf{Enc}(F_{\mathsf{class}}(x)).\end{split} \] (38)
* _[PERSON] decrypts and obtains the polynomial corresponding to a_ \((k,\ell)\)_-dimension path matrix_ \(F_{\mathsf{path}}(x)\) _and then checks its coefficients of_ \(x^{(i-1)\ell}(i=1,\ldots,k)\) _terms. In this example,_ \(k=2\)_,_ \(\ell=4\)_, so whether the coefficient of_ \(x^{0}\) _or_ \(x^{4}\) _is zero is checked._ _In fact,_ \[F_{\mathsf{path}}(x)=\big{\langle}P^{\prime}_{1},B\big{\rangle}+\big{\langle}P^ {\prime}_{2},B\big{\rangle}\cdot x^{4}+\mathsf{otherterms},\]\[F_{\text{class}}(x)=(\langle P_{1}^{\prime},B\rangle+C_{1})+(\langle P_{2}^{\prime},B\rangle+C_{2})\cdot x^{4}+\text{otherterms},\]

_and since \(\langle P_{1}^{\prime},B\rangle=r_{2}\langle P_{2},B\rangle,\langle P_{2}^{ \prime},B\rangle=r_{4}\langle P_{4},B\rangle\),_

\[\text{the coefficient of $x^{0}$ is zero}\iff\texttt{pc}_{2}=\langle P_{2},B \rangle=0\text{, and}\] \[\text{the coefficient of $x^{4}$ is zero}\iff\texttt{pc}_{4}=\langle P_{4},B \rangle=0\text{,}\]

_which links to leaf nodes \(L_{2}\) and \(L_{4}\), respectively. As shown in Equation (38), since the coefficient of \(x^{0}\) in the first polynomial is zero, if and only if \(\texttt{pc}_{2}=0\), which means \(X\) is classified to leaf node \(L_{2}\). Then, the coefficient of \(x^{0}\) in the second polynomial is the classification result; that is, \(C_{out}=C_{1}\)._

### Complexity

The client encrypts each element of the feature vectors with two different packing methods for comparison protocols and sends them to the model holder. The model holder encrypts the threshold for each decision node for \(2m\) times. In addition, the path and classification result matrices are encrypted \(S=\lceil(m+1)/m^{\prime}\rceil\)\((m^{\prime}=\lfloor n/(m+1)\rfloor)\) times, respectively. The model holder sends the pairs of threshold and feature vector elements and the pairs of path and classification result matrices to the server. Next, the server and client cooperate to perform the comparison protocol for \(m\) times. In this case, the client performs decryption \(m\) times. The server performs homomorphic multiplication of the path and classification result matrices \(2S\) times and sends the client results. The client obtains the classification result by decrypting the received path and classification result matrices \(2S\) times. ### Security Analysis

For a homomorphic encryption scheme, indistinguishability under chosen-plaintext attack (IND-CPA) is the basic security requirement. The SHE scheme used in the experiments in Section 4 is proven IND-CPA secure under the Ring-LWE assumption. In our proposed approach, as the input of the homomorphic computation consists of ciphertexts, the corresponding IND-CPA-secure SHE schemes will not be weakened. Consider the entities involved in the protocol one by one (see Figure 3) and assume that they are all honest but curious and that they do not collude with one another. * Client. The client can decrypt the ciphertext sent from the cloud server in Steps 5 and 7 using the secret key and obtain \(d^{\prime}\) related to the comparison result and the decision tree structure. However, in Step 4, the noise from the cloud server is added for randomization. Therefore, the client receives a polynomial with completely random coefficients in \(d^{\prime}\).