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

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

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

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

1 基础知识

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

v是在ℝ上选取n个元素组成的向量，v ∈ ℝⁿ，ℝⁿ表示的是在ℝ上选取n个元素组成向量v。||υ||表示向量v的模长，符号υ[i]指的是向量v的第i个分量。将u, v (u, v ∈ ℝⁿ)的内积写为 < u, v >=$\sum\limits_{i = 1}^n {u\left[ i \right] \cdot v} \left[ i \right]$∈ℝ。ℤ_N^*={x|1≤x≤N-1, gcd(x, N)=1}，其中N是与同态加密相关联的模数。{w_i}_i=1^k则表示从i=1, …, k的k个w_i值。对于分布 $\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个长度相同的大素数p，q, 满足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输入为x。x是一个拥有d个元素的向量，x =(x₁, x₂, …, x_d)∈ ℝ^d称为特征向量。所使用的分类模型为w。在x上计算分类函数C_w: ℝ^d↦{c₁, c₂, …, c_k}, 其输出c_k^*=C_w(x)，k^*∈{1, 2, …, k}。c_k^*是x基于w所属的分类，将其写为k^*，即k^*=C_w(x)。

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

1) 每个类c_i出现的概率，即{p(C=c_i)}_i=1^k。

2) x的分量x_j出现在某个类c_i中的概率。更具体地说，后者是当x属于c_i的范畴时, x的第j个分量x_j值为v的概率，由{{{p(X_j=v|C=c_i)}_v∈Dj} _j=1^d }_i=1^k表示，其中D_j是X_j的域。使用最大后验决策规则的分类函数通过选择具有最高后验概率的类来工作：

$ \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维的分界面用以将这些数据分为两类，分界方程可以表示为w^T x +b=0。其中: b是一个常数，w是一个长度为n的列向量，w^T中的T代表对模型w的转置，x代表一个包含n个属性的数据点，所以这里的x是一个n维的列向量。

SVM算法事实上就是在训练阶段学习到一个分类函数f(x)= w^T 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所示。

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

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

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

2.1 Bayes分类器

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

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

安全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; 类的先验表P：P(i)= 「Klogp(C=c_i)⎤;每个类i的每个特征jT_{i, j}：T_{i, j}(v)≈ 「Klogp(X_j=v|C=c_i)⎤，v∈D_j; 每个P按类别有一个条目，总共k个条目；T按类别和特征值有一个条目，即共有kD个条目，其中D=∑|D_j|。

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

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

2.2 决策树分类器

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

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

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

2.3 超平面分类器

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

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

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所示。

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

3.2.2 决策树分类器

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

3.2.3 超平面分类器

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

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

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

3.3 实验评估分析

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

4 结束语

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