Reception after the talk in the 2nd Floor Atrium of Siebel Center.
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.