2019支持隐私保护的_i_k__i_近邻分类器-徐剑 , 王安迪 , 毕猛 , 周福才.pdf

上善若水

170

15页

0次

2022-05-23

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2019,30(11):3503−3517 [doi: 10.13 328/j.cnki.jos.005573] http://www.jos.org.cn

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

∗

徐

剑

1,2

王安迪

毕

猛

1,3

周福才

(东北大学软件学院,辽宁沈阳 110169)

(信息安全国家重点实验室(中国科学院信息工程研究所),北京 100093)

(沈阳工业大学,辽宁沈阳 110023)

通讯作者: 王安迪, E-mail: 13940201525@163.com

摘要: k 近邻(k-nearest neighbor,简称 kNN)分类器在生物信息学、股票预测、网页分类以及鸢尾花分类预测等

方面都有着广泛的应用.随着用户隐私保护意识的日益提高,kNN 分类器也需要对密文数据提供分类支持,进而保证

用户数据的隐私性,即设计一种支持隐私保护的 k 近邻分类器(privacy-preserving k-nearest neighbor classifier,简称

PP-kNN).首先,对 kNN 分类器的操作进行分析,从中提取出一些基本操作,包括加法、乘法、比较、内积等.然后,选

择两种同态加密方案和一种全同态加密方案对数据进行加密.在此基础上设计了针对基本操作的安全协议,其输出

结果与在明文数据上执行同一方法的输出结果一致,且证明该协议在半诚实模型下是安全的.最后,通过将基本操作

的安全协议进行模块化顺序组合的方式实现 kNN 分类器对密文数据处理的支持.通过实验,对所设计的 PP-kNN 分

类器进行测试.结果表明,该分类器能够以较高效率实现对密文数据的分类,同时为用户数据提供隐私性保护.

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

中图法分类号: TP309

中文引用格式: 徐剑,王安迪,毕猛,周福才.支持隐私保护的 k 近邻分类器.软件学报,2019,30(11):3503−3517. http:/ /www.jos .

org.cn/1000-9825/5573.htm

英文引用格式: Xu J, Wang AD, Bi M, Zhou FC. Privacy-preserving k-nearest neighbor classifier. Ruan Jian Xue B ao/Journal of

Software, 2019,30(11):3503−3517 (in Chinese). http://www.jos.org.cn/1000-9825 /5573.ht m

Privacy-preserving k-Nearest Neighbor Classifier

XU Jian

1,2

, WANG An-Di

, BI Meng

1,3

, 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)

Abstra ct : 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 d esigned 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 h omomorphic encryption scheme are selected

to encrypt the data. S ecurity protocols are designed for each of these, which outputs are consistent with the same operation over pl aintext

data and proved that protocol is secure in the semi-honest model. Finally, these s ecurity protocols are designed in a modules composable

∗ 基金项目: 国家自然科学基金(61 872069); 中央高校基本科研业务费专项资金(N171704005, N181704004); 沈阳市科技计划

(18-013-0-01)

Foundation item: National Natural Science Foundation of China (61872069); Fundamental Research Funds for the Central

Universities (N171704005, N181704004); Science and Technology Plan of Shenyang Muni cipality (18-013-0-01)

收稿时间: 2017- 11-27; 修改时间: 2018-01-04; 采用时间: 2018-02-09

3504

Journal of Software 软件学报 Vol.30, No.11, November 2019

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.

Key words: kNN classifier; encrypted data; privacy-pr eserving; homo morphic encryption; supervised l earning

分类器是数据挖掘中对样本进行分类的方法的统称.其设计目标是在通过学习后,能够将数据分到已知类

别.分类器不仅应用在搜索引擎以及各种检索程序中,而且也大量应用在数据分析与预测领域.kNN 分类器是一

种重要的分类器,广泛应用于生物信息学、股票预测、网页分类、鸢尾花类别预测等领域.

分类器在广泛应用的同时,也产生了严重的用户隐私泄露问题

[1,2]

,一旦泄露,会给数据拥有者带来危害.比

