Efficient homomorphic evaluation of k-NN classifiers
Authors: Martin Zuber (CEA, LIST), Renaud Sirdey (CEA, LIST)
Volume: 2021
Issue: 2
Pages: 111–129
DOI: https://doi.org/10.2478/popets-2021-0020
Abstract: We design and implement an efficient, secure, homomorphic k-Nearest Neighbours determination algorithm, to be used for regression or classification over private data. Our algorithm runs in quadratic complexity with regard to the size of the database but is the only one in the literature to make the secure determination completely non-interactively. We show that our secure algorithm is both efficient and accurate when applied to classification problems requiring a small set of model vectors, and still scales to larger sets of model vectors with high accuracy yet at greater (sequential) computational costs.
Keywords: k-Nearest Neighbours, Fully Homomorphic Encryption, Machine Learning, Secure Cloud Computing
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
