Paper Appeared at ESORICS 2005
Posted 12 October 2005
The paper Privacy Preserving Clustering by
Somesh Jha (pictured at left), Louis Kruger (pictured at right), and
Patrick McDaniel appeared at the Tenth European Symposium on Research
in Computer Security (ESORICS). The conference was held September
12–14 in Milan, Italy. Louis presented the paper at the
conference.
The freedom and transparency of information flow on the Internet has heightened concerns of privacy. Given a set of data items, clustering algorithms group similar items together. Clustering has many applications, such as customer-behavior analysis, targeted marketing, forensics, and bioinformatics. In this paper, the authors presented the design and analysis of a privacy-preserving k-means clustering algorithm, where only the cluster means at the various steps of the algorithm are revealed to the participating parties. The crucial step in their privacy-preserving k-means is privacy-preserving computation of cluster means. They presented two protocols (one based on oblivious polynomial evaluation and the second based on homomorphic encryption) for privacy-preserving computation of cluster means. They have a JAVA implementation of their algorithm. Using their implementation, they performed a thorough evaluation of their privacy-preserving clustering algorithm on three data sets. Their evaluation demonstrated that privacy-preserving clustering is feasible, i.e., their homomorphic-encryption based algorithm finished clustering a large data set in approximately 66 seconds.
