In the machine learning (ML) era, people are paying more and more attention to the economic value of data in improving the efficiency of analysis, simulation, calculation, forecasting, and decision-making. It results the rise of data markets. As ML requires high-complexity calculations, individuals and companies tend to use cloud computing with data markets. However, this platform is known to have data security issues in privacy protection. The most modern method for privacy protection in cloud computing is fully homomorphic encryption (FHE). However, the high calculation cost makes conventional FHE impracti-cal for real-world applications. Although many researchers use CKKS FHE to resolve this problem, our experiments show that the calculation cost of some operators in CKKS FHE are still very high. In this paper, we propose new security protocols to design a new data packing method and to reduce the usage of time-consuming calculations. Then, an out-sourced K-means clustering method based on these new security protocols is proposed for demonstration and evaluation. Experiments show that our method is faster than SEOKC. It has shown good performance in high-dimensional data analysis with our new data pack-ing method.