Paper 2020/319

Secure k-ish nearest neighbors classifier

Hayim Shaul, Dan Feldman, and Daniela Rus


The $k$-nearest neighbors ($k$NN) classifier predicts a class of a query, $q$, by taking the majority class of its $k$ neighbors in an existing (already classified) database, $S$. In secure $k$NN, $q$ and $S$ are owned by two different parties and $q$ is classified without sharing data. In this work we present a classifier based on $k$NN, that is more efficient to implement with homomorphic encryption (HE). The efficiency of our classifier comes from a relaxation we make to consider $\kappa$ nearest neighbors for $\kappa\approx k$ with probability that increases as the statistical distance between Gaussian and the distribution of the distances from $q$ to $S$ decreases. We call our classifier $k$-ish Nearest Neighbors ($k$-ish NN). For the implementation we introduce {\em double-blinded coin-toss} where the bias and output of the toss are encrypted. We use it to approximate the average and variance of the distances from $q$ to $S$ in a scalable circuit whose depth is independent of $|S|$. We believe these to be of independent interest. We implemented our classifier in an open source library based on HElib and tested it on a breast tumor database. Our classifier has accuracy and running time comparable to current state of the art (non-HE) MPC solution that have better running time but worse communication complexity. It also has communication complexity similar to naive HE implementation that have worse running time.

Available format(s)
Publication info
Published elsewhere. pets
FHEsecure machine learningclassification
Contact author(s)
hayim shaul @ gmail com
2020-03-15: received
Short URL
Creative Commons Attribution


      author = {Hayim Shaul and Dan Feldman and Daniela Rus},
      title = {Secure k-ish nearest neighbors classifier},
      howpublished = {Cryptology ePrint Archive, Paper 2020/319},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.