New Secure Sparse Inner Product With Applications to Machine Learning
Guowen Xu, Shengmin Xu, Jianting Ning, Xinyi Huang, Hongwei Li, Rongxing Lu · IEEE Transactions on Dependable and Secure Computing · 2025
Sparse inner product (SIP) has the attractive property of overhead being dominated by the intersection of inputs between parties, independent of the actual input size. It has intriguing prospects, especially for boosting machine learning on large-scale data, which are tangled with sparse data. In this paper, we investigate privacy-preserving SIP problems that have rarely been explored before. Specifically, we propose two concrete constructions, one requiring offline linear communication, which can be amortized across queries, while the other has sublinear overhead but relies on the more computationally expensive tool. Our approach exploits state-of-the-art cryptography tools including garbled Bloom filters (GBF) and Private Information Retrieval (PIR) as the cornerstone but carefully fuses them to obtain nontrivial overhead reductions. We provide formal security analysis of the proposed constructions and implement them into representative machine learning algorithms including k-nearest neighbors, naive Bayes classification, and logistic regression. Compared to existing efforts, our method achieves 2-$50\times$speedup in runtime and up to$10\times$reduction in communication.