Paper 2023/527

Squirrel: A Scalable Secure Two-Party Computation Framework for Training Gradient Boosting Decision Tree

Wen-jie Lu, Ant Group and Zhejiang University
Zhicong Huang, Ant Group
Qizhi Zhang, Ant Group
Yuchen Wang, Ant Group
Cheng Hong, Ant Group
Abstract

Gradient Boosting Decision Tree (GBDT) and its variants are widely used in industry, due to their strong interpretability. Secure multi-party computation allows multiple data owners to compute a function jointly while keeping their input private. In this work, we present Squirrel, a two-party GBDT training framework on a vertically split dataset, where two data owners each hold different features of the same data samples. Squirrel is private against semi-honest adversaries, and no sensitive intermediate information is revealed during the training process. Squirrel is also scalable to datasets with millions of samples even under a Wide Area Network (WAN). Squirrel achieves its high performance via several novel co-designs of the GBDT algorithms and advanced cryptography. Especially, 1) we propose a new and efficient mechanism to hide the sample distribution on each node using oblivious transfer. 2) We propose a highly optimized method for gradient aggregation using lattice-based homomorphic encryption (HE). Our empirical results show that our method can be three orders of magnitude faster than the existing HE approaches. 3) We propose a novel protocol to evaluate the sigmoid func- tion on secretly shared values, showing 19×-200×-fold im- provements over two existing methods. Combining all these improvements, Squirrel costs less than 6 seconds per tree on a dataset with 50 thousands samples which outperforms Pivot (VLDB 2020) by more than 28×. We also show that Squirrel can scale up to datasets with more than one million samples, e.g., about 170 seconds per tree over a WAN.

Note: Add open source repo

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. USENIX Security'23
Contact author(s)
fionser @ gmail com
zhicong hzc @ antgroup com
wyc286375 @ antgroup com
vince hc @ antgroup com
History
2024-07-08: revised
2023-04-12: received
See all versions
Short URL
https://ia.cr/2023/527
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/527,
      author = {Wen-jie Lu and Zhicong Huang and Qizhi Zhang and Yuchen Wang and Cheng Hong},
      title = {Squirrel: A Scalable Secure Two-Party Computation Framework for Training Gradient Boosting Decision Tree},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/527},
      year = {2023},
      url = {https://eprint.iacr.org/2023/527}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.