Journal of Software:2019.30(11):3503-3517

(东北大学 软件学院, 辽宁 沈阳 110169;信息安全国家重点实验室(中国科学院 信息工程研究所), 北京 100093;东北大学 软件学院, 辽宁 沈阳 110169;沈阳工业大学, 辽宁 沈阳 110023)
Privacy-preserving k-Nearest Neighbor Classifier
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;Software College, Northeastern University, Shenyang 110169, China;Shenyang University of Technology, Shenyang 110023, China)
Chart / table
Similar Articles
Article :Browse 184   Download 186
Received:November 27, 2017    Revised:January 04, 2018
> 中文摘要: k近邻(k-nearest neighbor,简称kNN)分类器在生物信息学、股票预测、网页分类以及鸢尾花分类预测等方面都有着广泛的应用.随着用户隐私保护意识的日益提高,kNN分类器也需要对密文数据提供分类支持,进而保证用户数据的隐私性,即设计一种支持隐私保护的k近邻分类器(privacy-preserving k-nearest neighbor classifier,简称PP-kNN).首先,对kNN分类器的操作进行分析,从中提取出一些基本操作,包括加法、乘法、比较、内积等.然后,选择两种同态加密方案和一种全同态加密方案对数据进行加密.在此基础上设计了针对基本操作的安全协议,其输出结果与在明文数据上执行同一方法的输出结果一致,且证明该协议在半诚实模型下是安全的.最后,通过将基本操作的安全协议进行模块化顺序组合的方式实现kNN分类器对密文数据处理的支持.通过实验,对所设计的PP-kNN分类器进行测试.结果表明,该分类器能够以较高效率实现对密文数据的分类,同时为用户数据提供隐私性保护.
Abstract: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.
文章编号:     中图分类号:TP309    文献标志码:
基金项目:国家自然科学基金(61872069);中央高校基本科研业务费专项资金(N171704005,N181704004);沈阳市科技计划(18-013-0-01) 国家自然科学基金(61872069);中央高校基本科研业务费专项资金(N171704005,N181704004);沈阳市科技计划(18-013-0-01)
Foundation items:National Natural Science Foundation of China (61872069); Fundamental Research Funds for the Central Universities (N171704005, N181704004); Science and Technology Plan of Shenyang Municipality (18-013-0-01)
Reference text:


XU Jian,WANG An-Di,BI Meng,ZHOU Fu-Cai.Privacy-preserving k-Nearest Neighbor Classifier.Journal of Software,2019,30(11):3503-3517