Paper 2022/936

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

Sofiane Azogagh, University of Quebec at Montreal
Victor Delfour, University of Quebec at Montreal
Sébastien Gambs, University of Quebec at Montreal
Marc-Olivier Killijian, University of Quebec at Montreal

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.

Available format(s)
Publication info
Published elsewhere. WAHC22
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
2022-07-26: last of 3 revisions
2022-07-18: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.