
\section*{Acknowledgment}
We thank the anonymous reviewers for insightful comments and suggestions. 
Bai and Russello would like to acknowledge the MBIE-funded programme STRATUS (UOWX1503) for its support and inspiration for this research.
This research is supported by the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.
\section{Security Proofs}

\subsection{Proof of Theorem~\ref{theorem:1}}\label{appendix::1::a}
\textbf{Security against corrupted $\mathcal{S}$}. We construct a simulator $\textsf{Sim}_{\rm s}$ as follows. During setup, $\textsf{Sim}_{\rm s}$ runs $\mathcal{S}$'s setup protocol except with the following exception: $\textsf{Sim}_{\rm s}$ randomly samples $\mathsf{C}[i] \xleftarrow{\$} \{0,1\}^{ \ell_{\mathsf{v}}}$ for all $i \in [0, m)$.
As for selection protocol, $\textsf{Sim}_{\rm s}$ is provided with input $\boolshare{\mathsf{idx}}_{\rm s}$ and output $e$ (\ie, a PRF output share). It runs $\mathcal{S}$'s selection protocol except with the following exceptions: $\textsf{Sim}_{\rm s}$ runs simulator for $\mathcal{F}_{\textsf{pre}}$ to simulate the view of weight-1 bit vector generation.
Also, $\textsf{Sim}_{\rm s}$ runs simulator for $\mathcal{F}_{\textsf{pre}}$ to simulate the view of shared PRF protocol. 
Finally, $\textsf{Sim}_{\rm s}$ outputs $\mathcal{S}$'s view.
We prove the simulated view is indistinguishable from real-world execution via a sequence of hybrid games. 

\begin{itemize}
    \item $\textsf{H}_{\rm 0}$: Outputs $\mathcal{S}$'s view in the real-world protocol. 

    \item $\textsf{H}_{\rm 1}$: Same as $\textsf{H}_{\rm 0}$ except $\textsf{Sim}_{\rm s}$ randomly samples $\mathsf{C}[i] \xleftarrow{\$} \{0,1\}^{ \ell_{\mathsf{v}}}$ for all $i \in [0, m)$.
    By the security of ${F}$, $\textsf{H}_{\rm 1}$ is computationally indistinguishable from $\textsf{H}_{\rm 0}$.

    \item $\textsf{H}_2$: Same as $\textsf{H}_{\rm 1}$ except that $\textsf{Sim}_{\rm s}$ runs simulator for $\mathcal{F}_{\textsf{pre}}$ to generate $\mathcal{S}$'s view in the shared weight-1 bit vector protocol.
    In particular, the simulator for $\mathcal{F}_{\textsf{pre}}$ is provided with input $n$ and output $\boolshare{\mathsf{S}}_{\rm s}, \boolshare{\mathsf{idx}}_{\rm s}$, and in the end it generates a simulated view.  
    By the security of shared weight-1 bit vector protocol, $\textsf{H}_2$ and $\textsf{H}_{\rm 1}$ are indistinguishable.


    \item $\textsf{H}_3$: Same as $\textsf{H}_2$ except that $\textsf{Sim}_{\rm s}$ runs simulator to generate $\mathcal{S}$'s view in shared PRF protocol.
    Note that for all other view from running secret-shared computation, $\textsf{Sim}_{\rm s}$ can simulate it by randomly sampling shares, which is identically distributed in both worlds.
    However, $\textsf{Sim}_{\rm s}$ must ensure all prior simulated view be consistent with the final output, which is $\boolshare{\mathsf{M}[\mathsf{idx}][j]}_{\rm s}$.
    As such, $\textsf{Sim}_{\rm s}$ computes $f_j^{*} \leftarrow \boolshare{\mathsf{M}[\mathsf{idx}][j]} \oplus  \boolshare{\mathsf{C}[\mathsf{idx}][j]}^{*}$ for $j \in [0,  B)$, it then invokes the simulator for $\mathcal{F}_{\textsf{pre}}$ over $(\boolshare{\{\mathsf{idx}||j}^{*}_{\rm s}\}_{j \in [0,  B-1)}, \{f_j^{*}\}_{j \in [0,  B)})$ to simulate $\mathcal{S}$'s view in shared PRF protocol. 
    Since we are working in a hybrid model, such simulator must exist\footnote{A simulator who can simulate secret-shared XOR and AND computation will suffice to simulate any secure computation task.}. 
    $\textsf{H}_3$ and $\textsf{H}_2$ are indistinguishable by the security of shared PRF protocol.
\end{itemize}


\noindent\textbf{Security against corrupted $\mathcal{R}$}. 
Operations of $\mathcal{S}$ and $\mathcal{R}$ are almost symmetric during the protocol, so our strategy for proving a corrupted $\mathcal{R}$ is almost same as the one we construct against corrupted $\mathcal{S}$.
The proof for corrupted $\mathcal{R}$ is thus omitted.



\subsection{Proof of Theorem~\ref{theorem:sos-he}}\label{appendix::2::a}
    \textbf{Security against corrupted $\mathcal{S}$}. 
    We construct a simulator $\textsf{Sim}$ for corrupted $\mathcal{S}$ as follows. 
    During setup, $\textsf{Sim}$ runs $\mathcal{S}$'s setup protocol except with the following exception: 
    $\textsf{Sim}$ randomly samples $\mathsf{C}[i] \xleftarrow{\$} \mathbb{Z}_{N^2}$ for all $i \in [0, m)$. 
    Given semantic security of Paillier encryption, the simulated ciphertexts are indistinguishable from the ones in real-world protocol.
    
    In the selection protocol, for the view from generating weight-1 bit vector, $\textsf{Sim}$ calls the simulator for $\mathcal{F}_{\rm pre}$ to simulate corresponding view over randomly sampled $\boolshare{\mathsf{S}}_{\rm s}$ and $\boolshare{\mathsf{rdx}}_{\rm s}$\footnote{Note that a secret share can be regards as a random number over its sharing domain. Then, the sampled random numbers as the simulated shares are indistinguishable from the real-world protocol.}; the simulation is perfect in hybrid mode. 
    The view of B2A conversion can also be simulated using existing simulator for secure computation, such a simulator always exists given the security of B2A protocol. 
    Next, $\textsf{Sim}$ picks a random $\delta \xleftarrow{\$} \mathbb{Z}_m$, the simulation is also indistinguishable: in the real-world protocol, $\mathsf{idx}$ and $\mathsf{rdx}$ are all random, then $\delta = \mathsf{rdx} -\mathsf{idx}~(\mathsf{mod}~m)$ is also a random number in $\mathbb{Z}_m$.
    The simulator $\textsf{Sim}$ performs simulation for the next B2A conversion protocol, similarly as it previously does for $\mathsf{idx}$ and $\mathsf{rdx}$. The simulated view of B2A is indistinguishable from real-world protocol.
    For the view of share conversion from additive sharing to multiplicative sharing, $\textsf{Sim}$ first invokes the simulator for BMT generation in $\mathcal{F}_{\rm sprf}$ over a randomly sampled $a \xleftarrow{\$} \mathbb{Z}_{N^2}$ and the share $\addshare{c} \xleftarrow{\$} \mathbb{Z}_{N^2}$. 
    Next, $\textsf{Sim}$ samples $\gamma, e, f$ and $\addshare{x\cdot \gamma^{-1}}$ randomly from $\mathbb{Z}_{N^2}$. 
    Note that in the real-world protocol, $e \leftarrow \gamma^{-1} - a~(\mathsf{mod}~N^2)$ and $f \leftarrow \addshare{x}_{\rm r} - b~(\mathsf{mod}~N^2)$.
    Given that $a, b, \gamma$ and $\addshare{x}_{\rm r}$ are all random, then $e$ and $f$ are random elements in $\mathbb{Z}_{N^2}$ as well. 
    However, there is a difference since the simulator samples $\gamma$ from $\mathbb{Z}_{N^2}$ rather from $\mathbb{Z}_{N^2}^*$, the simulated $\gamma$ can be accidentally sampled from $\mathbb{Z}_{N^2} \backslash \mathbb{Z}_{N^2}^*$. 
    However, this bad probability can only happens with probability of $\frac{1}{p}+\frac{1}{q}$, which is negligible in $\kappa$.  
    Next, $\textsf{Sim}$ randomly samples $x_{\beta} \xleftarrow{\$} \mathbb{Z}_{N^2}$ rather than $x_{\beta} \xleftarrow{\$} \mathbb{Z}_{N^2}^*$, the probability to distinguish is negligible as we argued before.
    For $\addshare{m}_{\rm s}$, $\textsf{Sim}$ will randomly sample it from $[0, 2^{{ \ell_{\mathsf{v}}}+\lambda+1}]$, this is statically closed to the real-world view for statistical parameter $\lambda$. 
    
   
    \noindent\textbf{Security against corrupted $\mathcal{R}$}.  
    Simulator for a corrupted $\mathcal{R}$ can be constructed using the similar strategy as we constructed for $\mathcal{S}$ since all operations are symmetric between $\mathcal{S}$ and $\mathcal{R}$.
    Therefore, we omit the simulation for corrupted $\mathcal{R}$ in our proof.



\subsection{Proof of Theorem~\ref{theorem:2}}\label{appendix::3::a}
 
\textbf{Simulator for corrupted ${P}_0$}.
The simulator $\textsf{Sim}$ invokes the simulator of SOS setup protocol over $\mathsf{A}_{\mathcal{T}}$. 
Similarly, $\textsf{Sim}$ invokes the simulator of SOS setup protocol over $\mathcal{X}$. 
The simulation is perfect in the hybrid model. 
$\textsf{Sim}$ randomly samples $\boolshare{t}_0, \boolshare{l}_0 \boolshare{r}_0, \boolshare{v}_0$ and $\boolshare{c}_0$ from $\mathbb{Z}_{2^\ell}$. It is straightforward to see that the simulated view is indistinguishable from the real-world execution.   

As for evaluation protocol, the simulator in the beginning does not need to simulate $\boolshare{\mathsf{idx}}$ since it shares 0, which is locally done by the parties.
Then $\textsf{Sim}$ randomly samples $\boolshare{\mathsf{rst}}_0$. The above simulation is indistinguishable from the real-world view. 
Then $\textsf{Sim}$ calls the simulator of SOS selection protocol over $\mathcal{X}$.
In particular, $\textsf{Sim}$ samples $\boolshare{v}_0$ and $\boolshare{\mathcal{X}[v]}$ randomly, and invokes $\mathcal{F}_{\textsf{sos}}^{(\mathcal{X})}$ where $\boolshare{v}_0$ and $\boolshare{\mathcal{X}[v]}$ are the input and the output, respectively.
Afterwards, $\textsf{Sim}$ simulates the view of secure comparison, the view can be simulated as the secure computation is well-studied in existing work~\cite{demmler2015aby}.
Then $\textsf{Sim}$ randomly samples $\boolshare{\mathsf{idx}} \in \mathbb{Z}_{2^{\ell}}$, the simulation is perfect since the share is randomly computed from secure computation.
$\textsf{Sim}$ invokes the simulator for SOS selection protocol over $\mathsf{A}_{\mathcal{T}}$ with $\boolshare{\mathsf{idx}}_{\rm s}$ as the input and a random number $r \xleftarrow{\$} (\mathbb{Z}_{2^{ \ell_{\mathsf{v}}}})^5$ as the output. 
In particular, $r$ is used to simulate $\mathcal{S}$'s share of $\mathsf{A}_{\mathcal{T}}[\mathsf{idx}]$. 
The simulated view is indistinguishable from real-world view due to the security of SOS protocol. 
For all other operations that can be done locally, $\textsf{Sim}$ can simulate trivially (since no view involves in these operations).


\noindent\textbf{Simulator for corrupted ${P}_1$}.
The idea of simulating view for a corrupted ${P}_1$ is almost the same as the simulation for ${P}_0$ because the PDTE protocol is essentially symmetric for the two parties. 
Therefore, we omit the proof for the corrupted  ${P}_1$. 


\section{Correlated randomness generation}\label{appendix::2::c}
\subsection{BMT Generation} 
For a normal BMT  $(\addshare{a}, \addshare{b}, \addshare{c})$, $a$, $b$ and $c$ are all secret-shared among the parties. 
In our setting, we want to generate BMT $(a, b, \addshare{c})$ where ${P}_0$ holds $(a, \addshare{c}_0)$ and ${P}_1$ holds $(b, \addshare{c}_1)$.
In the following, we summarize two ways for generating such special BMTs using either AHE or OT. 


\noindent\textbf{AHE-based approach \cite{demmler2015aby}}. 
BMTs can be generated from AHE, \textit{e.g.}, Paillier encryption.
The parties can explore the additive homomorphic property to share the multiplication result over $\mathbb{Z}_n$.
In Fig.~\ref{protocol:BMT-AHE}, we give a protocol for generating BMTs from Paillier encryption.


