Privacy-Preserving k-NN for Small and Large Data Sets

Abstract

It is not surprising that there is strong interest in k- NN queries to enable clustering, classification and outlier- detection tasks. However, previous approaches to privacy- preserving k-NN are costly and can only be realistically ap- plied to small data sets. We provide efficient solutions for k-NN queries queries for vertically partitioned data. We pro- vide the first solution for the L (or Chessboard) metric as well as detailed privacy-preserving computation of all other Minkowski metrics. We enable privacy-preserving L by providing a solution to the Yao's Millionaire Problem with more than two parties. This is based on a new and practi- cal solution to Yao's Millionaire with shares. We also provide privacy-preserving algorithms for combinations of local met- rics into a global that handles the large dimensionality and diversity of attributes common in vertically partitioned data.