|
 TITLE:
Private Analysis of Data Sets
SPEAKER: Benny Pinkas [HP Labs]
DATE: 2:00 - 3:00 P.M., Tuesday March 30, 2004
LOCATION: Pi, 1 L (PA)
HOST: Vinay Deolalikar
ABSTRACT:
Consider a scenario of two or more parties holding large private data sets,
whose goal is to perform some simple analysis of the data while preserving
privacy. In other words, given data sets X and Y, the parties' goal is to
compute F(X,Y), for some function F, while hiding any other information about X
and Y. It is well known that generic constructions can perform this secure
computation with polynomial overhead for any polynomial-time F(), but our goal
is to design privacy preserving constructions with linear or sublinear overhead,
that can be applied to very large data sets. We describe such constructions,
secure against both semi-honest and malicious adversaries, for two types of
functions: (1) Computing the intersection of two sets, and (2) computing the
k-ranked item (e.g. the median) of the union of the sets.
|
|
|
printable version
