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.

The paper is available online: [Abstract] [pdf]

<< Back to index

This page updated November 12, 2005.