REVIEW 3 major objections 6 minor
Kangaroo: A Private and Amortized Inference Framework over WAN for Large-Scale Decision Tree Evaluation
T0 review · 3 major / 6 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Kangaroo: full amortization for private decision-tree inference via node-as-coefficient packing
desk verdict A genuinely fast packed-HE PDTE framework whose main speedup depends on an unproven obfuscation premise; worth refereeing, but the model-hiding claim needs work. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is node-as-coefficient packing: decision-tree thresholds, feature indices, flip conditions, node statuses, and leaf weights are encoded into sparse positions of BFV plaintext vectors, so each ciphertext slot is a distinct node. This rides on PackObliviousCom, which blinds the difference between the selected feature and threshold with random multipliers A, B and a random sign R, letting the client reveal only an oblivious sign, and on PackPathEva, which converts the client's plaintext path costs on the published obfuscated tree into a one-hot selection of the true leaf weight.
What would settle it
Run a chosen-input attack: submit many feature vectors crafted to make the blinded comparison value from PackObliviousCom land near zero, and check whether the client can recover the server's threshold or detect the random sign flip with probability noticeably above 2/(ζ+1). Additionally, collect the published obfuscated structure indices from trees padded to different sizes and count real versus dummy nodes per tree; if those counts correlate with the model's complexity, the claimed privacy of the structure index fails.
Extended reading notes
Core claim
On the paper's own terms, Kangaroo is the first private decision-tree evaluation scheme to achieve full amortization over packed homomorphic encryption: every coefficient slot in a BFV ciphertext represents one node, so processing many nodes costs roughly the same as processing one. The server hides the model by padding with dummy nodes and randomly swapping children, then publishes the obfuscated structure; the client performs path-cost evaluation in plaintext, while the server blinds and randomizes the comparison results so the client cannot read thresholds or feature indices. The result is a constant-round, semi-honest, two-party protocol whose cost per random-forest inference is dominate
Load-bearing premise
The server can publish an obfuscated version of each tree (dummy nodes plus random child swaps) and still keep the real thresholds, feature indices, and leaf weights secret from a semi-honest client; this is argued heuristically, not proven.
Editorial extensions
If this is right
- Total per-inference cost drops to about K/M packed-ciphertext operations per phase, effectively removing the number of decision nodes from the scaling law.
- The protocol runs in a constant number of rounds, so WAN latency no longer grows with tree depth.
- Large sparse ensembles with hundreds of thousands of nodes become practical for interactive private inference rather than batch-only workloads.
- The same packed model can be reused across client queries without re-encoding, enabling near-real-time responses for repeated inference.
- The same building blocks extend to single-cloud outsourcing settings, preserving the amortization gains.
Reading between the lines
- A natural next test is whether the same node-as-coefficient encoding works for gradient-boosted trees; the model-hiding trick is not inherently limited to random forests, but the threshold-privacy argument would need to be re-examined for boosted models that share nodes across trees.
- The adaptive encoding adjustment, which makes published tree structures unequal in size, appears to let a client count real versus dummy nodes per tree, potentially contradicting the claimed privacy of the model structure index; this deserves an explicit leakage analysis.
- Because the main comparison protocol leaks the comparison sign with probability about 2/(ζ+1), the enhanced comparison protocol in the appendix seems the safer default; adopting it would add negligible cost under the latency-aware strategy.
- A client issuing many chosen queries could plausibly reconstruct the feature indices used at each node from the packed feature-selection rotations, so the fixed-position hiding should be tested empirically rather than assumed.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Kangaroo, a two-party semi-honest protocol for private decision-tree evaluation based on packed BFV homomorphic encryption. The key idea is to encode decision-tree nodes as coefficients of packed ciphertexts, so that feature selection, comparison, and path evaluation are amortized across many nodes and trees. The framework includes three components — PackFeatureSel, PackObliviousCom, and PackPathEva — and the client performs path evaluation in plaintext over an obfuscated copy of the tree structure (T*), which is published to the client. The paper claims full amortization, constant rounds, no offline preprocessing, and large speedups over prior PDTE schemes in WAN settings, including an amortized inference time of about 60 ms per tree for a 969-tree, 411,825-node random forest. Security is argued in a simulation-based semi-honest model, with a defined leakage set L1,2 that includes the obfuscated structure indices.
Significance. If the claims are correct, Kangaroo would be a substantial step forward for large-scale private decision-tree evaluation: it would be the first scheme to fully amortize computation and communication over PHE for tree ensembles, with constant rounds and no offline phase. The empirical work is concrete and reproducible (public GitHub code, public baseline implementations, direct measurements), and the comparison truth table and the modulus-bound argument in the correctness proofs are sound. However, the significance is conditional on two load-bearing security questions: (1) the model-hiding mechanism that allows the client to see T* and evaluate paths in plaintext is not proven secure, and (2) the paper's own security proof admits a non-negligible comparison-sign leakage probability. Both issues directly affect the claimed privacy/utility tradeoff and the headline speedup numbers.
major comments (3)
- [Section III-C, VI-A, Appendix C-B] The threat model (item ④) lists the model structure index T_{k,s}, flip condition υ_k, and node status ψ_k as private, but the leakage L1,2 in Appendix C-B explicitly includes the obfuscated structure indices {T*_{k,s}}, and Theorem 4's simulator is handed T* as input. Thus the proof establishes only that the remaining messages are simulatable given T*; it does not prove that T* conceals the original tree skeleton, per-tree node count, or flip conditions. The argument in Section VI-A (dummy nodes plus random child swaps) is heuristic, and the client sees T* along with decrypted values V and I' in the clear. This is load-bearing because PackPathEva's plaintext evaluation is exactly what makes the scheme fast; if T* can be partially inverted, the server's model is exposed. Please provide a formal leakage statement or a proof of indistinguishability for T* against the actual client view.
- [Appendix C-B, Theorem 4 proof] The simulator for PackObliviousCom admits that the comparison sign is leaked with probability 2/(ζ+1). With the claimed 50-bit plaintext modulus q, ζ≈2^25, so this probability is about 2^{-24} per comparison — not negligible at the 128-bit security level claimed in Section VII-A. This directly contradicts the stated privacy goal ⑧ (comparison sign is sensitive). The leak-free variant in Fig. 13 appears only in the appendix and is not used in the benchmarks; if it becomes the core protocol, all experimental numbers must be regenerated. Please either prove negligible leakage for the main protocol or benchmark the leak-free variant and update the abstract's performance claims accordingly.
- [Section VI-C] The adaptive encoding adjustment packs variable numbers of nodes per tree and publishes the resulting structure indices T*_{k,s}. The text claims 'this process does not leak any structural information about the model, as the tree structures are randomly permuted before publishing.' This is not correct: variable packing makes a tight upper bound on each tree's real node count visible from T*, and tree size is part of the private model structure under item ④. At minimum, the threat model must be amended to allow tree-size leakage, or the packing must be padded to a uniform size and the amortization and benchmark sections updated accordingly.
minor comments (6)
- [Throughout] The text uses 'W AN' in many headings and sentences; should be 'WAN'.
- [Section I-B] Typo in related work: 'key steos' should be 'key steps'.
- [Section VII-A / Table VII] In Table VII, 'JD Cloud (5 Mbps), TP (1 Mbps), RTT (30 ms)' is unclear; specify whether TP is the ThinkPad-P53 client, and clarify whether the bandwidth figures are uplink/downlink for each party.
- [Algorithm 1] The variable M is reused for both the feature dimension and the local iterative value in lines 7–16; this is confusing and should be renamed (e.g., m') to avoid overloading.
- [Appendix B-C] The PackPathEva proof refers to 'line 2, line 6, and line 12' of Fig. 8, but the figure has four communication steps; the line references should be harmonized with the actual figure.
- [Section VII-B, microbenchmark text] The sentence 'it requires any offline operations' should read 'it requires no offline operations' (missing negation).
Circularity Check
No circular derivation: performance results are measured benchmarks; the security caveat is an unproven obfuscation premise, not a circular step.
full rationale
Kangaroo's headline result (969 trees, 411,825 nodes, ~60 ms/tree amortized) comes from direct timing measurements in Section VII against publicly available baseline implementations, with no fitted parameter that is later renamed as a prediction. The amortized complexity in Table II follows from the protocol's packing arithmetic and is not an input to itself. The one self-citation that could matter is the PGSIM-based private comparison [48], whose authors overlap with the present paper; however, Section II-C and Fig. 2 re-specify the comparison and Appendix C-B gives an independent simulation proof, so the cited work is not load-bearing. The most serious concern is in Appendix C-B: the threat model labels the model structure index T (item ④) private, while the leakage L1,2 explicitly includes the obfuscated structure indices T*, and Theorem 4 proves only simulability given T*. This is a genuine security-modeling gap (the obfuscation premise is asserted in Section VI-A, not proved), but it is not a circular reduction: the theorem states its leakage assumption explicitly, and no numerical or complexity result is defined in terms of the conclusion it supports. Score 2 reflects the minor self-citation and this caveat, not a construction-level circularity.
Assumptions & free parameters
free parameters (3)
- ζ (quantization precision parameter) =
2^(log q /2 - 1), i.e., 2^24 for the 50-bit plaintext modulus q
- M* (padded feature dimension) =
power of 2 per dataset, e.g., 16 (Heart, Diabetes, Boston) and 50 (Digits)
- Feature range [Xmin, Xmax] for quantization =
published ranges, extended for sensitive features
assumptions (6)
- standard math BFV (or the underlying RLWE) is IND-CPA secure
- domain assumption Both parties are semi-honest (honest-but-curious)
- ad hoc to paper Dummy nodes plus random child swaps make the published obfuscated structure protect the original model structure
- domain assumption Features and thresholds lie within the published ranges [Xmin, Xmax] and quantized comparisons preserve the plaintext decisions
- domain assumption No collusion between the cloud and either party in the outsourcing extension
- standard math A per-comparison sign-leak probability of 2/(ζ+1) is negligible/acceptable
Cite this review
Pith. "Pith review of Kangaroo: A Private and Amortized Inference Framework over WAN for Large-Scale Decision Tree Evaluation." pith.science (2026). https://pith.science/paper/37NJBYPG
@misc{pith2026250903123,
author = {Pith},
title = {Pith review of: Kangaroo: A Private and Amortized Inference Framework over WAN for Large-Scale Decision Tree Evaluation},
year = {2026},
howpublished = {\url{https://pith.science/paper/37NJBYPG}},
note = {Machine review of arXiv:2509.03123}
}
abstract
With the rapid adoption of Models-as-a-Service, concerns about data and model privacy have become increasingly critical. To solve these problems, various privacy-preserving inference schemes have been proposed. In particular, due to the efficiency and interpretability of decision trees, private decision tree evaluation (PDTE) has garnered significant attention. However, existing PDTE schemes suffer from significant limitations: their communication and computation costs scale with the number of trees, the number of nodes, or the tree depth, which makes them inefficient for large-scale models, especially over WAN networks. To address these issues, we propose Kangaroo, a private and amortized decision tree inference framework build upon packed homomorphic encryption. Specifically, we design a novel model hiding and encoding scheme, together with secure feature selection, oblivious comparison, and secure path evaluation protocols, enabling full amortization of the overhead as the number of nodes or trees scales. Furthermore, we enhance the performance and functionality of the framework through optimizations, including same-sharing-for-same-model, latency-aware, and adaptive encoding adjustment strategies. Kangaroo achieves a $14\times$ to $59\times$ performance improvement over state-of-the-art (SOTA) one-round interactive schemes in WAN environments. For large-scale decision tree inference tasks, it delivers a $3\times$ to $44\times$ speedup compared to existing schemes. Notably, Kangaroo enables the evaluation of a random forest with $969$ trees and $411825$ nodes in approximately $60$ ms per tree (amortized) under WAN environments.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.