2018/08/11 by Riddhi Ghosal, Ghosal, Riddhi, Sanjit Chatterjee +1
Computer Science · Mathematics · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1808.03811
openalex publication_date 2018/08/11 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
The k-means clustering is one of the most popular clustering algorithms in\ndata mining. Recently a lot of research has been concentrated on the algorithm\nwhen the dataset is divided into multiple parties or when the dataset is too\nlarge to be handled by the data owner. In the latter case, usually some servers\nare hired to perform the task of clustering. The dataset is divided by the data\nowner among the servers who together perform the k-means and return the cluster\nlabels to the owner. The major challenge in this method is to prevent the\nservers from gaining substantial information about the actual data of the\nowner. Several algorithms have been designed in the past that provide\ncryptographic solutions to perform privacy preserving k-means. We provide a new\nmethod to perform k-means over a large set using multiple servers. Our\ntechnique avoids heavy cryptographic computations and instead we use a simple\nrandomization technique to preserve the privacy of the data. The k-means\ncomputed has exactly the same efficiency and accuracy as the k-means computed\nover the original dataset without any randomization. We argue that our\nalgorithm is secure against honest but curious and passive adversary.\n