## CryptoDB

### Paper: Secure Two-Party k-Means Clustering

Authors: Paul Bunn Rafail Ostrovsky URL: http://eprint.iacr.org/2007/231 Search ePrint Search Google The k-Means Clustering problem is one of the most-explored problems in data mining to date. With the advent of protocols that have proven to be successful in performing single database clustering, the focus has changed in recent years to the question of how to extend the single database protocols to a multiple database setting. To date there have been numerous attempts to create specific multiparty k-means clustering protocols that protect the privacy of each database, but according to the standard cryptographic definitions of privacy-protection,'' so far all such attempts have fallen short of providing adequate privacy. In this paper we describe a Two-Party k-Means Clustering Protocol that guarantees privacy, and is more efficient than utilizing a general multiparty compiler'' to achieve the same task. In particular, a main contribution of our result is a way to compute efficiently multiple iterations of k-means clustering without revealing the intermediate values. To achieve this, we use novel techniques to perform two-party division and sample uniformly at random from an unknown domain size. Our techniques are quite general and can be realized based on the existence of any semantically secure homomorphic encryption scheme. For concreteness, we describe our protocol based on Paillier Homomorphic Encryption scheme (see [Pa]). We will also demonstrate that our protocol is efficient in terms of communication, remaining competitive with existing protocols (such as [JW]) that fail to protect privacy.
##### BibTeX
@misc{eprint-2007-13512,
title={Secure Two-Party k-Means Clustering},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Multiparty Computation, k-means clustering},
url={http://eprint.iacr.org/2007/231},
note={ paulbunn@math.ucla.edu 13677 received 12 Jun 2007},
author={Paul Bunn and Rafail Ostrovsky},
year=2007
}