Preserving privacy of digital information

Dr. Aggarwal is from Stanford University
More and more data is becoming available in digital form. While this has
enabled data mining tools to extract interesting and useful information
from the data, it has also created a growing threat to individual privacy.
I am interested in the question whether it is possible to protect privacy
of personal data without giving up the benefits of sharing information. In
this talk, I will present my work in two challenging areas of privacy
preservation.

My first topic is secure function evaluation. Consider several agencies
holding sensitive data. They wish to compute some function on the combined
data they hold, without revealing "too much" about their share of the
input. There exist generic protocols that can be used to compute any
function securely with polynomial overhead. However, this might be
impractical for large-sized inputs. This motivates the problem of devising
efficient protocols for frequently-used functions. I will describe
protocols for computing the median and the k-th ranked element of a set
shared by two or more parties. Our protocol has only a poly-logarithmic
overhead and is secure against malicious parties, too.

The second challenge we consider in this talk is how to release databases
containing sensitive information, e.g. medical databases. In order to
enable data mining and to compute interesting aggregates, trends or
patterns, e.g. epidemic outbreaks, the database owner might wish to
release a public version of the database. At the same time, any function
that compromises individual privacy should not be computable from the
released database. One notion that formalizes this trade-off between
privacy and utility is called "k-anonymity" (Sweeney 2002). The idea is to
hide database entries such that every individual is lost in a crowd of k
people. I will present the best known approximation algorithm for the
utility-maximization problem arising out of k-anonymity.