Polylogarithmic Private Approximations and Efficient Matching

摘要

In [12] a private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about x other than what can be deduced from f(x). We give the first two-party private approximation of the l_2 distance with polylogarithmic communication. This, in particular, resolves the main open question of [12]. We then look at the private near neighbor problem in which Alice has a query point in {0, 1}~d and Bob a set of n points in {0, 1}~d, and Alice should privately learn the point closest to her query. We improve upon existing protocols, resolving open questions of [13, 10]. Then, we relax the problem by defining the private approximate near neighbor problem, which requires introducing a notion of secure computation of approximations for functions that return sets of points rather than values. For this problem we give several protocols with sublinear communication.