## 3 PPDT Classification Model
### Proposed Protocol
The experiments were conducted on a standard PC with the Core i7-7700K (4.20 GHz) processor using a single thread mode. We used scikit-learn, a standard open-source machine learning library in Python 3.7.2, to train the decision trees. In both the BFV method and the comparison protocol by [PERSON] et al. [15], an input value must be represented as an integer \(a\in\mathbb{Z}_{n}\). At every an appropriate number of times when the multiplication is performed, the fractional part of a value must be truncated, and it should be normalized within the range of \([0,2^{13})\). In the performance evaluations, the computational time was measured by averaging over 10 trials for the following 8 data sets from the UCI machine learning repository [20]: _Heart Disease_ (HD), _Spambase_ (SP) (which were used for the benchmark in [15]), _Breast Cancer Wisconsin_ (BC), _Nursery_ (NS), _Credit-Screening_ (CS), _Sbuttle_ (ST), _EGG_ _EYE State_ (EGG), and _Bank Marketing_ (BK). The data set information and the parameters of the decision tree used are listed in Table 1.

### Performance Comparisons

#### 4.2.1 Path Cost Calculation

We compared the computational time to obtain the path costs under the three-party protocol when the proposed matrix multiplication in Section 3.2 and the [PERSON] et al. 's homomorphic inner product calculation [19] were used. Table 2 shows the computational time for the path costs. We also show the computation time in parentheses when LNP was introduced into the proposed path cost calculation. In calculating path costs by using the naive inner product, \(m+1\) homomorphic multiplications are required. Therefore, as the number of nodes in a tree \(m\) increases, the computation time for path costs also increases. On the other hand, when calculating the path cost by matrix multiplication, for the decision tree of \(m\leq 35\) of Table 2, the path cost computation time was the same. The reason is that for parameter \(n\), the entire path cost can be calculated with one matrix in the case of \(m\leq 35\). Therefore, for datasets other than BK, more than one path cost can be computed with one matrix. The computation time for the path cost was reduced by more than 90% compared to the inner product case. However, in the case of BK, only \(\lfloor n/(m+1)\rfloor=\lfloor 2048/1028\rfloor=1\) path cost could be calculated with a single matrix multiplication. Hence, there is no difference in the computation time for matrix multiplication and inner product when \(\lfloor n/(m+1)\rfloor=1\). With LNP being applied, the path cost computation time remained unchanged for decision trees (e.g., BC, ST, CS, HD) with \(m\leq 35\), as all path costs could be computed within a single matrix. However, for larger trees (e.g., NS, SP, EGG, BK), LNP significantly \begin{table}
\begin{tabular}{c c c c c} \hline \multirow{2}{*}{**Dataset Accuracy**} & \multicolumn{3}{c}{**Path Cost (ms)**} & \multicolumn{2}{c}{**Total Time (ms)**} \\ \cline{2-5}  & \multicolumn{2}{c}{**Matrix (+LNP)**} & **Inner Product** & **Matrix (+LNP)** & **Inner Product** \\ \hline BC & 96.4\% & 0.25 (0.25) & 3.04 & 44.19 (43.92) & 63.58 \\ ST & 99.8\% & 0.25 (0.25) & 6.74 & 66.85 (66.83) & 117.51 \\ CS & 90.8\% & 0.25 (0.25) & 7.47 & 77.57 (76.12) & 134.64 \\ HD & 61.1\% & 0.25 (0.25) & 9.73 & 98.82 (98.11) & 174.34 \\ NS & 98.6\% & 0.50 (0.37) & 11.72 & 130.87 (129.07) & 235.04 \\ SP & 90.4\% & 1.72 (0.86) & 13.13 & 321.89 (302.72) & 490.04 \\ EGG & 69.8\% & 88.57 (46.20) & 179.31 & 3425.44 (2516.35) & 4442.00 \\ BK & 88.6\% & 247.63 (131.14) & 252.87 & 6485.30 (4394.58) & 6455.17 \\ \hline \end{tabular}
\end{table} 
Table 2: Computation time for path cost calculation in two methods: matrix multiplication of Section 3.2 and the homomorphic inner product calculation of [PERSON] et al. [19] that we proposed in [24]. The computation time for the matrix multiplication with the addition of LNP is provided in parentheses. The computation time for LNP was measured as an average of 10 trials for each dataset class.