Mostree: Malicious Secure Private Decision Tree Evaluation with Sublinear Communication
Authors: 
Jianli Bai, Xiangfu Song, Xiaowu Zhang, Qifan Wang, Shujie Cui, Ee-Chien Chang, Giovanni RusselloAuthors Info & Claims
Pages 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.
References
[1]
Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. 2016. High-throughput semi-honest secure three-party computation with an honest majority. In ACM CCS. 805–817.
[2]
Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. 2013. More efficient oblivious transfer and extensions for faster secure computation. In ACM CCS. 535–548.
[3]
Nuttapong Attrapadung, Goichiro Hanaoaka, Takahiro Matsuda, Hiraku Morita, Kazuma Ohara, Jacob CN Schuldt, Tadanori Teruya, and Kazunari Tozawa. 2021. Oblivious Linear Group Actions and Applications. In ACM CCS. 630–650.
[4]
Jianli Bai, Xiangfu Song, Shujie Cui, Ee-Chien Chang, and Giovanni Russello. 2022. Scalable Private Decision Tree Evaluation with Sublinear Communication. In AsiaCCS. 843–857.
[5]
Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. 2009. Secure evaluation of private linear branching programs with medical applications. In ESORICS. Springer, 424–439.
[6]
Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. 2015. Machine learning classification over encrypted data. In NDSS, Vol. 4324. 4325.
[7]
Elette Boyle, Niv Gilboa, and Yuval Ishai. 2015. Function secret sharing. In EUROCRYPTO. Springer, 337–367.
[8]
Elette Boyle, Niv Gilboa, and Yuval Ishai. 2016. Function secret sharing: Improvements and extensions. In AMC CCS. 1292–1303.
[9]
Elette Boyle, Niv Gilboa, and Yuval Ishai. 2019. Secure computation with preprocessing via function secret sharing. In TCC. Springer, 341–371.
[10]
Andrej Bratko, Bogdan Filipič, Gordon V Cormack, Thomas R Lynam, and Blaž Zupan. 2006. Spam filtering using statistical data compression models. The Journal of Machine Learning Research 7 (2006), 2673–2698.
[11]
Justin Brickell, Donald E Porter, Vitaly Shmatikov, and Emmett Witchel. 2007. Privacy-preserving remote diagnostics. In ACM CCS. 498–507.
[12]
Jason Catlett. 1991. Overprvning Large Decision Trees. In IJCAI. Citeseer, 764–769.
[13]
Koji Chida, Daniel Genkin, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Yehuda Lindell, and Ariel Nof. 2018. Fast large-scale honest-majority MPC for malicious adversaries. In CRYPTO. Springer, 34–64.
[14]
Ivan Damgård, Daniel Escudero, Tore Frederiksen, Marcel Keller, Peter Scholl, and Nikolaj Volgushev. 2019. New primitives for actively-secure MPC over rings with applications to private machine learning. In IEEE S&P. IEEE, 1102–1120.
[15]
Emma Dauterman, Mayank Rathee, Raluca Ada Popa, and Ion Stoica. 2022. Waldo: A private time-series database from function secret sharing. In IEEE S&P. IEEE, 2450–2468.
[16]
Leo de Castro and Anitgoni Polychroniadou. 2022. Lightweight, Maliciously Secure Verifiable Function Secret Sharing. In EUROCRYPT. Springer, 150–179.
[17]
Martine De Cock, Rafael Dowsley, Caleb Horst, Raj Katti, Anderson CA Nascimento, Wing-Sea Poon, and Stacey Truex. 2017. Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation. IEEE TDSC 16, 2 (2017), 217–230.
[18]
Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. 2017. High-throughput secure three-party computation for malicious adversaries and an honest majority. In EUROCRYPT. Springer, 225–255.
[19]
Niv Gilboa and Yuval Ishai. 2014. Distributed point functions and their applications. In EUROCRYPT. Springer, 640–658.
[20]
Thang Hoang, Jorge Guajardo, and Attila A Yavuz. 2020. MACAO: A maliciously-secure and client-efficient active ORAM framework. Cryptology ePrint Archive (2020).
[21]
Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. 2003. Extending oblivious transfers efficiently. In CRYPTO. Springer, 145–161.
[22]
Yuval Ishai and Anat Paskin. 2007. Evaluating branching programs on encrypted data. In TCC. Springer, 575–594.
[23]
Keyu Ji, Bingsheng Zhang, Tianpei Lu, Lichun Li, and Kui Ren. 2021. UC Secure Private Branching Program and Decision Tree Evaluation. Cryptology ePrint Archive (2021).
[24]
Marc Joye and Fariborz Salehi. 2018. Private yet efficient decision tree evaluation. In IFIP DBSec. Springer, 243–259.
[25]
Ágnes Kiss, Masoud Naderpour, Jian Liu, N Asokan, and Thomas Schneider. 2019. Sok: Modular and efficient private decision tree evaluation. PoPETs 2019, 2 (2019), 187–208.
[26]
Hian Chye Koh, Wei Chin Tan, and Chwee Peng Goh. 2006. A two-step method to construct credit scoring models with data mining techniques. International Journal of Business and Information 1, 1 (2006), 96–118.
[27]
Sotiris B Kotsiantis. 2013. Decision trees: a recent overview. Artificial Intelligence Review 39, 4 (2013), 261–283.
[28]
Phi Hung Le, Samuel Ranellucci, and S Dov Gordon. 2019. Two-party private set intersection with an untrusted third party. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2403–2420.
[29]
Yehuda Lindell and Ariel Nof. 2017. A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority. In ACM CCS. 259–276.
[30]
Jack PK Ma, Raymond KH Tai, Yongjun Zhao, and Sherman SM Chow. 2021. Let’s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation. In NDSS.
[31]
Payman Mohassel and Peter Rindal. 2018. ABY3: A mixed protocol framework for machine learning. In ACM CCS. 35–52.
[32]
Dimitris Mouris, Pratik Sarkar, and Nektarios Georgios Tsoutsos. 2023. PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries with Full Security. Cryptology ePrint Archive (2023).
[33]
Vili Podgorelec, Peter Kokol, Bruno Stiglic, and Ivan Rozman. 2002. Decision trees: an overview and their use in medicine. Journal of medical systems 26, 5 (2002), 445–463.
[34]
Peter Rindal. [n. d.]. The ABY3 Framework for Machine Learning and Database Operations.https://github.com/ladnir/aby3.
[35]
Raymond KH Tai, Jack PK Ma, Yongjun Zhao, and Sherman SM Chow. 2017. Privacy-preserving decision trees evaluation via linear functions. In ESORICS. Springer, 494–512.
[36]
Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. 2019. Private Evaluation of Decision Trees using Sublinear Cost.PoPETs 2019, 1 (2019), 266–286.
[37]
Adithya Vadapalli, Ryan Henry, and Ian Goldberg. 2022. Duoram: A Bandwidth-Efficient Distributed ORAM for 2-and 3-Party Computation. Cryptology ePrint Archive (2022).
[38]
Sameer Wagh. 2022. Pika: Secure Computation using Function Secret Sharing over Rings. Cryptology ePrint Archive (2022).
[39]
David J Wu, Tony Feng, Michael Naehrig, and Kristin E Lauter. 2016. Privately Evaluating Decision Trees and Random Forests.PoPETs 2016, 4 (2016), 335–355.
Index Terms
- Mostree: Malicious Secure Private Decision Tree Evaluation with Sublinear Communication
Recommendations
Scalable Private Decision Tree Evaluation with Sublinear Communication
ASIA CCS '22: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications SecurityPrivate 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 ...
An efficient fair UC-secure protocol for two-party computation
With the development of modern Internet and mobile networks, there is an increasing need for collaborative privacy-preserving applications. Secure multi-party computation SMPC gives a general solution to these applications and has become a hot topic. ...
Efficient Secure Multi-Party Protocols for Decision Tree Classification
Information Security and PrivacyAbstractWe propose novel secure multi-party protocols for decision-tree classification. Our protocols hide not only an input vector and an output class but also the structure of the tree, which incurs an exponential communication complexity in terms of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2023
836 pages
ISBN:9798400708862
DOI:10.1145/3627106
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 December 2023
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- The Ministry of Business, Innovation and Employment (MBIE), New Zealand
Conference
ACSAC '23
Acceptance Rates
Overall Acceptance Rate 104 of 497 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 304Total Downloads
- Downloads (Last 12 months)304
- Downloads (Last 6 weeks)48
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in