# Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE

DevFeed: [Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE](<https://devfeed.tech/articles/signed-dyadic-path-encoding-for-efficient-non-interactive-private-decision-tree-evaluation-over-tfhe-133333.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16818>)

Author: Xintong Song, Yiqiang Zhao, Qizhi Zhang, Yao Li, Jiaji He, Fei Zhao

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>)

Topics: [FHE](<https://devfeed.tech/topics/fhe.md>), [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [catboost](<https://devfeed.tech/topics/catboost.md>)

Tags: [bootstrap](<https://devfeed.tech/tags/bootstrap.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [decision](<https://devfeed.tech/tags/decision.md>), [encoding](<https://devfeed.tech/tags/encoding.md>), [encrypted](<https://devfeed.tech/tags/encrypted.md>), [evaluation](<https://devfeed.tech/tags/evaluation.md>), [faster](<https://devfeed.tech/tags/faster.md>), [gradient](<https://devfeed.tech/tags/gradient.md>), [latency](<https://devfeed.tech/tags/latency.md>), [learning](<https://devfeed.tech/tags/learning.md>), [private](<https://devfeed.tech/tags/private.md>), [security](<https://devfeed.tech/tags/security.md>)

## AI overview

The proposed signed dyadic path-sum encoding reduces programmable bootstraps (PBS) in non-interactive TFHE decision-tree evaluation by packing the two leaf children of each leaf-parent into one test polynomial. This changes the PBS count from one per leaf to one per leaf-parent. The authors prove the labeling is range-minimal and its signed form magnitude-optimal, tightening the comparison-stage noise bound at fixed parameters. They report exact predictions under two derived conditions, with instantiated parameters giving per-inference failure below 2⁻⁶⁴ at 128-bit security. Because ring degree grows linearly with consumed plaintext range, the profitable regime is limited to depths of 4 or less. On standard UCI benchmarks at depths 1-4, latency falls by 1.51x-1.92x for single trees and 2x for ensembles, with no accuracy loss; the method is also reported faster when each scheme uses its own cost-optimal parameters.

## Source excerpt

arXiv:2611.16818v1 Announce Type: new Abstract: Private decision-tree evaluation lets a server classify a client's encrypted query without learning the input. In the non-interactive, path-based setting over TFHE, the server returns a single encrypted prediction by aggregating per-path comparison outcomes, and the standard per-leaf formulation pays one programmable bootstrap (PBS) per leaf, which dominates the cost. We propose a signed dyadic path-sum encoding that nearly halves this cost: each internal node receives a signed dyadic label so that every root-to-leaf path accumulates a distinct integer sum, which lets the two children of a leaf-parent be packed into a single test polynomial and resolved by one PBS, reducing the PBS count from the number of leaves to the number of leaf-parents. We formalize the distinct-sum property and prove that the dyadic labeling is the range-minimal encoding satisfying it, and its half-symmetric signed form is magnitude-optimal, tightening the comparison-stage noise bound at fixed parameters. We derive the two conditions under which the encrypted evaluation returns the exact prediction and instantiate parameters with per-inference failure below $2^{-64}$ at 128-bit security. We show that the ring degree grows linearly with the consumed plaintext range, which confines the profitable regime to depths $\leq 4$, where our method stays faster even when each scheme runs at its own cost-optimal parameters. We further extend the encoding to gradient-boosted ensembles. On standard UCI benchmarks at depths 1-4, our method reduces single-tree latency by $1.51\times$-$1.92\times$ and ensemble latency by $2\times$, without accuracy loss, while preserving the compact, non-interactive response.