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 the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance with polylogarithmic communication. This, in particular, resolves the main open question of Feigenbaum et al [FIMNSW01].

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 several open questions. 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.