Efficient Privacy Preserving Distributed Clustering Based on Secret Sharing

摘要

In this paper, we propose a privacy preserving distributedudclustering protocol for horizontally partitioned data based on a very efficientudhomomorphic additive secret sharing scheme. The model we useudfor the protocol is novel in the sense that it utilizes two non-colludingudthird parties. We provide a brief security analysis of our protocol fromudinformation theoretic point of view, which is a stronger security model.udWe show communication and computation complexity analysis of ourudprotocol along with another protocol previously proposed for the sameudproblem. We also include experimental results for computation and communicationudoverhead of these two protocols. Our protocol not only outperformsudthe others in execution time and communication overhead onuddata holders, but also uses a more efficient model for many data miningudapplications.