Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Polylogarithmic Private Approximations and Efficient Matching
verfasst von : Piotr Indyk, David Woodruff
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.