An exploration of privacy protection for outsourced k-NN in the multi-data-owner setting

The authors state that they are the first to propose and explore privacy protection for outsourced k-NN systems in the multi-data-owner setting. The study finds that, under a practical threat model covering a large number of scenarios, there exists a set of adaptive attacks that can breach the data privacy of any exact k-NN system, rooted in the mathematical properties of k-NN and its outputs. The authors propose Gaussian kernel kernel density estimation, from the same family as k-NN, as a privacy-preserving alternative, and explore countermeasures under other threat models, mostly realized by extending existing single-data-owner schemes.