Paper 2022/936
PROBONITE : PRivate One-Branch-Only Non-Interactive decision Tree Evaluation
Abstract
Decision trees are among the most widespread machine learning model 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 solution 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 maybe 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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. WAHC22
- Keywords
- Private Decision Tree Evaluation Homomorphic Encryption Functional Bootstrapping Blind Array Access Machine Learning Security and Privacy
- Contact author(s)
-
azogagh sofiane @ courrier uqam ca
delfour victor @ courrier uqam ca
gambs sebastien @ uqam ca
killijian marc-olivier 2 @ uqam ca - History
- 2022-07-26: last of 3 revisions
- 2022-07-18: received
- See all versions
- Short URL
- https://ia.cr/2022/936
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/936,
author = {Sofiane Azogagh and Victor Delfour and Sébastien Gambs and Marc-Olivier Killijian},
title = {PROBONITE : PRivate One-Branch-Only Non-Interactive decision Tree Evaluation},
howpublished = {Cryptology ePrint Archive, Paper 2022/936},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/936}},
url = {https://eprint.iacr.org/2022/936}
}
