This paper studies how to construct a representative-based clustering algorithms under the scenario that the dataset is partitioned into at least two sections. One section of the data is owned by Alice while the other is owned by Bob. Both want to compute clusters from the union of the data but do not trust each other. Thus, they do not want the other party to learn anything about their share of the data except what can be inferred from the results.

We present a protocol that allows Alice and Bob to carry this task under the k-medoids algorithm. Clustering with medoids (medians or other loss functions) is a more robust alternative that clustering with k-MEANS (the only method for which a privacy preserving protocol is known, but a methods that is statistically biased and statistically inconsistent with very low robustness to noise). Our approach highlights the necessary building blocks for extending our protocol to the family of representative-based clustering algorithms.