机器学习算法在同态加密数据集上的应用
贾春福1,2, 王雅飞1,2, 陈阳1, 孙梦洁1, 葛凤仪1    
1. 南开大学 网络空间安全学院, 天津 300350;
2. 天津市网络与数据安全技术重点实验室, 天津 300350
摘要:大数据时代要求数据在云端进行存储和计算,这导致敏感数据隐私泄露的问题。该文提出了一种在同态加密数据集上应用机器学习分类算法的方案:首先对明文进行预处理,保证其满足对数据进行同态加密的要求;然后在加密数据集上通过协议实现比较、排序等操作;最后获取分类结果。客户端将加密数据上传,可以保证服务器端不会获取任何敏感信息;选取同态加密算法,能够保证服务器端仍可对密文执行相关操作。实验结果表明:该方案适用于Bayes、超平面和决策树分类器,其经过修正具有良好的适用性能,准确率高。
关键词隐私保护    同态加密    分类器算法    加密数据运算    
Machine learning algorithm for a homomorphic encrypted data set
JIA Chunfu1,2, WANG Yafei1,2, CHEN Yang1, SUN Mengjie1, GE Fengyi1    
1. College of Cyberspace Security, Nankai University, Tianjin 300350, China;
2. Tianjin Key Laboratory of Network and Data Security Technology, Tianjin 300350, China
Abstract: The continuous development of big data requires that data be stored and analyzed in the cloud, which leads to privacy leakage of sensitive data. This paper presents a machine learning classification algorithm for homomorphic encrypted data sets. Firstly, preprocess the data set to meet the requirements of homomofphic encryption. The encrypted data set is then sorted by protocol and classified. Finally, the classification results are obtained. The client can then upload encrypted data and ensure that the server will not get any sensitive information. A homomorphic encryption algorithm is used to ensure that the server can still perform required operations on the ciphertext. Tests show that this scheme can provide accurate, useful results with Bayes, hyperplane and decision tree classifiers.
Key words: privacy-preserving    homomorphic encryption    classification algorithm    operations on encrypted data    

随着大数据时代的不断发展,越来越多的数据不再仅仅由一方享有,数据的共享处理越来越普遍。个人用户往往对数据的处理能力有限,较高计算复杂度的处理过程通常会由服务器进行操作。在这一过程中,就存在敏感数据的安全问题。用户通常希望自己的敏感信息不会被除自己之外的他方获取,如何在保证敏感信息不被泄露的前提下进行一些智能算法的应用,成为学界的研究热点。

数据隐私保护的提出就是基于上述应用背景。企业或个人用户希望自己的敏感信息不会被泄露,与此同时,又不能损害原数据的可用性。客户端将数据传输到云端,由其进行一些复杂度较高的运算,而后将运算结果返回给客户端。在这一过程中,不仅要保证通过网络收集到的、已经得到客户授权的敏感信息的存储安全,还要保证在运用、处理这些数据的过程中对敏感信息的保护,不能让经手处理数据的每一方都能获取敏感信息。

对于敏感数据集的保护,最简单的办法就是通过加密算法使原有的数据不可读,保护敏感信息。目前,学界已有的隐私保护机器学习算法主要有文[1-6]等,其均通过加密对原数据集进行处理,使之不可读,而后再运用机器学习算法进行运算。由于保护数据隐私不能损害数据的可用性,加密后的密文数据应仍具备计算能力,即服务器依然可以在密文数据集上执行运算操作[7-10]。为满足上述需求,本文选择同态加密方案。同态加密可以保证对密文执行的基础运算会对其明文有同样的影响,从而保证密文数据集的可用性[11]

本文提出在经同态加密方案处理后的密文上构造机器学习分类器的方案,并给出相应实验验证,证实密文上执行的分类器算法可以得出正确结果,该方案实现隐私保护的同时不影响数据的可用性。并且从效率及准确性的角度,方案也能够满足实际需求,能够进一步应用到适合场景。

1 基础知识

本节将对方案中所选取的同态加密方案以及分类器算法进行介绍,并提出现阶段存在的问题。首先,对于本文中出现的符号在此进行说明。

