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

Screen Gleaning: Receiving and Interpreting Pixels by Eavesdropping on...

Zhuoran Liu, Léo Weissbart, Dirk Lauret (Radboud University)

Read More

Practical Blind Membership Inference Attack via Differential Comparisons

Bo Hui (The Johns Hopkins University), Yuchen Yang (The Johns Hopkins University), Haolin Yuan (The Johns Hopkins University), Philippe Burlina (The Johns Hopkins University Applied Physics Laboratory), Neil Zhenqiang Gong (Duke University), Yinzhi Cao (The Johns Hopkins University)

Read More

Demo #6: Impact of Stealthy Attacks on Autonomous Robotic...

Pritam Dash, Mehdi Karimibiuki, and Karthik Pattabiraman (University of British Columbia)

Read More

Evaluating Personal Data Control In Mobile Applications Using Heuristics

Alain Giboin (UCA, INRIA, CNRS, I3S), Karima Boudaoud (UCA, CNRS, I3S), Patrice Pena (Userthink), Yoann Bertrand (UCA, CNRS, I3S), Fabien Gandon (UCA, INRIA, CNRS, I3S)

Read More