Privacy-Preserving Vertical K-Means Clustering
作者: Federico Mazzone, Trevor Brown, Florian Kerschbaum, Kevin H. Wilson, Maarten Everts, Florian Hahn, Andreas Peter
分类: cs.CR, cs.LG
发布日期: 2025-04-10
💡 一句话要点
提出基于同态加密和差分隐私的纵向K-Means聚类方法，降低通信复杂度并保护隐私。
🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)
关键词: 纵向联邦学习 K-Means聚类 同态加密 差分隐私 隐私保护 数据挖掘
📋 核心要点
- 现有纵向K-Means聚类方法在保护隐私的同时，面临着通信成本高昂或聚类效用显著降低的挑战。
- 该论文提出一种基于同态加密和差分隐私的方案，各方安全外包特征，计算方在加密状态下聚类，并仅对聚类中心应用差分隐私。
- 实验结果表明，该方法显著降低了通信复杂度，同时保持了与明文K-Means算法相当的准确性，适用于广域网部署。
📝 摘要（中文）
本文提出了一种保护隐私的纵向K-Means聚类方法。在纵向分区的场景下，数据分散在多个实体中，每个实体仅拥有部分特征。由于计算记录之间的距离需要访问所有分布式特征，而这些特征可能包含隐私敏感信息，因此直接共享不可行。本文旨在计算联合聚类，同时保护每个实体数据集的隐私。现有基于秘密共享或混淆电路的解决方案虽然实现了保护隐私的Lloyd算法变体，但通信成本高昂，复杂度为O(nkt)，其中n是数据点数量，k是聚类数量，t是迭代轮数。这些方法对于大型数据集或多方场景不切实际。另一类解决方案依赖差分隐私（DP）将各方的本地特征外包给中央服务器，但通常会因过度噪声而显著降低聚类结果的效用。本文提出了一种基于同态加密和DP的新颖解决方案，将通信复杂度降低到O(n+kt)。该方法允许各方安全地外包其特征一次，从而使计算方能够在加密下执行聚类操作。DP仅应用于聚类中心，确保隐私的同时最大限度地减少对效用的影响。实验表明，该解决方案使用仅73MB的通信量即可将100,000个二维点聚类成五个簇，而现有方法需要101GB，并且在100Mbps网络上仅需不到3分钟即可完成，而现有方法需要超过1天。这使得该解决方案即使对于WAN部署也具有实用性，同时保持与明文k-means算法相当的准确性。
🔬 方法详解
问题定义：在纵向数据划分场景下，多个参与方各自拥有部分数据特征，需要在保护各方数据隐私的前提下进行K-Means聚类。现有方法，如基于秘密共享或混淆电路的方法，通信复杂度高，难以应用于大规模数据集；基于差分隐私的方法，虽然降低了通信复杂度，但会引入大量噪声，影响聚类结果的准确性。
核心思路：利用同态加密技术，允许在加密数据上进行计算，从而保护各方原始数据。同时，结合差分隐私，仅对聚类中心添加噪声，以进一步保护隐私，并尽量减少对聚类结果的影响。核心在于将高昂的隐私计算转移到一次性的特征外包阶段，后续迭代计算在加密域进行，降低了整体通信复杂度。
技术框架：整体流程包括以下几个阶段：1) 各参与方使用同态加密算法加密各自的特征数据，并安全地外包给计算方；2) 计算方在加密数据上执行K-Means聚类算法的迭代过程，包括计算距离、更新聚类中心等；3) 在每次迭代更新聚类中心后，计算方对聚类中心添加差分隐私噪声；4) 迭代完成后，计算方将加密的聚类中心发送给拥有私钥的参与方进行解密。
关键创新：该方法的核心创新在于将同态加密和差分隐私相结合，既保证了数据的隐私性，又降低了通信复杂度。与现有方法相比，该方法避免了在每次迭代过程中进行复杂的隐私计算，而是通过一次性的特征外包和后续的加密计算，显著降低了通信成本。同时，仅对聚类中心添加差分隐私噪声，最大限度地减少了对聚类结果的影响。
关键设计：论文中可能涉及的关键设计包括：选择合适的同态加密算法（例如Paillier加密），以支持加密数据的加法和乘法运算；设计合理的差分隐私噪声添加机制，以平衡隐私保护程度和聚类结果的准确性；选择合适的K-Means算法变体，以适应加密数据的计算环境；以及优化通信协议，以减少数据传输量。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该方法在100Mbps网络上，使用73MB的通信量即可将100,000个二维点聚类成五个簇，耗时不到3分钟，而现有方法需要101GB的通信量，耗时超过1天。该方法在显著降低通信复杂度的同时，保持了与明文K-Means算法相当的准确性，使其适用于广域网部署。
🎯 应用场景
该研究成果可应用于金融、医疗、政务等多个领域，在这些领域中，数据通常以纵向方式分布在不同的机构或部门之间。例如，不同银行可能拥有客户的不同特征信息，通过该方法可以在保护客户隐私的前提下进行联合客户画像分析。在医疗领域，不同医院可以共享患者的部分医疗数据，用于疾病风险预测和个性化治疗方案制定。
📄 摘要（原文）
Clustering is a fundamental data processing task used for grouping records based on one or more features. In the vertically partitioned setting, data is distributed among entities, with each holding only a subset of those features. A key challenge in this scenario is that computing distances between records requires access to all distributed features, which may be privacy-sensitive and cannot be directly shared with other parties. The goal is to compute the joint clusters while preserving the privacy of each entity's dataset. Existing solutions using secret sharing or garbled circuits implement privacy-preserving variants of Lloyd's algorithm but incur high communication costs, scaling as O(nkt), where n is the number of data points, k the number of clusters, and t the number of rounds. These methods become impractical for large datasets or several parties, limiting their use to LAN settings only. On the other hand, a different line of solutions rely on differential privacy (DP) to outsource the local features of the parties to a central server. However, they often significantly degrade the utility of the clustering outcome due to excessive noise. In this work, we propose a novel solution based on homomorphic encryption and DP, reducing communication complexity to O(n+kt). In our method, parties securely outsource their features once, allowing a computing party to perform clustering operations under encryption. DP is applied only to the clusters' centroids, ensuring privacy with minimal impact on utility. Our solution clusters 100,000 two-dimensional points into five clusters using only 73MB of communication, compared to 101GB for existing works, and completes in just under 3 minutes on a 100Mbps network, whereas existing works take over 1 day. This makes our solution practical even for WAN deployments, all while maintaining accuracy comparable to plaintext k-means algorithms.