v是在ℝ上选取n个元素组成的向量,v ∈ ℝn,ℝn表示的是在ℝ上选取n个元素组成向量v。||υ||表示向量v的模长,符号υ[i]指的是向量v的第i个分量。将u, v (u, v ∈ ℝn)的内积写为 < u, v >=$\sum\limits_{i = 1}^n {u\left[ i \right] \cdot v} \left[ i \right]$∈ℝ。ℤN*={x|1≤xN-1, gcd(x, N)=1},其中N是与同态加密相关联的模数。{wi}i=1k则表示从i=1, …, kkwi值。对于分布 $\mathcal{D}$a$\mathcal{D}$表示a$\mathcal{D}$中均匀抽取样本。而ℝd$\mathcal{H}$则表示从ℝd$\mathcal{H}$的特征映射。π是一个随机置换序列,将原本的k个数值打乱顺序以保证数据的安全性,可以将它看成一个乱序函数;π-1则表示乱序函数的逆函数,即找到该数据在原始排序中的位置。用〖m〗表示m的密文。

1.1 同态加密

同态加密是一种特殊的加密方式,其特性为在密文上执行某种运算操作,将新密文解密后所得到的明文是原2个明文执行相同操作后的结果[12-14]。依据允许执行的运算种类和次数的不同,同态加密方案可以分为3类:允许一种操作无限次数的部分同态(partially homomorphic encryption)[15-16];允许一些运算有限次数的SW同态(somewhat homomorphic encryption);允许不限种类不限次数运算的全同态(fully homomorphic encryption)[17-18]。同态加密方案一般由4部分组成:密钥生成、加密算法、评估算法(对密文执行运算操作)和解密算法。

SW同态中经常使用的算法包括ElGamal乘法同态加密方案[15]和Paillier[16]加法同态加密方案等,这些都是部分同态加密方案,即只对某一种运算是同态的。在本文中,主要使用的加密方式为Paillier加密方案,其具有的特性是对密文执行乘法操作,相当于对明文执行加法操作,满足在加法和数乘操作的同态性。Paillier加密算法的明文空间为加法群ℤN2*,同样由以下4部分组成。

密钥生成(KeyGen):选取2个长度相同的大素数pq, 满足gcd(pq, (p-1)(q-1))=1,计算N=pq, λ=lcm(p-1, q-1)。选取整数g∈ ℤN2*。公钥对为(N, g),私钥为λ

加密算法(Enc(m)):选取随机数r∈ ℤN

$ c = E\left( m \right) = {g^m}{r^N}\left( {\bmod {N^2}} \right). $ (1)

解密算法(Dec(c)):

$ D\left( c \right) = \frac{{L\left( {{c^\lambda }\left( {\bmod {N^2}} \right)} \right)}}{{L\left( {{g^\lambda }\left( {\bmod {N^2}} \right)} \right)}}\bmod N = m. $ (2)

其中,$L\left( u \right) = \frac{{u - 1}}{N}$.

评估算法:

$ \begin{array}{l} E\left( {{m_1}} \right) \times E\left( {{m_2}} \right) = \left( {{g^{{m_1}}}r_1^N\left( {\bmod {N^2}} \right)} \right) \times \\ \left( {{g^{{m_2}}}r_2^N\left( {\bmod {N^2}} \right)} \right) = {g^{{m_1} + {m_2}}}{\left( {{r_1} \times {r_2}} \right)^N}\left( {\bmod {N^2}} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;E\left( {{m_1} + {m_2}} \right). \end{array} $ (3)
1.2 机器学习分类器

机器学习算法在处理较大数据集时可以减轻人工负担,针对不同的需求,机器学习算法分为许多种类。本文的关注重点为在密文数据集上执行分类算法。主要涉及3种分类算法:Bayes分类器[19]、应用支持向量机(support vector machine, SVM)算法构建的超平面分类器[20]和决策树分类器[21]。将原有的分类器算法逐步进行剖析,将其划归为基础运算并对密文执行该运算操作。

1.2.1 Bayes分类算法

Bayes理论主要用来描述2个条件概率之间的关系,由英国数学家Bayes提出。本文应用朴素Bayes思想构造分类器。为便于数据处理,将用户所需处理的对象X输入为xx是一个拥有d个元素的向量,x =(x1, x2, …, xd)∈ ℝd称为特征向量。所使用的分类模型为w。在x上计算分类函数Cw: ℝd↦{c1, c2, …, ck}, 其输出ck*=Cw(x),k*∈{1, 2, …, k}。ck*x基于w所属的分类,将其写为k*,即k*=Cw(x)。

朴素Bayes分类器的模型w由多个概率组成:

1) 每个类ci出现的概率,即{p(C=ci)}i=1k

