## 3 PPDT Classification Model
### Proposed Protocol
\begin{table}
\begin{tabular}{c c c c c} \hline \multirow{2}{*}{**Dataset**} & \multicolumn{3}{c}{**Dataset**} & **Model** \\ \cline{2-5}  & **\# Data** & **\# Attributes \(N\)** & **\# Classes \(C\)** & **\# Nodes \(m\)** \\ \hline BC & 569 & 30 & 2 & 8 \\ ST & 43,500 & 9 & 7 & 24 \\ CS & 653 & 15 & 2 & 26 \\ HD & 720 & 13 & 5 & 35 \\ NS & 12,960 & 8 & 5 & 49 \\ SP & 4601 & 57 & 2 & 110 \\ EGG & 14,980 & 14 & 2 & 724 \\ BK & 45,211 & 16 & 2 & 1027 \\ \hline \end{tabular}
\end{table} 
Table 1: Data set information and the size of trained decision tree. reduced the computation time--by 26% for NS, 50% for SP, 48% for EGG, and 47% for BK. The effect correlated with the number of classes: datasets with fewer classes (SP, EGG, BK each with 2) benefited more than did NS (5 classes), as fewer classes enhance pruning efficiency. See Table 1 and Figure 5 for dataset-specific details. #### 4.2.2 Protocol Efficiency

In this experiment, we used the XCMP of [PERSON] et al. [15] for comparisons. We implemented two protocols and measured their computation times. 1. To evaluate the efficiency of different homomorphic encryption approaches, we also integrated the XCMP scheme into the comparison component of the three-party protocol described in Section 3.3. The path cost computation was performed following the procedure outlined in Steps 6-8 of Section 3.3. 2. A naive two-party protocol using XCMP by [PERSON] et al. computed the result of two-party comparison (see Appendix B). Then, we computed the path cost under encrypt conditions by additive homomorphism. Table 3 provides the measurement results. In the naive two-party protocol, the path cost calculation is performed only by homomorphic addition, so \(O(m^{2})\) addition is required. Therefore, the path cost calculation accounted more than 80% of the total time. In contrast, when applied to the proposed protocol, the path cost calculation time was reduced to 0.5% of the total time. As a result, the time reduction is achieved by applying XCMP to the proposed protocol on the experiments' dataset. In particular, the reduction rate was higher for the EGG and BK datasets with a large number of decision nodes. Figure 5: Comparison of computation times with and without LNP across all datasets. For each dataset, the bar chart shows the path cost and total computation times, highlighting the reduction achieved by applying LNP. Datasets with fewer classes (e.g., SP, EGG, BK) showed more significant improvements due to more efficient pruning. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{3}{c}{**Path Cost (ms)**} & \multicolumn{2}{c}{**Total Time (ms)**} \\ \cline{2-5}  & **Three-Party** & **Two-Party** & **Three-Party** & **Two-Party** \\ \hline BC & 2.17 & 1577.51 & 302.19 & 1958.13 \\ ST & 2.17 & 11,745.70 & 647.51 & 12,724.20 \\ CS & 2.18 & 14,905.70 & 736.95 & 16,037.90 \\ HD & 2.18 & 27,041.40 & 961.19 & 28,298.90 \\ NS & 2.18 & 51,772.50 & 1321.47 & 54,268.10 \\ SP & 2.19 & 255,659.00 & 2996.92 & 263,008.00 \\ EGG & 74.01 & 10,947,300.00 & 19,432.90 & 11,013,300.00 \\ BK & 166.74 & 22,027,200.00 & 28,821.60 & 22,130,500.00 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Computation time with XCMP [15] in the following scenarios: three-party with matrix multiplication and LNP; two-party with homomorphic addition of XCMP results for computing the path cost. ### Time Complexity

To verify the computational complexity in Section 3.5, we measured the computation time of the proposed protocol for a decision tree constructed with the number of \(m\) decision nodes fixed between \([10,1000]\) using the BK dataset. Figure 6 provides the experimental results that demonstrated that the computation time was linear with the number of decision nodes. There were several points at which there was a rapid increase in the number of times the model holder's encryption was performed, the number of times the client was compounded, and the number of times the server's path cost was computed.