Privacy preservation in data mining has gained significant recognition because of the increased concerns to ensure privacy of sensitive information. It enables multiple parties to conduct collaborative data mining while preserving the privacy of their data. In this work, a cloud computing based protocol for privacypreserving distributed K-means clustering over horizontally partitioned data, shared between N parties, is proposed. Clustering is one of the elementary algorithms used in the field of data mining. Traditional cryptographic methods use encryption techniques or secure multiparty computation (SMC) to ensure privacy of data. But privacy in these techniques is at the expense of additional communication cost, which limits their use in practical applications. Hence, to reduce these overheads, threshold cryptography is used in the proposed work as a privacy-preserving mechanism. The proposed scheme is faster as compared to the previous schemes and experimental results presented in this paper.