Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation
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 s...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/148326 |
| _version_ | 1811677257943482368 |
|---|---|
| author | Ma, Jack P. K. Tai, Raymond K. H. Zhao, Yongjun Chow, Sherman S. M. |
| author2 | Network and Distributed Systems Security (NDSS) Symposium 2021 |
| author_facet | Network and Distributed Systems Security (NDSS) Symposium 2021 Ma, Jack P. K. Tai, Raymond K. H. Zhao, Yongjun Chow, Sherman S. M. |
| author_sort | Ma, Jack P. K. |
| collection | NTU |
| description | 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 2d 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 multikey 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. |
| first_indexed | 2024-10-01T02:34:30Z |
| format | Conference Paper |
| id | ntu-10356/148326 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:34:30Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1483262021-05-08T20:11:19Z Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation Ma, Jack P. K. Tai, Raymond K. H. Zhao, Yongjun Chow, Sherman S. M. Network and Distributed Systems Security (NDSS) Symposium 2021 Strategic Centre for Research in Privacy-Preserving Technologies & Systems Research Techno Plaza Engineering::Computer science and engineering Privacy-preserving Technology Machine Learning 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 2d 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 multikey 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. Info-communications Media Development Authority (IMDA) National Research Foundation (NRF) Published version 2021-05-07T02:59:12Z 2021-05-07T02:59:12Z 2021 Conference Paper Ma, J. P. K., Tai, R. K. H., Zhao, Y. & Chow, S. S. M. (2021). Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation. Network and Distributed Systems Security (NDSS) Symposium 2021. https://dx.doi.org/10.14722/ndss.2021.23166 1-891562-66-5 https://hdl.handle.net/10356/148326 10.14722/ndss.2021.23166 en © 2021 Network and Distributed Systems Security (NDSS) Symposium 2021. All rights reserved. application/pdf |
| spellingShingle | Engineering::Computer science and engineering Privacy-preserving Technology Machine Learning Ma, Jack P. K. Tai, Raymond K. H. Zhao, Yongjun Chow, Sherman S. M. Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation |
| title | Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation |
| title_full | Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation |
| title_fullStr | Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation |
| title_full_unstemmed | Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation |
| title_short | Let’s stride blindfolded in a forest : sublinear multi-client decision trees evaluation |
| title_sort | let s stride blindfolded in a forest sublinear multi client decision trees evaluation |
| topic | Engineering::Computer science and engineering Privacy-preserving Technology Machine Learning |
| url | https://hdl.handle.net/10356/148326 |
| work_keys_str_mv | AT majackpk letsstrideblindfoldedinaforestsublinearmulticlientdecisiontreesevaluation AT tairaymondkh letsstrideblindfoldedinaforestsublinearmulticlientdecisiontreesevaluation AT zhaoyongjun letsstrideblindfoldedinaforestsublinearmulticlientdecisiontreesevaluation AT chowshermansm letsstrideblindfoldedinaforestsublinearmulticlientdecisiontreesevaluation |