Jack P. K. Ma (The Chinese University of Hong Kong), Raymond K. H. Tai (The Chinese University of Hong Kong), Yongjun Zhao (Nanyang Technological University), Sherman S.M. Chow (The Chinese University of Hong Kong)

Decision trees are popular machine-learning classification models due to their simplicity and effectiveness. Tai et al. (ESORICS '17) propose a privacy-preserving decision-tree evaluation protocol purely based on additive homomorphic encryption, without introducing dummy nodes for hiding the tree structure, but it runs a secure comparison for each decision node, resulting in linear complexity. Later protocols (DBSEC '18, PETS '19) achieve sublinear (client-side) complexity, yet the server-side path evaluation requires oblivious transfer among $2^d$ real and dummy nodes even for a sparse tree of depth $d$ to hide the tree structure.

This paper aims for the best of both worlds and hence the most lightweight protocol to date. Our complete-tree protocol can be easily extended to the sparse-tree setting and the reusable outsourcing setting: a model owner (resp. client) can outsource the decision tree (resp. attributes) to two non-colluding servers for classifications. The outsourced extension supports multi-client joint evaluation, which is the first of its kind without using multi-key fully-homomorphic encryption (TDSC '19). We also extend our protocol for achieving privacy against malicious adversaries.

Our experiments compare in various network settings our offline and online communication costs and the online computation time with the prior sublinear protocol of Tueno et al. (PETS '19) and $O(1)$-round linear protocols of Kiss et al. (PETS '19), which can be seen as garbled circuit variants of Tai et al.'s. Our protocols are shown to be desirable for IoT-like scenarios with weak clients and big-data scenarios with high-dimensional feature vectors.

View More Papers

(Short) WIP: End-to-End Analysis of Adversarial Attacks to Automated...

Hengyi Liang, Ruochen Jiao (Northwestern University), Takami Sato, Junjie Shen, Qi Alfred Chen (UC Irvine), and Qi Zhu (Northwestern University) Best Short Paper Award Winner!

Read More

UIScope: Accurate, Instrumentation-free, and Visible Attack Investigation for GUI...

Runqing Yang (Zhejiang University), Shiqing Ma (Rutgers University), Haitao Xu (Arizona State University), Xiangyu Zhang (Purdue University), Yan Chen (Northwestern University)

Read More

PyPANDA: Taming the PANDAmonium of Whole System Dynamic Analysis

Luke Craig, Tim Leek (MIT Lincoln Laboratory), Andrew Fasano, Tiemoko Ballo (MIT Lincoln Laboratory, Northeastern University), Brendan Dolan-Gavitt (New York University), William Robertson (Northeastern University)

Read More

Flexsealing BGP Against Route Leaks: Peerlock Active Measurement and...

Tyler McDaniel (University of Tennessee, Knoxville), Jared M. Smith (University of Tennessee, Knoxville), Max Schuchard (University of Tennessee, Knoxville)

Read More