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

HTTPS-Only: Upgrading all connections to https: in Web Browsers

Christoph Kerschbaumer, Julian Gaibler, Arthur Edelstein (Mozilla Corporation), Thyla van der Merwey (ETH Zurich)

Read More

FARE: Enabling Fine-grained Attack Categorization under Low-quality Labeled Data

Junjie Liang (The Pennsylvania State University), Wenbo Guo (The Pennsylvania State University), Tongbo Luo (Robinhood), Vasant Honavar (The Pennsylvania State University), Gang Wang (University of Illinois at Urbana-Champaign), Xinyu Xing (The Pennsylvania State University)

Read More

Safer Illinois and RokWall: Privacy Preserving University Health Apps...

Vikram Sharma Mailthody, James Wei, Nicholas Chen, Mohammad Behnia, Ruihao Yao, Qihao Wang, Vedant Agarwal, Churan He, Lijian Wang, Leihao Chen, Amit Agarwal, Edward Richter, Wen-mei Hwu, and Christopher Fletcher (University of Illinois at Urbana-Champaign); Jinjun Xiong (IBM); Andrew Miller and Sanjay Patel (University of Illinois at Urbana-Champaign)

Read More

RandRunner: Distributed Randomness from Trapdoor VDFs with Strong Uniqueness

Philipp Schindler (SBA Research), Aljosha Judmayer (SBA Research), Markus Hittmeir (SBA Research), Nicholas Stifter (SBA Research, TU Wien), Edgar Weippl (Universität Wien)

Read More