An efficient secure k nearest neighbor classification protocol with high‐dimensional features
Maohua Sun, Ruidi Yang
Abstract
k Nearest neighbor (kNN) classification algorithm is a prediction model which is widely used for real-life applications, such as healthcare, finance, computer vision, personalization recommendation and precision marketing. The arrival of data explosion era results in the significant increase of feature dimension, which also makes for the increase of privacy concern over the available samples and unlabeled data in the applications of machine learning. In this paper, we present a secure low communication overhead kNN classification protocol that is able to deal with highdimensional features given in real numbers. First, to deal with feature values given in real numbers, we develop a specific data conversion algorithm, which is used in the chosen fully homomorphic scheme. This conversion algorithm is generic and applicable to other algorithms that need to handle real numbers using the fully homomorphic scheme. Second, we present a privacy-preserving euclidean distance protocol (PPEDP), which works with the Euclidean distance computation between two points given in real numbers in a high-dimensional space. Then, based on the novelty PPEDP and oblivious transfer, we