\begin{figure
	\framebox{\begin{minipage}{0.95\linewidth}
		{\bf Parameters}: 
			BMT module $n$, computational security parameter $\kappa$; statistical security parameter $\lambda$; Paillier plaintext module $N= p\cdot q$, where $p$ and $q$ are primes.
			
		\begin{enumerate}
		    \item ${P}_0$ generates a pair of Paillier public/private key pair $(\mathsf{pk}, \mathsf{sk}) \leftarrow \textsf{Gen}(1^{\kappa})$ and sends $\mathsf{pk}$ to ${P}_1$.
		    
		    \item ${P}_0$ chooses $a \xleftarrow{\$} \mathbb{Z}_{n}$ and sends $x \leftarrow \textsf{Enc}_{\mathsf{pk}}(a)$ to ${P}_1$. 
		    
		    \item ${P}_1$ chooses $b \xleftarrow{\$} \mathbb{Z}_{n}$ and $\rho \xleftarrow{\$} [0, 2^{\lambda})$, sends $x' \leftarrow x^b \cdot \textsf{Enc}_{\mathsf{pk}}(r + \rho\cdot n)~(\mathsf{mod}~N^2) $ to ${P}_0$.
		    
		    \item ${P}_0$ decrypts to get $\addshare{c}_0 \leftarrow \textsf{Dec}_{\mathsf{sk}}(x')~(\mathsf{mod}~n)$. 
		    
		    \item ${P}_1$ sets $\addshare{c}_1 \leftarrow -r~(\mathsf{mod}~n)$. 
		    
		\end{enumerate}
	\end{minipage}}
	\caption{BMT from AHE~\cite{demmler2015aby}}
	\label{protocol:BMT-AHE}
\end{figure}

\begin{figure
	\framebox{\begin{minipage}{0.95\linewidth}
		{\bf Parameters}: 
			BMT module $n$, $n$'s bit size $\ell$; computational security parameter $\kappa$.
		
	
		\begin{enumerate}
		    \item ${P}_0$ chooses $a \xleftarrow{\$} \mathbb{Z}_{n}$ and decomposes $a$ to its boolean form $(a_{\ell-1}, \cdots, a_1, a_0)$ such that $a = \sum_{i=0}^{\ell-1}2^i\cdot a_i$.
		    
		    \item For $0 \le i < \ell$: 
		    \begin{enumerate}
		        \item ${P}_1$ chooses $r_i \xleftarrow{\$} \mathbb{Z}_n$ and computes two messages $(m_i^0 = r_i, m_i^1 = r_i + 2^i\cdot b~(\mathsf{mod}~n))$;
		    
		        \item ${P}_0$ and ${P}_1$ invoke 1-out-of-2 OT functionality $\mathcal{F}_{\rm OT}$ where ${P}_1$ sends $(m_i^0, m_i^1)$ and ${P}_0$ sends $a_i$. In the end, ${P}_0$ receives $m_i^{a_i}$.
		    \end{enumerate}
		    \item ${P}_0$ sets $\addshare{c}_0 \leftarrow \sum_{i=0}^{\ell-1} m_i^{a_i}~(\mathsf{mod}~n)$, and ${P}_1$ sets  $\addshare{c}_1 \leftarrow \sum_{i=0}^{\ell-1}-r_i~(\mathsf{mod}~n)$. 
		\end{enumerate}
	\end{minipage}}
	\caption{BMT from OT~\cite{demmler2015aby}}
	\label{protocol:BMT-OT}
\end{figure}


\noindent\textbf{OT-based approach \cite{demmler2015aby}}
A BMT $(a, b, \addshare{c})$ can be generated by using OTs as shown in Fig.~\ref{protocol:BMT-OT}. 


\subsection{WBV Generation from FSS}
Boyle~\textit{et~al. }~\cite{gilboa2014distributed,boyle2015function,boyle2016function} formalize a new cryptographic primitive called \emph{Function Secret Sharing}~(FSS), and gave concrete constructions for useful functions.
We begin with formally defining \emph{Function Secret Sharing} for two parties. 



\begin{definition}[Function Secret Sharing]
\label{Def:FSS}
	A two-party FSS scheme ${\rm \Pi_{\rm fss}} = (\textsf{\rm Gen}, \textsf{\rm Eval})$ consists of a pair PPT algorithms as follows:
	\begin{itemize}
		\item $\textsf{\rm Gen} (1^{\kappa}, f)$ is a key generation algorithm, which takes as input a security parameter $1^{\kappa}$ and a function description $f$, outputs a tuple of keys $(k_0^{\rm fss}, k_1^{\rm fss})$, each for one party.
		\item $\textsf{\rm Eval} (k_i^{\rm fss}, x)$ is an evaluation algorithm, which on input a key $k_i^{\rm fss}$ for party $P_i$~($i \in \{0, 1\}$), and an evaluation point $x \in \{0, 1\}^\ell$, outputs a group element $y_i \in \mathbb{G}$ as the share of $f(x)$ for $P_i$.
	\end{itemize}
\end{definition}

\begin{definition}[Security of FSS] 
\label{Def:FSSsecurity}
	A secure two-party FSS satisfies the following requirements:
	\begin{itemize}
		\item $\textsf{\rm Correctness}$: for all function $f: \{0, 1\}^{\ell} \rightarrow \mathbb{G}$ and every $x \in \{0, 1\}^n$, if $(k_0^{\rm fss}, k_1^{\rm fss}) \leftarrow \textsf{\rm Gen} (1^{\kappa}, f)$ then ${\rm Pr} [\textsf{\rm Eval}(k_0^{\rm fss}, x)+\textsf{\rm Eval}(k_1^{\rm fss}, x)=f(x)] = 1$.
		
		\item $\textsf{\rm Secrecy}$: For every corrupted $P_i$ and every sequence of function $f_1, f_2,...$, there exists a PPT simulator $\textsf{Sim}$ such that 	for $i \in \{0, 1\}$
		\[\{ k_i^{\rm fss}:(k_0^{\rm fss}, k_1^{\rm fss}) \leftarrow \textsf{\rm Gen}(1^{\kappa}, f_\kappa) \}_{\kappa \in \mathbb{N}} \stackrel{c}{\equiv} \{ \textsf{Sim}_i(1^{\kappa}, i, \mathbb{G}) \}_{\kappa \in \mathbb{N}}\]
	\end{itemize}
\end{definition}


\begin{definition}[Point Function]\label{def:pointfun}
	A point function is a function $f_{\alpha, \beta}(x): \{0,1\}^{\ell} \rightarrow \mathbb{G}$ where $\mathbb{G}$ is an abelian group such that \begin{equation}
	f_{\alpha, \beta}(x) = \left\{
	\begin{array}{ll}
	\beta, & {\rm if} \; x = \alpha \\
	0, & {\rm otherwize} \\
	\end{array}
	\right.
	\end{equation}
\end{definition}


Our WBV is based on a point function defined in Definition~\ref{def:pointfun}, which can be shared using FSS with the key size of $O(\kappa \log m)$.
A trusted dealer can generate the keys for a point function with $O(\log m)$ PRG evaluations. 
In \cite{doerner2017scaling}, they use two-party computation to generate FSS keys, removing the trusted-dealer assumption. 
Indeed, the technique in \cite{doerner2017scaling} can be directly used for pre-processing WBV.
Specifically, each party ${P}_i$ just locally sample a random share $\boolshare{\mathsf{rdx}}_i \in \mathbb{Z}_2^{\ell}$, and then run the two-party FSS key generation protocol of \cite{doerner2017scaling} to compute the keys. 
Each party will hold a FSS key after secure computation, and then each party can evaluate his key over $i \in [0,m)$ to generate his own share of a WBV. 
By definition of point function, the parties will only share $1$ at $\mathsf{rdx}$, and 0 for any $i \ne \mathsf{rdx}$. 
\section{Conclusion} \label{section:conclusion}
In this paper, we study how to design sublinear-communication PDTE protocols with improved efficiency.
We first propose two communication-efficient shared oblivious selection (SOS) protocols with different trade-offs.
By combining these SOS protocols with secure computation and a tree encoding strategy, we propose two PDTE protocols both with sublinear communication efficiency.
Our experiments show our protocols are efficient and practical. 
As future research, we will extend our techniques to other privacy-preserving machine learning protocols. 
\section{Experiment}\label{section:experiment}
In this section, we report the concrete efficiency of our PDTE protocol. 
We implement the protocol in C++ under ABY framework~\cite{demmler2015aby}. 

\subsection{Experiment Setup}
We run our experiment on a desktop PC equipped with Intel(R) Core™ i9-9900 CPU at 3.10~GHz × 16 running Ubuntu 20.04 LTS and 32~GB of memory.
We use Linux \textsf{tc} tool to simulate local-area network~(LAN, RTT: 0.1~ms, 1~Gbps), metropolitan-area network~(MAN, RTT: 6~ms, 100~Mbps) and wide-area network~(WAN, RTT: 80~ms, 40~Mbps).
We set the computational security parameter $\kappa = 128$ and statistical security parameter $\lambda = 40$. 
As in prior work, we set the bit length to $\ell = 64$. For AHE, the plaintext module is $|N| = 2048$.
We implement the involved secure computation using GMW~\cite{micali1987play} protocol over boolean sharing as default. The times reported are averaged over ten trials.

\subsection{Tree Parameters}
We evaluate our protocols on 8 representative datasets from UCI repository\footnote{\url{https://archive.ics.uci.edu/ml}} as listed in Table~\ref{tab::paramters}. 
To compare with~\cite{kiss2019sok, ma2021let}, we directly use their used decision trees \textit{wine, Linnerud, breast, digits, diabetes} and \textit{Boston} which are trained using codes from~\cite{kiss2019sok}. 
We additionally train two trees, one is a deep-but-sparse tree \textit{spmabase} and another is a density tree \textit{MNIST} with a high-dimensional vector.

\begin{table}[!hp]
\footnotesize
\renewcommand{\arraystretch}{1.1}
\caption{Tree Parameters}\label{tab::paramters}
\centering
	\begin{tabular}{|c|c|c|c|}
	\hline
	\textbf{Decision Tree} & \textbf{Feature Dimension} $n$ & \textbf{Depth} $d$ & $\#$(\textbf{Nodes}) $m$\\
	\hline
    wine & 7 & 5 & 23\\
	\hline
    Linnerud & 3 & 6 & 39 \\
	\hline
	breast & 12 & 7 & 43 \\
	\hline
    digits & 47 & 15 & 337\\
	\hline
	spambase & 57 & 17 & 171 \\
	\hline
	diabetes & 10 & 28 & 787 \\
	\hline
	Boston & 13 & 30 & 851 \\
	\hline
	MNIST & 784 & 20 & 4179 \\
	\hline
    \end{tabular}
\end{table}


\begin{figure
\centering
    \subfigure[Online Communication] {\label{fig:online-communication:a} \includegraphics[height=1.2in,width=1.6in]{figure/OnlineCommunication.pdf}}
    \subfigure[Offline Communication] {\label{fig:online-communication:b} \includegraphics[height=1.2in,width=1.6in]{figure/OfflineCommunication.pdf}}
   
\caption{Online and Offline Communication Cost. Note that the $y$-axis is in logarithm scale.}
\label{fig:online-offline}
\end{figure}

\subsection{Performance Evaluation}
In this section, we report the efficiency of our protocol.
We first test PDTE protocols in communication and running time under different network settings and compare them with state-of-the-art PDTE protocols. 
Then we discuss trade-off by exploring the modular design of our PDTE design and give recommendations for different scenarios.  
Last we report performances over large synthetic deep trees to show the scalability of our PDTE protocols. 

We mainly compare our protocols with three representative PDTE works~\cite{kiss2019sok,tueno2019private,ma2021let}. Kiss~\textit{et~al. }~\cite{kiss2019sok} divide a PDTE protocol into three sub-protocols: feature selection, comparison and path evaluation and use either Garbled Circuit~(GC) or AHE to instantiate them. We select~\cite{kiss2019sok} because this work is the most summative in linear-cost PDTE protocols. We compare our work with their GGG and HHH since the former is computation-friendly and the latter is communication-friendly. Other two PDTE works are both sublinear-cost~\cite{tueno2019private,ma2021let} protocols, similar to ours. 
But only the ORAM-based PDTE protocol in \cite{tueno2019private} is truly sublinear-communication. 



\begin{figure*}[!htp]
\centering
\subfigure[UCI datasets on LAN (1Gbps/0.1ms)] {\label{fig:onlineRuntime:a}
\includegraphics[height=1.20in,width=1.62in]{figure/LANot.pdf}}
\subfigure[UCI datasets on MAN (100Mbps/6ms)] {\label{fig:onlineRuntime:b}
\includegraphics[height=1.22in,width=1.62in]{figure/MANot.pdf}}
\subfigure[UCI datasets on WAN (40Mbps/80ms)] {\label{fig:onlineRuntime:c}
\includegraphics[height=1.224in,width=1.62in]{figure/WANot.pdf}}
\caption{Online Runtime in LAN/MAN/WAN Setting. Note that the $y$-axis is in logarithm scale.}
\label{fig:onlineRuntime}
\end{figure*}



\noindent\textbf{PDTE Communication}.  
Fig.~\ref{fig:online-offline} details the communication consumption of our two PDTE protocols, and the comparison with~\cite{kiss2019sok,ma2021let}.
As we can see, our PRF-based construction~(with LowMC as the PRF instantiation) requires the least communication among these PDTE protocols and is slightly better than~\cite{ma2021let}.
Our HE-based PDTE protocol requires more communication than PRF-based one.
The main reason is that the ciphertext size evaluated in each round in our PRF-based protocol is smaller than that in our HE-based protocol. In the latter, for example, the ciphertext size is set to be $|N^2| = 4096$.
Although they all enjoy constant communication complexity per selection, the constant factor is much higher in HE-based protocol. 
GGG also shows better online communication performance than our HE-based protocol when trees are small. It is reasonable because GGG shifts all GC generation to the offline phase, resulting in efficient online efficiency independent of the tree size. However, GGG needs $n\ell$ 1-out-of-2 OT to perform oblivious feature selection. 
Thus, compared with GGG, our HE-based protocol shows less online communication cost when it comes to trees with a high-dimensional feature vector, like MNIST.

Towards offline communication, our two constructions both lie between GGG and the construction of Ma~\textit{et~al. }~\cite{ma2021let}. The protocol in~\cite{ma2021let} enjoys the lowest offline communication cost for small trees. However, their offline communication cost increases with the size of the tree since the tree in their protocol should be re-sent before each evaluation. Thus, as the tree size $m$ increases, our offline communication overhead will be outpaced by~\cite{ma2021let}. GGG costs the most even when the tree is medium-sized in Table~\ref{tab::paramters}, \ie, digits. As we discussed before, GGG can enjoy a better online communication cost by moving major communication to offline. However, as shown in Fig.~\ref{fig:online-communication:b}, the price is high, referring to big trees.

\noindent\textbf{PDTE Running Time}. 
We report the online running time of our PDTE protocols under different network settings~(LAN, MAN, WAN) in Fig.~\ref{fig:onlineRuntime}. The reported runtimes of protocol~\cite{ma2021let} are read from their paper. In this test, we use LowMC to instantiate the involved PRF in our PRF-based protocol. 

In the LAN setting, our HE-based protocol needs the most running time except for MNIST. It is clear to see that the running time of GGG and HHH grow with the tree size. Our HE-based protocol shows less computation when treating MNIST ($m = 4179$) than Boston ($m = 851$). This is because the depth of MNIST is smaller than Boston. Our PRF-based protocol lies between Ma \textit{et~al. }~\cite{ma2021let} protocol and HHH protocol. There is no doubt that protocol in~\cite{ma2021let} is the most efficient protocol to date under the LAN setting. This is because the most expensive operations in their protocol are OT and GC. Yet, in our PRF-based protocol, the most costly are secure LowMC evaluation. However, our PRF-based protocol still outruns linear protocols GGG and HHH by $24 \times$ to $65 \times$, respectively, for MNIST.

Our two protocols are slightly less efficient than HHH and require around $100 \times$ costs than GGG~\cite{ma2021let}, especially when the tree is tiny. One reason is that our work is based on GMW who is highly influenced by latency. Thus our PRF-based protocol runs an order slower when the latency increases from 0.1ms to 6ms. This ``negative" property appears on our HE-based protocol as well but in a mild influence since our HE-based protocol removes the costly LowMC operation. One should notice that our two protocols become slightly better than GGG and save at least $5 \times$ running times than HHH, for MNIST. With the increase of size/depth of the tree, our sublinear protocols will be more competitive.

We can also observe that as the network latency increases, our HE-based PDTE protocol gradually surpasses PRF-based one, \ie, $6 \times$ to $7 \times$ faster in the WAN setting.
The reason is that two-party PRF evaluation in the PRF-based protocol involves higher rounds than the HE-based construction, which causes significant time consumption over the high-latency network.

\begin{figure*
\centering
\subfigure[Trade-off under LAN (1Gbps/0.1ms)] {\label{fig:tradeoff:a}
\includegraphics[height=1.233in,width=1.63in]{figure/LANTradeoff.pdf}}
\subfigure[Trade-off under MAN (100Mbps/6ms)] {\label{fig:tradeoff:b}
\includegraphics[height=1.23in,width=1.63in]{figure/MANTradeoff.pdf}}
\subfigure[Trade-off under WAN (40Mbps/80ms)] {\label{fig:tradeoff:c}
\includegraphics[height=1.23in,width=1.63in]{figure/WANTradeoff.pdf}}
\caption{Trade-offs between Online Communication (x-axis) and Online Runtime (y-axis). Each figure shows the online complexities including communication and runtime. Note that diamond, square, triangle, round and six-pointed star represent AES$+$AES, AES$+$OT, LowMC$+$LowMC, LowMC$+$OT and HE+OT protocol, respectively. The shape filled by red, blue, yellow and green are Linnerud, digits, Boston and MNIST, respectively. Both $x$-axis and $y$-axis are in logarithm scale.
}
\label{fig:tradeoff}
\end{figure*}

\noindent\textbf{Trade-off.} 
We report the concrete trade-off between our PRF-based protocol and HE-based protocol. Since OT/PRF/HE can be used to instantiate SOS protocol, we investigate the differences when using different SOS protocols and give the corresponding experiments. To thoroughly examine the PRF-based protocol, we also implement AES as the underlying PRF. Specifically, we use A+B to denote the tree node is selected by A-based SOS protocol, and the attribute is obliviously shared by B-based SOS protocol.

We remove wine, breast, spambase and diabetes, which share similar parameters as the selected trees. 
Fig.~\ref{fig:tradeoff} shows the trade-off in three different network settings. 
In the scenarios with low network latency~(\textit{e.g.}, IoT), LowMC+OT can efficiently handle small trees like Linnerud. 
In the cases of deep trees with thousands of nodes, LowMC+LowMC shows less communication cost while LowMC+OT saves roughly 50\% runtime. Thus, in the situation where the computation performance matters more, LowMC+OT can be adopted to provide reasonable online computation overhead and communication cost. The reported runtime/communication of HE+OT under the LAN setting is significantly high than other PRF-based protocols.
With latency increasing, AES-based protocols suffer more than LowMC involved protocols, while HE+OT shows its advantages in runtime, as seen from Fig.~\ref{fig:tradeoff:b}. 
Under WAN with 80ms high network latency, the online running time for small trees by LowMC+LowMC is around 50\% higher than LowMC combining OT. 
This gap becomes progressively smaller as the tree depth increases. 
Under this setting, HE+OT is the first choice when considering time-consuming.

\begin{figure}[!tp]
\centering
    \subfigure[Total Communication] {\label{fig:scalability:a} \includegraphics[height=1.2in,width=1.6in]{figure/ComDeepTree.pdf}}
    \subfigure[Total Running Time]{\label{fig:scalability:b} \includegraphics[height=1.2in,width=1.6in]{figure/TimeDeepTree.pdf}}
\caption{Total Communication and Runtime Cost (LAN setting). Note that $y$-axis is in logarithm scale. }
\label{fig:scalability}
\end{figure}

\noindent\textbf{Scalability for High-depth Trees}. 
We report the scalability of our PDTE protocols and compare them with the ORAM-based PDTE protocol~\cite{tueno2019private} in LAN setting.
Unfortunately, Tueno~\textit{et~al. }~\cite{tueno2019private} only report results for trees with depth up to 23 since their experiments ran out of memory.
The experiments of our protocols are done for trees with the depth ranging from 18 to 50.
For tree's size, we follow the same setting of \cite{tueno2019private} by letting $m = 25d$. 
We perform the evaluation in the LAN setting as shown in Fig.~\ref{fig:scalability}. 
As we can see, our HE-based protocol requires $9 \times$ to $16 \times$ less communication and $4 \times$ to $7 \times$ less running time compared with \cite{tueno2019private}.
Our PRF-based protocol requires $43 \times$ to $60 \times$ less communication and $26 \times$ to $54 \times$ less running time compared with \cite{tueno2019private}.
Therefore, our PDTE protocols are more scalable for evaluation over large trees. 
\section{Private Decision Tree Evaluation with Sublinear Communication} \label{sec:construction}

In this section, we give our PDTE protocol with sublinear communication. 
We first propose two SOS protocols with sublinear communication under different trade-offs.
Leveraging the SOS functionality, we design our sublinear PDTE protocol. 

\begin{figure}[!hbp]
	\framebox{\begin{minipage}{0.95\linewidth}

		{\bf Parameters}: 
		Two parties denoted as $\mathcal{S}$ and $\mathcal{R}$; array length $m$; index bit length $\ell$; array element bit length $ \ell_{\mathsf{v}}$.
		
		\smallskip 
		{\bf [Setup]} 
		Upon receiving $(\textsc{Setup}, \mathsf{M},  \ell_{\mathsf{v}})$ from $\mathcal{S}$ and $(\textsc{Setup}, \perp)$ from $\mathcal{R}$, $\mathcal{S}$ stores $\mathsf{M}$ locally. 
		
	    \smallskip 
		{\bf [Select]} 
		Upon receiving $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm s})$ from $\mathcal{S}$ and $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm r})$ from $\mathcal{R}$:   
		\begin{enumerate}
		    \item $\mathcal{S}$ and $\mathcal{R}$ run a B2A conversion~\cite{demmler2015aby}, transforming $\boolshare{\mathsf{idx}}$ to its arithmetic form $\addshare{\mathsf{idx}}$ over $\mathbb{Z}_m$
		    
		    \item $\mathcal{S}$ samples $r \xleftarrow{\$} \mathbb{Z}_{2}^{ \ell_{\mathsf{v}}}$, computes $m$ messages $\{E_i\}_{i \in [0, m)}$ such that $E_i = r \oplus \mathsf{M}[i + \addshare{\mathsf{idx}}_{\rm s}~(\mathsf{mod}~m)]$. 
		    
		    \item
		    $\mathcal{S}$ and $\mathcal{R}$ invoke 1-out-of-$m$ OT functionality $\mathcal{F}_{\rm ot}$.
		    $\mathcal{S}$ inputs $\{E_i\}_{i \in [0, m)}$ and $\mathcal{R}$ provides $\addshare{\mathsf{idx}}_{\rm r}$ as choice input. 
		    By definition of OT, $\mathcal{R}$ receives $r \oplus \mathsf{M}[\mathsf{idx}]$. 
		    
		    \item $\mathcal{S}$ outputs $r$ and $\mathcal{R}$ outputs $r \oplus \mathsf{M}[\mathsf{idx}]$.
		\end{enumerate}
	\end{minipage}}
	\caption{Linear-communication SOS Protocol from OT \cite{tueno2019private}}
	\label{protocol:SOS_OT}	

\end{figure}

\subsection{Shared Oblivious Selection Protocol}
In Fig.~\ref{protocol:SOS_OT}, we first show an SOS protocol from $1$-out-of-$m$ OT as previously done in \cite{tueno2019private}.
We will use OT-based SOS protocol over feature vectors that are usually with low dimension.
Despite being conceptually efficient and straightforward for small arrays, OT-based construction requires $O(m)$ online communication; this is prohibitively high when $m$ is large.
For oblivious selection over tree nodes, we need communication-efficient SOS protocols since, usually, a tree contains thousands to millions of nodes~\cite{catlett1991overprvning}.

\begin{figure}[!htp]

	\framebox{
	    \begin{minipage}{0.95\linewidth}
	   
		\centerline{\textbf{Functionality $\mathcal{F}_{\rm {pre}}$}
		\smallskip
		
		{\bf Parameters}: Two parties denoted as $\mathcal{S}$ and $\mathcal{R}$; weight-1 bit vector length $m$; BMT arithmetic module $n$; index bit length $\ell$. 
		\begin{packed_item}
			\item \textbf{GenWBV}: upon receiving $(\textsc{GenWBV}, \ell, m)$ from all parties: 
			\begin{itemize}
			    \item sample $\mathsf{rdx} \xleftarrow{\$} \mathbb{Z}_{\ell}$, compute $\mathsf{S}$ such that $\mathsf{S}[\mathsf{rdx}] = 1$ and $\mathsf{S}[j] = 0$ for all $j \ne \mathsf{rdx}$.
			    
			    \item sample $e \xleftarrow{\$} \mathbb{Z}_2^{\ell}$, $ r \xleftarrow{\$} \mathbb{Z}_2^{m}$, send $(e, r)$ to $\mathcal{S}$ and $(e \oplus \mathsf{rdx}, \mathsf{S} \oplus r)$ to $\mathcal{R}$.
			\end{itemize}
			
            \item \textbf{GenBMT}: upon receiving $(\textsc{GenBMT}, n, \addshare{a}_{\rm s}, \addshare{b}_{\rm s})$ from $\mathcal{S}$ and $(\textsc{GenBMT}, n, \addshare{a}_{\rm r}, \addshare{b}_{\rm r})$ from $\mathcal{R}$: 
			\begin{itemize}
			    \item compute $c \leftarrow (\addshare{a}_{\rm s}+\addshare{a}_{\rm r})\cdot(\addshare{b}_{\rm s}+\addshare{b}_{\rm r})~(\mathsf{mod}~n)$. 
			    
			    \item sample $r \xleftarrow{\$} \mathbb{Z}_{n}$, send $-r~(\mathsf{mod}~n)$ to $\mathcal{S}$ and $r+c~(\mathsf{mod}~n)$ to $\mathcal{R}$.
			\end{itemize}
		\end{packed_item}
	\end{minipage}
	}
	\centering \caption{The Pre-processing Functionality $\mathcal{F}_{\rm {pre}}$}
	\label{Fun:PRE}
\end{figure}
\begin{figure}[!htp]

	\framebox{
    	\begin{minipage}{0.95\linewidth}
    
    		\centerline{\textbf{Functionality $\mathcal{F}_{\rm sprf}$}
    		\smallskip
    		{\bf Parameters}: Two parties denoted as $\mathcal{S}$ and $\mathcal{R}$; PRF $F: \{0,1\}^{\kappa} \times \{0,1\}^{\ell} \rightarrow \{0, 1\}^{ \ell_{\mathsf{b}}}$. 
    		\begin{packed_item}
    			\item \textbf{Eval}: upon receiving (\textsc{Eval}, $\mathsf{sk}$, $\boolshare{\mathsf{idx}}_{\rm s}$) from $\mathcal{S}$ and (\textsc{Eval}, $\boolshare{\mathsf{idx}}_{\rm r}$) from $\mathcal{R}$, compute:
     			\begin{itemize}
        			\item reconstruct $\mathsf{idx} \leftarrow \boolshare{\mathsf{idx}}_{\rm s} \oplus \boolshare{\mathsf{idx}}_{\rm r}$, compute ${F}(\mathsf{sk}, \mathsf{idx})$ 
        			\item sample $r \xleftarrow{\$} \mathbb{Z}_{2}^{ \ell_{\mathsf{b}}}$, send $r$ to $\mathcal{S}$ and $r \oplus {F}(\mathsf{sk}, \mathsf{idx})$ to $\mathcal{R}$
     			\end{itemize}
    		\end{packed_item}
    	\end{minipage} 
    }
	\centering \caption{The Shared PRF Functionality $\mathcal{F}_{\rm sprf}$ 
	}
	\label{Fun:SOPRF}
\end{figure}

\smallskip
\subsubsection{\textbf{Available Ideal Functionalities}}
Before describing our protocol, we introduce two ideal functionalities.
One is called preprocessing functionality $\mathcal{F}_{\textsf{pre}}$ defined in Fig.~\ref{Fun:PRE} that generates useful correlated randomnesses, including shared weight-1 bit vector~(WBV) and Beaver multiplication triple (BMT). 
Another is called two-party shared PRF functionality $\mathcal{F}_{\textsf{sprf}}$ in Fig.~\ref{Fun:SOPRF}. 
In particular, WBVs can be constructed from Function Secret Sharing~(FSS)~\cite{boyle2015function,boyle2016function} with sublinear communication, and BMTs can be generated from AHE or OT~\cite{demmler2015aby}. 
We summarize how to generate these correlated randomnesses in Appendix~\ref{appendix::2::c}. 
One can initialize $\mathcal{F}_{\textsf{sprf}}$ by evaluating a block cipher circuit using secure two-party computation. 
In the following, we will use these ideal functionalities directly; such approach, which is known as hybrid-model, is commonly used in designing secure computation protocols~\cite{goldreich2009foundations,hazay2010efficient}. 


\smallskip
\subsubsection{\textbf{The PRF-based SOS Protocol}}
Our PRF-based SOS protocol in Fig.~\ref{protocol:SOS} only needs a single two-party PRF invocation regardless of the array length.
The protocol is inspired by Floram, but we propose new techniques to improve efficiency. 

\noindent\textbf{\textbf{New Pre-processing Technique}}. 
We propose a new preprocessing technique for WBVs inspired by Beaver's circuit derandomization technique~\cite{beaver1991efficient}, moving all its generation work to the offline phase. 
Let $\mathsf{S}$ be a WBV over a random index $\mathsf{rdx}$, the parties can use $\mathsf{S}$ during the online phase to share an element at location $\mathsf{idx}$.  
Specifically, the parties simply reveal $\delta = \mathsf{rdx} - \mathsf{idx}~(\mathsf{mod}~m)$ and compute:
\begin{align*}
\boolshare{\mathsf{C}[\mathsf{idx}]} &= \bigoplus_{i \in [0, m)} \boolshare{\mathsf{S}[\delta + i ~(\mathsf{mod}~m)]} \cdot \mathsf{C}[i],
\end{align*}
then $\mathsf{C}[\mathsf{idx}]$ is shared between parties as required.\footnote{$\boolshare{\mathsf{S}[\delta + i~(\mathsf{mod}~m)]} \cdot \mathsf{C}[i]$ is computed in the secret-shared fashion, \ie, $\mathcal{S}$ computes $\boolshare{\mathsf{C}[\mathsf{idx}]}_{\rm s} = \bigoplus_{i \in [0, m)}  \boolshare{\mathsf{S}[\delta + i~(\mathsf{mod}~m)]}_{\rm s} \cdot \mathsf{C}[i]$, and $\mathcal{R}$ computes $\boolshare{\mathsf{C}[\mathsf{idx}]}_{\rm r} = \bigoplus_{i \in [0, m)}  \boolshare{\mathsf{S}[\delta + i~(\mathsf{mod}~m)]}_{\rm r} \cdot \mathsf{C}[i]$.}
This derandomization technique enables the parties to pre-generate sufficient weight-1 bit vectors to trade an efficient online protocol.


Note that $\mathsf{idx}$ and $\mathsf{rdx}$ are shared in boolean form, for better efficiency, the parties first perform B2A conversion~\cite{demmler2015aby} before performing subtraction; this can be efficiently done by $\ell$ OTs in $O(1)$ round for $\ell$-bit boolean sharing~\cite{demmler2015aby}. 
Indeed, we can get rid of B2A conversion using a slightly different technique.
Specifically, when $m = 2^{k}$, the parties can simply reveal $\delta = \mathsf{idx} \oplus \mathsf{rdx}$ and compute: 
\[\boolshare{\mathsf{C}[\mathsf{idx}]} = \bigoplus_{i \in [0, m)} \boolshare{\mathsf{S}[\delta \oplus i]} \cdot \mathsf{C}[i].\]
For generic cases where $2^{k-1}\le m \le 2^{k}$, $\mathcal{S}$ has to pad $\mathsf{M}$ of size $2^k$ and randomly places elements in the padded array before encryption; this certainly needs more storage space but only doubles the storage cost at most. 

 
\noindent\textbf{Reduce Overhead of Two-party PRF Evaluation}. 
Our protocol only needs a single mask to hide the underlying message, instead of two used in Floram~(see section~\ref{sec:background}). 
In short, Floram works for secret-shared data; it is necessary to use two masks, each for protecting a share from one party. 
For our setting, double-masking is overkill since $\mathcal{S}$ already knows $\mathsf{M}$. We only need one mask to protect $\mathsf{M}$ from $\mathcal{R}$. 
As such, we change the original masking mechanism to $\mathsf{C}[i] \leftarrow \mathsf{M}[i] \oplus {F}(\mathsf{sk}_{\rm s}, i)$ for $i \in [0, m)$. 
Our optimization reduces half of the two-party PRF evaluations, which can significantly improve efficiency in practice since two-party PRF evaluation contributes the main overhead to the PRF-based protocol.

In addition, we provide implementation-level optimizations. 
In particular, Floram uses AES for instantiating ${F}$. However, AES contains many AND gates, \textit{e.g.}, AES-128 needs 6,400 AND-gates per evaluation\footnote{\url{https://homes.esat.kuleuven.be/~nsmart/MPC/}}, which incurs significant overhead when evaluated by secure computation. 
We provide an optimized implementation from LowMC block cipher~\cite{albrecht2015ciphers}. 
LowMC is MPC-friendly, designed with much fewer AND-gates. It provides tunable options between block size, evaluation round and security level; this allows us to choose the best parameters for different scenarios. 
 



\begin{figure}
	\framebox{\begin{minipage}{0.95\linewidth

			{\bf Parameters}: 
			PRF $F: \{0,1\}^{\kappa} \times \{0,1\}^{\ell} \rightarrow \{0, 1\}^{ \ell_{\mathsf{b}}}$; index bit length $\ell$; bit length of PRF output $ \ell_{\mathsf{b}}$; bit length of array element $ \ell_{\mathsf{v}}$; number of PRF output for an element $ B = \lceil \frac{ \ell_{\mathsf{v}}}{ \ell_{\mathsf{b}}} \rceil$; array length $m = |\mathsf{M}|$. 
		
		\smallskip 
		{\bf [Setup]} Upon receiving $(\textsc{Setup}, \mathsf{M},  \ell_{\mathsf{v}})$ from $\mathcal{S}$ and $(\textsc{Setup}, \perp)$ from $\mathcal{R}$: 
		\begin{enumerate}
			\item $\mathcal{S}$ samples a secret key $\mathsf{sk}_{\rm s} \xleftarrow{\$} \{0,1\}^{\kappa}$ for ${F}$, and encrypts $\mathsf{M}$ to obtain ciphertext $\mathsf{C}$ such that $\mathsf{C}[i][j] = \mathsf{M}[i][j] \oplus {F}(\mathsf{sk}_{\rm s}, i||j)$ for $i \in [0, m)$ and $j \in [0, B)$.  
			
			\item $\mathcal{S}$ sends $\mathsf{C}$ to $\mathcal{R}$.
			$\mathcal{S}$ stores $(\mathsf{sk}_{\rm s}, \mathsf{C})$ and $\mathcal{R}$ stores $\mathsf{C}$. 
		\end{enumerate}
		
		\smallskip 
		{\bf [Select]} 
		Upon receiving $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm s})$ from $\mathcal{S}$ and $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm r})$ from $\mathcal{R}$:   
		\begin{enumerate}
		    \item \label{SOS:select:line1} $\mathcal{S}$ and $\mathcal{R}$ send $(\textsc{GenWBV}, \ell, m)$ to $\mathcal{F}_{\rm pre}$, obtain $(\boolshare{\mathsf{rdx}}, \boolshare{\mathsf{S}})$. 
		
		    \item \label{SOS:select:line2} $\mathcal{S}$ and $\mathcal{R}$ convert $\boolshare{\mathsf{idx}}$ and $\boolshare{\mathsf{rdx}}$ to arithmetic share form $\addshare{\mathsf{idx}}$ and $\addshare{\mathsf{rdx}}$ by B2A conversion~\cite{demmler2015aby}. 
		    
			\item \label{SOS:select:line3} $\mathcal{S}$ and $\mathcal{R}$ compute $\addshare{\delta} = \addshare{\mathsf{rdx}} - \addshare{\mathsf{idx}}~(\mathsf{mod}~m)$, and reveal $\delta$ in clear. 
			Then they compute $\boolshare{e} = \bigoplus_{i=0}^{m-1} \boolshare{\mathsf{S}[i + \delta~(\mathsf{mod}~m)]} \cdot \mathsf{C}[i]$. 
			
			\item $\mathcal{S}$ and $\mathcal{R}$ compute $ B$ shared indexes $\boolshare{\mathsf{idx} || j} = \boolshare{\mathsf{idx} << \lceil \log  B \rceil} + j$ for $j \in [0, B)$, locally. 
			
			\item \label{SOS:select:line4} $\mathcal{S}$ and $\mathcal{R}$ call $\mathcal{F}_{\textsf{sprf}}$ for each of $ B$ blocks. For $j \in [0,  B)$, $\mathcal{S}$ inputs (\textsc{Eval}, $\mathsf{sk}_{\rm s}$, $\boolshare{\mathsf{idx}||j}_{\rm s}$) and $\mathcal{R}$ inputs (\textsc{Eval}, $\boolshare{\mathsf{idx}||j}_{\rm r}$) to $\mathcal{F}_{\textsf{sprf}}$, $\mathcal{F}_{\textsf{sprf}}$ sends $\boolshare{f_j}_{\rm s}$ to $\mathcal{S}$ and $\boolshare{f_j}_{\rm r}$ to $\mathcal{R}$ such that  $\boolshare{f_j}_{\rm s} \oplus \boolshare{f_j}_{\rm r} = {F}(\mathsf{sk}_{\rm s}, \mathsf{idx}||j)$.
			
			
			\item \label{SOS:select:line5} Let $\boolshare{f}$ be $\boolshare{f_0}||\cdots||\boolshare{f_{ B-1}}$, $\mathcal{S}$ and $\mathcal{R}$ locally compute $\boolshare{m} = \boolshare{e} \oplus \boolshare{f}$. 
		\end{enumerate}
	\end{minipage}}
	\caption{The PRF-based SOS Protocol}
	\label{protocol:SOS}	

\end{figure}

\noindent\textbf{{Optimized Multi-block Masking Strategy}}. 
We propose an MPC-friendly masking method for $\mathsf{M}$ with large-size elements.
Specifically, suppose each element has a size of $ \ell_{\mathsf{v}}$, and the PRF output is of size $ \ell_{\mathsf{b}}$.
Note that when $ \ell_{\mathsf{b}} <  \ell_{\mathsf{v}}$, a single PRF output cannot mask the whole element. 
To handle the issue, we divide the element into multiple blocks and generate a mask for each.
In addition, we design a fixed-key masking strategy, which turns to be MPC-friendly.
Specifically, denote $\mathsf{M}[i][j]$ as $\mathsf{M}[i]$'s $j$-th block, $\mathcal{S}$ simply encrypts the block as: 
\[
\mathsf{C}[i][j] \leftarrow \mathsf{M}[i][j] \oplus {F}(\mathsf{sk}_{\rm s}, i||j),
\] 
where ${i||j} = {i} \cdot 2^{\lceil \log_2 {B} \rceil} + j$, $ B = \lceil \frac{ \ell_{\mathsf{v}}}{ \ell_{\mathsf{b}}} \rceil$.
Since $F: \{0,1\}^{\kappa} \times \{0,1\}^{\ell} \rightarrow \{0, 1\}^{ \ell_{\mathsf{b}}}$ is defined over $\ell$-bits inputs, one should note that $\ell$ should be large enough, \ie, ${i} \cdot 2^{\lceil \log_2 {B} \rceil} + j < 2^{\ell}$ for all $i \in [0, m)$ and $j\in [0,  B)$, otherwise it is possible to encounter a wrap-around issue incurring $i_1||j_1 = i_2||j_2$ and ${F}(\mathsf{sk}_{\rm s}, i_1||j_1) = {F}(\mathsf{sk}_{\rm s}, i_2||j_2)$, then $\mathcal{R}$ can easily learn:
\[
\mathsf{M}[i_1][j_1]\oplus \mathsf{M}[i_2][j_2] = \mathsf{C}[i_1][j_1] \oplus \mathsf{C}[i_2][j_2].
\]
As such, we require all $i||j$ are unique for $i \in [0, n)$ and $j\in [0,  B)$. 
Indeed, setting $\lceil \log_2 {n} \rceil + \lceil \log_2 {B} \rceil \le \ell$ suffices for the goal. 
Taking a concrete example, when $\ell = 64$, $ B = 5$, our indexing method can support oblivious selection on $2^{61}$ elements, which is already sufficient in practice.

Two benefits follow from the design. 
First, since $i$ is boolean-shared bit-by-bit and $j$ is public, sharing ${i||j}$ is essentially free: each party just cyclically left-shifts its share of ${i}$ by $\lceil \log_2 {B} \rceil$ bits, and sets the lower $\lceil \log_2 {B} \rceil$ bits to be the share of $j$, \ie, $i||j = (i << \lceil \log_2 {B} \rceil) + j$.  
Note that $j$ is publicly known to both parties, hence sharing ${j}$ is easy, \textit{e.g.}, $j = 0 \oplus j$.
As a result, the parties can non-interactively share ${i||j}$ for all $j \in [0,  B)$ from the sharing of ${i}$. 
Second, since ${F}$ uses a fixed key $\mathsf{sk}_{\rm s}$, we can implement two-party PRF evaluation in a SIMD mode, allowing the parties to perform PRF evaluation in parallel during oblivious selection, which improves efficiency by reducing rounds. 

{
\noindent\textbf{Complexity Analysis}.
Same as Floram, the parties need to perform linear memory scan over all encrypted array elements; this is relatively cheap given highly efficient hardware nowadays. 
Besides, our protocol requires both parties to store the encrypted array locally. 
We believe the price is desirable to trade a better online communication in scenarios where multiple invocations are frequently performed between the parties. 
However, concretely, the overhead for two-party PRF evaluation can be relatively high.  
In particular, even using LowMC PRF, the parties still have to evaluate thousands of AND gates using secure computation, which can cause massive time consumption over a high-latency network; this motivates us to design a round-efficient SOS protocol. 
}


\noindent\textbf{Security}.
We have Theorem~\ref{theorem:1} to capture security of the PRF-based SOS protocol. The proof can be found in Appendices~\ref{appendix::1::a}.

\begin{theorem}\label{theorem:1}
Let ${F}$ be a secure PRF, the oblivious selection protocol in Fig.~\ref{protocol:SOS} securely computes the functionality $\mathcal{F}_{\textsf{sos}}^{(\mathsf{M})}$ in $(\mathcal{F}_{\textsf{sprf}}, \mathcal{F}_{\textsf{pre}})$-hybrid model under a semi-honest adversary. 
\end{theorem}

\subsubsection{\textbf{The HE-based SOS protocol}}
The prior PRF-based SOS protocol has sublinear communication, but the parties must perform a two-party PRF evaluation per oblivious selection.
Though we provide optimizations to reduce the overhead, its round complexity is relatively high given the intrinsic complexity of PRFs; this can incur considerable time consumption over a high-latency network.


\noindent\textbf{New Solution}. 
We design a sublinear SOS protocol with better round complexity by using Paillier's AHE~\cite{paillier1999public}. 
The idea is similar to the PRF-based SOS protocol, but we explore the additive homomorphic property of Paillier encryption to eliminate two-party PRF evaluation. 
Our key technique is a new share conversion protocol between additive arithmetic sharing and multiplicative arithmetic sharing over $\mathbb{Z}_{N^2}$, which is of independent interest. 

Like the PRF-based SOS protocol, $\mathcal{S}$ encrypts $\mathsf{M}$, but uses its public key $\mathsf{pk}$ and sends ciphertext $\mathsf{C}$ to $\mathcal{R}$.  
When selecting an element indexed by a shared index $\mathsf{idx}$ among $\mathsf{M}$, the parties still use the shared weight-1 bit vector to obliviously share $\boolshare{\mathsf{C}[\mathsf{idx}]}$ in boolean fashion, and then convert $\boolshare{\mathsf{C}[\mathsf{idx}]}$ to arithmetic sharing $\addshare{\mathsf{C}[\mathsf{idx}]}$ over $\mathbb{Z}_{N^2}$ by B2A conversion.  
However, one should note that such operation can only \emph{additively} share $\mathsf{C}[\mathsf{idx}]$: 
\[\addshare{\mathsf{C}[\mathsf{idx}]}_{\rm s} + \addshare{\mathsf{C}[\mathsf{idx}]}_{\rm r} = \mathsf{C}[\mathsf{idx}]~(\mathsf{mod}~N^2).\]
In order to facilitate homomorphic property of Paillier encryption, we need the ciphertext to be shared \emph{multiplicatively} over $\mathbb{Z}^*_{N^2}$: 
\[\multshare{\mathsf{C}[\mathsf{idx}]}_{\rm s} \cdot \multshare{\mathsf{C}[\mathsf{idx}]}_{\rm r} = {\mathsf{C}[\mathsf{idx}]}~(\mathsf{mod}~N^2).\] 
With such conversion, the parties can explore a shared decryption technique to share the encrypted message. 
Therefore, our first challenge is designing an efficient protocol to perform such conversion. 


\begin{figure}[!tp]
	\framebox{

	\begin{minipage}{0.95\linewidth
		{\bf Parameters}: 
			index bit length $\ell$; array element bit size $ \ell_{\mathsf{v}} \ll |N|$; array length $m =  |\mathsf{M}|$; computational security parameter $\kappa$; statistical security parameter $\lambda$.
		
		\smallskip 
		{\bf [Setup]} Upon receiving $(\textsc{Setup}, \mathsf{M},  \ell_{\mathsf{v}})$ from $\mathcal{S}$ and $(\textsc{Setup}, \perp)$ from $\mathcal{R}$. Then:   
		\begin{enumerate}
			\item $\mathcal{S}$ generates Paillier public/secret key pair $(\mathsf{pk}, \mathsf{sk}) \leftarrow \mathsf{Gen}(1^{\kappa})$.
			
			\item $\mathcal{S}$ encrypts $\mathsf{M}$ to obtain $\mathsf{C}$ such that $\mathsf{C}[i] \leftarrow \mathsf{Enc}_{\mathsf{pk}}(\mathsf{M}[i])$ for $i \in [0, m)$.
		
			
			\item $\mathcal{S}$ sends $(\mathsf{pk}, \mathsf{C})$ to $\mathcal{R}$. Both $\mathcal{S}$ and $\mathcal{R}$ store $\mathsf{C}$ locally. 
		\end{enumerate}
		
		\smallskip 
		{\bf [Select]} 
		Upon receiving $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm s})$ from $\mathcal{S}$ and $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm r})$ from $\mathcal{R}$. Then:   
		\begin{enumerate}
		    \item $\mathcal{S}$ and $\mathcal{R}$ send $(\textsc{GenWBV}, \sigma = \lceil \log_2 m \rceil, m)$ to $\mathcal{F}_{\rm pre}$, obtain $(\boolshare{\mathsf{rdx}}, \boolshare{\mathsf{S}})$. 
		
		    \item $\mathcal{S}$ and $\mathcal{R}$ convert $\boolshare{\mathsf{idx}}$ and $\boolshare{\mathsf{rdx}}$ to arithmetic share form $\addshare{\mathsf{idx}}$ and $\addshare{\mathsf{rdx}}$ by B2A conversion~\cite{demmler2015aby}. 
		    
			\item $\mathcal{S}$ and $\mathcal{R}$ compute $\addshare{\delta} = \addshare{\mathsf{rdx}} - \addshare{\mathsf{idx}}$, and reveal $\delta$ in clear. They can share  $\boolshare{x} = \boolshare{\mathsf{C}[\mathsf{idx}]} = \bigoplus_{i=0}^{m-1} \boolshare{\mathsf{S}[i + \delta]} \cdot \mathsf{C}[i]$. 
			
			\item $\mathcal{S}$ and $\mathcal{R}$  convert $\boolshare{x}$ to $\addshare{x}$ by B2A conversion.
			
		\item The parties convert $\addshare{x}$ to its multiplicative sharing form $\multshare{x}$ over $\mathbb{Z}_{N^2}$ as follows:
		\begin{enumerate}
			\item $\mathcal{S}$ samples $a \xleftarrow{\$} \mathbb{Z}_{N^2}$ and sends $(\textsc{GenBMT}, N^2, a, 0)$ to $\mathcal{F}_{\rm pre}$.
			$\mathcal{R}$ samples $b \xleftarrow{\$} \mathbb{Z}_{N^2}$ and sends $(\textsc{GenBMT}, N^2, 0, b)$ to $\mathcal{F}_{\rm pre}$. 
			In the end, the parties obtain sharing $\addshare{c}$ where $c = a\cdot b~(\mathsf{mod}~N^2)$.
			
			\item $\mathcal{S}$ samples $\gamma \xleftarrow{\$} \mathbb{Z}_{N^2}^*$ and sends $e \leftarrow \gamma^{-1} - a~(\mathsf{mod}~N^2)$ to $\mathcal{R}$. $\mathcal{R}$ sends $f \leftarrow \addshare{x}_{\rm r} - b~(\mathsf{mod}~N^2)$ to $\mathcal{S}$.
			
			\item $\mathcal{S}$ computes $\addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm s} \leftarrow a \cdot f + \addshare{c}_{\rm s}~(\mathsf{mod}~N^2)$ and $\mathcal{R}$ computes $\addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm r} \leftarrow e\cdot f + b\cdot e + \addshare{c}_{\rm r}~(\mathsf{mod}~N^2)$. $\mathcal{S}$ sends $\addshare{x}_{\rm s} \cdot \gamma^{-1} + \addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm s}~(\mathsf{mod}~N^2)$ to $\mathcal{R}$.
			
			\item $\mathcal{S}$ sets $\multshare{x}_{\rm s} \leftarrow \gamma~(\mathsf{mod}~N^2)$. $\mathcal{R}$ sets $\multshare{x}_{\rm r} \leftarrow \addshare{x}_{\rm s}\cdot \gamma^{-1} + \addshare{x\cdot \gamma^{-1}}_{\rm s} + \addshare{x\cdot \gamma^{-1}}_{\rm r}~(\mathsf{mod}~N^2)$.
		\end{enumerate}
			\item $\mathcal{R}$ samples $\beta \xleftarrow{\$} \mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$, $\rho \xleftarrow{\$} [ 0, 2^{\lambda})$ and computes $x_{\beta} \leftarrow \multshare{x}_{\rm r} \cdot \mathsf{Enc}_{\mathsf{pk}}(\beta + \rho \cdot 2^{ \ell_{\mathsf{v}}})~(\mathsf{mod}~N^2)$.
			
			\item $\mathcal{S}$ computes $\addshare{m}_{\rm s} = \mathsf{Dec}_{\mathsf{sk}}(\multshare{x}_{\rm s}\cdot x_{\beta})~(\mathsf{mod}~2^{ \ell_{\mathsf{v}}})$, and $\mathcal{R}$ sets $\addshare{m}_{\rm r} \leftarrow -\beta~(\mathsf{mod}~2^{ \ell_{\mathsf{v}}})$. 
			
			\item $\mathcal{S}$ and $\mathcal{R}$ run A2B conversion protocol to transform $\addshare{m}$ over $\mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$ to its boolean sharing form $\boolshare{m}$ over $\mathbb{Z}_2^{ \ell_{\mathsf{v}}}$.
			
		\end{enumerate}
	\end{minipage}}
   
	\caption{The HE-based SOS Protocol} 
	\label{protocol:SOS-he}	

