聚类是一种重要的无监督机器学习方法，可以揭示隐藏在数据中的内在模式和特 征，在数据分析领域有广泛的应用。为了分析大规模数据，外包计算(outsourced computation)是一种有效的解决方法。但是如果涉及到敏感数据，外包计算可能会存在隐私泄漏的问题。全同态加密(fully homomorphic encryption)可以在密文上进行操作而不需要解密，非常适合于外包计算的场景。目前，已经有许多基于全同态加密的隐私保护聚类算法的研究，但是目前的研究结果要么受限于全同态加密所带来的额外开销而非常耗时，要么经过一两次聚类算法的计算迭代后就要求解密再加密，才能继续进行计算。 在此项工作中，我们提出了一种高效的找出一列数据中最小值或最大值的方法， 充分利用了全同态加密的单指令多数据(single-instruction-multiple-data)加速 计算的天然属性。将这种方法和同态加密的自举(bootstrap)相结合，我们的此项工作实现了一种实用的基于全同态加密的聚类算法协议，数据方和计算方之间只需要进行一轮交互即可完成聚类。我们实现的此聚类协议是基于 CKKS这一全同态加密方 案。 实验结果表明我们的协议相比于其他已有的相关工作有显著的性能提升。我们在许多公开测试集上测试了我们的协议，在密文上的结果达到了和明文上结果几乎一样的精度。