2) x的分量xj出现在某个类ci中的概率。更具体地说,后者是当x属于ci的范畴时, x的第j个分量xj值为v的概率,由{{{p(Xj=v|C=ci)}vDj} j=1d }i=1k表示,其中DjXj的域。使用最大后验决策规则的分类函数通过选择具有最高后验概率的类来工作:

$ \begin{array}{l} {k^*} = \arg \max p\left( {C = {c_i}|\mathit{\boldsymbol{X = x}}} \right) = \\ \;\;\;\;\arg \max p\left( {C = {c_i}, \mathit{\boldsymbol{X = x}}} \right) = \\ \arg \max p\left( {C = {c_i}, {X_1} = {x_1}, \cdots , {X_d} = {x_d}} \right). \end{array} $ (4)

其中, i∈[k].

1.2.2 决策树分类算法

决策树分类器允许服务器使用客户端的输入x遍历二元决策树,使得服务器不学习输入x,并且客户端不学习树的结构和每个节点的阈值。决策树中每一个非叶节点都是一个属性,通过对是否满足该点属性进行判断从而分为左右两支,每一个节点都有Boole值与之对应。构造一个多项式P,在输入所有Boole变量和叶节点上每个类的值时,输出为x预测的类。

1.2.3 超平面分类器分类算法

SVM是一种典型的分类模型,由Cortes和Vapnik[22]于1995年首次提出,它可以在特征空间上找出用于分类数据的间隔最大的分界线。超平面分类器由SVM算法构建。SVM算法用x表示数据、用y表示类别(y一般取-1和1来表示分类后的2个不同类),线性分类器通过对大量数据的学习,在n维的数据空间中找到一个n-1维的分界面用以将这些数据分为两类,分界方程可以表示为wT x +b=0。其中: b是一个常数,w是一个长度为n的列向量,wT中的T代表对模型w的转置,x代表一个包含n个属性的数据点,所以这里的x是一个n维的列向量。

SVM算法事实上就是在训练阶段学习到一个分类函数f(x)= wT x +b。当f(x)等于0时,x是位于超平面上的点; 当f(x)大于0时,把y值赋为1表示它的类别是在“1”中; 当f(x)小于0时,将类别y值赋为-1,以此将实例数据集分成两类。所以在测试阶段,将输入的未知的数据点x代入f(x)当中,若f(x)大于0,就将其类别y值赋为1,如果小于0就将y值赋为-1;当f(x)等于0时,原则上x是超平面上的数据点,类别y值赋为-1或者1均可,但由于是二元分类,因此在选定超平面时应当避免f(x)等于0的点,使f(x)的值大于或者小于0。

2 加密数据上的分类操作

隐私保护是指将隐私数据进行保护,使之不被泄露。在本文提出的方案中,保护的核心部分是敏感信息,并不完全局限于原有数据。针对Bayes分类器,对其概率进行加密保护;针对决策树分类器,对其信息增益率进行加密保护;针对超平面分类器,则对原数据进行加密。虽然针对不同分类算法选择不同的加密对象,但仍能够保证敏感信息不会被服务器端获取。

前文中也提出,由于同态加密算法只支持在密文上执行基础的运算操作,故其对于机器学习算法中的某些运算并不支持。参照现有文[14, 23-24],为解决这些问题,本文设计了在密文上进行比较以及排序的协议。协议如表 1所示。

表 1 加密数据的比较协议[2, 18]
协议1 加密数据的比较
A输入:〖a〗和〖b〗,ab的比特长l,公钥PKP
B输入:私钥SKP
B输出:(ab)
A:〖x〗←〖b〗·〖2l〗·〖a-1mod N2
  A从(0, 2λ+l)∩ℤ中选取一个随机整数r
A: 〖z〗←〖x〗·〖r〗 mod N2
A把〖z〗传给B
B解密〖z
A: cr mod 2l
B: dz mod 2l
B输出t=(d>c)

