## 3 PPDT Classification Model
### Proposed Protocol
\(N\)

\(X=[X_{0},\ldots,X_{N-1}]\)

Feature vector

\(D_{i}\)

Decision node

\(L_{j}\)

Leaf node

\(\lambda_{i}\)

Index of feature vectors to be compared by decision node \(D_{i}\)

\(t_{i}\)

Threshold of decision node \(D_{i}\)

\(c_{j}\)

Class to be output by leaf node \(L_{j}\)

\(m\)

Number of decision nodes in the decision tree

\(m+1\)

Number of leaf nodes in the decision tree

Parameters being used in the ring-LWE-based encryption schemes:

\(n\)

An integer of power of \(2\) that denotes the degree of polynomial \(x^{n}+1\). Define a polynomial ring \(\mathcal{Z}:=\mathbb{Z}[x]/(x^{n}+1)\),

An integer composed of \(q=q_{1}\times\cdots\times q_{k}\) (\(q_{i}\) is a prime number). Define a polynomial ring representing a ciphertext space \(\mathcal{Z}_{q}:=\mathbb{Z}_{q}[x]/\left(x^{n}+1\right)\),

Define a plaintext space \(\mathcal{Z}_{p}:=\mathbb{Z}_{p}[x]/\left(x^{n}+1\right)\), where \(p\) and \(q\) are mutually prime natural numbers with the relation \(p<q\),

Standard deviation of the discrete Gaussian distribution defining the secret key space \(\mathcal{Z}_{(0,q^{2})}\). The elements of \(\mathcal{Z}_{(0,q^{2})}\) are polynomials on the ring \(\mathcal{Z}\). Each coefficient is independently sampled from the discrete Gaussian distribution of the variance \(\sigma^{2}\). ## Appendix A Ring-LWE-Based Homomorphic Encryption

This study used the ring-LWE-based public key homomorphic encryption library called the Simple Encrypted Arithmetic Library (SEAL) v.3.3 [22] to implement our pro tocols. SEAL implements the somewhat homomorphic encryption scheme proposed by [PERSON] et al. [21]. Due to the additive and multiplicative homomorphism, packing plaintexts provides an efficient homomorphic inner product and matrix multiplication calculations. See [21,22] for details on the encryption scheme. The somewhat homomorphic encryption scheme consists of the following four basic algorithms:

* \(\mathsf{ParamGen}(\mathbb{1}^{\lambda})\): input security parameter \(1^{\lambda}\) and output system parameter \(pp=(n,q,p,\sigma)\). * \(\mathsf{KeyGen}\): input system parameter \(pp\) and output public key \(pk\) and secret key \(sk\). * \(\mathsf{Enc}(pk,\cdot)\): input plaintext \(m\) and output ciphertext \(c\). * \(\mathsf{Dec}(sk,\cdot)\): input ciphertext \(c\) and output plaintext \(m\). Homomorphic addition and multiplication algorithms are defined by \(\mathsf{Add}\) and \(\mathsf{Mul}\), and the corresponding decryption algorithms are represented by \(\mathsf{DecA}\) and \(\mathsf{DecM}\), respectively. Let \(c=\mathsf{Enc}(pk,m)\) and \(c^{\prime}=\mathsf{Enc}(pk,m^{\prime})\) denote the ciphertexts of the two plaintexts \(m\) and \(m^{\prime}\), respectively. Then, the sum and product of \(m\) and \(m^{\prime}\) can be calculated as follows. \[\mathsf{Add}(c,c^{\prime}) =c_{add} \in\mathcal{Z}_{q}, \tag{1}\] \[\mathsf{DecA}(sk,c_{add}) =m+m^{\prime} \in\mathcal{Z}_{p};\] \[\mathsf{Mul}(c,c^{\prime}) =c_{mul} \in\mathcal{Z}_{q},\] \[\mathsf{DecM}(sk,c_{mul}) =nm^{\prime} \in\mathcal{Z}_{p}.\]

Hereafter, we write \(\mathsf{Enc}(pk,\cdot):=\llbracket\cdot\rrbracket,\mathsf{Add}(c,c^{\prime}) :=c\oplus c^{\prime}\), and \(\mathsf{Mul}(c,c^{\prime})=c\otimes c^{\prime}\). The difference between \(c\) and \(c^{\prime}\) can be obtained using homomorphic addition, and we define \(\mathsf{Sub}(c,c^{\prime}):=c\ominus c=\mathsf{Add}(c,-c^{\prime})\). ## Appendix B XCMP [15]

Assume that client and server have two \(\ell\)-bit integer values such as \(a\) and \(b\), respectively. According to the algorithm in Figure 11, the server computes \(\llbracket C\rrbracket\) to obtain the comparison result in encrypted form. In this scheme, the comparison result is a constant term in the polynomial \(C\), as shown in \(C=\mathds{1}\{a>b\}+\text{other terms of degree}\). It is possible to perform scalar multiples, additions, and subtractions on the resulting ciphertext \(\llbracket C\rrbracket\).