如,不法分子盗取患者癌症信息,利用患者迫切希望治愈的心理,向患者销售高价药品,骗取钱财;在利用 kNN 进

行股票预测时,如果股民的个股信息在分类过程中被泄露,就会给股票市场带来混乱.分类器处理的数据量大、

种类多,与之相关的用户数据隐私保护形势也非常严峻.目前,针对数据分类过程中的隐私保护研究主要集中在

密文数据运算方面,但是该类技术也存在如下问题:(1) 一些分类器对密文数据的运算复杂,运算效率较低;

(2) 加密技术针对的是特定的分类器,缺乏普适性.

kNN 分类器是监督学习中“懒惰学习”(lazy learni ng)的典型代表,监督学习过程由两个阶段构成.

(1) 样本训练阶段:在此阶段,首先获取在准备工作阶段处理好的训练数据;然后根据分类器类型选择分

类算法,对训练数据进行训练得到模型 W,以此作为分类阶段的一项输入.

(2) 应用阶段(分类阶段):分类器 C 通过模型 W 对测试向量 X 进行分类预测,得到最终的分类结果 C(W,X).

在样本训练和分类阶段,都可能发生用户隐私信息的泄露:在样本训练阶段,数据拥有者不希望自己拥有的

数据信息被泄露出去,甚至对训练者也要进行保密,这就需要对训练数据进行加密处理;在分类阶段,训练者会

将得到的模型 W 作为分类器的构成部分,并将分类器发布出去提供服务,但不希望成果被第三方获取,这就需要

对分类模型和测试向量进行加密.总而言之,分类器要保证数据的隐私性必须从两方面入手:(1) 训练数据集和

模型 W 的隐私保护;(2) 测试向量 X 和分类结果 C(W,X)的隐私保护.

目前已有一些关于分类器隐私保护的研究成果,但大多数方案都是针对训练阶段数据的隐私保护,很少有

针对分类模型和分类过程的保护.因此,设计基于加密数据的基本操作加密协议并以模块化顺序组合的方法构

造安全的分类器,使其从训练阶段到分类过程都能保证安全性,同时保证待测数据能够获得一个准确的类别,是

当前机器学习隐私保护的重要研究方向之一.

1 相关工作

分类器的构造和实施过程就决定其在隐私保护方面存在隐患,例如,在训练样本上执行分类器算法,生成分

类模型,很容易造成样本数据的泄露;在测试样本上执行分类模型,生成预测结果时,客户端会很容易得到分类

模型,而服务器端也可以轻易获取到输入的测试数据.因此,分类器在样本训练和分类阶段的数据隐私问题已成

为分类器隐私保护中最为重要的研究内容之一.

(1) 样本训练阶段

为了保证在样本训练阶段原始数据的隐私性,应将原始数据隐藏起来,在此阶段,不同的分类器会选择不同

的算法来训练原始数据,比如贝叶斯算法、支持向量算法、决策树算法等.这些算法包含了点积运算、加法运

算、比较运算.为了保证隐藏后的数据仍然能够进行上述运算,本阶段使用的隐私保护技术应满足 3 个方面的

要求:(1) 不改变原始数据的整体分布趋势;(2) 不能从隐藏后的数据中直接推算出原始数据值;(3) 确保经过变

换后的数据不会降低分类器的分类效果.目前,研究人员采用的技术主要分两类:数据干扰和数据加密.文献[3]

提出一种基于非线性维数降低(即非度量多维缩放)来干扰原始数据的隐私保护框架,使用 k-Nearest Neighbor

分类算法对分类任务中的新型隐私保护数据挖掘(privacy-preserving data mining,简称 PPDM)方法进行了测试,

在隐藏隐私数据的同时,保证了数据的有效性;文献[4]提出了数据扰动技术并利用该技术构建了决策树分类器,

之后,相继提出了不同的扰动方法

[5,6]

.但是,扰动技术不能保证密文数据的语义安全,且数据添加了统计噪声易

of 15

免费下载

软件学报计算机技术

关注

评论