Kona: An Efficient Privacy-Preservation Framework for KNN Classification by Communication Optimization

K-nearest neighbors (KNN) classification plays a significant role in various applications due to its interpretability. The accuracy of KNN classification relies heavily on large amounts of highquality data, which are often distributed among different parties and contain sensitive information. Dozens of privacy-preserving frameworks have been proposed for performing KNN classification with data from different parties while preserving data privacy. However, existing privacypreserving frameworks for KNN classification demonstrate communication inefficiency in the online phase due to two main issues: (1) They suffer from huge communication size for secure Euclidean square distance computations. (2) They require numerous communication rounds to select the k nearest neighbors. In this paper, we present Kona, an efficient privacy-preserving framework for KNN classification. We resolve the above communication issues by (1) designing novel Euclidean triples, which eliminate the online communication for secure Euclidean square distance computations, (2) proposing a divideand-conquer bubble protocol, which significantly reduces communication rounds for selecting the k nearest neighbors. Experimental results on eight real-world datasets demonstrate that Kona significantly outperforms the state-of-the-art framework by 1.1× ∼ 3121.2× in communication size, 16.7× ∼ 5783.2× in communication rounds, and 1.1× ∼ 232.6× in runtime.