Wei Xu (Xidian University), Hui Zhu (Xidian University), Yandong Zheng (Xidian University), Song Bian (Beihang University), Ning Sun (Xidian University), Hao Yuan (Xidian University), Dengguo Feng (School of Cyber Science and Technology), Hui Li (Xidian University)

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× to 59× 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× to 44× 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.

View More Papers

Achieving Interpretable DL-based Web Attack Detection through Malicious Payload...

Peiyang Li (INSC and the State Key Laboratory of Internet Architecture, Tsinghua University and Ant Group), Fukun Mei (INSC and the State Key Laboratory of Internet Architecture, Tsinghua University), Ye Wang (INSC and the State Key Laboratory of Internet Architecture, Tsinghua University), Zhuotao Liu (INSC and the State Key Laboratory of Internet Architecture, Tsinghua University),…

Read More

U.S. Election Expert Perspectives on End-to-end Verifiable Voting Systems

Julie M. Haney (National Institute of Standards and Technology, Gaithersburg, Maryland), Shanee Dawkins (National Institute of Standards and Technology, Gaithersburg, Maryland), Sandra Spickard Prettyman (Cultural Catalyst LLC, Chicago), Mary F. Theofanos (National Institute of Standards and Technology, Gaithersburg, Maryland), Kristen K. Greene (National Institute of Standards and Technology, Gaithersburg, Maryland), Kristin L. Kelly Koskey (Cultural Catalyst LLC, Chicago), Jody L. Jacobs (National Institute of Standards…

Read More

From Reports to Insights: Challenges and Opportunities in Citizen-Driven...

Daan Vansteenhuyse (DistriNet, KU Leuven), Hadji Musaev (DistriNet, KU Leuven), Lieven Desmet (DistriNet, KU Leuven)

Read More