papers/hanzo-fhe-inference/sections/06-encrypted-decision-tree-inference.tex

\section{Encrypted Decision Tree Inference}

\label{sec:tree}
% ============================================================================

\subsection{Oblivious Tree Evaluation}

To prevent information leakage from access patterns, we evaluate the entire
tree obliviously: every path is evaluated, and the result is selected via
encrypted multiplexing.

\begin{algorithm}
\caption{Oblivious Decision Tree Evaluation}
\label{alg:tree}
\begin{algorithmic}[1]
\Require Encrypted input $\texttt{Enc}(\mathbf{x})$, tree $\mathcal{T}$ with
    nodes $(i_v, t_v, l_v)$ for feature index, threshold, leaf value
\Ensure Encrypted prediction $\texttt{Enc}(y)$
\For{each internal node $v$}
    \State $b_v \leftarrow \texttt{Enc}(x_{i_v}) < t_v$ \Comment{Encrypted comparison}
\EndFor
\For{each leaf $\ell$ with path $P_\ell = (v_1, d_1), \ldots, (v_k, d_k)$}
    \State $s_\ell \leftarrow \prod_{(v, d) \in P_\ell}
    \begin{cases} b_v & \text{if } d = \texttt{left} \\
    1 - b_v & \text{if } d = \texttt{right} \end{cases}$
\EndFor
\State $\texttt{Enc}(y) \leftarrow \sum_\ell s_\ell \cdot l_\ell$
\end{algorithmic}
\end{algorithm}

\subsection{Ensemble Parallelism}

Gradient-boosted ensembles (XGBoost, LightGBM) consist of $T$ independent trees.
All trees are evaluated in parallel on GPU, with the encrypted results summed:
\begin{equation}
\texttt{Enc}(y) = \sum_{t=1}^{T} \texttt{Enc}(y_t).
\end{equation}

This parallelism makes ensemble evaluation only marginally slower than single
tree evaluation on GPU ($T = 500$ trees in 0.9s vs.\ single tree in 0.05s).

% ============================================================================