Polylogarithmic Private Approximations and Efficient Matching

David Woodruff
Massachusetts Institute of Technology

Wednesday, March 8, 2:00PM
Burchard 124
Computer Science Department
Stevens Institute of Technology
 

Abstract


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 secure two-party private approximation of the L_2 distance with polylogarithmic communication. This, in particular, resolves the main open question of Feigenbaum et al [FIMNSW00] (who achieve sqrt{n} communication for Hamming distance).

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.

This is work to appear in TCC '06, joint with Piotr Indyk.