Privacy-Preserving Shared-Additive-Inverse Protocols and Their Applications

Privacy-preserving clustering algorithms group similar databases populated at distributed locations to improve data qualities and enable accurate data analysis and thus provide fundamental security components for distributed data mining with privacy concerns. This paper makes three contributions regarding shared κ-means clustering algorithms. First, a new notion called shared-additive-inverse (SAI) protocols — a building block for efficient implementation of shared κ-means clustering protocols within the arbitrarily partitioned database model, is introduced and formalized. Second, a generic implementation of SAI protocols from shared-scalar-product (SSP) protocols is proposed which is provably secure in the semi-honest model assuming that any underlying SSP protocol is privacy-preserving. Finally, we propose an immediate application of SAI protocols for privacy-preserving computation of shared cluster means — a crucial step in the shared κ-means clustering algorithms. To the best of our knowledge, this is the first implementation of shared κ-means clustering algorithms with provable security from SAI protocols which in turn are derived from SSP protocols.