Mostree: Malicious Secure Private Decision Tree Evaluation with Sublinear Communication
Open Access
- 4 December 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 799-813
Abstract
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.Keywords
Funding Information
- The Ministry of Business, Innovation and Employment (MBIE), New Zealand (STRATUS (UOWX1503))
This publication has 13 references indexed in Scilit:
- Two-party Private Set Intersection with an Untrusted Third Party2019
- SoK: Modular and Efficient Private Decision Tree EvaluationProceedings on Privacy Enhancing Technologies, 2019
- A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority2017
- High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority2016
- Function Secret Sharing2016
- Machine Learning Classification over Encrypted Data2015
- More efficient oblivious transfer and extensions for faster secure computation2013
- Decision trees: a recent overviewArtificial Intelligence Review, 2011
- Privacy-preserving remote diagnostics2007
- Decision Trees: An Overview and Their Use in MedicineJournal of Medical Systems, 2002