research-article

Open access

PROBONITE: PRivate One-Branch-Only Non-Interactive decision Tree Evaluation

Authors:

Sofiane Azogagh,

Victor Delfour,

Sébastien Gambs,

Marc-Olivier KillijianAuthors Info & Claims

WAHC'22: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

Pages 23 - 33

https://doi.org/10.1145/3560827.3563377

Published: 07 November 2022 Publication History

Abstract

Decision trees are among the most widespread machine learning models used for data classification, in particular due to their interpretability that makes it easy to explain their prediction. In this paper, we propose a novel protocol for the private classification of a client request in a non-interactive manner. In contrast to existing solutions to this problem, which are either interactive or require evaluating all the branches of the decision tree, our approach only evaluates a single branch of the tree. Our protocol is based on two primitives that we also introduce in this paper and that may be of independent interest : Blind Node Selection and Blind Array Access. Those contributions are based on recent advances in homomorphic cryptography, such as the functional bootstrapping mechanism recently proposed for the Fully Homomorphic Encryption over the Torus scheme TFHE. Our private decision tree evaluation algorithm is highly efficient as it requires only one round of communication and d comparisons, with d being the depth of the tree, while other state-of-the-art non-interactive protocols need 2^d comparisons.

References

[1]

Adi Akavia, Max Leibovich, Yehezkel S. Resheff, Roey Ron, Moni Shahar, and Margarita Vald. 2022. Privacy-Preserving Decision Trees Training and Prediction. ACM Trans. Priv. Secur., Vol. 25, 3, Article 24 (may 2022), 30 pages. https://doi.org/10.1145/3517197

Digital Library

[2]

Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. 2022. OpenFHE: Open-Source Fully Homomorphic Encryption Library. Cryptology ePrint Archive, Paper 2022/915. (2022). https://eprint.iacr.org/2022/915 https://eprint.iacr.org/2022/915.

[3]

Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. 2015. Machine Learning Classification over Encrypted Data. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, February 8--11, 2015. The Internet Society, 220--233. https://www.ndss-symposium.org/ndss2015/machine-learning-classification-over-encrypted-data

[4]

Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. 2018. Fast Homomorphic Evaluation of Deep Discretized Neural Networks. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19--23, 2018, Proceedings, Part III (Lecture Notes in Computer Science), Hovav Shacham and Alexandra Boldyreva (Eds.), Vol. 10993. Springer, 483--512. https://doi.org/10.1007/978--3--319--96878-0_17

[5]

Leo Breiman. 2001. Random Forests. Mach. Learn., Vol. 45, 1 (2001), 5--32. https://doi.org/10.1023/A:1010933404324

Digital Library

[6]

Sergiu Carpov, Malika Izabachène, and Victor Mollimard. 2018. New techniques for Multi-value input Homomorphic Evaluation and Applications. Cryptology ePrint Archive, Paper 2018/622. (2018). https://eprint.iacr.org/2018/622 https://eprint.iacr.org/2018/622.

[7]

Olive Chakraborty and Martin Zuber. 2022. Efficient and Accurate homomorphic comparisons. Cryptology ePrint Archive, Paper 2022/622. (2022). https://eprint.iacr.org/2022/622 https://eprint.iacr.org/2022/622.

[8]

Hao Chen, Ilaria Chillotti, and Ling Ren. 2019. Onion Ring ORAM: Efficient Constant Bandwidth Oblivious RAM from (Leveled) TFHE. Cryptology ePrint Archive, Paper 2019/736. (2019). https://eprint.iacr.org/2019/736 https://eprint.iacr.org/2019/736.

[9]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachè ne. 2016a. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4--8, 2016, Proceedings, Part I (Lecture Notes in Computer Science), Jung Hee Cheon and Tsuyoshi Takagi (Eds.), Vol. 10031. 3--33. https://doi.org/10.1007/978--3--662--53887--6_1

[10]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachè ne. 2018. TFHE: Fast Fully Homomorphic Encryption over the Torus. IACR Cryptol. ePrint Arch. (2018), 421. https://eprint.iacr.org/2018/421

