An Efficient Secure KNN Classification Protocol

Abstract

The k Nearest Neighbor (kNN) classification algorithm is a prediction model widely used for real-life applications such as healthcare, finance, computer vision, personalized recommendations, and precision marketing. The arrival of the data explosion era has resulted in a significant increase in feature dimension, which has also raised privacy concerns over the available samples and unlabeled data in machine learning applications. In this paper, we present a secure low communication overhead kNN classification protocol that can handle high-dimensional features represented in real numbers. First, to manage feature values given in real numbers, we develop a specific data conversion algorithm 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 computes the Euclidean distance between two points represented in real numbers in a high-dimensional space. Then, based on the novel PPEDP and oblivious transfer, we propose a new classification approach, the efficient secure kNN classification protocol (ESkNN), with low communication overhead, suitable for a sample set with high-dimensional features and real number feature values. Moreover, we implement ESkNN in C++. Experimental results show that ESkNN is several orders of magnitude faster than existing works and scales up to 18,000 feature dimensions in a memory-limited environment.

Innovative Points and Significance

#Innovation Points

In this paper, we propose a secure, low-communication overhead kNN classification protocol that can handle high-dimensional features given in real numbers.

#Significance

① We propose a new data conversion algorithm that can handle real numbers and can be used with the BGV homomorphic scheme. This conversion algorithm is generic and applicable to other algorithms that need to handle real numbers with the BGV homomorphic scheme.

② We propose a privacy-preserving Euclidean distance protocol (PPEDP) based on the BGV homomorphic scheme. By using the novel data conversion algorithm, PPEDP can compute the Euclidean distance between two points given in real numbers in a high-dimensional space.

③ We propose a new classification method, the efficient secure kNN (ESkNN) classification protocol based on PPEDP and OT. Similarly, our ESkNN can handle real numbers. We use the HElib and EMP toolkits to construct the protocol, making our building block PPEDP usable in other applications.

In this article, we present a privacy-preserving Euclidean distance protocol (PPEDP) that allows us to compute the Euclidean distance between two points given in real numbers in a high-dimensional space without worrying about privacy leakage.

Through a year of graduate study, I have transitioned from a clueless freshman to the graduation stage. In this fleeting year, I have opened the door to the world of scientific research, attempted to write and submit papers for the first time, participated in international conferences, and spoken at them… so many firsts have enriched my graduate life, giving me a new understanding of “scientific research”—a term both familiar and strange.

As the century-old elder Bingxin said: “Reading is good, good at reading, and reading good books.” Even at the graduate stage, reading and thinking remain an essential part of scientific research. Upon entering school, my advisor recommended professional books and papers, requiring me to read extensively each week and write reading notes. Through reading related to information security, I gradually gained a certain understanding of this unfamiliar field, focusing on the current state of research and previous works, which provided me with new insights. Additionally, through reading numerous papers, I mastered some useful skills: familiarizing myself with paper formats, learning various methods to search and download foreign papers, improving my English reading ability, and gaining more understanding of foreign journals and universities… all of these were practical experiences gained from extensive reading. Meanwhile, many websites now offer numerous video courses, such as those on the Computer Society’s official website and Chinese university MOOC, which are very beneficial for research in target fields. Only by paying attention to accumulation regularly can we achieve great progress when needed.

Lastly, I would like to express my gratitude to my graduate advisor, Professor Sun Maohua, who has guided my exploration in the target field like a bright lamp. Professor Sun’s encouragement and assistance have been an indispensable part of my graduate career.