在密文比较协议中,对于2个数据ab,在加密数据上计算明文所对应的2l+b-a,并检查第l+1比特位的值(实际上对应于2l),如果值为1,则表示ba,否则b < a。在这一过程中,虽存在双方的交互,但仍能够保证AB双方不能获取对方的输入信息。并且,加密算法在此保证了仅获知密文并不能够破解出其敏感信息。

由于分类算法中涉及到选取序列中最大值、最小值以及获取序列排序顺序的问题,本文利用了文[14]中的排序思想,结合安全性证明,针对现有方案进行了改进。改进后的排序算法如表 2所示。

表 2 加密数据的最大值协议
协议2 加密数据的最大值
A输入:k个加密整数(〖a1〗, 〖a2〗, …, 〖ak〗),ai的比特长l,公钥PKP
B输入:密钥SKP,比特长l
A输出:最大值ai
A在{1, 2,…, k}上选择一个随机序列π
A: 〖max〗←〖aπ(1)
B: m←1
fori=2 tok do
  运用协议1进行比较,使B获得bi=(max≤aπ(i))
 A从(0, 2λ+l)∩ℤ中选取2个随机整数risi
 A: 〖mi〗←〖max〗·〖ri
  A: 〖ai〗←〖aπ(i)〗·〖si
 A将〖mi〗和〖ai〗传给B
 ifbi是真then
  B: mi
  B: 〖vi〗←Refresh〖ai
 else
  B: 〖vi〗←Refresh〖mi
  end if
 B把〖vi〗、〖bi〗传给A
 A〖max←〖vi〗·(g-1·〖bi〗)ir·〖bi-si
end for
Bm传给A
A输出π-1(m)

通过上述协议可以解决密文上比较大小以及排序问题。协议的设计具有普遍性,对于3种分类算法均可适用,对于适用Paillier算法加密的密文数据,经参数调整均可适用。

2.1 Bayes分类器

Bayes分类器的输入是原数据统计概率经加密后得到的密文。方案使用Paillier加密,其加密的明文应当为整数形式,故对于原概率需要进行编码处理。由于分类算法中使用的基本运算操作为加法和比较算法,故将概率与大整数相乘,从而得到满足需求的明文,将条件概率p(xj|ci)乘以常数而保持分类结果不变。