[11]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020a. TFHE: fast fully homomorphic encryption over the torus. Journal of Cryptology, Vol. 33, 1 (2020), 34--91.

Digital Library

[12]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. August 2016 b. TFHE: Fast Fully Homomorphic Encryption Library. ( August 2016). https://tfhe.github.io/tfhe/.

[13]

Ilaria Chillotti, Marc Joye, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. 2020b. CONCRETE: Concrete Operates oN Ciphertexts Rapidly by Extending TfhE. In WAHC 2020--8th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Vol. 15.

[14]

Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. 1998. Private Information Retrieval. J. ACM, Vol. 45, 6 (1998), 965--981. https://doi.org/10.1145/293347.293350

Digital Library

[15]

Kelong Cong, Debajyoti Das, Jeongeun Park, and Hilder Vitor Lima Pereira. Efficient Privacy Preserving Tools based on Homomorphic Encryption. ( ????). Poster presented at FHE.org Conference 2022, Trondheim, Norway.

[16]

Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. (2017). http://archive.ics.uci.edu/ml

[17]

Dario Fiore, Anca Nitulescu, and David Pointcheval. 2020. Boosting Verifiable Computation on Encrypted Data. Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4--7, 2020, Proceedings, Part II (Lecture Notes in Computer Science), Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas (Eds.), Vol. 12111. Springer, 124--154. https://doi.org/10.1007/978--3-030--45388--6_5

[18]

Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2013. Proceedings, Part I (Lecture Notes in Computer Science), Ran Canetti and Juan A. Garay (Eds.), Vol. 8042. Springer, 75--92. https://doi.org/10.1007/978--3--642--40041--4_5

[19]

Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In Proceedings of the nineteenth annual ACM symposium on Theory of computing. 182--194.

Digital Library

[20]

Oded Goldreich and Rafail Ostrovsky. 1996 a. Software Protection and Simulation on Oblivious RAMs. J. ACM, Vol. 43, 3 (may 1996), 431--473. https://doi.org/10.1145/233551.233553

Digital Library

[21]

Oded Goldreich and Rafail Ostrovsky. 1996 b. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), Vol. 43, 3 (1996), 431--473.

Digital Library

[22]

Ilia Iliashenko and Vincent Zucca. 2021. Faster homomorphic comparison operations for BGV and BFV. Proc. Priv. Enhancing Technol., Vol. 2021, 3 (2021), 246--264. https://doi.org/10.2478/popets-2021-0046

[23]

Malika Izabachè ne, Renaud Sirdey, and Martin Zuber. 2019. Practical Fully Homomorphic Encryption for Fully Masked Neural Networks. In Cryptology and Network Security - 18th International Conference, CANS 2019, Fuzhou, China, October 25--27, 2019, Proceedings (Lecture Notes in Computer Science), Yi Mu, Robert H. Deng, and Xinyi Huang (Eds.), Vol. 11829. Springer, 24--36. https://doi.org/10.1007/978--3-030--31578--8_2

[24]

Stanisław Jarecki and Vitaly Shmatikov. 2007. Efficient two-party secure computation on committed inputs. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 97--114.

Digital Library

[25]

Wenjie Lu, Jun-Jie Zhou, and Jun Sakuma. 2018a. Non-interactive and Output Expressive Private Comparison from Homomorphic Encryption. In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS 2018, Incheon, Republic of Korea, June 04-08, 2019, Jong Kim, Gail-Joon Ahn, Seungjoo Kim, Yongdae Kim, Javier Ló pez, and Taesoo Kim (Eds.). ACM, 67--74. https://doi.org/10.1145/3196494.3196503

Digital Library

[26]

Wen-jie Lu, Jun-Jie Zhou, and Jun Sakuma. 2018b. Non-interactive and output expressive private comparison from homomorphic encryption. In Proceedings of the 2018 on Asia Conference on Computer and Communications Security. 67--74.

[27]

Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. 2016. XPIR : Private Information Retrieval for Everyone. Proc. Priv. Enhancing Technol., Vol. 2016, 2 (2016), 155--174. https://doi.org/10.1515/popets-2016-0010

