Efficient homomorphic evaluation of k-NN classifiers

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.