.png){kind=icon}
.png){kind=icon}
Return
Constant-Round Privacy-Preserving KNN Classification Based on Function Secret Sharing
.png){kind=icon}
PRE
AI
刘
X
X
DOI：10.1109/tbdata.2026.3689015.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-nearest neighbors (KNN) classification algorithm is widely used in machine learning for its simplicity and effectiveness in non-parametric settings. However, when applied to sensitive data, such as medical or financial records, ensuring the privacy of both the training dataset and user queries is crucial. Existing privacy-preserving KNN (PP-KNN) classification schemes often suffer from inefficiencies due to the sequential nature of operations like top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> selection and majority voting. These operations require chains of dependent secure comparisons, resulting in communication rounds that scale with either the dataset size <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> or the neighborhood size <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> (e.g., <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(n+k\log _{}{n})$</tex-math></inline-formula> or <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(kn)$</tex-math></inline-formula>). To address these challenges, we propose a constant-round PP-KNN classification scheme based on function secret sharing (FSS) in a non-colluding two-server setting. Specifically, we employ an FSS-based batch comparison algorithm to parallelize the secure comparisons in both top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> selection and majority voting, thereby transforming iterative comparison chains into stage-wise constant-round evaluations. This design enables the entire classification pipeline to complete in a fixed 10 rounds, achieving a round complexity independent of both <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>. Formal security analysis shows that the proposed scheme is secure under the semi-honest adversarial model. Furthermore, performance evaluations demonstrate that our approach achieves competitive computation and communication efficiency compared with existing solutions.
Keywords:
Secure multi-party computation
function secret sharing
data privacy
k-nearest neighbors (KNN) classification
Journal
I
IF:
5.7
Papers:
834
Citations:
3.0K
Organization
Cited Papers