[28]

Goldreich Oded. 2009. Foundations of Cryptography: Volume 2, Basic Applications 1st ed.). Cambridge University Press, USA.

[29]

Femi G. Olumofin and Ian Goldberg. 2011. Revisiting the Computational Practicality of Private Information Retrieval. In Financial Cryptography and Data Security - 15th International Conference, FC 2011, Gros Islet, St. Lucia, February 28 - March 4, 2011, Revised Selected Papers (Lecture Notes in Computer Science), George Danezis (Ed.), Vol. 7035. Springer, 158--172. https://doi.org/10.1007/978--3--642--27576-0_13

[30]

Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael P. Wellman. 2018. SoK: Security and Privacy in Machine Learning. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P). 399--414. https://doi.org/10.1109/EuroSP.2018.00035

[31]

Michael O. Rabin. 2005. How To Exchange Secrets with Oblivious Transfer. IACR Cryptol. ePrint Arch. (2005), 187. http://eprint.iacr.org/2005/187

[32]

Adi Shamir. 1979. How to Share a Secret. Commun. ACM, Vol. 22, 11 (nov 1979), 612--613. https://doi.org/10.1145/359168.359176

Digital Library

[33]

Sean W. Smith and David Safford. 2001. Practical server privacy with secure coprocessors. IBM Syst. J., Vol. 40, 3 (2001), 683--695. https://doi.org/10.1147/sj.403.0683

Digital Library

[34]

Anselme Tueno, Yordan Boev, and Florian Kerschbaum. 2020. Non-interactive Private Decision Tree Evaluation. Data and Applications Security and Privacy XXXIV - 34th Annual IFIP WG 11.3 Conference, DBSec 2020, Regensburg, Germany, June 25--26, 2020, Proceedings (Lecture Notes in Computer Science), Anoop Singhal and Jaideep Vaidya (Eds.), Vol. 12122. Springer, 174--194. https://doi.org/10.1007/978--3-030--49669--2_10

[35]

Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. 2019. Private Evaluation of Decision Trees using Sublinear Cost. Proc. Priv. Enhancing Technol., Vol. 2019, 1 (2019), 266--286. https://doi.org/10.2478/popets-2019-0015

[36]

David J. Wu, Tony Feng, Michael Naehrig, and Kristin E. Lauter. 2016. Privately Evaluating Decision Trees and Random Forests. Proc. Priv. Enhancing Technol., Vol. 2016, 4 (2016), 335--355. https://doi.org/10.1515/popets-2016-0043

[37]

Martin Zuber and Renaud Sirdey. 2021. Efficient homomorphic evaluation of k-NN classifiers. Proc. Priv. Enhancing Technol., Vol. 2021, 2 (2021), 111--129. io

Cited By

Yang HShen SLiu ZZhao Y(2024)cuXCMP: CUDA-Accelerated Private Comparison Based on Homomorphic EncryptionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.326767719(3581-3592)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3267677
Petrean DPotolea ROprisa C(2024)Packed Code Detection using Shannon Entropy and Homomorphic Encrypted Executables2024 IEEE 20th International Conference on Intelligent Computer Communication and Processing (ICCP)10.1109/ICCP63557.2024.10793050(01-08)Online publication date: 17-Oct-2024
https://doi.org/10.1109/ICCP63557.2024.10793050
Azogagh SDelfour VKillijian M(2024)Oblivious Turing Machine2024 19th European Dependable Computing Conference (EDCC)10.1109/EDCC61798.2024.00017(17-24)Online publication date: 8-Apr-2024
https://doi.org/10.1109/EDCC61798.2024.00017
Show More Cited By

Index Terms

PROBONITE: PRivate One-Branch-Only Non-Interactive decision Tree Evaluation
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Classification and regression trees
2. Security and privacy
  1. Cryptography
  2. Security services
    1. Privacy-preserving protocols

Recommendations

Level Up: Private Non-Interactive Decision Tree Evaluation using Levelled Homomorphic Encryption
CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