\end{figure}


\noindent\textbf{Additive to Multiplicative Sharing Conversion over $\mathbb{Z}_{N^2}$}. 
Given an additive sharing $\addshare{x}$ over $\mathbb{Z}_{N^2}$ where $\mathcal{S}$ holding $\addshare{x}_{\rm s}$ and $\mathcal{R}$ holding $\addshare{x}_{\rm r}$, we want to convert it to its multiplicative sharing form $\multshare{x}$ satisfying $x = \multshare{x}_{\rm s} \cdot \multshare{x}_{\rm r}~(\mathsf{mod}~N^2)$.

The idea is $\mathcal{S}$ can sample a random value $\gamma \xleftarrow{\$} \mathbb{Z}^*_{N^2}$, and $\mathcal{R}$ can recover $x\cdot \gamma^{-1}~(\mathsf{mod}~N^2)$ by running a secure protocol with $\mathcal{S}$.
Now the question is how to securely compute $x\cdot \gamma^{-1}~(\mathsf{mod}~N^2)$. It is easy to see that: 
\[x\cdot \gamma^{-1} = \addshare{x}_{\rm s}\cdot \gamma^{-1} + \addshare{x}_{\rm r} \cdot \gamma^{-1}~(\mathsf{mod}~N^2).\]
Since $\mathcal{S}$ can compute $\addshare{x}_{\rm s}\cdot \gamma^{-1}~(\mathsf{mod}~N^2)$ by itself, the only issue is how to share the cross term $\addshare{x}_{\rm r}\cdot \gamma^{-1}~(\mathsf{mod}~N^2)$ securely.
Indeed, this can be done with the help of a BMT of special form $a\cdot b = c~(\mathsf{mod}~N^2)$ where $\mathcal{S}$ holds $a$, $\mathcal{R}$ holds $b$, and the parties share $c$.\footnote{Any BMT $(\addshare{a}, \addshare{b}, \addshare{c})$ can be easily transformed to a special BMT by revealing $a$ to $\mathcal{S}$ and $b$ to $\mathcal{R}$, respectively.
In $\mathcal{F}_{\textsf{pre}}$, this can be simply done by letting $\mathcal{S}$ input $(a,0)$ and $\mathcal{R}$ input $(0, b)$.} 
With the BMT, $\mathcal{S}$ reveals $e \leftarrow \gamma^{-1} - a~(\mathsf{mod}~N^2)$ and $\mathcal{R}$ reveals $f \leftarrow \addshare{x}_{\rm r} - b~(\mathsf{mod}~N^2)$, then $\mathcal{S}$ computes $\addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm s} \leftarrow a \cdot f + \addshare{c}_{\rm s}~(\mathsf{mod}~N^2)$ and $\mathcal{R}$ computes $\addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm r} \leftarrow e\cdot f + b\cdot e + \addshare{c}_{\rm r}~(\mathsf{mod}~N^2)$.
$\mathcal{S}$ sends $\addshare{x}_{\rm s}\cdot \gamma^{-1} + \addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm s}~(\mathsf{mod}~N^2)$ to $\mathcal{R}$. In the end,  $\mathcal{S}$ holds $\gamma$ and $\mathcal{R}$ recovers $x\cdot \gamma^{-1}~(\mathsf{mod}~N^2)$ by setting 
\[x\cdot \gamma^{-1} = \addshare{x}_{\rm s}\cdot \gamma^{-1} + \addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm s} + \addshare{\addshare{x}_{\rm r}\cdot \gamma^{-1}}_{\rm r}~(\mathsf{mod}~N^2).\]
Now $x$ is multiplicatively shared between parties over $\mathbb{Z}^*_{N^2}$.

\smallskip 
\noindent\underline{\emph{Remark}}.
Note that additive sharing is over $\mathbb{Z}_{N^2}$ whereas multiplicative sharing is over $\mathbb{Z}^*_{N^2}$, we show our conversion still works and give explanation. 
Specifically, $\mathbb{Z}_{N^2}^*$ includes all elements in $\mathbb{Z}_{N^2}$ except $\{0, p, 2p, \cdots, (p\cdot q^2-2)\cdot p, (p\cdot q^2-1)\cdot p, q, 2q, \cdots, (q\cdot p^2-2)\cdot q, (q\cdot p^2-1)\cdot q\}$. 
It is clear that if $\gamma$ is accidentally sampled from $\mathbb{Z}_{N^2} \backslash \mathbb{Z}_{N^2}^*$, there will be no way to compute $\gamma^{-1}$. 
However, the bad probability of this accident is only $ \frac{|\mathbb{Z}_{N^2} \backslash \mathbb{Z}_{N^2}^*|}{|\mathbb{Z}_{N^2}|} < \frac{p\cdot q^2 + q\cdot p^2-1}{N^2} < \frac{p\cdot q^2+ q \cdot p^2}{N^2} = \frac{1}{p} +  \frac{1}{q}$, which is negligible.
In our protocol, $\mathcal{S}$ knows $p$ and $q$ so can always select $\gamma$ with inverse from $\mathbb{Z}_{N^2}^*$.
This introduces indistinguishable difference following our prior argument. 
Therefore, our conversion works over $\mathbb{Z}_{N^2}$ correctly and securely except with negligible failing/distinguishable probability. 
Besides that, we do not differentiate $\mathbb{Z}_{N^2}$ and $\mathbb{Z}^*_{N^2}$.


\noindent\textbf{Sharing Encrypted Message over $\mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$ Additively}.  
For a ciphertext $x = \mathsf{Enc}_{\mathsf{pk}}( m)$ that is multiplicatively shared over $\mathbb{Z}_{N^2}$, \ie, $\mathcal{S}$ has $\multshare{x}_{\rm s}$ and $\mathcal{R}$ has $\multshare{x}_{\rm r}$ such that $x = \multshare{x}_{\rm s} \cdot \multshare{x}_{\rm r}~(\mathsf{mod}~N^2)$, the parties can explore homomorphic property of Paillier encryption to additively share $m \in \mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$.
Note that $\mathcal{S}$ has Paillier public/secret key pair $(\mathsf{pk}, \mathsf{sk})$.
Specifically, $\mathcal{R}$ computes and sends a randomized ciphertext $x_{\beta} \leftarrow \multshare{x}_{\rm r} \cdot \mathsf{Enc}_{\mathsf{pk}}(\beta + \rho \cdot 2^{ \ell_{\mathsf{v}}})~(\mathsf{mod}~N^2)$ to $\mathcal{S}$, where $\beta \xleftarrow{\$}  \mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$ and $\rho \xleftarrow{\$} [ 0, 2^\lambda)$ are randomly sampled by $\mathcal{R}$.\footnote{We use Paillier's plaintext domain $\mathbb{Z}_N$ to hold messages of length $ \ell_{\mathsf{v}}$ where $2^{ \ell_{\mathsf{v}}} \ll |N|$. Here $\rho \cdot 2^{ \ell_{\mathsf{v}}}$ is used for statically hiding $m+\beta$, meanwhile still allows $\mathcal{S}$ to compute $m+\beta~(\mathsf{mod}~2^{ \ell_{\mathsf{v}}})$ correctly.}
$\mathcal{S}$ can compute $\multshare{x}_{\rm s}\cdot x_{\beta} = \mathsf{Enc}_{\mathsf{pk}}(m+\beta+\rho \cdot 2^{ \ell_{\mathsf{v}}})$ and decrypt it to learn $m+\beta~(\mathsf{mod}~2^{ \ell_{\mathsf{v}}})$. $\mathcal{R}$ has $-\beta~(\mathsf{mod}~2^{ \ell_{\mathsf{v}}})$.
Obviously, $\mathcal{S}$ and $\mathcal{R}$ finally additively share $m$ over $\mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$.
The parties can perform A2B conversion to transform $\addshare{m}$ over $\mathbb{Z}_{2^{ \ell_{\mathsf{v}}}}$ to boolean sharing $\boolshare{m}$ over $\mathbb{Z}_{2}^{ \ell_{\mathsf{v}}}$. 


\noindent\textbf{Security}.
We have Theorem~\ref{theorem:sos-he} for the security of our HE-based SOS protocol. The proof can be found in Appendices~\ref{appendix::2::a}.


\begin{theorem}\label{theorem:sos-he}
If Paillier encryption is semantically secure and $N$ is computationally hard to factorize, the oblivious selection protocol in Fig.~\ref{protocol:SOS-he} securely computes the functionality  $\mathcal{F}_{\textsf{sos}}^{(\mathsf{M})}$ in $(\mathcal{F}_{\rm pre})$-hybrid model under a semi-honest adversary. 
\end{theorem} 

\subsection{The Proposed PDTE Protocol}
With our data structure, decision tree algorithm and SOS protocols, it is straightforward to design our PDTE protocol modularly. 
We show the protocol in Fig.~\ref{protocol:PDTE} built on the top of an ideal SOS functionality.


\noindent\textbf{\textbf{PDTE Setup}}. 
${P}_0$ and ${P}_1$ perform necessary work to setup SOS functionality for tree array $\mathsf{A}_{\mathcal{T}}$ and feature array $\mathcal{X}$. 
Moreover, ${P}_0$ shares $\mathsf{A}_{\mathcal{T}}[0]$~(\ie, the root node)~with ${P}_1$ as the evaluation starting node. 
From the property of boolean sharing, the parties can parse the root bit-by-bit to get the sharing of all attributes $\boolshare{t}, \boolshare{l}, \boolshare{r}, \boolshare{v}$, and $\boolshare{c}$.


\noindent\textbf{\textbf{PDTE Evaluation}}. 
In each iteration, ${P}_0$ and ${P}_1$ first call SOS functionality $\mathcal{F}^{(\mathcal{X})}_{\rm SOS}$ to share ${\mathcal{X}[v]}$.
The parties then perform a secure comparison between $\boolshare{\mathcal{X}[v]}$ and $\boolshare{t}$ to compute a comparison result $\boolshare{b}$.
The evaluation can then decide which child becomes the next evaluation node by employing a MUX computation: $\boolshare{\mathsf{idx}} \leftarrow \boolshare{l} \oplus \boolshare{b} \cdot (\boolshare{l} \oplus \boolshare{r})$.
That is, the parties share $\boolshare{\mathsf{idx}} = \boolshare{l}$ if $b = 1$, otherwise $\boolshare{\mathsf{idx}} = \boolshare{r}$.

From the shared index $\mathsf{idx}$, the parities invoke $\mathcal{F}^{(\mathcal{X})}_{\rm SOS}$ to share $\mathsf{A}_{\mathcal{T}}[\mathsf{idx}]$. $\boolshare{t}, \boolshare{l}, \boolshare{r}, \boolshare{v}, \boolshare{c}$ are then updated correspondingly.
Besides, $\boolshare{c}$ is stored in $\boolshare{\mathsf{rst}}$ where the final classification label will stay in. 
Note that we encode a self-loop for each leaf node, thus $\boolshare{\mathsf{rst}}$ will always hold a correct classification label once the evaluation reaches a leaf node. 
Moreover, it is easy to hide length information: ${P}_0$ and ${P}_1$ just run $d$ iterations of evaluation. 
In the end, ${P}_0$ sends $\boolshare{\mathsf{rst}}_0$ to ${P}_1$, and ${P}_1$ recovers ${\mathsf{rst}}$ as classification result.

The protocol runs in $O(d)$ iterations with $d$ secure comparison and MUX operations. 
If the OT-based SOS protocol is used over $\mathcal{X}$ and a sublinear SOS protocol is used over $\mathsf{A}_{\mathcal{T}}$, then the total communication complexity is $O(n \ell d)$. 


\begin{figure}
	\framebox{\begin{minipage}{0.95\linewidth}

			{\bf Parameters}: Computational security parameter $\kappa$;
			${P}_0 $ provides a tree $\mathcal{T}$; ${P}_1$ provides a feature vector $\mathcal{X}$;
		    the longest tree depth $d$.
		
			
		\smallskip
		{\bf [Setup]}
		\begin{enumerate}
		    \item ${P}_0$ encodes its decision tree $\mathcal{T}$ to an array $\mathsf{A}_{\mathcal{T}}$.  
		    
			\item ${P}_0$ and ${P}_1$ invoke functionality $\mathcal{F}^{(\mathsf{A}_{\mathcal{T}})}_{\rm SOS}$. ${P}_0$ sends $(\textsc{Setup}, \mathsf{A}_{\mathcal{T}},  \ell_{\mathsf{v}})$ to $\mathcal{F}^{(\mathsf{A}_{\mathcal{T}})}_{\rm SOS}$ and ${P}_1$ sends $(\textsc{Setup})$ to $\mathcal{F}^{(\mathsf{A}_{\mathcal{T}})}_{\rm SOS}$.
			
			\item ${P}_0$ and ${P}_1$ invoke functionality $\mathcal{F}^{(\mathcal{X})}_{\rm SOS}$. ${P}_1$ sends $(\textsc{Setup}, \mathcal{X}, \ell)$ to $\mathcal{F}^{(\mathcal{X})}_{\rm SOS}$, and ${P}_0$ sends $(\textsc{Setup})$ to $\mathcal{F}^{(\mathcal{X})}_{\rm SOS}$. 
			
		    \item ${P}_0$ shares root node $\mathsf{A}_{\mathcal{T}}[0]$ with ${P}_1$. Both parties parse $\boolshare{\mathsf{A}_{\mathcal{T}}[0]}$ as $\boolshare{t}||\boolshare{l}||\boolshare{r}||\boolshare{v}||\boolshare{c}$.
		\end{enumerate}
		
		\smallskip 
		{\bf [Evaluation]}
		\begin{enumerate}
		  \item For $i \in [1, d]$
		    \begin{enumerate}
		        \item  ${P}_0$ sends $(\textsc{Eval}, \boolshare{v}_{\rm s})$ and ${P}_1$  sends $(\textsc{Eval}, \boolshare{v}_{\rm r})$ to $\mathcal{F}^{(\mathcal{X})}_{\rm SOS}$. 
		        In the end, ${P}_0$ and ${P}_1$ share $\boolshare{\mathcal{X}[v]}$.
		        
		        \item ${P}_0$ and ${P}_1$ run secure comparison protocol to compute  $\boolshare{b} \leftarrow \boolshare{\mathcal{X}[v]} > \boolshare{t}$.
		        
		        \item ${P}_0$ and ${P}_1$ compute index of next tree node $\boolshare{\mathsf{idx}} \leftarrow \boolshare{l} \oplus \boolshare{b} \cdot (\boolshare{l} \oplus \boolshare{r})$.
		        
		        \item ${P}_0$ sends $(\textsc{Eval} \boolshare{\mathsf{idx}}_{\rm 0})$, and ${P}_1$  sends $(\textsc{Eval}, \boolshare{\mathsf{idx}}_{\rm 1})$ to $\mathcal{F}^{(\mathsf{A}_{\mathcal{T}})}_{\rm SOS}$. 
		        In the end, ${P}_0$ and ${P}_1$ share $\boolshare{\mathsf{A}_{\mathcal{T}}[\mathsf{idx}]}$.
		        
		        \item parse $\boolshare{t}||\boolshare{l}||\boolshare{r}||\boolshare{v}||\boolshare{c} \leftarrow \boolshare{\mathsf{A}_{\mathcal{T}}[\mathsf{idx}]}$.
		        
		        \item set $\boolshare{\mathsf{rst}} \leftarrow \boolshare{c}$.
		    \end{enumerate}
		    
		    \item ${P}_0$ and ${P}_1$ reveal ${\mathsf{rst}}$ to ${P}_1$ as output. 
		\end{enumerate}
	\end{minipage}}
	\caption{Our PDTE Protocol}
	\label{protocol:PDTE}

\end{figure}


\noindent\textbf{Optimization 1 - Reduce SOS Invocations}. 
We can reduce the number of SOS invocations by exploring a data locality property in decision tree evaluation. 
Our observation is that tree evaluation will only go from a parent to one of its children.
Therefore, we can pack the parent with its children together as a bigger node to reduce invocations of oblivious selection. 
We call the packed node as a \emph{cluster}. 
If the parent node is a leaf, $\mathcal{S}$ needs to allocate two dummy nodes to make the cluster's size indistinguishable from others.
The parties then use oblivious selection to share the desired cluster between parties.
Since our SOS protocol supports SIMD mode, the parties can share a cluster by only one invocation, whereas it requires two in the original protocol. 
In this way, we reduce PDTE evaluation invocation from $d$ to $\lceil d/2 \rceil$.
We can generalize the idea to pack a parent node with its descendants in the following $q$ layers, reducing invocations from $d$ to $\lceil d/q \rceil$.

The remaining issue is how to traverse within a cluster obliviously.
This can be done by $q$ MUX operations, and each is over two smaller sub-trees.
However, the total communication for traversing within a cluster will be $O(2^q)$. 
In practice, we can set $q = 2$ or 3 to reduce 50\% or 67\% rounds from SOS protocol while not increasing communication too much. 

\noindent\textbf{Optimization 2 - Reduce Local Computation}. 
In our PDTE protocol, each oblivious selection causes a linear scan over the whole decision tree, incurring $O(d\cdot m)$ computation in total.
We can reduce the overhead when $\mathcal{T}$ is a complete tree.
That is, instead of performing the scan over all nodes, the parties only need to run oblivious selection over $i$-th layer of $\mathcal{T}$ for the $i$-th iteration of evaluation. 
Therefore, the total local computation from SOS will only be $O(m)$.
Note that we can not use this optimization directly over sparse trees; otherwise, $\mathcal{R}$ can learn the tree structure of each layer, \textit{e.g.}, number of nodes of each layer.
Nevertheless, we can always transform a non-complete tree into a complete one by padding dummy nodes and then we can optimize the padded tree. 
In practice, padding is cost-effective for those near-complete trees but not for sparse trees.

\noindent\textbf{Security}.
We have Theorem~\ref{theorem:2} towards security of our PDTE protocol. The proof can be found in Appendices~\ref{appendix::3::a}.


\begin{theorem}\label{theorem:2}
The PDTE protocol in Fig.~\ref{protocol:PDTE} securely computes the functionality $\mathcal{F}_{\rm DT}$ in $(\mathcal{F}^{(\mathsf{A}_{\mathcal{T}})}_{\rm SOS}, \mathcal{F}^{(\mathcal{X})}_{\rm SOS})$-hybrid model against semi-honest adversary.
\end{theorem}
\section{Introduction}
Decision trees are popular machine learning techniques for data classification. 
Due to their effectiveness and simplicity, 
decision trees have been widely adopted in various applications, such as spam filtering~\cite{bratko2006spam}, credit risk assessment~\cite{koh2006two} and disease diagnosis~\cite{podgorelec2002decision}.
Typically, there are two parties: a tree holder holding a tree model; and a feature provider holding a feature vector that needs to be classified.
However, performing the evaluation processed in such a two-party setting can lead to privacy issues. On the one hand, if the feature vectors is sent in plaintext to the model provider it might reveal individuals' information that are privacy sensitive. This might be the case in healthcare and credit risk assessment applications. On the other hand, the model is a valuable asset for the model provider. If freely accessible, it may leak sensitive information about the training data. 

Private Decision Tree Evaluation~(PDTE) protocols~\cite{kiss2019sok,wu2016privately,tai2017privacy}  address the above privacy issues.
A PDTE protocol enables two reciprocal-distrustful parties to collaboratively perform the tree evaluation without revealing any sensitive information to each other.

There are several crucial aspects when dealing with decision trees under privacy settings. For instance, in non-private decision tree evaluations, the tree is traversed from root to leaf along one path. Ideally, PDTE should also traverse the tree along on path. In this case, the total number of comparisons is linear to the depth $d$ of the tree and sublinear to the size of the tree. However, revealing the evaluation path can leak sensitive information even when the tree and the feature vector are well protected (\textit{e.g.}, by encryption). 
For instance, given the evaluation path, the tree holder can learn whether two feature vectors have the same range of attributes by comparing two evaluation paths; the feature provider can learn  information about the tree structure during evaluation.
In addition, even the length of a decision path can reveal significant information.
For example, if the length is unique among all decision paths, it will immediately reveal the path being evaluated. 

To protect the evaluation path, previous PDTE protocols~\cite{bost2015machine,wu2016privately,tai2017privacy,kiss2019sok} pad the tree to be complete or near-complete and run comparisons for all internal nodes to conceal the decision path information.  
As a consequence, these protocols suffer from (super) linear computation/communication complexity and are inefficient when evaluating large trees, \textit{e.g.}, trees containing millions of nodes~\cite{catlett1991overprvning}.

\begin{table*}[!ht]
    \footnotesize  
    \renewcommand{\arraystretch}{1.3}
	\caption{S{\upshape ummary of Existing Two-party PDTE Protocols}.}
	
	\label{tab::comparison:twoparty}
	\centering 
	\begin{threeparttable
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
		\hline
		\hline
		\textbf{Protocol} & \textbf{Comparison} & \textbf{Communication} & \textbf{Round} & \textbf{Leakage} &\textbf{SC}&  \textbf{One-time Setup} & \textbf{Primitives}\\
		\hline
		\hline

		\hline
		Bost \textit{et~al. }~\cite{bost2015machine} & $\lceil m/2 \rceil$ & $O(n + m)$ & $\geq$ 6 & $m$ & \Circle & \CIRCLE & Leveled-FHE\\
		\hline
		~ Wu \textit{et~al. }~\cite{wu2016privately} & $2^d$ & $O(2^{d}+ (n + m)\ell)$ & 6 & $m,d$ & \Circle &\CIRCLE & AHE,OT\\
		\hline
		~ Tai \textit{et~al. }~\cite{tai2017privacy} & $\lceil m/2 \rceil$ & ${O}((n + m)\ell)$ & 4 & $m$ & \Circle & \CIRCLE & AHE\\
		\hline
		~ Kiss \textit{et~al. }~\cite{kiss2019sok}(GGG) & $d$ & ${O}(\overline{m}\ell)$ & 2 & $\overline{m},d$ & \Circle & \Circle & GC,OT\\
		\hline
		~ Kiss \textit{et~al. }~\cite{kiss2019sok}(HHH) & $\lceil m/2 \rceil$ & ${O}((n + m)\ell)$ & 4 & $m$ & \Circle & \CIRCLE & AHE\\
		\hline
		~ Brickell \textit{et~al. }~\cite{brickell2007privacy} & $d$ & ${O}((n + m)\ell)$ & 2 & $m$ & \Circle & \Circle & AHE,GC,OT\\
		\hline
        ~ Joye \textit{et~al. }~\cite{joye2018private} & $d$ & $O(d(\ell+n)+2^d)$ & $2d$ & $d$ & \Circle & \CIRCLE & AHE, OT\\
        \hline
		~ Tueno \textit{et~al. }~\cite{tueno2019private}(OT)& $d$ & $O((m+n)\ell)$ & $4d$ & $d$ & \Circle & \CIRCLE & SS,OT\\
		\hline
		~ Tueno \textit{et~al. }~\cite{tueno2019private}(GC)& $d$ & $O((m+n)\ell)$ & $4d$ & $d$ & \Circle & \CIRCLE & SS,GC,OT\\
		\hline
		~ Tueno \textit{et~al. }~\cite{tueno2019private}(ORAM)& $d$ & $O(d^4\ell)$ & $d^2+3d$ & $d$ & \CIRCLE & \CIRCLE & SS,ORAM,GC\\
		\hline
		~ Ma \textit{et~al. }~\cite{ma2021let} & $d$ & $O(dn\ell)$ & $2d - 1$ & $m,d$ & \LEFTcircle & \LEFTcircle & SS,GC,OT\\
		\hline
		~ Our PRF-based & $d$ & $O(dn\ell)$ & $(3r_{{F}} + 5)d$ & $m,d$ & \CIRCLE & \CIRCLE & SS,OT,PRF \\
		\hline
		~ Our HE-based & $d$ & $O(dn)$ & $8d$ & $m,d$ & \CIRCLE & \CIRCLE & SS,OT,AHE \\
		\hline
		\hline
	\end{tabular}

	\footnotesize{ \textbf{SC} represents sublinear communication, \textbf{One-time Setup} denotes the tree holder is not required to re-send the tree to the feature provider. $m$: the number of tree nodes, $\overline{m}$: the number of tree nodes in a depth-padded tree, see~\cite{kiss2019sok}, $n$: the dimension of a feature vector, $d$: the longest depth of a tree, $\ell$: the bit size of feature values, $r_{{F}}$: the number of rounds required for securely evaluating PRF ${F}$. \CIRCLE: yes, \Circle: no, \LEFTcircle: partially support.


	}
    \end{threeparttable}
\end{table*}

\noindent\textbf{Techniques}. 
This paper proposes a PDTE protocol to obliviously perform decision tree evaluation without leaking the tree model, the feature values or the evaluation path. 
More importantly, our protocol has a sublinear communication complexity without relying on generic RAM-based secure computation~\cite{tueno2019private}. 

To hide which node is being accessed during decision tree evaluation, we formalize a functionality called Shared Oblivious Selection~(SOS).  
The functionality allows two parties to obliviously read an element from an array, meanwhile hiding the location and the selected value with secret sharing. 
We design two efficient SOS protocols based on different techniques. 
Our first PRF-based SOS protocol adapts Floram~\cite{doerner2017scaling}, which is a communication-efficient Oblivious RAM~(ORAM) protocol, for read-only mode.
We propose a new preprocessing technique, moving most of its communication overhead to the offline phase. 
We also design optimized masking mechanisms to make the SOS protocol more efficient. 
Our second HE-based SOS protocol explores the additive homomorphic property of Paillier encryption~\cite{paillier1999public} to eliminate two-party PRF evaluation. 
This is done by a share conversion protocol from additive arithmetic sharing to multiplicative arithmetic sharing. 
Notably, both SOS protocols achieve sublinear offline communication and constant online communication. 


We design our PDTE protocols by combining a tree encoding method, the SOS functionality and secure computation. 
By initializing SOS functionality with either PRF-based or HE-based SOS protocols, we obtain two PDTE protocols with different trade-offs. 
Our PDTE protocols enjoy sublinear communication with the best security properties of existing PDTE protocols.
We prove the security against a semi-honest adversary and analyze its complexity.
As shown in Table~\ref{tab::comparison:twoparty}:
although many existing PDTE protocols can support sublinear comparisons, only the ORAM-based PDTE protocol~\cite{tueno2019private} requires sublinear communication both in the online and offline phases.
We also observe that the two-party PDTE protocol from Ma~\textit{et~al. }~\cite{ma2021let} only supports one single classification under standard PDTE security definition.
It is unclear how to enhance \cite{ma2021let} to support multiple invocations without re-sending new permuted encrypted trees, which essentially incurs linear (offline) communication. 
However, in some real applications like disease diagnosis, the feature provider (patient) may frequently or periodically interact with the tree holder (health center) to monitor his/her health. 
Our protocols fully support multiple PDTE queries but only need one-time setup.
The setup still needs linear communication, but the overhead will be amortized across queries.

We implemented our PDTE protocols and performed  experiments to evaluate the communication and computation performance for different trees under different network conditions. 
We also compared the performance of our PDTE with the protocols proposed in~\cite{kiss2019sok,tueno2019private,ma2019privacy}.
The results show that our PRF-based protocol reduces communication around 62$\times$ for large trees when compared to~\cite{kiss2019sok} and 0.2$\times$ than~\cite{ma2021let}. In the WAN setting with high network latency, our HE-based protocol outperforms the state-of-the-art~\cite{kiss2019sok} by 83$\times$ in terms of online computation.
When compared with \cite{tueno2019private}, our PRF-based protocol requires approximately $40\times$ less total running time while our HE-based protocol saves around $5.5\times$ total running time.
Experiments show that our PDTE protocols are practical and scalable, especially for the evaluation of large trees.


\noindent\textbf{Contributions}. Our contributions can be summarized as below: 
\begin{itemize}

\item We propose two SOS protocols that enable two parties to collaboratively and obliviously share an element from an array using only sublinear communication. 


\item We propose two sublinear-communication PDTE protocols by carefully combining a modified tree encoding method, the SOS functionality and efficient secure computation techniques. 
We also propose various optimization techniques to make our protocols even more efficient. 

\item We implemented our PDTE protocols and evaluate their performance. 
The experimental results show that our protocols are practical: in particular, our PDTE protocols are scalable when evaluating large trees. 

\end{itemize}

\noindent\textbf{Paper organization}. 
We introduce background information in Section~\ref{sec:background}, and provide an overview of our techniques in Section~\ref{sec:ovewview}. 
We construct our primitives and protocols in Section~\ref{sec:construction}, and report experiments and evaluation results in Section~\ref{section:experiment}. 
We summarize related work in Section~\ref{section:related} and conclude the paper in Section~\ref{section:conclusion}.


\section{Overview of Our Approach} \label{sec:ovewview}
In this section, we show our protocol setting, security requirement and techniques overview for our PDTE protocol. 

\subsection{Protocol Setting and Security Guarantee} 
Our PDTE protocol is in the two-party setting in which a tree holder ${P}_0$ owns a decision tree model $\mathcal{T}$ and a feature provider ${P}_1$ provides a feature vector $\mathcal{X} = (x_1, \cdots, x_n)$.
At the end of the protocol, ${P}_1$ receives a prediction $\mathcal{T}(\mathcal{X})$.
We assume both parties have sufficient storage to store $\mathcal{T}$ or $\mathcal{X}$ locally.
In our protocol, there is no third-party involved in the computation.  

We assume an adversary is static semi-honest.
A corrupted party will strictly follow the protocol but may attempt to learn as much information as possible.
Formally, let $\mathcal{F}_{\rm DT}(\mathcal{T}, \mathcal{X})$ $\rightarrow$ $(\mathcal{F}_0(\mathcal{T},$ $\mathcal{X}), \mathcal{F}_1(\mathcal{T}, \mathcal{X}))$ be the decision tree functionality 
where a decision tree model $\mathcal{T}$ and a feature vector $\mathcal{X}$ is provided by ${P}_0$ and ${P}_1$ respectively.
In the end, the output of $\mathcal{F}_{\rm DT}$ is that ${P}_i$ obtains $\mathcal{F}_i(\mathcal{T}, \mathcal{X})$ for $i \in \{0,1\}$.  
A PDTE protocol ${\Pi}$ securely computes $\mathcal{F}_{\rm DT}$ if there exist PPT simulators $\textsf{Sim}_0$ and $\textsf{Sim}_1$ such that for any $\mathcal{T}$ and $\mathcal{X}$: 
\begin{align*}
&\{\textsf{Sim}_0(1^{\lambda}, \mathcal{T}, \mathcal{F}_0(\mathcal{T}, \mathcal{X}))\} 
\overset{c}{\equiv} \{ \textsf{View}^{\Pi}_0(1^{\lambda}, \mathcal{T}, \mathcal{X}) \}, \\
& \{\textsf{Sim}_1(1^{\lambda}, \mathcal{X}, \mathcal{F}_1(\mathcal{T}, \mathcal{X}))\}
\overset{c}{\equiv} 
\{ \textsf{View}^{\Pi}_1(1^{\lambda}, \mathcal{T}, \mathcal{X}) \}.
\end{align*}

For our setting, $\mathcal{F}_0(\mathcal{T},\mathcal{X})=\{\perp, \mathcal{L}_0(\mathcal{X})\}$ and $\mathcal{F}_1(\mathcal{T}, \mathcal{X}) = \{\mathcal{T}(\mathcal{X}),$ $\mathcal{L}_1(\mathcal{T})\}$. $\mathcal{L}_0$ and $\mathcal{L}_1$ denote two stateless leakage functions where $\mathcal{L}_0(\mathcal{X}) = \{n\}$ and $\mathcal{L}_1(\mathcal{T}) = \{m, d\}$, \ie, ${P}_0$ obtains no output but only the number of features $n$ in the query whereas the output of ${P}_1$ contains classification result $\mathcal{T}(\mathcal{X})$, {the number of tree nodes $m$, and the length of longest decision path $d$}. 



\subsection{Design Goals}
\begin{itemize}
    
    \item We aim to achieve a high security standard for our PDTE protocol. 
    The protocol should only output the classification result to the feature provider.
    Besides that, the parties only learn minimal leakages as we defined. 
   
   
    
    \item We aim to design PDTE protocol with sublinear communication, and with concretely practical efficiency than construction from generic ORAM-based secure computation. 
    
    
    \item We aim to design our PDTE protocol in a modular manner. This allows us to optimize each component for the whole PDTE protocol, which also allows us to argue the security of our PDTE protocol easily. 
    
\end{itemize}


\begin{figure
	\centering 

	\includegraphics[height=1.2in]{figure/DT-circle.pdf} 
	\caption{{A Modified Decision Tree}} 
	\label{fig:DT-circle} 
\end{figure} 


\smallskip
\subsection{Technique Overview}

\noindent\textbf{Encoding Decision Trees and Feature Vectors}. 
We follow the OAI approach~\cite{tueno2019private} to encode decision trees.
The difference is that we modify a traditional decision tree as shown in Fig.~\ref{fig:DT-circle}. 
We redirect each leaf node by setting its left and right children indexing to the leaf itself.
The modified decision tree is encoded as an array $\mathsf{A}_{\mathcal{T}}$ shown in Fig.~\ref{fig:tree}. 
A node in the tree is stored in $\mathsf{A}_{\mathcal{T}}$ in Depth First Search~(DFS) order, and we use $\mathsf{A}_{\mathcal{T}}[i]$ to store all necessary information of the $i$-th node. 
Specifically, $\mathsf{A}_{\mathcal{T}}[i]$ is constructed by five values: 1) threshold, $t$; 2) left child index, $l$; 3) right child index, $r$; 4) feature ID, $v$ and 5) classification label, $c$.
For example, the right most leaf in Fig.~\ref{fig:tree} can be represented as $\mathsf{A}_{\mathcal{T}}[4] = a||4||4||b||c_3$, where $a \xleftarrow{\$} R$ and $b \in [0,n-1]$. 
Similarly, a feature vector from the feature provider can be naturally represented as an array $\mathcal{X}$ of length $n$.

