ECCC-Report TR05-117https://eccc.weizmann.ac.il/report/2005/117Comments and Revisions published for TR05-117en-usThu, 13 Oct 2005 19:13:00 +0200
Paper TR05-117
| Polylogarithmic Private Approximations and Efficient Matching |
Piotr Indyk,
David P. Woodruff
https://eccc.weizmann.ac.il/report/2005/117A 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.
Thu, 13 Oct 2005 19:13:00 +0200https://eccc.weizmann.ac.il/report/2005/117