MALTree: Maliciously Secure Decision Tree Inference Using MPC With a Helper

In the context of the Machine Learning as a Service (MLaaS) paradigm, secure decision tree inference mechanisms leverage cryptographic primitives including Secure Multi-Party Computation (MPC) and Homomorphic Encryption (HE) to facilitate cloud-based inference services while ensuring the confidentiality of both model parameters and client input data. Nevertheless, prevailing approaches predominantly rely on the semi-honest adversary model, which proves inadequate against malicious behaviors potentially encountered in practical settings. Moreover, these methods often operate under constrained security assumptions, such as the inability to tolerate a dishonest majority, and suffer from substantial computational overhead. To overcome these limitations, this work introduces a maliciously secure protocol for decision tree inference designed to operate under a dishonest majority corruption model. During the feature matching phase, the proposed protocol employs a lightweight permutation vector-based technique in lieu of conventional high-cost matrix operations or oblivious transfers, thereby markedly reducing both communication and computational complexity. For secure node evaluation, the protocol enhances the existing DReLU mechanism through the integration of information-theoretic Message Authentication Codes (MACs) and consistency verification checks, thereby bolstering resilience against malicious adversaries without incurring expensive preprocessing overhead. Experimental evaluations demonstrate that the proposed protocol maintains high online execution efficiency even under stringent security constraints, offering a viable and practical solution for deployment in resource-constrained environments.