International Association
for Cryptologic Research

The $k$-nearest neighbors classifier is a simple machine learning algorithm with applications in image recognition, finance, medical diagnosis and so on. It involves a measurement which is compared against a database of preclassified vectors, so that the result depends on the $k$ vectors in the database that are closest to the measurement. In the client-server model, this classification process can be outsourced to an external party that offers machine learning as a service, where the measurement is sent in the form of a query. However, this raises privacy concerns if sensitive information is contained in the query.

We design a secure and non-interactive version of the $k$-nearest neighbors classifier, based on fully homomorphic encryption, which does not leak any information about the query to the server. Our algorithm is instantiated with the TFHE homomorphic encryption scheme, and the selection of the top-$k$ elements is done with a novel strategy based on a type of data-oblivious algorithm---sorting networks. Compared to prior work from PoPETs 2021, the asymptotic complexity is improved from $O(d^2)$ to $O(d \log^2 {k})$, where $d$ is the number of entries in the $k$-NN model. Experimental results show that the proposed protocol can be up to 16 times faster (not accounting for difference in CPU) than previous approaches for a moderately sized database.