Silent Guardians: Independent and Secure Decision Tree Evaluation Without Chatter

Jinyuan Li, Liang Feng Zhang · 2026

Read Silent Guardians: Independent and Secure Decision Tree Evaluation Without Chatter by Jinyuan Li, Liang Feng Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-28143.txt.

Introduction

Li and Zhang propose PVODTE, a protocol for running decision trees in the cloud without giving up privacy or trust. Clients hide their data, providers hide their model, and both want proof the answer is right. Two servers each compute alone, with no messages between them, using homomorphic secret sharing. A MAC-based check catches any tampering. The design is the first of its kind and suits slow wide-area networks.

Catalog record

CREATORJinyuan Li, Liang Feng Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119977
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.28143

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Silent Guardians: Independent and Secure Decision Tree Evaluation Without Chatter Jinyuan Li, Liang Feng Zhang Abstract As machine learning as a service (MLaaS) gains increasing popularity, it raises two critical challenges: privacy and verifiability. For privacy, clients are reluctant to disclose sensitive private information to access MLaaS, while model providers must safeguard their proprietary models. For verifiability, clients lack reliable mechanisms to ensure that cloud servers execute model inference correctly. Decision trees are widely adopted in MLaaS due to their popularity, interpretability, and broad applicability in domains like medicine and finance. In this context, outsourcing decision tree evaluation (ODTE) enables both clients and model providers to offload their sensitive data and decision tree models to the cloud securely. However, existing ODTE schemes often fail to address both privacy and verifiability simultaneously. To bridge this gap, we propose 𝖯𝖵𝖮𝖣𝖳𝖤 \sf PVODTE , a novel two-server private and verifiable ODTE protocol that leverages homomorphic secret sharing and a MAC-based verification mechanism. 𝖯𝖵𝖮𝖣𝖳𝖤 \sf PVODTE eliminates the need for server-to-server communication, enabling independent computation by each cloud server. This “non-interactive” setting addresses the latency and synchronization bottlenecks of prior arts, making it uniquely suitable for wide-area network (WAN) deployments. To our knowledge, 𝖯𝖵𝖮𝖣𝖳𝖤 \sf PVODTE is the first two-server ODTE protocol that eliminates server-to-server communication. Furthermore, 𝖯𝖵𝖮𝖣𝖳𝖤 \sf PVODTE achieves security against malicious servers, where servers cannot learn anything about the client’s input or the providers’ decision tree models, and servers cannot alter the inference result without being detected. I Introduction Machine Learning as a Service (MLaaS) enables access to advanced machine learning models without requiring extensive in-house resources or expertise. Driven by cloud computing, MLaaS has evolved into a paradigm [ 1 ] where a model provider (e.g., a hospital) deploys a pre-trained model (e.g., a diagnostic decision tree) to the cloud, offering inference services to clients (e.g., patients) who submit sensitive input data (e.g., health records). Outsourcing MLaaS to the cloud delivers well-documented benefits for both parties: high scalability, ubiquitous access, and low economical cost. However, this paradigm raises two fundamental security challenges [ 2 ] : (i) Privacy: Model providers (e.g., hospitals) hesitate to outsource proprietary diagnostic models to cloud service providers due to risks of intellectual property exposure; clients (e.g., patients) fear privacy violations when transmitting plaintext sensitive data (e.g., health records). (ii) Verifiability: Untrusted cloud servers may return incorrect inference results (e.g., manipulated medical diagnoses), but clients lack mechanisms to verify result correctness. To address both privacy and verifiability in MLaaS, privacy-preserving and verifiable model inference (PVMI) has emerged as a key research direction. PVMI protocols guarantee two core properties: (i) cloud servers cannot access the provider’s proprietary model or client’s sensitive input in plaintext; (ii) malicious server behavior (e.g., result manipulation) is detectable. PVMI solutions are broadly categorized into single-server and multi-server paradigms based on the number of cloud servers involved. In the single-server setting, the provider’s encrypted model and client’s encrypted input are sent to one cloud server, which performs encrypted inference and returns an encrypted result. Prior works [ 2 , 3 , 5 , 4 ] use additively homomorphic encryption (AHE) [ 6 ] or fully homomorphic encryption (FHE) [ 7 ] to outsource models like neural networks and decision trees. For verifiability, some works [ 2 , 3 ] integrate zero-knowledge proofs (ZKPs) [ 8 ] , while others [ 5 , 4 ] lack such mechanisms, leaving clients unable to verify the correctness of inference results. However, single-server designs suffer from prohibitive computational overhead due to AHE/FHE, limiting their real-world practicality [ 9 ] . To mitigate these computational bottlenecks, multi-server architectures use secret sharing (SS) [ 12 , 10 , 11 ] , where the model and input are split into shares, and then distributed across two or more non-colluding servers [ 13 , 14 , 15 , 17 , 16 , 18 , 19 , 1 , 20 ] . SS-based protocols replace expensive homomorphic operations with lightweight arithmetic, improving efficiency. However, they introduce new challenges: high network latency and excessive bandwidth consumption due to frequent server-to-server (S2S) communication (e.g., data exchange between servers) during inference, especially in wide-area networks (WANs). Moreover, existing SS-based PVMI protocols [ 13 , 14 , 15 , 17 , 16 , 18 , 19 , 1 , 20 ] only satisfy privacy but lack verifiability, clients cannot detect malicious server behavior like result manipulation. In this work, we focus on a specific type of machine learning model: decision trees, which are popular, interpretable, and widely used in applications like medical diagnosis [ 21 , 22 ] , financial distress prediction [ 23 ] , and more [ 25 , 24 ] . Specifically, we target the outsourced decision tree evaluation (ODTE) problem: securely outsourcing a decision tree model and the client input to the cloud, with inference performed on encrypted or secret-shared data such that the model and input remain private, and the result is verifiable. Prior work on ODTE prioritizes privacy (i.e., hiding the model and the client input from servers). According to the number of required servers, existing ODTE protocols can be classified into three categories: (i) single-server protocols [ 5 , 4 ] that minimize server requirements but suffer from prohibitive computational overhead due to the reliance on FHE; (ii) two-server protocols [ 18 , 19 , 1 , 20 ] that retain a relatively simple setup but require \mathcal{O}(h) , \mathcal{O}(\lambda) or \mathcal{O}(\log(\lambda)) S2S rounds, where h is the height of the decision tree and \lambda is the security parameter, leading to high network latency; (iii) three-server protocols [ 15 , 17 , 16 ] that reduce S2S rounds to constant but increase deployment complexity (three cloud servers). Unfortunately, all existing ODTE protocols suffer from two critical limitations: (i) Performance bottlenecks : They suffer from either significant computational overhead (single-server designs) or high network latency (multi-server designs); (ii) Weak security guarantees : No protocol provides security against malicious servers. Malicious servers may compromise the privacy of clients and model providers, or manipulate inference results. These gaps motivate our core research question: Can we design an ODTE protocol that simultaneously achieves three goals: (i) maintaining a practical two-server setup to avoid FHE; (ii) eliminating S2S rounds to minimize network latency; and (iii) achieving security against malicious servers to ensure privacy and verifiability? TABLE I: Comparison of ODTE protocols. Protocol #Servers Malicious security #S2S Rounds Techniques [ 4 ] 1 \circ \bf 0 FHE [ 5 ] 1 \circ \bf 0 FHE [ 15 ] 3 \circ 25 RSS [ 16 ] 3 \circ 5 FSS, RSS [ 17 ] 3 \circ 4 FSS [ 18 ] 2 \circ h+3 SS, HE [ 19 ] 2 \circ 2h SS, OT [ 26 ] 2 \circ 2(h+1) FHE [ 1 ] 2 \circ 2(\lambda-1) SS [ 20 ] 2 \circ \log(\lambda)+5 SS, OT Ours 2 \bullet \bf 0 HSS Remark: A protocol that possesses a particular property in a given column is marked with a \bullet ; otherwise, it is marked with a \circ . #Servers denotes the number of required servers. #S2S Rounds denotes the rounds of S2S communication. h denotes the height of the decision tree, \lambda denotes the security parameter.

Read the complete text