支持隐私保护的K-means聚类模型研究  

Research on Privacy-Preserving K-means Clustering Model

作　　者：栗维勋 杨立波 孙志于[2] 宁志言 高明慧 王琛[5] 徐剑[5] LI Wei-xun;YANG Li-bo;SUN Zhi-yu;NING Zhi-yan;GAO Ming-hui;WANG Chen;XU Jian(State Grid Hebei Power Company,Shijiazhuang 050000,China;Xinjiang Meteorological Information Center,Urumqi 830002,China;China NARI Group Corporation(State Grid Electronic Power Research Institute),Nanjing 211106,China;Beijing Kedong Electric Power Control System Co.,Ltd.,Beijing 100192,China;Northeastern University,Shenyang 110169,China)

机构地区：[1]国网河北省电力有限公司,河北石家庄050000 [2]新疆气象信息中心,新疆乌鲁木齐830002 [3]南瑞集团有限公司(国网电力科学研究院有限公司),江苏南京211106 [4]北京科东电力控制系统有限责任公司,北京100192 [5]东北大学,辽宁沈阳110169

出　　处：《中国电子科学研究院学报》2021年第5期506-516,共11页Journal of China Academy of Electronics and Information Technology

基　　金：国家自然科学基金资助项目(61872069);中央高校基本科研业务费专项资金资助(N2017012)。

摘　　要：K-means是一种典型的聚类算法,在机器学习领域有着重要的作用。随着外包聚类服务的发展以及用户隐私保护意识的日益提高,K-means聚类也需要对密文数据提供支持,进而保证用户数据的隐私性。为此,文中利用全同态加密(Fully Homomorphic Encryption,FHE)设计了面向加密数据的K-means聚类模型(K-means Clustering Model over Encrypted Data,K-means-CMED),并且对K-means-CMED及其实体构成进行描述,设计了对应基本运算的通信协议,包括:MUX选择协议、范式距离计算协议、比较协议以及求最小值协议。基于上述通信协议,给出了K-means-CMED的构建过程。对协议的正确性、安全性进行了分析。最后,利用FCPS数据集进行性能测试,结果表明K-means-CMED的密文聚类性能与明文接近,满足聚类的实际应用需求,并解决了外包数据聚类的隐私保护问题。K-means is a typical clustering algorithm,which plays an essential role in the machine learning field.With the increasing awareness of user privacy protection,K-means clustering also needs to provide clustering support for encrypted data,so as to ensure the privacy of user data.In this paper,we propose a K-means Clustering Model over Encrypted Data(K-means-CMED)based on the Fully Homomorphic Encryption(FHE).In particular,we firstly depict the underlying model and the formal definition.After that,we give our proposal by presenting the basic privacy-preserving operations,including MUX selection protocol,normal distance calculation protocol,comparison protocol,and minimum data obtaining protocol.Based on the above communication protocol for interactive calculation,K-means-CMED is con structed.We give the corresponding analysis for the correctness and security of our proposal.At last,the performance of the model is tested on the FCPS dataset.The experimental results show that the encrypted data clustering performance of K-Means-CMED is close to that of plaintext,which meets the practical application requirements of clustering,and solves the privacy protection problem of outsourced data clustering.

关 键 词：K-MEANS聚类 密文数据 全同态加密 隐私保护 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]