摘要: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.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5573