Halving the Expensive Part of Encrypted Decision Trees by Relabeling the Paths

A signed dyadic labeling trick cuts the dominant cost of private decision-tree evaluation over TFHE nearly in half, with formal proofs of optimality — but only for shallow trees.

Imagine you're running a mail-sorting machine where every letter must pass through an expensive X-ray scanner before it reaches its destination bin. The standard setup puts one scanner at every bin — one per leaf in decision-tree speak. This paper notices that two adjacent bins always share a parent corridor, so you can merge those two scans into one by giving each corridor a cleverly chosen signed number. Walk any path from the entrance, add up the numbers, and the final sum uniquely identifies the bin. Two sibling bins, one scan. That's the whole trick, and it's a good one. The committed claim: a signed dyadic path-sum encoding reduces the number of programmable bootstraps (PBS) — the single most expensive operation in TFHE-based private inference — from the number of leaves to the number of leaf-parents, which is roughly half. The encoding is provably range-minimal (no labeling can use a smaller integer range and still guarantee distinct path sums) and the half-symmetric signed variant is magnitude-optimal, meaning it keeps the noise budget as tight as possible at fixed security parameters. This is not a heuristic speedup; it's a formally proven structural optimization. The ladder is clear and honest. The standard non-interactive path-based TFHE evaluation (SortingHat, TFHE-based frameworks) pays one PBS per leaf. This method pays one PBS per leaf-parent, yielding 1.51×–1.92× latency reduction on single trees at depths 1–4, and 2× on gradient-boosted ensembles, all on standard UCI benchmarks with zero accuracy loss. The authors are explicit about the ceiling: ring degree grows linearly with consumed plaintext range, confining the profitable regime to depth ≤ 4. Beyond that, the encoding's advantage evaporates because the polynomial degree blows up. This is an honest limitation, not buried in footnotes. Architecturally, this lives in the TFHE (Torus Fully Homomorphic Encryption) family — specifically the non-interactive, path-based evaluation paradigm where the server returns a single ciphertext. The key compute primitive is the programmable bootstrap (PBS), which is both the enabling operation and the bottleneck. The method is purely algebraic — no neural components, no approximate arithmetic. It leans on the structure of binary trees and properties of dyadic rationals to pack two comparisons into one test polynomial. The extension to gradient-boosted ensembles (XGBoost-style) is a natural but nontrivial generalization. Integrity is strong for a crypto/systems paper. The distinct-sum property and range-minimality are formally proven, not just empirically observed. The authors derive exact conditions under which encrypted evaluation returns the correct prediction and instantiate parameters with per-inference failure probability below 2⁻⁶⁴ at 128-bit security. Benchmarks use standard UCI datasets. The comparison is against the natural baseline (one PBS per leaf) with each scheme running at its own cost-optimal parameters — a detail that matters, since unfair parameter choices can manufacture speedups. The depth ≤ 4 limitation is stated upfront, not hidden. The milestone question is where this gets interesting. Depth-4 trees are small. Most production random forests and gradient-boosted ensembles use depths 6–12. The next concrete target: an encoding or architectural trick that extends the profitable regime to depth 6–8 without blowing up the ring degree. That would cover the majority of real-world tabular ML workloads. Alternatively, combining this with other PBS-reduction techniques (like tree pruning or hybrid evaluation strategies) could push practical depth further. The gap is structural, not just engineering. The obvious experiment not run: evaluation at depths 5–8 to characterize exactly how the crossover point behaves and whether hybrid strategies (dyadic encoding for shallow subtrees, standard encoding for deep ones) could extend the useful range. The authors prove depth ≤ 4 is the profitable regime and stop there. My read: this is honest scoping, not hiding bad results. The math shows the wall clearly, and there's no trick to get past it within this encoding family. They're saving the hybrid approach for the next paper, or someone else will pick it up.