使用精度为52 bit双精度浮点类型计算条件概率,每个概率p均可表示为p=m·2e,其中m的二进制表示为(m)2=1.dd为52 bit整数。故1≤m < 2,m可重写为$m = \frac{{m'}}{{{2^{52}}}}, m' \in {\mathbb{N}} \cap \left[ {{2^{52}}, {2^{53}}} \right)$。用这种表示方法可以找到能让所有数变成整数的大数K。为便于处理,取K=252

安全Bayes分类器是基于朴素Bayes分类器的一种改进。为了保证数值的稳定性,对概率分布取对数:

$ \begin{array}{l} \;\;\;\;\;{k^*} = \arg \max \log p\left( {C = {c_i}|\mathit{\boldsymbol{X = x}}} \right) = \\ \arg \max \left\{ \begin{array}{l} \log p\left( {C = {c_i}} \right) + \\ \sum\limits_{j = 1}^d {\log p\left( {{X_j} = {x_j}|C = {c_i}} \right)} \end{array} \right\}, i \in \left[ k \right]. \end{array} $ (5)

服务器端需要为模型准备kd+1张表,其中的计算包含前文描述的大数K; 类的先验表PP(i)= 「Klogp(C=ci)⎤;每个类i的每个特征jTi, jTi, j(v)≈ 「Klogp(Xj=v|C=ci)⎤,vDj; 每个P按类别有一个条目,总共k个条目;T按类别和特征值有一个条目,即共有kD个条目,其中D=∑|Dj|。

在本文的示例中,依照上述方式计算条目将少于3 600条。此外,该准备步骤可以在服务器启动时一劳永逸地完成,因此可以在计算效率时将其平摊到每次计算中。

安全Bayes分类器的具体方案如表 3所示,其可在保护敏感信息同时满足分类要求。

表 3 安全Bayes分类器
协议3 安全Bayes分类器
客户端(C)Input:x=(x1, x2, …, xd)∈ℤd
服务器端(S)Input:概率表{logp(C=ci)}1≤ik和{logp(Xj=v|C=ci)}vDj}1≤jd, 1≤ik
客户端Output:令p(x, ci0)最大的i0
1. S准备表P和{Ti, j}1≤ik, 1≤jd,并用Paillier算法对其中的条目进行加密
2. S将〖P〗和{〖Ti, j〗}i, j发送给C
3.对所有的1≤ikC计算〖pi〗=〖P(i)〗 $\prod\limits_{j = 1}^d {} $Ti, j(xj)〗
4. CS一起运行argmax协议(协议2),使C得到i0=argmaxipi
5. C输出i0

2.2 决策树分类器

决策树分类器会将最终结果呈树状分布,每一个节点是一个属性,数据集由根节点进行遍历,每到一个节点就进行一次分类,直到遍历完所有属性。在这部分的设计过程中,本文曾尝试将原数据集作为明文直接进行加密,得到结果后进行分类。但是由于经过加密之后,原来的分布特征会发生改变,很大程度上会影响密文分类结果的准确性,故新方案对此问题进行调整。

由于使用Paillier加密明文数据集后得到的密文数据集具有无序性、随机性的特点,而决策树算法选取最佳属性计算信息增益率时,使用到的有效数据为每种属性取值的count计数,与数据本身的取值并无直接联系。因此使用原有方案不能实现密文数据的有效聚合,从而不能实现密文数据集的决策树分类。

在本方案中,仅对判定属性和信息增益率进行加密,将加密结果发送给服务器端,服务器端对加密后密文执行比较、排序等操作,将排好序的序列返回给客户端,客户端对其解密得到顺序。再使用原数据集进行节点遍历,得到分类结果。信息增益率是用来衡量最佳属性的评价标准。在这一过程中,仍能够保证服务器端不会获取到明文数据集的任何信息,与此同时,客户端对于服务器端的操作也不能获取有用信息。

2.3 超平面分类器

在超平面分类算法中,需要用到向量内积的运算操作,基于Paillier加密方式的特殊性,不能直接在密文上用向量内各元素乘积相加的方式来计算。Paillier加密方式中,明文的加法对应于密文的乘法;明文的乘法对应于密文的幂运算。故若想在明文上实现内积运算,需要在密文上执行幂运算和乘法运算。具体协议如表 4所示。

表 4 内积协议
协议4 计算内积[14]
A输入:x=(x1, x2, …, xd)∈ℤd,公钥PKP
B输入:y=(y1, y2, …, yd)∈ℤd,私钥SKP
B输出:〖 < x, y>〗
A加密x1, x2, …, xd并把加密数据〖xi〗传给B
B: 〖v〗=∏ixiyi mod N2
B输出〖v

本文对超平面分类算法中所涉及的基本运算做了修改,使之可以适用于在密文上的操作。超平面分类器协议如表 5所示。

表 5 超平面决策分类器协议
协议5 超平面决策分类器
Client's(C)输入:x=(x1, x2, …, xd)∈ℤd,公钥PKP
Server's(S)输入:{wi}i=1k任意i∈[k], wi∈ℤn,密钥SKP
Client's(C)输出:argmax < wi, x>,其中i∈[k]
fori tok do
 CS运用协议3计算内积,其中CA输入的xSB输入的wi
 C取得协议结果〖vi 〗     vi← < x, wi>
end for
CS运行协议1计算最大值,其中CASB,〖v1〗, 〖v2〗, …, 〖vk〗是输入数据的密文。C取得协议结果i0
i0←argmaxvi, i∈[k]
C输出i0

3 实验

对本文提出的方案进行实验验证。验证过程主要分为2部分:在纯明文环境中执行分类算法,得到分类结果;在方案设计的隐私保护环境下执行相应算法,得到在密文数据集上的结果。解密之后对2个结果进行对比评估。

3.1 实验环境

本实验采用的CPU为Intel Core i7,加密部分使用的是JAVA语言,分类器实现采用Python。安全Bayes分类器和决策树分类器均使用Nursery数据集进行实验,共有12 960条数据,选取其中的10 000条数据进行实验,使用UTF-8编码,约1 MB。超平面分类器实验使用的数据集是the Wisconsin Breast Cancer(Original)数据集,是原始数据集的一个简化版本,可以在University of California Irvine(UCI)机器学习数据库中下载[25],在python中直接调用sklearn.datasets import load_breast_cancer即可获取数据。

3.2 实验结果 3.2.1 安全Bayes分类器

对数据集进行分割,用其中的90%作为训练数据,剩下的10%作为测试数据。首先在建立好的模型上计算类的先验概率(如表 6所示),由于推荐的概率极小(约等于0),故而下面不对其进行描述。而后计算各个特征的后验概率,如表 7所示。对明文分类结果如表 8所示。

表 6 类别的先验概率
不推荐 推荐 非常推荐 优先考虑 最先考虑
0.333 0.000 0.033 0.395 0.239

表 7 各特征的后验概率
属性 属性取值 不推荐 非常推荐 优先考虑 最先考虑
父母职业 普通 0.428 0.593 0.485 0.319
较好的 0.434 0.407 0.375 0.530
很好的 0.138 0.000 0.140 0.151
当前托儿所 适合 0.257 0.403 0.346 0.107
不太适宜 0.225 0.407 0.312 0.044
不适宜 0.173 0.190 0.210 0.104
有问题 0.172 0.000 0.098 0.325
问题很大 0.173 0.000 0.035 0.420
家庭结构 完整 0.260 0.370 0.263 0.224
曾经完整 0.254 0.315 0.262 0.247
单亲 0.244 0.207 0.244 0.257
收养 0.242 0.108 0.231 0.272
孩子数目 1 0.251 0.454 0.276 0.192
2 0.249 0.318 0.254 0.235
3 0.253 0.105 0.237 0.285
更多 0.247 0.122 0.232 0.288
住所条件 方便 0.337 0.617 0.367 0.251
不方便 0.333 0.322 0.330 0.335
很不方便 0.334 0.061 0.303 0.414
财务状况 适宜 0.498 0.647 0.523 0.455
紧张 0.502 0.354 0.477 0.545
社会状况 无问题 0.333 0.515 0.346 0.286
轻微问题 0.332 0.485 0.344 0.292
有问题 0.336 0.000 0.310 0.423
健康状况 推荐 0.000 1.000 0.533 0.370
优先考虑 0.000 0.000 0.467 0.630
不推荐 1.000 0.000 0.000 0.000

表 8 明文的分类结果
预测结果 实际结果
不推荐 非常
推荐
优先
考虑
最先
考虑
精确率/%
不推荐 333 0 0 0 100.00
非常推荐 0 0 0 0 0.00
优先考虑 0 0 379 288 56.82
最先考虑 0 0 0 0 0.00
分类精度/% 100.00 0.00 100.00 0.00

由于对模型进行了数据处理,相当于对训练用的明文进行了修改。分别用未经加密的logp和-Klogp对测试数据进行处理,得到的分类准确率均为71.20%。用Pailier对-Klogp做加密处理后,将1 000条测试数据放入分类器进行分类,准确率亦为71.20%,分类结果如表 9所示。与未加密的模型相比,分类结果完全相同,相似度为100%,准确率不变,误差率为0,与预期相符。

表 9 已加密模型的分类结果
预测结果 实际结果
不推荐 非常
推荐
优先
考虑
最先
考虑
精确率/%
不推荐 333 0 0 0 100.00
非常推荐 0 0 0 0 0.00
优先考虑 0 0 379 288 56.82
最先考虑 0 0 0 0 0.00
分类精度/% 100.00 0.00 100.00 0.00

3.2.2 决策树分类器

对决策树叶节点数据个数进行统计,得到在纯明文环境下的分类结果,如表 10所示。依照方案设计加密处理后进行分类,此次数据集进行决策树分类的程序的运行时间为0.679 s,结果如表 11所示。对比2次分类结果,使用柱状图 1进行描述,可以发现二者拟合度为100%。本实验由于使用二叉决策树,在每个分叉节点会有数据丢失,故表 1011中分类的数据总数不同。

图 1 决策树分类器2次分类结果拟合

表 10 数据集第1次分类结果分布情况
结果 不推荐 推荐 非常推荐 优先考虑 最先考虑
计数 333 1 0 26 210

表 11 数据集第2次分类结果分布情况
结果 不推荐 推荐 非常推荐 优先考虑 最先考虑
计数 333 1 3 26 210

3.2.3 超平面分类器

首先读取明文数据集,然后将30个属性即30维数据降到二维来展示。其中,0代表的是恶性肿瘤,1代表的是良性肿瘤。图 2a2b分别是等距特征映射(IsoMap)降维图和主成分分析(principal component analysis,PCA)降维图,比较后大致可以看出PCA降维后的点分布比较均匀,更有利于进行超平面决策分类。使用PCA对30维数据进行分析得到图 3所示的PCA能量图,发现在30维数据中只有前5维数据会对实验结果产生影响,即前5个属性对判断乳腺癌良性还是恶性起决定作用。

图 2 IsoMap降维图和PCA降维图的比较

图 3 PCA能量值图

在进行分类过程中,选择数据集中的80%数据作为训练集,20%数据作为测试集。首先,使用SVM直接对原始训练集数据进行分类找到分类超平面,然后再用超平面去划分训练集数据,看能否区分训练集数据。整个分类过程运行时间大约为1.654 s。先将密文数据集降到二维平面显示,得到如图 4的PCA降维图。与明文数据的PCA降维图比较可以看出,加密后的数据点杂乱无章,很难看出两类数据之间的联系。

图 4 对加密数据的PCA降维图

与对明文数据集进行处理的方式一样,尝试对密文数据集进行标准化处理和降二维处理,得到的分类评分如表 12所示。从表格对比中可得出结论,评分结果可以接受但均不是很高,故对其进行参数优化使其结果更加理想。经过对参数进行优化,对密文的分类结果评分能够达到0.7左右,可以接受,但相比明文分类结果还是较低。

表 12 密文数据集处理和分类结果
数据集处理 训练集
分类评分
测试集
分类评分
密文数据集 0.629 0.632
标准化处理的密文数据集 0.619 0.705
降二维处理的密文数据集 0.625 0.667

3.3 实验评估分析

实验表明:对提取出的“特征”进行加密,改写加密算法,可以实现在加密数据上应用机器学习分类算法。这一特性与文[2, 4, 19]中对原数据集进行加密不同。对于安全Bayes分类器和决策树分类器,通过加密概率和信息增益率能够实现加密后分类结果与明文分类结果基本一致,具有较好的实验结果。对于超平面分类器,由于数据集的预处理以及中间计算过程的精度损耗,密文数据集上的结果与明文结果有一定出入,但仍在可接受范围内,满足一般实际需求。

4 结束语

数据安全一直是学界研究热点。同态加密能够实现保护敏感信息的同时不影响数据可用性,故可在加密数据上执行机器学习算法。本文提出针对3种不同分类器的密文分类方案,并对其进行实验验证和评估。Bayes分类器将原数据集的后验概率进行加密,而后执行分类处理,得到结果与原明文进行分类结果基本一致;决策树分类器对信息增益率进行加密,对特征属性进行排序,使其能够满足分类需求,达到较好结果;超平面分类器对原数据集加密形成的密文数据集进行分类处理,通过一系列参数优化,分类评分可以接受。本文所提出的3种基于加密敏感信息的分类器具有代表性和较为广泛的应用前景。除此之外,应用同态加密算法能够保证数据的安全性,对于客户端和服务器端不可获取对方敏感信息。

参考文献
[1]
[1] BOST R, ADA POPA R, TU S, et al. Machine learning classification over encrypted data[C]//22nd Annual Network and Distributed System Security Symposium. San Diego, USA:MIT CSAIL, 2015:186-219.
[2]
BOST R, POPA R A, TU S, et al. Machine learning classification over encrypted data[C]//22nd Annual Network and Distributed System Security Symposium. San Diego, USA:MIT CSAIL, 2015:4325.
[3]
BARNI M, FAILLA P, LAZZERETTI R, et al. Privacy-preserving ECG classification with branching programs and neural networks[J]. IEEE Transactions on Information Forensics and Security, 2011, 6(2): 452-468. DOI:10.1109/TIFS.2011.2108650
[4]
GRAEPEL T, LAUTER K, NAEHRIG M. ML confidential:Machine learning on encrypted data[M]//KWON T, LEE M K, KWON D. Information Security and Cryptology. Berlin, Germany:Springer, 2012:1-21.
[5]
CARPOV S, GAMA N, GEORGIEVA M, et al. Privacy-preserving semi-parallel logistic regression training with fully homomorphic encryption[J]. ePrint Archive, 2019:101.
[6]
曹来成, 刘宇飞, 董晓晔, 等. 基于属性加密的用户隐私保护云存储方案[J]. 清华大学学报(自然科学版), 2018, 58(2): 150-156.
CAO L C, LIU Y F, DONG X Y, et al. User privacy-preserving cloud storage scheme on CP-ABE[J]. Journal of Tsinghua University (Science and Technology), 2018, 58(2): 150-156. (in Chinese)
[7]
CHEON J H, JEONG J, KI D, et al. Privacy-preserving k-means clustering with multiple data owners[J]. IACR Cryptology ePrint Archive, 2019:466.
[8]
SO J, GULER B, AVESTIMEHR A S, et al. CodedPrivateML:A fast and privacy-preserving framework for distributed machine learning[Z]. arXiv:1902.00641, 2019.
[9]
KISS Á, NADERPOUR M, LIU J, et al. SoK:Modular and efficient private decision tree evaluation[J]. Proceedings on Privacy Enhancing Technologies, 2019(2): 187-208.
[10]
BLOM F, BOUMAN N J, SCHOENMAKERS B, et al. Efficient secure ridge regression from randomized Gaussian elimination[Z]. IACR Cryptology ePrint Archive 2019/773, 2019.
[11]
蒋林智, 许春香, 王晓芳, 等. (全)同态加密在基于密文计算模型中的应用[J]. 密码学报, 2017, 4(6): 596-610.
JIANG L Z, XU C X, WANG X F, et al. Application of (fully) homomorphic encryption for encrypted computing models[J]. Journal of Cryptologic Research, 2017, 4(6): 596-610. (in Chinese)
[12]
李增鹏, 马春光, 周红生. 全同态加密研究[J]. 密码学报, 2017, 4(6): 561-578.
LI Z P, MA C G, ZHOU H S. Overview on fully homomorphic encryption[J]. Journal of Cryptologic Research, 2017, 4(6): 561-578. (in Chinese)
[13]
ACAR A, AKSU H, ULUAGAC A S, et al. A survey on homomorphic encryption schemes:Theory and implementation[J]. ACM Computing Surveys, 2018, 51(4): 79.
[14]
BRAKERSKI Z, VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[M]//ROGAWAY P. Advances in Cryptology. Berlin, Germany:Springer, 2011:505-524.
[15]
ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[M]//Advances in Cryptology. Berlin, Germany:Springer, 1985:10-18.
[16]
PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[M]//Advances in Cryptology-EUROCRYPT'99. Berlin, Germany:Springer, 1999:223-238.
[17]
GENTRY C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing. Bethesda, USA:ACM, 2009:169-179.
[18]
BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]//2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Palm Springs, USA:IEEE, 2011:97-106.
[19]
VAIDYA J, KANTARCIOĞLU M, CLIFTON C. Privacy-preserving naive Bayes classification[J]. The VLDB Journal, 2008, 17(4): 879-898. DOI:10.1007/s00778-006-0041-y
[20]
LAUR S, LIPMAA H, MIELIKÄINEN T. Cryptographically private support vector machines[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia, USA:ACM, 2006:618-624.
[21]
BLUM A, DWORK C, MCSHERRY F, et al. Practical privacy:The SuLQ framework[C]//Proceedings of the Twenty-Fourth Symposium on Principles of Database Systems, Baltimore, USA, 2005:128-138.
[22]
Cortes C, Vapnik V. Support-vector networks[J]. Machine Learning, 1995, 20(3): 273-297.
[23]
VEUGEN T. Comparing encrypted data[EB/OL]. (2011). https://www.researchgate.net/publication/266527434_COMPARING_EnCRYPTED_DATA.
[24]
AVIDAN S, BUTMAN M. Efficient methods for privacy preserving face detection[C]//Advances in Neural Information Processing Systems. Cambridge, USA:MIT Press, 2006:57.
[25]
BACHE K, LICHMAN M. UCI machine learning repository[EB/OL].[2019-07-26]. https://archive.ics.uci.edu/ml/index.php.