{"id":"ca1154bb-5c93-44df-b894-dfc29a3adb0c","arxiv_id":"2509.03123","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Kangaroo packs decision tree nodes into polynomial coefficients under BFV homomorphic encryption and uses packed feature selection, blinded comparison, and masked path evaluation to amortize private inference across large random forests over WAN.","lead":"Kangaroo is a private-inference framework that evaluates large decision trees and random forests on encrypted client data using packed homomorphic encryption and secret sharing, reporting 14x to 59x speedups over prior schemes in WAN settings and about 60 ms per tree on a 969-tree forest when amortized. The practical point is that it targets the gap between small-scale private tree evaluation and the large, deep models actually deployed in model-as-a-service applications.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Model privacy rests on an unproven obfuscation premise: T* is published to the client and treated as leakage (L1,2) in Appendix C-B, not protected data, while adaptive encoding additionally exposes per-tree sizes.","rationale":"The reader's weakest assumption is exactly the load-bearing concern: publishing an obfuscated tree structure to the client and claiming model privacy is a heuristic, not a proof. I agree with that assessment. The comparison-sign leak with probability 2/(ζ+1) is real, but it is a parameter-level flaw with an explicit appendix fix (PackObliviousCom+) and does not threaten the amortization architecture itself. The model-hiding assumption, by contrast, is the enabler of the entire plaintext path-evaluation design; if the obfuscated T* does not hide the true structure, the server's model is exposed no matter how strong the comparison protocol is. The paper deserves credit for internally consistent correctness proofs of the building blocks, a released implementation, and benchmarks against public baselines. Those support the systems contribution but do not close the model-hiding gap. The CONDITIONAL verdict therefore stands: the framework is a plausible engineering contribution, but the headline claim of private large-scale inference is conditional on a heuristic model-hiding premise that the formal security analysis in Appendix C-B does not cover. The proposed structure-recovery experiment would settle whether that premise is actually sound or only assumed.","tokens_in":37288,"tokens_out":12744,"duration_ms":158454,"concrete_test":"Run a structure-recovery experiment using the released GitHub implementation on a small forest (e.g., M=2, τ*≈7 with 3 dummy nodes, ζ=2^8 or 2^16). Have the honest-but-curious client issue 10^4 chosen-input queries (all-min, all-max, random X), record exactly what the client sees (T*, V from PackObliviousCom, I' and I'' from PackPathEva), and perform a maximum-likelihood or classifier-based test to predict per-node ψ_k (dummy/real) and υ_k (flip sign). If prediction accuracy is significantly above chance, the obfuscation premise is falsified. If accuracy stays at chance, model-hiding survives this test and the remaining concern narrows to the formal gap plus size leakage, which can be patched by making published tree sizes uniform.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Kangaroo's headline speedup depends on a single premise: the server can publish an obfuscated copy of each tree (structure indices T*, dummy nodes, random child swaps) to the client, and the client's plaintext path evaluation over that obfuscated tree still protects the server's model, including item ④ (structure, flip condition, node status). This premise is what makes PackPathEva cheap: the client evaluates paths in plaintext rather than over ciphertext. The formal security argument does not actually establish this premise. In Appendix C-B, the leakage to both parties, L1,2, explicitly includes the obfuscated model structure indices {T*_{k,s}}. The simulator for PackPathEva is handed T* as an input, so Theorem 4 proves only that the remaining messages are simulatable given T*; it never proves that T* conceals ψ_k, υ_k, or the real tree skeleton. The heuristic in Section VI-A (dummy nodes plus random child swaps) is not analyzed against a client who sees T* along with the decrypted values V and I' in the clear. Moreover, the adaptive encoding adjustment in Section VI-C makes the number of encrypted slots per tree unequal, so the published T* leaks a tight upper bound on each tree's real node count, information the threat model explicitly lists as private. If this obfuscation premise fails, the main speedup is not private: the client can un-obfuscate the structure and recover thresholds and weights from the plaintext path evaluation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":37582,"tokens_out":6977,"duration_ms":81280,"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":[{"comment":"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.","section":"Section III-C, VI-A, Appendix C-B"},{"comment":"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":"Appendix C-B, Theorem 4 proof"},{"comment":"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.","section":"Section VI-C"}],"minor_comments":[{"comment":"The text uses 'W AN' in many headings and sentences; should be 'WAN'.","section":"Throughout"},{"comment":"Typo in related work: 'key steos' should be 'key steps'.","section":"Section I-B"},{"comment":"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.","section":"Section VII-A / Table VII"},{"comment":"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.","section":"Algorithm 1"},{"comment":"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":"Appendix B-C"},{"comment":"The sentence 'it requires any offline operations' should read 'it requires no offline operations' (missing negation).","section":"Section VII-B, microbenchmark text"}],"recommendation":"major_revision","confidential_remarks":"The paper shows strong engineering and a genuinely amortized design, but the security framing is too strong. The main protocol's speed depends on the client seeing T*, and the security proof does not cover model hiding; the proof also explicitly leaks comparison signs with probability about 2^{-24}. I would ask the authors to either prove the obfuscation security or precisely define the leakage model, and to benchmark the leak-free comparison variant. If the obfuscation premise cannot be substantiated, the paper should be repositioned as a heuristic with a much weaker privacy claim; as written, the abstract and Section III-C overstate the achieved security."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kangaroo is a serious systems paper. The core idea—encode each decision node as a polynomial coefficient and pack many trees into one ciphertext—is real, and the authors actually build it: code is on GitHub, benchmarks use public baselines, and the comparison truth table and no-wraparound bounds check out. The amortized cost scaling with K/M rather than with node count is plausible from the protocol structure. That is a genuine advance over Sortinghat and Levelup.\n\nThe soft spots are in the security argument, not in the engineering. First, the model-hiding premise: the server publishes an obfuscated tree structure T* to the client and treats it as leakage. The simulator for PackPathEva is handed T*, so Theorem 4 only proves that the rest of the transcript is simulatable given T*. It never proves that T* conceals the real structure, flip conditions, or node status. The heuristic in Section VI-A (dummy nodes plus random child swaps) is not analyzed against a client who sees T* along with decrypted V and I'. And the adaptive encoding in VI-C makes tree sizes unequal, so T* leaks an upper bound on each tree's real node count—information the threat model lists as private. This is the load-bearing weakness because the plaintext path evaluation is what makes the protocol fast. If T* can be un-obfuscated, the client recovers thresholds and weights.\n\nSecond, the main PackObliviousCom proof admits a comparison-sign leak with probability 2/(ζ+1) ≈ 1.2e-7 per comparison. For the 969-tree forest with 411k nodes, that's about a 5% chance of at least one sign leak per query. The leak-free variant in the appendix is not benchmarked and not used in the main protocol. That's a fixable gap, but it should be fixed before deployment claims.\n\nThird, the headline \"60 ms per tree (amortized)\" is honest but easy to misread. End-to-end for one query on that forest is roughly a minute. That's fine for batch or async use, but it's not real-time single-query inference.\n\nNone of this refutes the core approach. The amortization is real; the issues are in the privacy analysis and presentation. I'd send this to a serious referee. If the authors tighten the model-hiding argument (or explicitly scope the claim to settings where T* is acceptable leakage), benchmark the leak-free comparison, and report total latency, this becomes a strong paper.","headline":"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.","tokens_in":38140,"tokens_out":2711,"would_cite":true,"duration_ms":29752,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Kangaroo: full amortization for private decision-tree inference via node-as-coefficient packing","keywords":["private decision tree evaluation","packed homomorphic encryption","amortized inference","random forest","model privacy","oblivious comparison","secure path evaluation","wide-area network"],"falsifier":"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.","tokens_in":1594,"feed_emoji":"🔒","tokens_out":1795,"duration_ms":65191,"temperature":0.7,"pith_summary":"This paper tries to establish that private decision-tree inference can be made to scale to very large ensembles over wide-area networks by treating each polynomial coefficient in a packed homomorphic ciphertext as one decision-tree node. The proposed framework, Kangaroo, combines a model-hiding step (dummy nodes and random child swaps) that lets the client walk an obfuscated tree in plaintext with packed protocols for feature selection, oblivious comparison, and path evaluation. If the claims hold, communication and computation stop scaling with the total number of nodes and trees; they scale instead with the number of packed ciphertexts, roughly K/M. Concretely, the paper reports evaluating a random forest of 969 trees and 411,825 nodes in about 60 ms per tree (amortized) under WAN conditions, with 14x-59x speedups over one-round schemes and 3x-44x for large-scale models.","feed_headline":"Packed ciphertexts cut private tree inference to 60 ms per tree","feed_subtitle":"Each tree node becomes one ciphertext slot, so large forests cost roughly the same as a handful of trees.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Sortinghat constant-round baseline that Kangaroo claims a 14x-59x speedup over in WAN settings.","marker":"[10]"},{"why":"Supplies the Levelup one-round comparison and path-evaluation baseline, and the framework evaluates against its RCC and XXCMP components.","marker":"[11]"},{"why":"Supplies the depth-round sparse-tree baseline (Ma et al.) used as a performance comparison in large-scale single-tree benchmarks.","marker":"[19]"},{"why":"Supplies the HE-SOS baseline, another sublinear-communication scheme Kangaroo compares against for large trees.","marker":"[20]"},{"why":"Supplies the modular GGH/HGH two-party decision-tree evaluation baselines and the path-evaluation taxonomy Kangaroo builds upon.","marker":"[15]"},{"why":"Supplies the HHH path-cost evaluation approach and an AHE baseline; Kangaroo adapts the path-cost idea while replacing AHE with PHE.","marker":"[14]"},{"why":"Supplies the private data comparison protocol that PackObliviousCom extends with SIMD packing and secret-sharing blinding.","marker":"[48]"},{"why":"Supplies the BFV cryptosystem that implements the packed homomorphic encryption used throughout Kangaroo.","marker":"[76]"},{"why":"Supplies the SIMD batching technique that lets BFV slots be treated as independent coefficients, enabling the node-as-coefficient packing.","marker":"[79]"}],"fun_headline_variants":["Amortized private inference: 60 ms per tree for huge forests","Packed ciphertexts enable private decision trees at WAN speed","Kangaroo: private tree evaluation with full amortization","Full amortization makes private tree evaluation practical over WAN","Private forest inference: 60 ms per tree with amortized packing"],"cache_read_input_tokens":39680,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Amortized private inference: 60 ms per tree for huge forests","Packed ciphertexts enable private decision trees at WAN speed","Kangaroo: private tree evaluation with full amortization","Full amortization makes private tree evaluation practical over WAN","Private forest inference: 60 ms per tree with amortized packing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000725,"raw_usage":{"total_tokens":3120,"prompt_tokens":814,"completion_tokens":2306,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":2218}},"tokens_in":558,"tokens_out":2306,"duration_ms":17798,"temperature":1.0,"reasoning_tokens":2218,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:10:02.172448+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}