Paper 2024/619
BPDTE: Batch Private Decision Tree Evaluation via Amortized Efficient Private Comparison
, Harbin Institute of Technology, ViewSouces (Shanghai) Technology Co., LtdAbstract
Machine learning as a service requires clients to entrust their information to the server, raising privacy concerns. Private Decision Tree Evaluation (PDTE) are proposal to address these concerns in decision trees, which are fundamental models in machine learning. However, existing solutions perform poorly with massive datasets in real-world applications, therefore, we focus on the batching variant called BPDTE, which supports a single evaluation on multiple data and significantly improves performance. Firstly, we propose three private comparison (PrivCMP) algorithms that privately compare two numbers to determine which one is larger, by utilizing thermometer encoding and a novel folklore-inspired dichotomy method. These algorithms are non-interactive, batchable, and high-precision, achieving an amortized cost of less than 1 ms at 32-bit precision. Secondly, we propose six BPDTE schemes based on our PrivCMP and the Clear Rows Relation (CRR) algorithm, introduced to ensure batching security. Experimental results show that our schemes improve amortized efficiency, offer more flexible batch sizes, and achieve higher precision. Finally, we provide a formal security analysis of these schemes.
Note: Update the authors and main draft.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Private ComparisonHomomorphic EncryptionPrivate Decision Tree Evaluation
- Contact author(s)
-
24b903126 @ stu hit edu cn
hnlu @ sjtu edu cn
guoyifeng @ cmict chinamobile com
wanggeng @ sjtu edu cn
yuhaining @ hit edu cn
zhanghongli @ hit edu cn
anbaoyu @ cmict chinamobile com
lijinyu @ cmict chinamobile com
suli @ cmict chinamobile com - History
- 2025-05-13: last of 3 revisions
- 2024-04-22: received
- See all versions
- Short URL
- https://ia.cr/2024/619
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/619,
author = {Huiqiang Liang and Haining Lu and Yifeng Guo and Geng Wang and Haining Yu and Hongli Zhang and Baoyu An and Jinyu Li and Li Su},
title = {{BPDTE}: Batch Private Decision Tree Evaluation via Amortized Efficient Private Comparison},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/619},
year = {2024},
url = {https://eprint.iacr.org/2024/619}
}
