Before revision:  In this work we present the first scalable and efficient algorithm for solving KNN with Fully Homomorphic Encryption (FHE)that is realized by a polynomial whose degree is independent of n, the number of points. We implemented our algorithm in an open source library based on HELib implementation for the Brakerski-Gentry-Vakuntanthan's FHE scheme, and ran experiments on MIT's OpenStack cloud. Our experiments show that given a query point q, we can find the set of 20 nearest points out of more than 1000 points in less than an hour. Our result introduces a statistical coreset, which is a data summarization technique that allows statistical functions, such as moments, to be efficiently and scalably computed. As a central tool, we design a new coin toss technique which we use to build the coreset. This coin toss technique and computation of statistical functions may be of independent interest.
After revision:  In this work we present a classifier based on kNN, that can be implemented efficiently with homomorphic encryption (HE). The efficiency of our classifier comes from a relaxation we make on kNN, where we allow it to consider kappa nearest neighbors for kappa ~ k with some probability. We therefore call our classifier k-ish Nearest Neighbors (k-ish NN). The success probability of our solution depends on the distribution of the distances from q to S and increase as its statistical distance to Gaussian decrease. To implement our classifier we introduce the concept of double-blinded coin-toss. In a doubly-blinded coin-toss the success probability as well as the output of the toss are encrypted. We use this coin-toss to efficiently approximate the average and variance of the distances from q to S. We believe these two techniques may be of independent interest.