Abstract

Differential privacy has become one of the frequently applied techniques in the development of randomized estimation algorithms that are resistant to adaptive updates and queries. This heavily relies on the fact that it is possible to take estimates from several copies of the randomized algorithm and obscure them by returning their private median. This approach does not easily translate to a setting in which the algorithm returns not just an estimate but a specific object from a given set. As opposed to estimates, there is no obvious method for outputting a private aggregate of several samples from the set of valid answers, which in this case is supposed to be an element of the set as well. We focus on the nearest neighbor search problem via Locality Sensitive Hashing. This problem has recently been showed to be vulnerable to the adaptive queries. We demonstrate various techniques that can be used to make its output adversarially robust.