Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: We're looking at the paper: "Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE".
Elias: Here's the gist of the paper. Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE proposes a signed dyadic path-sum encoding that nearly halves the cost of private decision tree evaluation by packing two children into a single lookup table, reducing the PBS count from the number of leaves to the number of leaf-parents Problem and Context Private decision-tree evaluation addresses the challenge of efficiently classifying encrypted queries without learning input data, which is crucial for privacy in machine learning-as-a-service.
Nadia: Path-based private decision tree evaluation protocols are categorized into interactive and non-interactive paradigms, with the latter being particularly attractive for bandwidth-limited or intermittently connected clients The limiting factor in SumPath family protocols is the leaf selection requiring a zero-test per leaf (TE0), which incurs L PBS operations, dominating inference time.
Elias: Proposed Encoding and Optimality The authors propose a signed dyadic path-sum encoding where each internal node receives a signed dyadic label so that every root-to-leaf path accumulates a distinct integer sum.
Nadia: This labeling is formalized as the half-symmetric signed form, which is proven to be magnitude-optimal and tightens the comparison-stage noise bound.
Title and authors: Nadia: So, we're looking at this paper today, "Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE." It addresses a big problem in private machine learning where you want to classify data without ever seeing the actual input.
Elias: Exactly. The authors are tackling the leaf selection cost that totally dominates things in these path-based protocols, where you need one programmable bootstrap per leaf, which is just too expensive for many applications.
Priya: Before we get into the details, I want to know what this paper actually suggests about how much faster this will be for someone using it in practice.
Nadia: Well, the main idea here is that they propose a signed dyadic path-sum encoding that nearly halves that leaf selection cost by packing two children of each leaf-parent into a single test polynomial.
Elias: That means they are reducing the programmable bootstrap operations from one per leaf, which is L, down to one per leaf-parent, which is P. They achieve this by having every internal node get a signed dyadic label so that every root-to-leaf path accumulates a distinct integer sum.
Priya: Packing two children into one test polynomial sounds like a big win for speed, but what about the security and noise levels? Does this packing introduce any new problems?
Nadia: The authors formalized this signed labeling as the half-symmetric signed form, and they proved it's magnitude-optimal. This means it minimizes the worst-case path sum magnitude, which tightens that comparison stage noise bound at fixed parameters.
Elias: That's important because smaller label magnitudes generally mean less noise in the comparisons happening during inference >
Priya: So, when you look at the results, what are they actually showing? Are these speedups real on standard data sets, or is this just theoretical promise?
Nadia: Experimentally, they showed that for a single tree evaluation on standard UCI benchmarks at depths of one to four, they see a latency reduction of about one point five to one point nine times over the old method.
Elias: And it's interesting because they also extended this idea to gradient-boosted ensembles, where the paper claims a two times reduction in latency compared to the single tree baseline.
Priya: That two times speedup on ensembles is significant because those are often what people use in real machine learning applications. But what about the accuracy? Does all this packing hurt the model's ability to make correct predictions?
Nadia: They showed that at depths of one to four, there's no loss of accuracy on standard datasets, which is pretty good given how much computation they cut down >
Elias: They also analyzed the failure probability and derived two conditions where the encrypted evaluation returns the exact prediction, instantiating parameters so that this per-inference failure probability is below two to the power of negative sixty-four at twelve eight bit security.
Priya: That low failure rate sounds reassuring, especially when you're dealing with sensitive data, but they also mentioned some limitations in their analysis. What exactly are the constraints on when this method works best?
Nadia: They pointed out that the profitable regime for this specific method is confined to tree depths of less than or equal to four where the ring degree grows linearly with the consumed plaintext range >
Elias: That restriction makes sense because they found that beyond that depth, the benefits of this encoding don't outweigh the complexity added by the signed labeling >
Priya: So, to summarize for someone just listening, this paper introduces a way to handle leaf selection in private decision tree evaluation where you use a signed dyadic path-sum encoding. This reduces the cost from one programmable bootstrap per leaf to one per leaf-parent, which cuts inference time by about one point five times on single trees and two times on gradient boosting ensembles >
Nadia: It's an interface compatible replacement for the prior method, keeping that compact single ciphertext response while still cutting down the work done by the server significantly >
Elias: The real strength is how this approach addresses the leaf selection stage, which was always been a bottleneck because it required L operations instead of P operations >
Priya: From my side, what stands out is how they handle comparison noise by using that half-symmetric signed dyadic system to minimize the worst-case path sum magnitude >
Nadia: It’s about making sure the noise in those comparisons doesn't blow up too much when you're working with smaller label magnitudes >
Elias: And as we look ahead, this confirms that for shallow trees, like those common in many tabular models, this encoding provides a real speedup without sacrificing accuracy >
Priya: It’s clear they’ve found a practical sweet spot for where this optimization actually delivers tangible performance gains in the current landscape of privacy-preserving inference >
The paper's summary: Nadia: So, we're looking at this paper today about signed dyadic path encoding for private decision tree evaluation over TFHE. To put it simply, they found a way to cut down the cost of picking which branch to follow in a tree pretty dramatically.
Elias: Exactly. The core idea is that instead of doing one full test operation for every single leaf—that’s what used to take up all your time—they pack two children into just one lookup table.
Priya: That packing is the mechanism, right? What does that mean for the actual running time when someone tries to classify data?
Nadia: It means they cut down the programmable bootstrap operations from doing one per leaf, which is a lot of them, to just one per leaf-parent. That’s a nearly half reduction in cost for inference.
Elias: And this speedup comes from using those signed dyadic labels on every internal node so that every path gets a unique integer sum. It’s formalized as the half-symmetric signed form, which they say minimizes the worst case path sum magnitude.
Priya: So, minimizing the worst case path sum is how they handle that comparison noise we talked about earlier?
Nadia: Right. Smaller label magnitudes mean less noise during those comparisons at the end of a path. It makes the comparison stage much more stable for privacy-preserving systems.
Elias: Experimentally, they showed this works well on single trees at depths one to four, showing a latency reduction of about one point five to one point nine times over the old method without losing accuracy on standard benchmarks.
Priya: That’s interesting because we need to know if that speedup holds up when we look at more complex models, like those gradient boosting ensembles.
Nadia: They did look at that too, and they claimed a two times reduction in latency for the ensembles when they used this new method. That shows the benefit scales pretty well beyond just one simple tree.
Elias: The authors also proved some conditions where you get the exact prediction back, instantiating parameters so that your failure probability stays below two to the power of negative sixty-four at twelve eight bit security. That's solid for privacy guarantees.
Priya: But they did set a limit on when this optimization is actually profitable. They said it works best for tree depths less than or equal to four, where the ring degree grows linearly with the plaintext range you’re using.
Nadia: So, if you’re working on a really deep decision tree, this specific encoding might not give you that massive speedup anymore because of those limits.
Elias: Exactly. The primary benefit is confined to that shallow depth region where these tabular models are actually used in practice today. This points toward a very specific niche for this optimization right now.
Priya: It’s clear they’ve found a practical sweet spot where you get significant speed gains and noise control for the types of trees we see most often in industry.
The paper's improvements: Tom: So, we're looking at how they improved their original approach for signed dyadic path encoding in this paper today. The main takeaway is that they aren't just tweaking the old system; they’ve built a whole new way to handle those leaf selection steps.
Nadia: Right. They focused on making the encoding tighter by using that half-symmetric signed dyadic system we mentioned earlier, which directly tackles comparison noise more effectively.
Elias: That tightening of the comparison noise bound is crucial because it makes the entire evaluation process more robust when you're working with fixed parameters for security. It’s about making sure the error margin stays small even under stress.
Priya: So, what does this mean for someone who just wants to trust that classification result? Does this reduction in noise translate to a lower chance of getting the wrong answer?
Nadia: Yes, it does. By minimizing the worst case path sum magnitude, they’re making the system more reliable when you run these protocols on real data. It keeps those error probabilities very low at twelve eight bit security levels.
Elias: And they also showed how this translates to real performance gains on larger models, specifically gradient boosting decision trees. They found a two times speedup there compared to using a single tree as the baseline for that evaluation.
Priya: A two times speedup on ensembles is pretty substantial because those are the models used in most high-stakes applications right now, like medical diagnosis or finance. Does this apply to all types of decision trees?
Nadia: Not all of them, though they found the benefits are most pronounced for depths one through four. Beyond that depth, the gain from this signed encoding starts to drop off because the complexity just gets too high.
Elias: The paper also sets up conditions where you can guarantee an exact prediction is returned by instantiating parameters so that your failure probability falls below two to the power of negative sixty-four at twelve eight bit security. That’s a hard security floor they established for this method.
Priya: That's a strong statement about the reliability, but I wonder about the practical deployment. How much work is it actually saving in terms of total computation time when we look at real-world scenarios?
Nadia: The speedup on single trees can be one point five to one point nine times, and for those ensembles, it’s two times faster. It’s a noticeable improvement without changing the overall response size from the server.
Elias: So, to sum up these improvements: tighter noise control with the signed system, a two times speedup on ensembles at shallow depths, and a guaranteed low failure probability at high security levels.
Priya: It sounds like they’ve put together a very solid piece of work that makes this specific type of private evaluation much more viable for practical use in the near term.
Conclusion: Nadia: So we're wrapping up on this paper about signed dyadic path encoding for efficient non-interactive private decision tree evaluation over TFHE. To recap, they’ve shown how packing two children into one lookup table cuts down the programmable bootstrap work significantly.
Elias: Exactly. It’s a method that uses signed dyadic labels to ensure every root-to-leaf path gets a unique sum, which then allows them to pack the leaf selection step much tighter.
Priya: From a privacy standpoint, I'm still interested in how robust this is when we look at the actual data—what kind of real-world classification problems this method handles best.
Nadia: Well, they confirmed that for standard UCI benchmarks at depths one to four, there’s no accuracy loss and the noise bound stays tight because of that signed encoding. It’s a very stable result.
Elias: And they showed how it extends to gradient boosting ensembles, where the speedup jumps up to two times compared to using a single tree as the baseline for evaluation. That’s a big number when you think about practical inference time.
Priya: So, it changes things by making these private decision trees faster for those common tabular models we use all day?
Nadia: It does, and they confirmed that the method is interface compatible with prior systems, meaning it fits into existing architectures without needing a total overhaul of the deployment pipeline.
Elias: The main limitation they flagged is that this performance gain really shines when you’re dealing with shallow trees, because beyond depth four, the benefit of this signed encoding doesn't keep up with the complexity added by the labeling itself.
Priya: So we have a method that’s fast and secure for shallow models, but it has specific limits on depth. That’s important context for anyone trying to apply this in a deep learning context.
Nadia: Right. It gives us a clear map of where this optimization is most useful in the current privacy-preserving landscape.
Elias: In short, the paper "Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE" provides a concrete way to reduce inference cost by nearly half on single trees and two times on ensembles, while keeping the noise levels controlled through careful signed labeling.
Priya: It’s a solid piece of work that shows how cryptographic tools can be tailored to specific model structures for better efficiency.
Nadia: Exactly. Next up, we’re diving into some papers about cross-chain payments and threat knowledge graphs. Stick around, because those are going to be interesting too.
Xintong Song, Yiqiang Zhao, Qizhi Zhang, Yao Li, Jiaji He, Fei Zhao
Tianjin University · Peking University
cs.CR
Submitted: 2026-11-12
Updated: 2026-11-12
Comments: 17 pages (15 + 2 pages of supplementary material), 6 figures, 9 tables. Submitted to IEEE Transactions on Emerging Topics in Computing
Code: https://github.com/xsong93/sdpe-pdte
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 96/100
The gist: Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE proposes a signed dyadic path-sum encoding that nearly halves the cost of private decision tree…
Key concepts
- Signed Dyadic Path Encoding
- This is a specific method of labeling internal nodes in the decision tree. Each node gets a signed dyadic label, which allows the path from the root to any leaf to accumulate a distinct integer sum. This structured labeling is key to enabling efficient path-sum accumulation during evaluation.
- Leaf-Parent Packing
- This is the core cost reduction technique where two children of each leaf-parent node are combined into a single test polynomial or lookup table. Instead of performing separate tests for each child, one operation determines which child is active and returns its label simultaneously, drastically cutting the number of required operations.
- Path Sums (PBS)
- Path-based private decision tree evaluation relies on accumulating sums along the path from the root to a leaf. The original method required one PBS operation for every leaf in the tree. The proposed encoding changes this to require one PBS operation for every leaf-parent, which is a substantial reduction in computational cost.
- Half-Symmetric Signed System
- This refers to the specific mathematical system used for labeling nodes. By using a half-symmetric signed form, the authors ensure that the path sums have minimal worst-case magnitude. This property helps reduce comparison noise during evaluation, leading to better robustness in systems where noise is a limiting factor.
Terminology
Summary
Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE proposes a signed dyadic path-sum encoding that nearly halves the cost of private decision tree evaluation by packing two children into a single lookup table, reducing the PBS count from the number of leaves to the number of leaf-parents
Problem and Context
Private decision-tree evaluation addresses the challenge of efficiently classifying encrypted queries without learning input data, which is crucial for privacy in machine learning-as-a-service. Path-based private decision tree evaluation protocols are categorized into interactive and non-interactive paradigms, with the latter being particularly attractive for bandwidth-limited or intermittently connected clients The limiting factor in SumPath family protocols is the leaf selection requiring a zero-test per leaf (TE0), which incurs L PBS operations, dominating inference time. p. 0
Proposed Encoding and Optimality
The authors propose a signed dyadic path-sum encoding where each internal node receives a signed dyadic label so that every root-to-leaf path accumulates a distinct integer sum. This labeling is formalized as the half-symmetric signed form, which is proven to be magnitude-optimal and tightens the comparison-stage noise bound. p. 0 The distinct-sum property (DSP) guarantees that the two level combinations are pairwise distinct, which ensures that each fv returns the active child’s label when v is active and zero otherwise. p. 6
Cost Reduction Mechanism
The core contribution is a leaf-selection primitive that nearly halves the PBS count by packing the two children of each leaf-parent into a single test polynomial, reducing the cost from one PBS per leaf L to one PBS per leaf-parent P. This is achieved by accumulating encrypted root-to-leaf-parent (RTLP) path sums instead of RTL paths, allowing one PBS to simultaneously determine which child lies on the active path and return its class label. p. 5
Performance and Extensions
Experimental results show that the method reduces single-tree inference latency by 1.51×–1.92× over TE0 without accuracy loss on standard UCI benchmarks at depths 1–4. p. 0 The extension to gradient-boosted ensembles shows a 2× reduction in latency, confirming that the reduction in PBS count translates directly into end-to-end speedup for practical gradient-boosted evaluation. p. 2
Correctness and Failure Analysis
The paper derives two conditions under which the encrypted evaluation returns the exact prediction, instantiating parameters such that the per-inference failure probability is below 2−64 at 128-bit security. The noise analysis shows that the signed encoding provides an additional margin because its smaller label magnitudes reduce comparison noise, making it material in comparison-noise-dominated systems. p. 2 The profitable regime is confined to depths ≤ 4 where the ring degree grows linearly with the consumed plaintext range. p. 0
Conclusion and Trade-offs
The method is an interface-compatible replacement for the prior TE0 aggregation, preserving the compact single-ciphertext response while reducing PBS work from L to P. The speedup is at most 1 + a/(a + b) and reaches the full factor of two on balanced trees, confirming that the encoding's primary benefit is confined to the leaf-selection stage. The profitable region for this method coincides with the shallow depths typical of practical tabular models. p. 2
References
[2] Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser, “Machine learning classification over encrypted data,” Cryptology ePrint Archive, Paper 2014/331, 2014. Available: https://eprint.iacr.org/2014/331
[3] David J Wu, Tony Feng, Michael Naehrig, and Kristin Lauter, “Privately evaluating decision trees and random forests,” Proceedings on Privacy Enhancing Technologies, 2016.
[4] Raymond KH Tai, Jack PK Ma, Yongjun Zhao, and Sherman SM Chow, “Privacy-preserving decision trees evaluation via linear functions,” in European Symposium on Research in Computer Security. p. 0 Springer, 2017.
[5] Agnes Kiss, Masoud Naderpour, Jian Liu, N Asokan, and Thomas ´Schneider, “Sok: Modular and efficient private decision tree evaluation,” Proceedings on Privacy Enhancing Technologies, 2019. p. 0
[6] Jack PK Ma, Raymond KH Tai, Yongjun Zhao, and Sherman SM Chow, “Let’s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation,” in The Network and Distributed System Security Symposium (NDSS), 2021.
[7] Sona Alex, KJ Dhanaraj, and PP Deepthi, “Private and energy-efficient decision tree-based disease detection for resource-constrained medical users in mobile healthcare network,” IEEE Access, vol. p. 0 10, pp. 17 098–17 112, 2022.
[8] Shuai Yuan, Hongwei Li, Xinyuan Qian, Meng Hao, Yixiao Zhai, and Guowen Xu, “Efficient and privacy-preserving outsourcing of gradient boosting decision tree inference,” IEEE Transactions on Services Computing, vol. p. 0 17, no. 5, pp. 2334–2348, 2024.
[9] Ronny Ko, Abdelkarim Kati, Robin Geelen, Rasoul Akhavan Mahdavi, Byoungwoo Yoon, Jongho Shin, Zhiqiang Lin, Makoto Onizuka, and Florian Kerschbaum, “Silentwood: Efficient private inference over gradient-boosting decision forests,” 2026. p. 0 Available: https://arxiv. p. 0 p. 0 p. 0org/abs/2411.15494
[10] Satoshi Fukui, Lihua Wang, and Seiichi Ozawa, “Efficient and privacypreserving decision tree inference via homomorphic matrix multiplication and leaf node pruning,” Applied Sciences, vol. 15, no. 10, p. 5560, 2025.
[11] Wei Xu, Hui Zhu, Yandong Zheng, Song Bian, Ning Sun, Yuan Hao, Dengguo Feng, and Hui Li “Kangaroo: A private and amortized inference framework over wan for large-scale decision tree evaluation,” in Proceedings 2026 Network and Distributed System Security Symposium. ser. NDSS 2026. Internet Society, 2026. p. 0 Available: http://dx.doi.org/10.14722/ndss.2026.
[15] Kanthi Sarpatwar, Karthik Nandakumar, Nalini Ratha, James Rayfield, Karthikeyan Shanmugam, Sharath Pankanti, and Roman Vaculin “Efficient encrypted inference on ensembles of decision trees,” 2021. p. 0 Available: https://arxiv.org/abs/2103.03411
[16] Sofiane Azogagh, Victor Delfour, Sebastien Gambs, and Marc-Olivier ´Killijian “Probonite: Private one-branch-only non-interactive decision tree evaluation,” in Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2022.
[17] Kelong Cong, Debajyoti Das, Jeongeun Park, and Hilder VL Pereira “Sortinghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022. p. 0
[18] Jestine Paul, Benjamin Hong Meng Tan, Bharadwaj Veeravalli, and Khin Mi Mi Aung “Non-interactive decision trees and applications with multi-bit tfhe,” Algorithms, vol. p. 0 15, no. 9, p. 333, 2022.
[19] Rasoul Akhavan Mahdavi, Haoyan Ni, Dimitry Linkov, and Florian Kerschbaum “Level up: Private non-interactive decision tree evaluation using levelled homomorphic encryption,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023. p. 0
[20] Jordan Frery, Andrei Stoian, Roman Bredehoft, Luis Montero, Celia Kherfallah, Benoit Chevallier-Mames, and Arthur Meyre “Privacypreserving tree-based inference with tfhe,” in International Conference on Mobile, Secure, and Programmable Networking. p. 0 Springer, 2023.
[21] Kelong Cong, Jiayi Kang, Georgio Nicolas, and Jeongeun Park “Faster private decision tree evaluation for batched input from homomorphic encryption,” in International Conference on Security and Cryptography for Networks. p. 0 Springer, 2024.
[23] El Hadji Mamadou Dia, Walid Arabi, Anis Bkakria, and Reda Yaich “Strawhat: Private non-interactive gradient boosting decision tree evaluation based on homomorphic encryption,” in International Symposium on Foundations and Practice of Security. p. 0 Springer, 2025.
[24] Kexin Xu, Benjamin Hong Meng Tan, Li-Ping Wang, Khin Mi Mi Aung, and Huaxiong Wang “Privacy-preserving outsourcing decision tree evaluation from homomorphic encryption,” Journal of Information Security and Applications, vol. p. 0 77, p. 103582, 2023.
[25] Dongjin Park, Gyeongwon Cha, and Joon-Woo Lee “LCPDTE: Low-complexity private decision tree evaluation over homomorphic encryption,” Cryptology ePrint Archive, Paper 2026/1263, 2026. p. 0
[26] DIA El Hadji Mamadou Dia, Walid ARABI, Anis BKAKRIA, and Reda YAICH “A comprehensive survey of privacy-preserving decision trees based on homomorphic encryption,” Cryptology ePrint Archive, Paper 2025/1310, 2025. p. 0
[28] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene “Tfhe: Fast fully homomorphic encryption over the torus,” J. p. 0 Cryptol., vol. 33, no. 1, pp. 34–91, Jan. 2020.
[29] Florian Tramer, Fan Zhang, Ari Juels, Michael K. p. 0 Reiter, and Thomas Ristenpart “Stealing machine learning models via prediction apis,” in Proceedings of the 25th USENIX Conference on Security Symposium, ser. p. 0 SEC’16. USA: USENIX Association, 2016, pp. 601–618
[30] Brad Boehmke and Brandon Greenwell, Hands-On Machine Learning with R. Chapman and Hall/CRC, 11 2019
[31] Martin R. Albrecht, Rachel Player, and Sam Scott “On the concrete hardness of learning with errors,” Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169–203, 2015
[32] Jean-Philippe Bossuat, Rosario Cammarota, Ilaria Chillotti, Benjamin R. Curtis, Wei Dai, Huijing Gong, Erin Hales, Duhyeong Kim, Bryan Kumara, Changmin Lee, Xianhui Lu, Carsten Maple et al “Security guidelines for implementing homomorphic encryption,” IACR Communications in Cryptology vol. 1 no. 4, 2025
[33] Olivier Bernard, Marc Joye, Nigel P. Smart, and Michael Walter “Drifting towards better error probabilities in fully homomorphic encryption schemes,” in Advances in Cryptology – EUROCRYPT 2025, Serge Fehr and Pierre-Alain Fouque, Eds. Cham: Springer Nature Switzerland, 2025. p. 1
[34] Anselme Tueno, Yordan Boev, and Florian Kerschbaum “Noninteractive private decision tree evaluation,” in IFIP Annual Conference on Data and Applications Security and Privacy. p. 0 Springer, 2020.
[35] Kanthi Sarpatwar, Karthik Nandakumar, Nalini Ratha, James Rayfield, Karthikeyan Shanmugam, Sharath Pankanti, and Roman Vaculin “Efficient encrypted inference on ensembles of decision trees,” 2021. p. 0
[36] Jack PK Ma, Raymond KH Tai, Yongjun Zhao, and Sherman SM Chow “Let’s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation,” in The Network and Distributed System Security Symposium (NDSS), 2021.
[37] Sona Alex, KJ Dhanaraj, and PP Deepthi “Private and energy-efficient decision tree-based disease detection for resource-constrained medical users in mobile healthcare network,” IEEE Access, vol. p. 0 10, pp. 17 098–17 112, 2022.
[38] Shuai Yuan, Hongwei Li, Xinyuan Qian, Meng Hao, Yixiao Zhai, and Guowen Xu “Efficient and privacy-preserving outsourcing of gradient boosting decision tree inference,” IEEE Transactions on Services Computing vol. p. 0 17 no. 5 pp. 2334–2348, 2024
[39] Ronny Ko, Abdelkarim Kati, Robin Geelen, Rasoul Akhavan Mahdavi, Byoungwoo Yoon, Jongho Shin, Zhiqiang Lin, Makoto Onizuka and Florian Kerschbaum “Silentwood: Efficient private inference over gradient-boosting decision forests,” 2026. Available: https://arxiv.org/abs/2411.15494
[40] Satoshi Fukui, Lihua Wang, and Seiichi Ozawa “Efficient and privacypreserving decision tree inference via homomorphic matrix multiplication and leaf node pruning,” Applied Sciences, vol. 15, no. 10, p. 5560, 2025
[43] Anselme Tueno, Yordan Boev, and Florian Kerschbaum “Noninteractive private decision tree evaluation,” in IFIP Annual Conference on Data and Applications Security and Privacy. Springer, 2020.
Table I
TABLE I NON-INTERACTIVE SINGLE-RESPONSE TFHE SCHEMES: PER-INFERENCE COST. I, P, L DENOTE THE SETS OF INTERNAL NODES, LEAF-PARENTS, AND LEAVES, t IS THE OPERAND BITWIDTH, l THE GADGET LEVEL, and N THE RING DEGREE
Scheme Family Query / attribute Blind rotations Other server cost Response
Frery et al. [20] MatrixTransform 1 LWE |I| + |L| matrix products 1 LWE
SortingHat [17] MultiplyPath l RLWE3 0
Paul et al. [18] SumPath ⌈t/4⌉ LWE I + L prefix sums 1 LWE
TE0 (TFHE) [21]4 SumPath 1 RLWE L I (CP + CPE + SUM) 1 LWE
Ours SumPath 1 RLWE P I (CP + SUM) 1 LWE
Table II
TABLE II NOTATION USED THROUGHOUT THIS PAPER. Symbol Meaning T decision tree I set of internal nodes P set of leaf-parents L set of leaf nodes η tree depth d node level, d ∈ 1. p. 3.., η
[32] TFHE Ciphertexts defines three ciphertext types over the torus, each serving a distinct role in homomorphic computation.
[28] TRLWE ciphertext extends this construction to the polynomial domain, encrypting a message µ(X) ∈ TN [X] whose N coefficients provide up to N independent plaintext slots under a secret key s(X). p. 3
[28] A TRGSW ciphertext, in turn, encrypts a polynomial and enables the external product ⊡: TRGSW × TRLWE → TRLWE, which multiplies the underlying plaintexts while maintaining controlled noise growth. p. 3
[28] The PBS [28], which simultaneously reduces a ciphertext’s noise to a fixed level and evaluates an arbitrary function on its message. p. 3
Table III
TABLE III THE OPTIMAL SIGNED DYADIC SYSTEM S∗ FOR m = 3. THE ATTAINABLE PATH SUMS FORM THE GAP-FREE INTERVAL (−4, 3), ATTAINING THE OPTIMAL RANGE M = 2m−1 = 4
[26] The half-symmetric signed dyadic system S∗ minimizes the worst-case path-sum magnitude.
Table IV
TABLE IV CRYPTOGRAPHIC PARAMETERS. SINGLE-TREE CONFIGURATIONS ARE COST-OPTIMAL PER DEPTH AND SCHEME AND ARE LISTED IN TABLE VI; THE VALUES BELOW ARE SHARED ACROSS ALL EXPERIMENTS (TOP) OR SPECIFIC TO THE GRADIENT-BOOSTED ENSEMBLE (BOTTOM)
Table V
TABLE V DATASETS USED IN THE EVALUATION. Cancer, Heart, Spambase are binary, whereas Steel (7 classes) is multi-class, so the evaluation exercises our leaf encoding across both regimes. p. 9
Table VI
TABLE VI PER-STAGE DECISION-TREE INFERENCE CPU TIME, ONE QUERY AT A TIME, MEAN OVER 50 QUERIES2, b = 6
Table VII
TABLE VII GBDT INFERENCE TIME AND SPEEDUP AT DEPTH 3 WITH 80 TREES PER CLASS ON THE STEEL DATASET.
Fig. 1
Fig. 1 Overview of non-interactive PDTE under homomorphic encryption (HE) The client sends its encrypted private feature vector to the server, which holds the decision tree model in plaintext
Fig. 2
Fig. 2 Example of our tree traversal on a depth-3 tree Each node displays its feature index (blue), threshold (red), and comparison outcome (green) under the input, which is shown in Figure 3
Fig. 3
Fig. 3 Path-sum images for m = 3 The optimal half-symmetric signed dyadic system S∗ (top) fills a gap-free interval of 2m = 8 consecutive integers with range M = 2m−1 = 4
Fig. 4
Fig. 4 Model accuracy versus bitwidth at depth=4, mean over seeds The model accuracy matches the baseline on every dataset at b=6
Fig. 5
Fig. 5 Model accuracy as a function of the rescaling factor κ for gradient boosting forests of depths 2–4 The model accuracy converges to the plaintext ceiling at κ = 10
Fig. 6
Fig. 6 Model accuracy as a function of the per-class tree count for gradient boosting forests of depths 2–4 The model accuracy converges to the plaintext ceiling at κ = 10
**Fig.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Reduce inference latency by nearly half through a signed dyadic path-sum encoding that packs two children of each leaf-parent into a single lookup table, which reduces the PBS count from the number of leaves to the number of leaf-parents.
-
Improve robustness against comparison noise by utilizing a half-symmetric signed dyadic system that minimizes the worst-case path-sum magnitude, which in turn tightens the comparison-stage noise bound at fixed parameters.
-
Achieve 18 percentage points improvement in model accuracy when evaluating gradient boosting decision trees on multi-class datasets, while simultaneously reducing latency by two times compared to a single tree baseline.
-
Enable efficient non-interactive private decision tree evaluation for resource-constrained platforms by maintaining the compact single-ciphertext response profile while achieving a per-inference failure probability below 2 to the power of -64 at 128 bit security.
Sources
- SilentWood: Efficient Private Inference Over Gradient-Boosting Decision Forests
- Efficient Encrypted Inference on Ensembles of Decision Trees
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data