Constant-Round Privacy-Preserving KNN Classification Based on Function Secret Sharing
Bin Liu, Xue Yang, Xiaohu Tang · IEEE Transactions on Big Data · 2026
Privacy-preserving $k$-nearest neighbors (KNN) classification has attracted significant attention in recent years. However, existing schemes often face challenges such as high computational cost and excessive communication rounds, which limit their practical applicability. In this paper, we propose a constant-round privacy-preserving KNN classification scheme based on function secret sharing (FSS) with two non-colluding servers. To enhance data privacy and computation efficiency in secure KNN classification, we design several lightweight secure two-party computation (2PC) protocols, including Euclidean distance computation, integer comparisons, and frequency computation. To further reduce communication rounds, we introduce a batch comparison algorithm that efficiently sorts a set to extract the $k$-minimum values and the maximum value. Compared to the best-known schemes that require $\mathcal{O}(n + k \log n)$ or $\mathcal{O}(kn)$ communication rounds, where $n$ represents the dataset size, our approach achieves only 10 communication rounds. Security analysis confirms that the proposed scheme effectively preserves data privacy. Performance evaluations demonstrate that our scheme is competitive with existing works in terms of accuracy, computation cost, and communication efficiency.