  Outsourcing decision tree inference services to the cloud is highly
beneficial, yet raises critical privacy concerns on the proprietary decision
tree of the model provider and the private input data of the client. In this
paper, we design, implement, and evaluate a new system that allows highly
efficient outsourcing of decision tree inference. Our system significantly
improves upon the state-of-the-art in the overall online end-to-end secure
inference service latency at the cloud as well as the local-side performance of
the model provider. We first presents a new scheme which securely shifts most
of the processing of the model provider to the cloud, resulting in a
substantial reduction on the model provider's performance complexities. We
further devise a scheme which substantially optimizes the performance for
encrypted decision tree inference at the cloud, particularly the communication
round complexities. The synergy of these techniques allows our new system to
achieve up to $8 \times$ better overall online end-to-end secure inference
latency at the cloud side over realistic WAN environment, as well as bring the
model provider up to $19 \times$ savings in communication and $18 \times$
savings in computation.
