Kangaroo: A Private and Amortized Inference Framework over WAN for Large-Scale Decision Tree Evaluation

Kangaroo: A Private and Amortized Inference Framework over WAN for Large-Scale Decision Tree Evaluation

Speakers: Wei Xu

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=FnK_t-gq8TM

Overview

Wang (presenting on behalf of author Wei Xu, who faced visa issues) introduces Kangaroo, a novel framework for privacy-preserving decision tree inference that achieves second-level latency for large-scale tree evaluation over wide area networks. Decision trees and ensemble methods like random forests are widely used in sensitive applications including medical diagnosis, financial risk assessment, and customer behavior prediction. Kangaroo uses packed homomorphic encryption (PHE) to amortize computation and communication overhead, achieving 14 to 59x speedup over state-of-the-art single-round schemes on small datasets while remaining minimally affected by tree structure changes. The framework features constant communication rounds, no offline preprocessing requirements, and support for both client-server and outsourcing scenarios.

Background

▶ Watch: Decision trees in sensitive domains: medical, financial, behavioral (0:15)

Private Decision Tree Evaluation (PDTE) enables a client to have their data evaluated by a model provider's decision tree without revealing the client's data or the model's parameters. Existing PDTE schemes fall into two categories: depth-related schemes (O(d) communication cost, perform well on local area networks but poorly on WANs) and constant-round schemes (O(1) communication rounds but with O(t) computation cost, where t is the total node count). Prior research from NDSS 2021 demonstrated that depth-related schemes perform best in LANs while all existing schemes struggle to scale efficiently in real-world WAN deployments with high latency and limited bandwidth.

The challenge of scaling to large, deep decision tree models in production environments motivates Kangaroo's design: a constant-round scheme that efficiently amortizes the costs introduced by large-scale tree models in WAN settings. The framework must protect node features, thresholds, model structure, comparison results, client data, and path evaluation results under a semi-honest adversary model.

Key Findings

▶ Watch: Kangaroo design: constant rounds with packed homomorphic encryption (3:00)

14-59x faster than state-of-the-art: On small datasets, Kangaroo outperforms existing single-round schemes by 14 to 59 times. The performance advantage grows with model complexity.

Minimal sensitivity to tree structure: Unlike depth-related schemes affected by tree depth and constant-round schemes affected by node count, Kangaroo's performance remains relatively stable across different tree structures, making it suitable for real-world models of varying complexity.

Second-level latency on real networks: Evaluation on JD Cloud and Alibaba Cloud infrastructure demonstrated that Kangaroo achieves practical latency levels even for large-scale tree evaluation in real WAN conditions.

No offline preprocessing: Unlike many prior schemes that require expensive preprocessing phases for each new client evaluation, Kangaroo operates entirely online, reducing deployment complexity and eliminating amortization assumptions.

Extensible design: By changing the model hiding/extraction and encoding/packing methods, Kangaroo can be extended to support outsourcing scenarios without introducing additional overhead, making it adaptable to various deployment architectures.

Technical Deep Dive

▶ Watch: Novel path evaluation protocol on plaintext avoids rotation overhead (5:30)

Kangaroo's workflow consists of four phases. Model hiding and extraction: the model is obfuscated to protect IP while extracting parameters needed for inference. Model encoding and packing: model parameters are encoded into polynomial representations and packed into ciphertexts once for permanent use across all future inferences. Client data encryption: feature vectors are encoded into polynomials and encrypted using PHE. Model inference: client and server execute a constant number of communication rounds.

The framework addresses two key technical challenges. The low packing utilization problem arises when using packed homomorphic encryption -- existing approaches do not fully exploit SIMD (Single Instruction Multiple Data) capabilities. Kangaroo represents each coefficient as a decision node and designs parallel feature selection and secure comparison protocols that maximize packing efficiency.

The path evaluation overhead problem occurs because treating each node as a coefficient requires numerous ciphertext rotation operations. Kangaroo introduces a novel path evaluation protocol that operates directly on plaintext, avoiding the massive computational cost of ciphertext rotations entirely. Additional optimizations include same-sharing for the same model, latency-aware strategy to avoid offline computation, and adaptive encoding adjustment that packs multiple trees onto a single ciphertext to improve computational utilization.

Demo / Proof of Concept

▶ Watch: Four-phase workflow from model hiding to inference (7:00)

The evaluation was conducted on real network infrastructure using JD Cloud and Alibaba Cloud in addition to simulated network conditions. Experiments demonstrated that Kangaroo is 14 to 59 times faster than state-of-the-art one-round schemes on small datasets. The framework showed minimal impact from tree structure variations compared to depth-related and multi-round schemes, and achieved second-level latency for large-scale tree evaluation on real-world networks.

Defensive Implications

▶ Watch: Results: 14-59x faster, second-level latency on real cloud networks (10:00)

Kangaroo makes privacy-preserving machine learning inference practical for decision tree models in production environments. Organizations using decision trees for sensitive applications (credit scoring, medical triage, fraud detection) can now evaluate models on encrypted client data with practical latency over real WAN connections. This eliminates the need to share sensitive feature data with model providers, reducing compliance risk under privacy regulations like GDPR and HIPAA while maintaining model IP protection.

Key Takeaways

• Kangaroo achieves 14-59x speedup over prior constant-round private decision tree evaluation schemes
• The framework is minimally affected by tree depth or structure changes, making it practical for large-scale real-world models
• Packed homomorphic encryption enables amortized computation that scales efficiently over WAN connections
• No offline preprocessing is required, simplifying deployment and reducing client-side overhead
• Modular design supports both client-server and outsourcing scenarios without additional overhead

About the Speaker(s)

Wang, a PhD candidate at the University of Washington, presented on behalf of Wei Xu and the co-authors who were unable to attend due to visa issues. The research focuses on practical privacy-preserving machine learning inference for production WAN deployments.