  Private decision tree evaluation (PDTE) allows a decision tree holder to run
a secure protocol with a feature provider. By running the protocol, the feature
provider will learn a classification result. Nothing more is revealed to either
party. In most existing PDTE protocols, the required communication grows
exponentially with the tree's depth $d$, which is highly inefficient for large
trees. This shortcoming motivated us to design a sublinear PDTE protocol with
$O(d)$ communication complexity. The core of our construction is a shared
oblivious selection (SOS) functionality, allowing two parties to perform a
secret-shared oblivious read operation from an array. We provide two SOS
protocols, both of which achieve sublinear communication and propose
optimizations to further improve their efficiency. Our sublinear PDTE protocol
is based on the proposed SOS functionality and we prove its security under a
semi-honest adversary. We compare our protocol with the state-of-the-art, in
terms of communication and computation, under various network settings. The
performance evaluation shows that our protocol is practical and more scalable
over large trees than existing solutions.