As machine learning as a service continues gaining popularity, concerns about privacy and intellectual property arise. Users often hesitate to disclose their private information to obtain a service, while service providers aim to protect their ...
Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can "freely" perform the operation inevitably means ...
Lossy encryption: constructions from general assumptions and efficient selective opening chosen ciphertext security
ASIACRYPT'11: Proceedings of the 17th international conference on The Theory and Application of Cryptology and Information Security

Lossy encryption was originally studied as a means of achieving efficient and composable oblivious transfer. Bellare, Hofheinz and Yilek showed that lossy encryption is also selective opening secure. We present new and general constructions of lossy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WAHC'22: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

November 2022

70 pages

ISBN:9781450398770

DOI:10.1145/3560827

Program Chairs:
Michael Brenner
Leibniz Universität Hannover
,
Anamaria Costache
NTNU: Norwegian University of Science and Technology
,
Kurt Rohloff
NJIT and Duality Technologies

Copyright © 2022 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]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Canada Research Chair on privacy-preserving and ethical analysis of Big Data
Discovery Grant from NSERC
Discovery Grant from NSERC #2
NSERC-RDC DEEL

Conference

CCS '22

Sponsor:

SIGSAC

CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security

November 7, 2022

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 6 of 17 submissions, 35%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
397
Total Downloads

Downloads (Last 12 months)166
Downloads (Last 6 weeks)21

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang HShen SLiu ZZhao Y(2024)cuXCMP: CUDA-Accelerated Private Comparison Based on Homomorphic EncryptionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.326767719(3581-3592)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3267677
Petrean DPotolea ROprisa C(2024)Packed Code Detection using Shannon Entropy and Homomorphic Encrypted Executables2024 IEEE 20th International Conference on Intelligent Computer Communication and Processing (ICCP)10.1109/ICCP63557.2024.10793050(01-08)Online publication date: 17-Oct-2024
https://doi.org/10.1109/ICCP63557.2024.10793050
Azogagh SDelfour VKillijian M(2024)Oblivious Turing Machine2024 19th European Dependable Computing Conference (EDCC)10.1109/EDCC61798.2024.00017(17-24)Online publication date: 8-Apr-2024
https://doi.org/10.1109/EDCC61798.2024.00017
Choi JChoi JLee YHong J(2024)Privacy-Preserving Rule Induction Using CKKSIEEE Access10.1109/ACCESS.2024.349804012(171540-171558)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3498040
Petrean DPotolea R(2024)Random forest evaluation using multi-key homomorphic encryption and lookup tablesInternational Journal of Information Security10.1007/s10207-024-00823-123:3(2023-2041)Online publication date: 14-Mar-2024
https://dl.acm.org/doi/10.1007/s10207-024-00823-1
Cong KKang JNicolas GPark J(2024)Faster Private Decision Tree Evaluation for Batched Input from Homomorphic EncryptionSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_1(3-23)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71073-5_1
Shin HChoi JLee DKim KLee Y(2024)Fully Homomorphic Training and Inference on Binary Decision Tree and Random ForestComputer Security – ESORICS 202410.1007/978-3-031-70896-1_11(217-237)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70896-1_11
Adir AAharoni EDrucker NLevy RShaul HSoceanu OAdir AAharoni EDrucker NLevy RShaul HSoceanu O(2024)Privacy-Preserving Machine Learning with HEHomomorphic Encryption for Data Science (HE4DS)10.1007/978-3-031-65494-7_10(235-270)Online publication date: 25-Jul-2024
https://doi.org/10.1007/978-3-031-65494-7_10
Akhavan Mahdavi RNi HLinkov DKerschbaum FMeng WJensen CCremers CKirda E(2023)Level Up: Private Non-Interactive Decision Tree Evaluation using Levelled Homomorphic EncryptionProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623095(2945-2958)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623095
Xu KTan BWang LAung KWang H(2023)Privacy-preserving outsourcing decision tree evaluation from homomorphic encryptionJournal of Information Security and Applications10.1016/j.jisa.2023.10358277:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.jisa.2023.103582

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten