K-means clustering is a powerful and frequently used technique in data mining. However, privacy breaching is a serious problem if the k-means clustering is used without any security treatment, while privacy is a real concern in many practical applications. Recently, four privacy-preserving solutions based on cryptography have been proposed by different researchers. Unfortunately none of these four schemes can achieve both security and completeness with good efficiency. In this paper, we present a new scheme to overcome the problems occurred previously. Our scheme deals with data standardization in order to make the result more reasonable. We show that our scheme is secure and complete with good efficiency.