  A private decision tree evaluation (PDTE) protocol allows a feature vector
owner (FO) to classify its data using a tree model from a model owner (MO) and
only reveals an inference result to the FO. This paper proposes Mostree, a PDTE
protocol secure in the presence of malicious parties with sublinear
communication. We design Mostree in the three-party honest-majority setting,
where an (untrusted) computing party (CP) assists the FO and MO in the secure
computation. We propose two low-communication oblivious selection (OS)
protocols by exploiting nice properties of three-party replicated secret
sharing (RSS) and distributed point function. Mostree combines OS protocols
with a tree encoding method and three-party secure computation to achieve
sublinear communication. We observe that most of the protocol components
already maintain privacy even in the presence of a malicious adversary, and
what remains to achieve is correctness. To ensure correctness, we propose a set
of lightweight consistency checks and seamlessly integrate them into Mostree.
As a result, Mostree achieves sublinear communication and malicious security
simultaneously. We implement Mostree and compare it with the state-of-the-art.
Experimental results demonstrate that Mostree is efficient and comparable to
semi-honest PDTE schemes with sublinear communication. For instance, when
evaluated on the MNIST dataset in a LAN setting, Mostree achieves an evaluation
using approximately 768 ms with communication of around 168 KB.
