支持隐私保护的k近邻分类器  

Privacy-preserving k-Nearest Neighbor Classifier

作　　者：徐剑[1,2] 王安迪 毕猛[1,3] 周福才[1] XU Jian;WANG An-Di;BI Meng;ZHOU Fu-Cai(Software College,Northeastern University,Shenyang 110169,China;State Key Laboratory of Information Security(Institute of Information Engineering,Chinese Academy of Sciences),Beijing 100093,China;Shenyang University of Technology,Shenyang 110023,China)

机构地区：[1]东北大学软件学院,辽宁沈阳110169 [2]信息安全国家重点实验室(中国科学院信息工程研究所),北京100093 [3]沈阳工业大学,辽宁沈阳110023

出　　处：《软件学报》2019年第11期3503-3517,共15页Journal of Software

基　　金：国家自然科学基金(61872069);中央高校基本科研业务费专项资金(N171704005,N181704004);沈阳市科技计划(18-013-0-01)~~

摘　　要：k近邻(k-nearest neighbor,简称kNN)分类器在生物信息学、股票预测、网页分类以及鸢尾花分类预测等方面都有着广泛的应用.随着用户隐私保护意识的日益提高,kNN分类器也需要对密文数据提供分类支持,进而保证用户数据的隐私性,即设计一种支持隐私保护的k近邻分类器(privacy-preserving k-nearest neighbor classifier,简称PP-kNN).首先,对kNN分类器的操作进行分析,从中提取出一些基本操作,包括加法、乘法、比较、内积等.然后,选择两种同态加密方案和一种全同态加密方案对数据进行加密.在此基础上设计了针对基本操作的安全协议,其输出结果与在明文数据上执行同一方法的输出结果一致,且证明该协议在半诚实模型下是安全的.最后,通过将基本操作的安全协议进行模块化顺序组合的方式实现kNN分类器对密文数据处理的支持.通过实验,对所设计的PP-kNN分类器进行测试.结果表明,该分类器能够以较高效率实现对密文数据的分类,同时为用户数据提供隐私性保护.k-nearest neighbor(kNN)classifier has wide applications in many areas such as bioinformatics,stock forecasting,Web-page classification,and Iris classification prediction.With the increasing awareness of user privacy protection,kNN classifier classification also needs to provide supports for encrypted data,so privacy-preserving kNN classifier(PP-kNN)is designed to keep the privacy of user data.Firstly,the operation of kNN classifier is analyzed,and a set of basic operations is extracted,including addition,multiplication,comparison,inner product,etc.Then,two homomorphic encryption schemes and one fully homomorphic encryption scheme are selected to encrypt the data.Security protocols are designed for each of these,which outputs are consistent with the same operation over plaintext data and proved that protocol is secure in the semi-honest model.Finally,these security protocols are designed in a modules composable way to achieve the encryption of the kNN classifier.The PP-kNN classifier is implemented and evaluated based on real data,the result show that the classifier could classify the ciphertext data with higher efficiency,and also provide privacy protection for user data.

关 键 词：KNN分类器 加密数据 隐私保护 同态加密 监督学习 

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