\begin{algorithm
\caption{$\mathsf{rst}\leftarrow \textsf{DT}(\mathsf{A}_{\mathcal{T}}, \mathcal{X})$}\label{alg:dte}
    \begin{algorithmic}[1]
    \State $\mathsf{idx} \leftarrow 0, \mathsf{rst} \leftarrow \perp$
    \For{$0\le i <d$}
        \State \label{line3} $ t||l||r||v||c \leftarrow \mathsf{A}_{\mathcal{T}}[\mathsf{idx}]$
        \State \label{line4} $ b \leftarrow \mathcal{X}[v] < t$
        \State \label{line5}  $ \mathsf{idx} \leftarrow r \oplus b\cdot (l\oplus r)$ \Comment{if $b = 1$, $\mathsf{idx} = l$; else $\mathsf{idx} = r$ }
        \State \label{line6} $ \mathsf{rst} \leftarrow c$
    \EndFor
    
    \State \Return $\mathsf{rst}$
    \end{algorithmic}
\end{algorithm}

\noindent\textbf{The Proposed Decision Tree Algorithm}. 
Given a decision tree array $\mathsf{A}_{\mathcal{T}}$ and a feature array $\mathcal{X}$, we can perform decision tree evaluation over the two arrays. 
Algorithm~\ref{alg:dte} shows the algorithm, notably, it always runs $d$ iterations to output a correct classification result, independent of which path is taken.


The algorithm starts from the root node, \ie, $\mathsf{idx} = 0$, and it allocates a value $\mathsf{rst}$ for classification result.
In each iteration, the algorithm first selects a node $t||l||r||v||c \leftarrow  \mathsf{A}_{\mathcal{T}}[\mathsf{idx}]$ according to $\mathsf{idx}$.
From the feature ID $v$, the algorithm can select $\mathcal{X}[v]$, and do a comparison $b \leftarrow \mathcal{X}[v] < t$.
If $b = 1$, then set $\mathsf{idx} \leftarrow l$, otherwise $\mathsf{idx} \leftarrow r$.
In the end of each iteration, update $\mathsf{rst} \leftarrow c$. 
Due to our modification to decision tree, we can ensure that $\mathsf{rst}$ will hold a correct classification result once the evaluation reaches a leaf.
Indeed, this also ensures us to hide the length of the longest path by setting iteration number as $d'$ where $d'\ge d$. Note that setting $d'\ge d$ also hides $d$.
For simplicity, in this paper, we take $d'=d$. 

\noindent\textbf{Challenges and Solutions}. 
Things are tricky when evaluating Algorithm~\ref{alg:dte} in the secret domain. 
A basic requirement is to seal all values from both parties. 
For this part, we observe that the involved computation including comparison~(line.\ref{line4}, Algorithm~\ref{alg:dte}) and 1-out-of-2 MUX operation~(line.\ref{line5}, Algorithm~\ref{alg:dte}).
We choose boolean sharing for the underlying secret-sharing scheme because it matches well with performing bite-level secure computation.
For secure comparison and secure MUX protocol, we use existing protocols~\cite{demmler2015aby} directly. 

However, hiding intermediate values is not sufficient to get rid of all the leakages. 
Taking node selection as an example~(line.\ref{line3}, Algorithm~\ref{alg:dte}), if the secure computation leaks the memory access pattern during each iteration, the client can learn $\mathsf{idx}$ directly, then the client learns decision path, which is not allowed from our security requirement.
The goal here is to obliviously share $\mathsf{A}_{\mathcal{T}}[\mathsf{idx}]$ between parties where $\mathsf{A}_{\mathcal{T}}$ is provided by the tree holder and $\mathsf{idx}$ is also secret-shared, but neither party learns $\mathsf{idx}$ or $\mathsf{A}_{\mathcal{T}}[\mathsf{idx}]$\footnote{{In our protocol, ${\mathsf{idx}}$ is secret-shared from previous secure computation, which means neither party learns the underlying value.
Our definition of SOS functionality also ensures $\mathsf{M}[\mathsf{idx}]$ is inherently randomly shared.}
}.

\begin{figure
	\centering 

	\includegraphics[height=1.2in]{figure/tree-array.pdf} 
	\caption{Encoding A Decision Tree as an Array: `$\blacktriangle$' represents the value can set as any value, and `$\bigstar$' represents the value can be randomly selected from $[0,1,\dots,n-1]$, where $n$ is the dimension of corresponding feature vector} 
	\label{fig:tree} 
\end{figure}


\begin{figure}

    \framebox{\begin{minipage}{0.93\linewidth}
       
    		\centerline{\textbf{Functionality $\mathcal{F}^{(\mathsf{M})}_{\rm sos}$}} 
    		\smallskip
    		{\bf Parameters}: Two parties denoted as $\mathcal{S}$ and $\mathcal{R}$. 
    		\begin{packed_item}
    			\item \textbf{Setup}: upon receiving (\textsc{Setup}, $\mathsf{M}$, $ \ell_{\mathsf{v}}$) from $\mathcal{S}$ and (\textsc{Setup}) from $\mathcal{R}$, store $\mathsf{M}$. 
    			
    			\item \textbf{Select}: upon receiving $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm s})$ from $\mathcal{S}$ and $(\textsc{Select}, \boolshare{\mathsf{idx}}_{\rm r})$ from $\mathcal{R}$:
    			\begin{itemize}
    			   
    			    \item recover $\mathsf{idx} \leftarrow \boolshare{\mathsf{idx}}_{\rm s} \oplus \boolshare{\mathsf{idx}}_{\rm r}$
    			    \item $e \xleftarrow{\$} \mathbb{Z}_{2}^{ \ell_{\mathsf{v}}}$, send $e$ to $\mathcal{S}$ and $e \oplus \mathsf{M}[\mathsf{idx}]$ to $\mathcal{R}$
    			\end{itemize}
    		\end{packed_item}
    	\end{minipage}
	}
	\centering \caption{The Shared Oblivious Selection Functionality $\mathcal{F}_{\rm sos}^{(\mathsf{M})}$
	}\label{Fun:SOS}
\end{figure}


In Fig.~\ref{Fun:SOS}, we formalize the above task as a Shared Oblivious Selection~(SOS) functionality.
A possible way to realize $\mathcal{F}_{\rm sos}^{(\mathsf{M})}$ is via generic ORAM-based secure computation.
Tueno~\textit{et~al. }~\cite{tueno2019private} use Circuit ORAM~\cite{wang2015circuit} to design a sublinear-communication PDTE protocol. 
However, this approach requires the parties to evaluate ORAM circuit \emph{inside} secure computation, causing massive computation and communication overhead in practice.  
Our goal is to minimize the overhead by designing specialized SOS protocols. 
Our design follows from the observation that ORAM is overkill since PDTE protocols only need read operations.
Therefore, what we need is a secure computation protocol over Oblivious Read-Only-Memory~(OROM).
Such simplification allows us to design specialized SOS protocols to compute $\mathcal{F}_{\rm sos}^{(\mathsf{M})}$ more efficiently. 
We also propose many optimizations to improve efficiency both asymptotically and concretely, some of them are of independent interests. 

\noindent\textbf{Put All Together}. 
We will use both SOS protocol and boolean-sharing based secure computation to evaluate our modified decision tree evaluation algorithm.
Intuitively, when performing decision tree evaluation using secure computation, all intermediate values are secret-shared between the parties, and the parties run secure computation to traverse the decision tree obliviously. 
Note that the algorithm itself does not leak length information. We further use oblivious selection to conceal access pattern leakage. 
The parties cannot learn which decision path is taken since everything is evaluated in the secret domain. 
We also propose concrete optimizations in our PDTE protocol.
We will discuss our techniques in detail in the next section.
\section{Background}\label{sec:background}

\iffalse 
\begin{figure}[!t]
	\centering
	\renewcommand{\arraystretch}{1.3}
	\includegraphics[width=2.8in]{figure/padding.pdf}
	\caption{Padding of a decision tree}
	\label{fig:padding}
\end{figure}
\fi 


In this section, we introduce background information of decision tree evaluation,  cryptographic primitives and definitions used in this paper. 
Table~\ref{table::notion} shows notations used throughout this paper.
\begin{table
\small
   

	\caption{Description of Symbols \& Notations}
	\label{table::notion}
    \centering	
		\begin{tabular}{c|l }  
			\cline{1-2}
			 {\bf Symbols} & {\bf Descriptions} \\
			\hline
			$\kappa$ & computational security parameter \\
			$\lambda$ & statistical security parameter \\
			$m$ & the number of nodes in a decision tree \\
		
			$d$ & the length of the longest path in a decision tree\\
			$d'$ & a pre-defined depth satisfying $d' \ge d$\\	 
			$\mathcal{T}$ & the decision tree \\
			$\mathcal{X} = (x_1,..., x_n)$ & feature vector of length $n$\\
			$\mathsf{A}_{\mathcal{T}}$ & the encoded array for a decision tree $\mathcal{T}$\\
			$t/l/r/v/c$ & the threshold/left child index/right child index/\\
			 & feature ID/label of a tree node~(some non-existing \\
			 & items will be given during tree encoding)\\
			$\ell$ & the default boolean sharing bit length, \ie, $\ell = |t| =$ \\
			 &$|l| = |r| = |v| = |c| = |x_i|$ \\
			$ \ell_{\mathsf{v}}$ & the bit length of array elements\\
			$ \ell_{\mathsf{b}}$ & the bit length of PRF outputs, \textit{e.g.}, 64, 128, or 256 \\
			$ B = \lceil \frac{ \ell_{\mathsf{v}}}{ \ell_{\mathsf{b}}} \rceil$ &  the number of blocks for $ \ell_{\mathsf{v}}$-bit element\\
			\hline
		\end{tabular}
\end{table}

\subsection{Decision Tree Evaluation}

In a decision tree $\mathcal{T}$, each non-leaf node, also called \textit{decision node}, has a threshold $t \in \mathbb {Z}_{2^\ell}$ and each leaf node, also known as \textit{classification label}, has a label value $c \in \mathbb {Z}_{2^\ell}$.
A \emph{feature vector}, \ie, a query, is the data to be classified and is denoted as $\mathcal{X} = (x_1,..., x_n) \in \mathbb{Z}_{2^{\ell}}^n$ with $n$ feature values. 

Decision tree evaluation takes a tree and a feature vector as input and outputs a label as the classification result. 
The evaluation starts from the root, and it compares the threshold $t_1$ with $x_{v(1)}$ where $v : i \in \{1, 2 , ... , m\} \rightarrow j \in \{1, 2 , ... , n\}$ is a map that determines which feature value in $\mathcal{X}$ should be compared with the threshold of $i$-th node. 
We will simply use $x_{v_i}$ and $x_{v(i)}$ interchangeably throughout the paper. 
Depending on whether the comparison results in 1~($x_{v_i}<t_i$) or 0~($x_{v_i} \geq t_i$), the evaluation goes either to the left or to the right child and continues the comparison until reaching a leaf. 
We call this path from the root to a leaf as the \emph{decision path} or \emph{evaluation path} for input $\mathcal{X}$. 
The \emph{depth} for a decision tree is the length of the longest path.
Without ambiguity, we use $\mathcal{T}(\mathcal{X})$ to denote the classification result when using $\mathcal{T}$ over feature vector $\mathcal{X}$. 

\subsection{Cryptographic Primitives}

\smallskip 
\noindent\textbf{Oblivious Transfer (OT).}
OT allows a receiver to obliviously choose one out of many values from a sender~\cite{goldreich2009foundations}.
The security of OT guarantees that the receiver only learns the chosen message, and the sender has no idea which value is chosen by the receiver.
OT is generally computationally expensive since it requires public-key operations.
With OT extension protocols~\cite{ishai2003extending}, it is efficient to generate (polynomially) many OTs from a small number of OTs.

\noindent\textbf{Boolean Sharing.}
We denote boolean sharing $\boolshare{x}$ as sharing of $x \in \mathbb{Z}_{2}$. For a two-party case, $\boolshare{x}$ denotes ${P}_0$ holds $\boolshare{x}_0$ and ${P}_1$ holds $\boolshare{x}_1$, such that $x = \boolshare{x}_0 \oplus \boolshare{x}_1$, where $\oplus$ represents bitwise XOR. 
For boolean sharing $\boolshare{x}$ and $\boolshare{y}$, ${P}_0$ and ${P}_1$ can compute the following operations over shares without interaction. 
Here $\oplus$ and $\cdot$ denotes addition and multiplication over $\mathbb{Z}_2$. 
\begin{packed_item}
    \item $\boolshare{z} \leftarrow \boolshare{x} \oplus \boolshare{y}$: Given $\boolshare{x}$ and $\boolshare{y}$, to compute boolean sharing of $z = x\oplus y$, ${P}_0$ just computes $\boolshare{z}_0 \leftarrow \boolshare{x}_0 \oplus \boolshare{y}_0$ and ${P}_1$ computes $\boolshare{z}_1 \leftarrow \boolshare{x}_1 \oplus \boolshare{y}_1$. 
    
    \item $\boolshare{z} \leftarrow \boolshare{x} \oplus c$: Given $\boolshare{x}$ and a constant $c$, to compute boolean sharing of $z = x\oplus c$, ${P}_0$ just computes $\boolshare{z}_0 \leftarrow \boolshare{x}_0 \oplus c$ and ${P}_1$ computes $\boolshare{z}_1 \leftarrow \boolshare{x}_1$. 
    
    \item $\boolshare{z} \leftarrow c \cdot \boolshare{x}$: Given a constant $c \in \mathbb{Z}_2$ and a boolean sharing $\boolshare{x}$, to compute boolean sharing of $z = c  \cdot x$, ${P}_0$ just computes $\boolshare{z}_0 \leftarrow c  \cdot  \boolshare{x}_0$ and ${P}_1$ computes $\boolshare{z}_1 \leftarrow  c  \cdot  \boolshare{x}_1$. 
\end{packed_item}

${P}_0$ and ${P}_1$ need to perform an interactive protocol to compute $\boolshare{z} \leftarrow \boolshare{x}  \cdot \boolshare{y}$.
One of efficient approaches is using a Beaver Multiplication Triple~(BMT)~\cite{beaver1995precomputing}. 
A BMT $(\boolshare{a}, \boolshare{b}, \boolshare{c})$ satisfies $a  \cdot b = c$.
Suppose ${P}_0$ and ${P}_1$ have pre-shared a BMT $(\boolshare{a}, \boolshare{b}, \boolshare{c})$, then they can compute $\boolshare{z} \leftarrow \boolshare{x}  \cdot \boolshare{y}$ efficiently.
Specifically, ${P}_0$ and ${P}_1$ first compute $\boolshare{e} \leftarrow \boolshare{x}\oplus \boolshare{a}$ and $\boolshare{f} \leftarrow \boolshare{y}\oplus \boolshare{b}$, and reveal $e$ and $f$.
In the end, they compute $\boolshare{z} \leftarrow \boolshare{c} \oplus (e \cdot \boolshare{b}) \oplus (f \cdot \boolshare{a}) \oplus (e \cdot f)$, which can be done by local computation. 
BMTs over $\mathbb{Z}_2$ can be efficient prepossessed by OT extension~\cite{kolesnikov2013improved}. 

In this paper, we will mainly use boolean sharing over $\mathbb{Z}_{2}^{\ell}$ for secure computation. 
The parties share each bit of $x$ using boolean sharing, and computation is done bit-by-bit.

\noindent\textbf{Arithmetic Sharing}. 
We denote sharing a secret $x \in \mathbb{Z}_{n}$ with arithmetic sharing as $\addshare{x}$, such that ${P}_0$ holds $\addshare{x}_0 \in \mathbb{Z}_n$ and ${P}_1$ holds $\addshare{x}_1 \in \mathbb{Z}_{n}$ satisfying $x = \addshare{x}_0 + \addshare{x}_1~(\mathsf{mod}~n)$. 
Arithmetic sharing is an ideal sharing semantic for computing arithmetic operations such as addition, subtraction and multiplication.
Adding arithmetic-shared $\addshare{x}$ with $\addshare{y}$ or adding $\addshare{x}$ with a constant $c \in \mathbb{Z}_n$ can be efficiently done by local computation, 
and multiplication between two shared data can be done with the help of a BMT over $\mathbb{Z}_n$.

\noindent\textbf{Share Conversion}.
Different sharing methods have their advantages/disadvantages for different kinds of computation. 
In particular, boolean sharing is friendly to the boolean circuit, including XOR, AND, \textit{etc.}, while arithmetic sharing is friendly to arithmetic computation such as addition and multiplication.  
Typical computation usually contains different types of computation, thus it is better to mix-use different types of sharing forms for better efficiency.
Share conversion techniques can be used for converting between boolean sharing and arithmetic sharing:

\begin{packed_item}
    \item \emph{Boolean to Arithmetic~(B2A) conversion} : Given $\boolshare{x}$ over $\mathbb{Z}_2^{\ell}$, B2A conversion transforms $\boolshare{x}$ to its arithmetic sharing $\addshare{x}$ over $\mathbb{Z}_{2^{\ell}}$.
    B2A can be done with $\ell$ OT~\cite{demmler2015aby} in $O(1)$ round. 
    
    \item \emph{Arithmetic to Boolean~(A2B) conversion} : Given $\addshare{x}$ over $\mathbb{Z}_{2^{\ell}}$, A2B conversion transforms $\addshare{x}$ to its boolean sharing $\boolshare{x}$ over $\mathbb{Z}_2^{\ell}$. 
    A2B can be done by computing an addition circuit over $\addshare{x}_0$ and $\addshare{x}_1$ using boolean sharing~\cite{demmler2015aby, patra2021aby2} in $O(\log \ell)$ rounds.
\end{packed_item}

For efficiency reason, we mainly use boolean sharing in this paper, and deploy B2A and A2B conversion whenever necessary. 

\noindent\textbf{Distributed Oblivious RAM}.
A similar primitives related to our paper is called Distributed Oblivious RAM~(DORAM) for oblivious data access.
A famous DORAM protocol is Floram~\cite{doerner2017scaling} proposed by Doerner and Shelat, which supports both read and write over secret-shared data.
Since we only care about read operation in our setting, we show the following two read-related protocols of Floram:

\begin{packed_item}
    \item 
    \underline{$ (\mathsf{sk}_{\rm s}, \mathsf{sk}_{\rm r}, \mathsf{C}) \leftarrow  \textsf{Init}(1^{\kappa}, \mathsf{M})$}: 
    the protocol initializes a masked array $\mathsf{C}$ from an array $\mathsf{M}$ of length $m$. $\mathcal{S}$ obtains $\mathsf{sk}_{\rm s}$ and $\mathcal{R}$ obtains $\mathsf{sk}_{\rm r}$, and both parties locally store $\mathsf{C}$.
    In details, $\mathcal{S}$ holds $\boolshare{\mathsf{M}[i]}_{\rm s}$, chooses a PRF key $\mathsf{sk}_{\rm s} \xleftarrow{\$} \{0,1\}^{\kappa}$, and sends $\boolshare{\mathsf{M}[i]}_{\rm s}  \oplus {F}(\mathsf{sk}_{\rm s}, i)$ for $i \in [0, m)$ to $\mathcal{R}$, where ${F}$ represents a PRF function. 
    Similarly, $\mathcal{R}$ holds $\boolshare{\mathsf{M}[i]}_{\rm r}$, chooses $\mathsf{sk}_{\rm r} \xleftarrow{\$} \{0,1\}^{\kappa}$, and sends $\boolshare{\mathsf{M}[i]}_{\rm r} \oplus {F}(\mathsf{sk}_{\rm r}, i)$ for $i \in [0, m)$ to $\mathcal{S}$. 
    In the end, both parties can locally compute and store $\mathsf{C}$ such that $\mathsf{C}[i] = \boolshare{\mathsf{M}[i]}_{\rm s} \oplus \boolshare{\mathsf{M}[i]}_{\rm r} \oplus {F}(\mathsf{sk}_{\rm s}, i) \oplus {F}(\mathsf{sk}_{\rm r}, i) = \mathsf{M}[i]  \oplus {F}(\mathsf{sk}_{\rm s}, i) \oplus {F}(\mathsf{sk}_{\rm r}, i)$ for $i \in [0, m)$. 
    
    \item 
    \underline{$ (\boolshare{\mathsf{M}[\mathsf{idx}]}) \leftarrow  \textsf{Read}(\mathsf{sk}_{\rm s}, \mathsf{sk}_{\rm r}, \boolshare{\mathsf{idx}},  \mathsf{C})$}: the protocol takes ($\mathsf{sk}_{\rm s}$, $\boolshare{\mathsf{idx}}_{\rm s}$) from $\mathcal{S}$, ($\mathsf{sk}_{\rm r}$, $\boolshare{\mathsf{idx}}_{\rm r}$) from $\mathcal{R}$, and $\mathsf{C}$ locally stored by both parties. In the end, the parties boolean-share $\mathsf{M}[\mathsf{idx}]$, \ie, $\mathcal{S}$ receives $\boolshare{\mathsf{M}[\mathsf{idx}]}_{\rm s}$  and  $\mathcal{R}$ receives $\boolshare{\mathsf{M}[\mathsf{idx}]}_{\rm r}$. 
    In details, the parties use function secret sharing~(FSS)~\cite{boyle2015function} to share a weight-1 bit vector $\mathsf{S}$ of size $m$ that satisfies $\mathsf{S}[\mathsf{idx}] = 1$ and $\mathsf{S}[i] = 0$ for all $i \ne \mathsf{idx}$. 
    $\mathcal{S}$ computes $c_{\rm s} \leftarrow \bigoplus_{i \in [0, m)} \boolshare{\mathsf{S}[i]}_{\rm s} \cdot \mathsf{C}[i]$ and $\mathcal{R}$ computes $c_{\rm r} \leftarrow \bigoplus_{i \in [0, m)} \boolshare{\mathsf{S}[i]}_{\rm r} \cdot \mathsf{C}[i]$. 
    It is easy to check $\mathsf{C}[\mathsf{idx}] = c_{\rm s} \oplus c_{\rm r}$.
    The parties then perform two invocations of two-party PRF evaluation to boolean-share $\boolshare{{F}(\mathsf{sk}_{\rm s}, {\mathsf{idx}})}_{\rm s}$ and $\boolshare{{F}(\mathsf{sk}_{\rm r}, {\mathsf{idx}})}_{\rm r}$, thus the parties can share $\mathsf{M}[\mathsf{idx}]$ by taking off two masks.
\end{packed_item}

\noindent\textbf{Paillier Encryption}. 
Paillier encryption scheme is a public key scheme based on Decisional Composite Residuosity problem \cite{paillier1999public}. The scheme $\mathcal{PE} =  (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})$ is defined as follows:

\begin{packed_item}
	\item $\textsf{Gen}(1^\kappa):$ Take as input a security parameter $\kappa$, generate two primes $p$, $q$ (size determined by $\kappa$). Compute $N=p\cdot q$. The public key $\mathsf{pk} = N$ and the private key $\mathsf{sk} = (N, p, q)$.
	
	\item $\textsf{Enc}_{\mathsf{pk}}(x,r)$: Take as input a message $x \in \mathbb{Z}_N$ and a public key $\mathsf{pk}$, with a uniform $r \xleftarrow{\$} \mathbb{Z}^*_N$, the ciphertext is $c := (1+N)^x \cdot r^N \bmod N^2$. We also use $\textsf{Enc}(x)$ if we do not care $r$.  
	
	\item$\textsf{Dec}_{\mathsf{sk}}(c)$: Take as a ciphertext $c\in \mathbb{Z}_{N^2}$ and a private key $\mathsf{sk}$, the decrypted plaintext is $x := \frac{(c^{\phi(N)} \bmod N^2) -1}{N} \cdot \phi(N)^{-1} \bmod N$, where $\phi(N) = (p-1)(q-1)$. 
\end{packed_item}


Paillier encryption is an additively homomorphic encryption~(AHE) scheme. At a high level, we can express the homomorphic operations as the following:
\begin{packed_item}
\item Homomorphic addition: Given two ciphertexts $c=\textsf{Enc}_{pk}(x, r)$ and $c'=\textsf{Enc}_{pk}(x', r')$, then $c_{\rm add}=c \cdot c' = ((1+N)^x\cdot r^N )\cdot ((1+N)^{x'}\cdot {r'}^N) = (1+N)^{x + x'}\cdot (rr')^N=  \textsf{Enc}_{pk}(x+x', rr')$.
\item Homomorphic multiplication with a constant: Given a ciphertext $c=\textsf{Enc}_{pk}(x,r)$ and a constant $a$, then $c_{\rm mult}=c^a = ((1+N)^x\cdot r^N)^{a} =  (1+N)^{ax}\cdot (r^{a})^N = \textsf{Enc}_{pk}(a\cdot x, r^a)$.
\end{packed_item}

\section{Related Work} \label{section:related}
There are many two-party PDTE protocols in the literature~\cite{brickell2007privacy,barni2009secure,bost2015machine,kiss2019sok,wu2016privately,tai2017privacy}. 
Among them, a few works~\cite{tueno2019private,joye2018private,ma2021let} achieve sublinear cost. In the following, we summarize these works separately. 

\noindent\textbf{Linear-cost Protocols.}
Brickell \textit{et~al. }~\cite{brickell2007privacy} pack each tree node into a GC circuit and then transmit the encrypted tree itself to the feature provider. With the help of HE and OT, the feature provider can perform oblivious evaluation by herself. However, the security requires that the encrypted tree should be refreshed for each tree evaluation, incurring linear costs. 
This work was later optimized by Barni \textit{et~al. }~\cite{barni2009secure}. The communication cost is saved by only sending encrypted internal nodes rather than the whole tree. However, it is still linear to the tree size. 
Bost \textit{et~al. }~\cite{bost2015machine} express the decision tree as a high-degree polynomial and encrypt it using an expensive Leveled Fully Homomorphic Encryption~(Leveled-FHE) scheme. 
Wu \textit{et~al. }~\cite{wu2016privately} propose a cheaper protocol by only relying on OT and AHE. Yet, the construction requires the tree holder to pad the tree to be complete in order to hide the tree structure. This padding strategy incurs massive communication and computation overhead, especially for deep-but-sparse trees. 
Subsequent PDTE protocols \cite{kiss2019sok, de2017efficient,liu2019secure} follow the same approach. To avoid padding, Tai \textit{et~al. }~\cite{tai2017privacy} propose a novel path cost mechanism using AHE. This protocol performs better for sparse trees but still runs at linear cost. 
Kiss \textit{et~al. }~\cite{kiss2019sok} systematically compare existing PDTE protocols. They mix HE and GC in different evaluation phases and report their concrete efficiency. Same as previous works, they trade efficiency for privacy by doing comparisons for all decision nodes, resulting in linear computation/communication. 
Ideally, the best solution is to perform only the necessary comparisons meanwhile hiding the decision path.

\noindent\textbf{Sublinear-cost Protocols.}
Three up-to-date work~\cite{joye2018private,tueno2019private,ma2021let} consider sub-linear decision tree protocols.
Joye and Salehi~\cite{joye2018private} reduce the number of secure comparisons to $d$. The comparison is based on DGK protocol~\cite{damgaard2007efficient} using AHE. In tree level $l$, they employ 1-out-of-$2^l$ OT to obliviously select an AHE encrypted tree node. In the end, the involved OT incurs $O( 2^d-1)$ communication in total. Thus, this PDTE protocol is only sublinear in computation.
Tueno \textit{et~al. }~\cite{tueno2019private} organize a decision tree as an array and build an oblivious array indexing (OAI). Such an interactive OAI allows the participants to pick the desired tree node and its corresponding attribute obliviously. 
OAI can be instantiated utilizing GC, OT or Oblivious RAM (ORAM). The first two OAIs can only realize sublinear complexity on the feature provider side since they also require OT to transfer among $2^d$ nodes, same as~\cite{joye2018private}. 
If employing ORAM, it takes $O(d^4)$ communication cost and requires $d^2$ (\textit{e.g.}, complete tree) rounds.


In order to further reduce communication cost, in protocol~\cite{ma2021let}, the tree holder encrypts the tree and sends it to the feature provider. In each tree level, there is an OT and a comparison between both parties. The feature provider searches local encrypted tree for the next node after comparison. Since the authors move the most expensive oblivious selection operations to feature provider's local computation, their protocol is very efficient in terms of computation. Nevertheless, we notice that this searching property means this tree cannot be reused across evaluations because the feature provider can learn some information from memory access patterns during different evaluations.
Accordingly, to reach the genuine PDTE when using~\cite{ma2021let}, toward every evaluation, the decision tree model should be re-randomized and transmitted to the feature provider, causing linear complexity in terms of communication and computation.

\noindent\textbf{Outsourced Protocols.} 
Some also try to gain more efficiency with the help of cloud servers, which is called outsourced PDTE protocols~\cite{liang2019efficient, ma2021let,ji2021uc,zheng2019towards}. They aim to use outsourced cloud servers to release the heavy burden from the tree holder and the feature provider. However, most of them suffer linear complexities~\cite{liang2019efficient, zheng2019towards} or leak more information~\cite{liang2019efficient} than prior two-party protocols. 
\section{Security Definition}\label{Security} 

\subsection{Semi-honest Security}
We design our protocols and prove their security under semi-honest security model~\cite{goldreich2009foundations,hazay2010efficient}.
A protocol $\Pi$ securely computes a function $f$ under semi-honest adversary if the adversary cannot learn more information beyond what can be computed from his input and output.
A protocol may allow the parties to learn certain leakages after execution, and we treat such leakages as a part of the output. 
Formally, let $f(x,y) = (f_0(x,y),f_1(x,y))$ be a function with inputs $x,y$ and outputs $(f_0(x,y),f_1(x,y))$.
For a two-party protocol $\Pi$ computing function $f(x,y)$, we use $\textsf{View}^{\Pi}_i(1^{\lambda}, x, y) = (\omega,r^i;m^{i}_1,...,m^{i}_t)$ to denote the view of the $i$-th party~($i \in \{0, 1\}$) during protocol execution where $\omega \in \{x, y\}$ depends on $i$ {, $r^i$ represents the contents of its random values, and $m^{i}_1,...,m^{i}_t$ denotes the messages received by the $i$-th party}. 

\begin{definition}
The protocol $\Pi$ securely computes $f$ for any inputs $(x,y)$ if for any party ${P}_i$~($i \in \{0, 1\}$) corrupted by a semi-honest adversary $\mathcal{A}$, there exists a \emph{probabilistic polynomial time} (PPT) simulator $\textsf{Sim}_i$ that can produce a simulated view that is computationally indistinguishable from $\textsf{View}^{\Pi}_i(1^{\lambda}, x, y)$:
\[\{\textsf{Sim}_i(1^{\lambda}, x, f_i(x,y) )\} 
\overset{c}{\equiv} 
\{ \textsf{View}^{\Pi}_i(1^{\lambda}, x, y) \}.\]
\end{definition}












\iffalse 
\subsection{Semi-honest security in the outsourcing setting.} 
Similar to most prior works fall in the outsourcing field~\cite{zheng2019towards}\cite{mohassel2017secureml}, We suppose the server and the client are fully trusted thus they honestly outsource the tree $\mathcal{T}$ and $X$ to two non-concluding CSPs $S_0$ and $S_1$. 

Let
\[\begin{array}{l} \mathcal{F}_{\rm ODT}(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1) \\
\rightarrow (\mathcal{F}_0(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1), \mathcal{F}_1(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1)) \end{array}\]
be the decision tree functionality in our outsourcing setting such that $S_0$ provides tree's shared part  $\mathcal{T}_0$ and feature vector's shared part $X_0$ and outputs $\mathcal{F}_0(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1) = \{c_0, \mathcal{L}_0(\mathcal{T}, X)\}$, while $S_1$ provides tree's shared part $\mathcal{T}_1$ and feature vector's shared part $X_1$ and outputs $\mathcal{F}_1(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1) = \{c_1, \mathcal{L}_1(\mathcal{T}, X)\}$. Stateless function $\mathcal{L}_0(\mathcal{T}, X)$ equals $\mathcal{L}_1(\mathcal{T}, X)$ which contains minimal leakages $(m, n)$ in the existing work. Let ${\rm \pi}$ be the protocol for computing $\mathcal{F}_{\rm ODT}$. We denote the joint output of both parties by $\textsf{output}^\pi({1^\lambda }, \mathcal{T}_0, X_0, \mathcal{T}_1, X_1) = (\textsf{output}_0^\pi({1^\lambda }, \mathcal{T}_0, X_0, \mathcal{T}_1, X_1), \textsf{output}_1^\pi({1^\lambda }, \mathcal{T}_0, X_0, \mathcal{T}_1, X_1))$. It is considered secure in the presence of static semi-honest adversaries if there exist PPT simulators $\mathcal{S}_0$ and $\mathcal{S}_1$ such that 
\[\begin{array}{l}
\{ {\cal S}_0(1^\lambda,{\cal T}_0,X_0,{\cal F}_0(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1)),\\
\mathcal{F}_{\rm ODT}(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1)\} _{{\cal T}_0,{\cal T}_1 \in \mathbb{T},X_0,X_1 \in _{2^l}^m;\lambda  \in \mathbb{N}}\\
\mathop  \equiv \limits^c \{ \textsf{View}_0^\pi (1^\lambda ,{\cal T}_0,X_0,{\cal T}_1,X_1),\\ \textsf{output}^\pi(1^\lambda,
\mathcal{T}_0, X_0, \mathcal{T}_1, X_1)\} _{{\cal T}_0,{\cal T}_1 \in \mathbb{T},X_0,X_1 \in _{2^l}^m;\lambda  \in \mathbb{N}}
\end{array}\]
and
\[\begin{array}{l}
\{{{\cal S}_1}({1^\lambda },{{\cal T}_1},{X_1},{{\cal F}_1}(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1)),\\ \mathcal{F}_{\rm ODT}(\mathcal{T}_0, X_0, \mathcal{T}_1, X_1)\} _{{{\cal T}_0},{{\cal T}_1} \in \mathbb{T},{X_0},{X_1} \in _{{2^l}}^m;\lambda  \in \mathbb{N}}\\
\mathop  \equiv \limits^c \{ \textsf{View}_1^\pi ({1^\lambda },{{\cal T}_0},{X_0},{{\cal T}_1},{X_1}),\\ \textsf{output}^\pi({1^\lambda }, \mathcal{T}_0, X_0, \mathcal{T}_1, X_1)\} _{{{\cal T}_0},{{\cal T}_1} \in \mathbb{T},{X_0},{X_1} \in _{{2^l}}^m;\lambda  \in \mathbb{N}}
\end{array}\]
where $\mathbb{T}$ denotes all possible decision trees, and $S_i$'s view of computation is $\textsf{View}^{\rm \pi}_i(1^{\lambda}, \mathcal{T}_0, X_0, \mathcal{T}_1, X_1)$.
\fi 