期刊名称：Proceedings on Privacy Enhancing Technologies
电子版ISSN：2299-0984
出版年度：2020
卷号：2020
期号：3
页码：42-61
DOI：10.2478/popets-2020-0045
语种：English
出版社：Sciendo
摘要：The k-nearest neighbors (kNN) 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 kNN,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 kNN,that is more efficient to implement with homomorphic encryption (HE). The efficiency of our classifier comes from a relaxation we make to consider κ nearest neighbors for κ ≈ 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 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.
