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

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16818
Primary Topic
Cryptography and Data Security
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Xintong Song, Yiqiang Zhao, Jiaji He, Fei Zhao et al.
arXiv (Cornell University)
Cryptography and Data Security
preprint

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

Xintong Song, Yiqiang Zhao, Jiaji He, Fei Zhao, Yao Li, Qizhi Zhang
preprint en

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.

arXiv (Cornell University)
Cryptography and Data Security
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon