Secure Decision Forest Evaluation
Authors: 
Slim Bettaieb, Loic Bidoux, Olivier Blazy, Baptiste Cottier, David PointchevalAuthors Info & Claims
ARES '21: Proceedings of the 16th International Conference on Availability, Reliability and Security
Article No.: 24, Pages 1 - 12
Abstract
Decision forests are classical models to efficiently make decision on complex inputs with multiple features. While the global structure of the trees or forests is public, sensitive information have to be protected during the evaluation of some client inputs with respect to some server model. Indeed, the comparison thresholds on the server side may have economical value while the client inputs might be critical personal data. In addition, soundness is also important for the receiver. In our case, we will consider the server to be interested in the outcome of the model evaluation so that the client should not be able to bias it. In this paper, we propose a new offline/online protocol between a client and a server with a constant number of rounds in the online phase, with both privacy and soundness against malicious clients.
References
[1]
Arash Afshar, Payman Mohassel, Benny Pinkas, and Ben Riva. 2014. Non-Interactive Secure Computation Based on Cut-and-Choose. In EUROCRYPT 2014(LNCS, Vol. 8441), Phong Q. Nguyen and Elisabeth Oswald (Eds.). Springer, Heidelberg, 387–404. https://doi.org/10.1007/978-3-642-55220-5_22
[2]
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 2009(LNCS, Vol. 5789), Michael Backes and Peng Ning (Eds.). Springer, Heidelberg, 424–439. https://doi.org/10.1007/978-3-642-04444-1_26
[3]
Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The Round Complexity of Secure Protocols (Extended Abstract). In 22nd ACM STOC. ACM Press, 503–513. https://doi.org/10.1145/100216.100287
[4]
Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. 2015. Machine Learning Classification over Encrypted Data. In NDSS 2015. The Internet Society.
[5]
Justin Brickell, Donald E. Porter, Vitaly Shmatikov, and Emmett Witchel. 2007. Privacy-preserving remote diagnostics. In ACM CCS 2007, Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson (Eds.). ACM Press, 498–507. https://doi.org/10.1145/1315245.1315307
[6]
Martine De Cock, Rafael Dowsley, Caleb Horst, Raj Katti, Anderson C. A. Nascimento, Stacey C. Newman, and Wing-Sea Poon. 2016. Efficient and Private Scoring of Decision Trees, Support Vector Machines and Logistic Regression Models based on Pre-Computation. Cryptology ePrint Archive, Report 2016/736. http://eprint.iacr.org/2016/736.
[7]
Aurélien Dupin, David Pointcheval, and Christophe Bidan. 2018. On the Leakage of Corrupted Garbled Circuits. In ProvSec 2018(LNCS, Vol. 11192), Joonsang Baek, Willy Susilo, and Jongkil Kim(Eds.). Springer, Heidelberg, 3–21. https://doi.org/10.1007/978-3-030-01446-9_1
[8]
Taher ElGamal. 1984. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In CRYPTO’84(LNCS, Vol. 196), G. R. Blakley and David Chaum (Eds.). Springer, Heidelberg, 10–18.
[9]
Shimon Even, Oded Goldreich, and Abraham Lempel. 1982. A Randomized Protocol for Signing Contracts. In CRYPTO’82, David Chaum, Ronald L. Rivest, and Alan T. Sherman (Eds.). Plenum Press, New York, USA, 205–210.
[10]
Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. 1999. Spambase Data Set. http://archive.ics.uci.edu/ml/datasets/Spambase/.
[11]
Vladimir Kolesnikov and Thomas Schneider. 2008. Improved Garbled Circuit: Free XOR Gates and Applications. In ICALP 2008, Part II(LNCS, Vol. 5126), Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz (Eds.). Springer, Heidelberg, 486–498. https://doi.org/10.1007/978-3-540-70583-3_40
[12]
Yehuda Lindell. 2013. Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries. In CRYPTO 2013, Part II(LNCS, Vol. 8043), Ran Canetti and Juan A. Garay (Eds.). Springer, Heidelberg, 1–17. https://doi.org/10.1007/978-3-642-40084-1_1
[13]
Yehuda Lindell and Benny Pinkas. 2007. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In EUROCRYPT 2007(LNCS, Vol. 4515), Moni Naor(Ed.). Springer, Heidelberg, 52–78. https://doi.org/10.1007/978-3-540-72540-4_4
[14]
Yehuda Lindell and Ben Riva. 2014. Cut-and-Choose Yao-Based Secure Computation in the Online/Offline and Batch Settings. In CRYPTO 2014, Part II(LNCS, Vol. 8617), Juan A. Garay and Rosario Gennaro (Eds.). Springer, Heidelberg, 476–494. https://doi.org/10.1007/978-3-662-44381-1_27
[15]
S.G. Mallat and Zhifeng Zhang. 1993. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing 41, 12 (1993), 3397–3415. https://doi.org/10.1109/78.258082
[16]
Payman Mohassel and Matthew Franklin. 2006. Efficiency Tradeoffs for Malicious Two-Party Computation. In PKC 2006(LNCS, Vol. 3958), Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin (Eds.). Springer, Heidelberg, 458–473. https://doi.org/10.1007/11745853_30
[17]
Raymond K. H. Tai, Jack P. K. Ma, Yongjun Zhao, and Sherman S. M. Chow. 2017. Privacy-Preserving Decision Trees Evaluation via Linear Functions. In ESORICS 2017, Part II(LNCS, Vol. 10493), Simon N. Foley, Dieter Gollmann, and Einar Snekkenes (Eds.). Springer, Heidelberg, 494–512. https://doi.org/10.1007/978-3-319-66399-9_27
[18]
Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. 2019. Private Evaluation of Decision Trees using Sublinear Cost. PoPETs 2019, 1 (Jan. 2019), 266–286. https://doi.org/10.2478/popets-2019-0015
[19]
Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. 2017. Faster Secure Two-Party Computation in the Single-Execution Setting. In EUROCRYPT 2017, Part III(LNCS, Vol. 10212), Jean-Sébastien Coron and Jesper Buus Nielsen (Eds.). Springer, Heidelberg, 399–424. https://doi.org/10.1007/978-3-319-56617-7_14
[20]
David J. Wu, Tony Feng, Michael Naehrig, and Kristin E. Lauter. 2016. Privately Evaluating Decision Trees and Random Forests. PoPETs 2016, 4 (Oct. 2016), 335–355. https://doi.org/10.1515/popets-2016-0043
[21]
Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract). In 27th FOCS. IEEE Computer Society Press, 162–167. https://doi.org/10.1109/SFCS.1986.25
[22]
Samee Zahur, Mike Rosulek, and David Evans. 2015. Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates. In EUROCRYPT 2015, Part II(LNCS, Vol. 9057), Elisabeth Oswald and Marc Fischlin (Eds.). Springer, Heidelberg, 220–250. https://doi.org/10.1007/978-3-662-46803-6_8
Index Terms
- Secure Decision Forest Evaluation
Index terms have been assigned to the content through auto-classification.
Recommendations
Secure public-key encryption scheme without random oracles
Since the first practical and secure public-key encryption scheme without random oracles proposed by Cramer and Shoup in 1998, Cramer-Shoup's scheme and its variants remained the only practical and secure public-key encryption scheme without random ...
Chosen-ciphertext secure bidirectional proxy broadcast re-encryption schemes
A proxy re-encryption PRE scheme supports the delegation of decryption rights via a proxy, who makes the ciphertexts decryptable by the delegatee. However, how to structure a chosen-ciphertext secure proxy re-encryption scheme without pair is still an ...
A secure signature scheme
IWCMC '06: Proceedings of the 2006 international conference on Wireless communications and mobile computingDigital signature is commonly used for authentication. So, it is important to design a signature with a security proof. In 1999, Gennaro et al. and Cramer et al. respectively proposed practical and provably secure signature schemes under the standard ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2021
1447 pages
ISBN:9781450390514
DOI:10.1145/3465481
Copyright © 2021 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 ACM 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: 17 August 2021
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ARES 2021
ARES 2021: The 16th International Conference on Availability, Reliability and Security
August 17 - 20, 2021
Vienna, Austria
Acceptance Rates
Overall Acceptance Rate 228 of 451 submissions, 51%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 63Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format