随着各种智能设备的普及，大量的数据被不断地生成和收集，机器学习技术允许从这些数据中分析提取隐藏且有价值的信息。一般来说，训练数据集越大，机器学习训练得到的模型也会越准确，但同时也需要大量的计算资源。云计算以其存储量大、计算能力强、扩展性强、性价比高等特点已逐步成为机器学习训练的理想平台。然而将存储和计算任务外包到云服务器，隐私问题会得不到保障。

在机器学习模型的训练和预测阶段，云服务器可能获取训练数据及用户查询和分类的结果，会涉及用户的隐私问题。同时，云服务器通过机器学习得到的训练模型应该为其独有而不被公开，且不应泄露任何有关参数。针对这些问题，在机器学习训练和预测的过程中，采取有效的隐私保护措施是非常有必要的^[1]。在目前的机器学习技术中，决策树是应用最广泛的模型之一，已经成功地应用于各种领域，如医疗诊断、人脸识别^[2]等方面。在医疗诊断中，医护人员可以将患者的医疗记录上传到云服务器，得到潜在疾病的症状评估和风险介绍。而患者不希望自己的个人隐私和诊断结果被泄露，医院方在云服务器上训练好的机器学习模型也应为医院私有。过去的几年里，已经提出了许多方案来解决这些隐私保护问题。这些方案主要分为非加密技术和加密技术两大类。非加密技术如数据随机化混淆^[3]和差分隐私^[4]会更易实现，但是隐私保护能力和机器学习模型的实用性较低。加密技术如同态加密的计算开销相对较高，但是方案通常不会影响模型的实用性，而且提供的隐私保障更高。在决策树评估中，需要对加密的决策树节点进行运算，而同态加密技术可以直接对加密的数据进行加法或乘法操作，且解密结果与用同一方法处理未加密的原始数据得到的输出结果一致，因此本文将利用同态加密解决隐私问题。早期对此问题的研究主要集中在隐私保护决策树的训练上，近年来，已有学者提出在分类阶段保护隐私，但目前的方案计算开销较大，且模型隐私仍没有得到很好的保护。

Bost等^[5]最早提出一种隐私保护决策树评估(privacy-preserving decision tree evaluation, PPDE)系统，将决策树视为多项式，通过计算该多项式得到分类结果，但该方案使用的是完全同态加密，计算成本昂贵，此外，在他们的工作中，预测模型属于公开信息，而实际情况中模型拥有者希望模型被保密。随后，学者们提出了更轻量级的密码系统即加性同态加密代替全同态加密，计算开销有所减少。Tueno等^[6]提出了一种将决策树表示为数组的方案，实现了不经意数组索引，在该方案中采用了乱码电路^[7]、不经意传输^[8]和不经意随机存取存储器，只需执行树的深度d次比较，计算开销有所降低，但该方案无法保证模型参数不被泄露。Cock等^[9]通过引入一个可信的第三方进行初始化来提高评估效率，该方案基于密钥共享技术，对深度和宽度较小的树处理效率较高，但对深度和宽度较大的树处理速度较低。而且这些方案不支持多用户多密钥，且仍无法很好地保护决策树模型的隐私。Aloufi等^[10]提出了一个多密钥同态决策树评估方案，允许多个模型所有者将决策树的评估委托给不可信方，但计算开销较大。Xue等^[11]提出了一个基于同意的隐私保护决策树评估方案，保护了决策树模型的隐私，同时引入了服务代理商以减少用户的计算开销，但方案不支持多用户多密钥。Liu等^[12]引入可信第三方密钥生成中心以支持多密钥，且降低了通信开销，同时支持模型的隐私保护，但不支持服务代理，用户的计算开销较大。

本文设计了一个同时保护查询数据、分类结果、决策树模型隐私且支持多用户多密钥和服务代理的多密钥隐私保护决策树评估(multi-key privacy-preserving decision tree evaluation, MPDE)方案。MPDE方案支持多用户多密钥，使用了可信第三方密钥生成中心，密钥分发完后即离线，降低了参与方之间的通信开销。引入第三方计算服务提供商，通过先授权后评估的方法，使授权的第三方可以直接从云服务器获取分类结果，且模型更接近现实，减少了用户方的计算开销。采用分布式双陷门公钥密码(distributed two-trapdoor public-key crypto, DT-PKC)系统^[13]，改进了安全比较协议，使该方案能够同时保护查询隐私、分类结果和决策树模型。

1 基础技术 1.1 分布式双陷门公钥密码系统

DT-PKC是一种加性同态密码系统，可以用来在多密钥环境中实现隐私保护和安全的外包计算。在BCP(Bresson-Catalano- Pointcheval)加密算法中有一个主密钥，可以用来解密所有的密文，而不考虑底层的公钥，这种主密钥泄露会导致整个系统的安全崩溃。为了克服这种攻击，在DT-PKC中，p和q是2个大素数，N=pq，主密钥λ被分成λ₁和λ₂两部分分别发送给云存储服务器(cloud storage server, CSS)和计算服务提供商(computing service provider, CSP)。因此，主密钥解密过程由2部分组成，该系统中明文域为Z_N, 密文域为Z_N², 加解密过程如下：

1) 加密：对于明文m∈Z_N, 私钥为sk, 公钥为pk=g^sk，选取随机数r∈Z_N, 计算得到：

$ X=g^{r} \bmod N^{2}, $

(1)

$ Y=(1+m N) \operatorname{pk}^{r} \bmod N^{2}, $

(2)

则密文为[m]=(X, Y)。

2) 解密：对于密文[m]=(X, Y)，CSS解密得到

$ Y^{\prime}=Y^{\lambda_{1}} \bmod N^{2}=\left(1+m \lambda_{1} N\right) \mathrm{pk}^{r \cdot \lambda_{1}} \bmod N^{2}. $

(3)

记为算法PDec_λ1(Y)。将{Y, Y′}发送到CSP, CSP计算得到

$ Y^{\prime \prime}=Y^{\lambda_{2}} \bmod N^{2}=\left(1+m \lambda_{2} N\right) \mathrm{pk}^{r \cdot \lambda_{2}} \bmod N^{2}. $

(4)

则明文为

$ m=\left(Y^{\prime} \cdot Y^{\prime \prime}-1\right) / N \bmod N^{2} . $

(5)

该部分解密过程记为算法PDec_λ2(Y, Y′)。

3) 同态性质：对于使用同一公钥加密的任意两个密文，加性同态性质有

$ \left[m_{1}\right] \cdot\left[m_{2}\right]=\left[m_{1}+m_{2}\right] . $

(6)

乘法同态性质有

$ \left[m_{1}+m_{2}\right]=\left[m_{1}\right]^{m_{2}} . $

(7)

对于任意给定的x∈Z_N, 有

$ [m]^{x}=[x \cdot m] . $

(8)

当x=N-1时, 有

$ [m]^{N-1}=[-m] . $

(9)

1.2 决策树

决策树^[14]的输入是一个n维特征向量M∈Zⁿ，树的每个决策节点d_k(k∈{1, 2, …, c])对应于布尔函数f_k(M)=1{a＜t}，其中：a是输入向量的特征值，t是阈值，c为决策节点数。该函数表示如果a＜t, 则函数输出为1，每个叶节点l_k与输出值v_k相关联；否则函数输出为0。

1.3 BLS短签名

BLS(Boneh-Lynn-Shacham) 签名算法是一种可以实现签名聚合和密钥聚合的算法。主要思想是将待签名的消息散列到一个椭圆曲线上的一个点，并利用双线性映射e函数的交换性质，在不泄露私钥的情况下验证签名的正确性。

设G和G₀分别是以大素数p为阶的加法和乘法群，G的生成元为g。建立双线性映射e: G×G→G₀，对于任意x, y∈Z_p和P, Q∈G₀，e满足：e(xP, yQ)=e(P, xyQ)=e(xyP, Q)=e(P, Q)^xy。

选取Hash函数H: {0, 1}^*→Z_p。签名过程如下：

1) 密钥生成：随机选取sk∈Z_p作为用户私钥，计算其公钥pk=g·sk。

2) 签名：对于消息m∈{0, 1}^*，计算签名Sig(m)=sk·H(m)。

3) 验证：已知公钥pk和消息m，如果e(pk, H(m))=e(Sig(m), g)，那么验证者接受该签名，否则拒绝该签名。证明过程为

$ \begin{gathered} e(\mathrm{pk}, H(m))=e(g \cdot \mathrm{sk}, H(m))= \\ e(\mathrm{sk} \cdot H(m), g)= \\ e(\operatorname{Sig}(m), g) . \end{gathered} $

(10)

1.4 代理重加密

代理重加密(proxy re-encryption, PRE)技术^[15]是委托可信第三方将用自己公钥加密的密文转化为可以用另一方私钥解密的密文。用户A用自己的公钥pk_UA加密明文m，得到密文[m]，使用用户A的私钥sk_UA和用户B的公钥pk_UB生成一个重加密密钥rk_A→B，代理方用密钥rk_A→B将密文[m]转化为用户B的私钥能够解密的密文[$\widetilde{m}$ ]，并发送给用户B，用户B解密得到明文，即可实现云端密文数据共享。

2 MPDE方案架构

MPDE方案模型由5个实体组成(见图 1)，分别为：

1) 密钥生成中心(key generation center, KGC)：是完全可信的参与方，主要负责为其他参与者分发和管理公私钥对，完成后便会离线。

2) 用户(user, U)：U可以是医院的医护人员，可分为数据使用者和数据提供者(data provider，DP), 数据提供者的数据被上传到云服务器进行训练。数据使用者可以通过授权第三方服务机构，利用云服务器提高的模型访问服务，得到诊断结果。部分数据提供者也可以是数据使用者。

3) 云存储服务器(cloud storage server, CSS)：云存储服务器可存储用户上传的数据，也可以根据其私有的决策树模型向用户提供分类服务。

4) 计算服务提供商(computing service provider, CSP)：负责部分解密CSS发送的中间结果，并协助CSS完成机器学习任务。

5) 服务代理商(service agent, SA)：第三方代理机构，用户授权的SA可以通过与CSS进行交互完成安全分类并获得加密结果。

3 MPDE方案

MPDE方案基于DT-PKC系统，主要由初始化、密钥分发、加密、授权、比较、分类结果计算、删除7个步骤组成，具体描述如下。

步骤1  初始化阶段。KGC选择2个大素数p、q，计算N=pq。取p^*=(p-1)/2，q^*=(q-1)/2，计算主密钥λ=p^*·q^*。随机选择μ∈Z_N²，计算生成元g=-μ^2NmodN²。KGC公开公共参数F=(N, g)，并秘密保存所有素数p、q、p^*、q^*和主密钥λ。

步骤2  密钥分发阶段。KGC将主密钥λ随机分成λ₁和λ₂两部分，分别发送给CSS和CSP，其中λ₁和λ₂同时满足λ₁+λ₂≡0 mod λ和λ₁+λ₂≡1 mod N²。对每个用户U_i(i∈{1, 2, …, η}，其中η为用户数)，KGC随机选择满足安全需求的sk_Ui∈[1, N/2]作为用户U_i私钥，并计算其公钥$\mathrm{pk}_{U_{i}}=g^{\mathrm{sk}_{U_{i}}}\bmod N^{2}$。对于每个数据提供者DP_j(j∈{1, 2，…，φ}，其中φ为数据提供者个数)，随机选择sk_DPj作为DP_j的私钥，并计算其公钥pk_DPj= $g^{\mathrm{sk} _{\mathrm{DP}_{j}}}$，则联合公钥为$\mathrm{Pk}_{\Sigma}=g^{\mathrm{sk}_{U_{i}}+\sum\limits_{j=1}^{\varphi} \mathrm{sk}_{\mathrm{DP}_{j}}}$。KGC随机选择sk_SA∈[1, N/2]作为SA的私钥，并计算其公钥pk_SA=g^sk_SAmodN²。

步骤3  加密阶段。对于给定的特征向量M=[a₁, a₂, …, a_n]∈Zⁿ，每个特征值a_i(i=1, 2, …, n)的二进制表示为a_{i, 1}a_{i, 2}…a_{i, l}，其中l为每个特征值的二进制位数。用户U_i加密特征向量M的过程如下：

1) 用户U_i随机选择r_{i, j}∈Z_N，计算A_{i, j}=g^{r_{i, j}}mod N²和$B_{i, j}=\left(1+a_{i, j} N\right) \mathrm{sk}_{U_{i}}^{r_{i, j}} \bmod N^{2}$，则加密a_{i, j}得到其密文为

$ \begin{gathered} {\left[a_{i, j}\right]=\left(A_{i, j}, B_{i, j}\right), i \in\{1,2, \cdots, n\},} \\ j \in\{1,2, \cdots, l\} . \end{gathered} $

特征值a_i的密文为

$ \left[a_{i}\right]=\left[a_{i, 1}\right]\left\|\left[a_{i, 2}\right]\right\| \cdots \|\left[a_{i, l}\right]. $

其中“‖”为级联运算。

特征向量M的密文为

$ [\boldsymbol{M}]=\left[a_{1}\right]\left\|\left[a_{2}\right]\right\| \cdots \|\left[a_{n}\right]. $

2) 用户U_i为特征向量生成名称σ和标签H(σ)，并生成一个伪身份UID以保护用户隐私，最后发送{UID, H(σ), [M]}给CSS。

步骤4  授权阶段。用户U_i授权SA，通过SA来获取标签为H(σ)的分类结果。

1) 用户U_i使用其私钥sk_Ui和SA的公钥pk_SA生成重加密密钥$r \mathrm{k}_{U_{i} \rightarrow \mathrm{SA}}=g^{\mathrm{pk}_{\mathrm{SA}} / \mathrm{sk}_{U_{i}}}$，计算授权信息δ={UID, SID, H(σ), rk_Ui→SA, time}，其中time为授权到期时间，UID和SID分别为U_i和SA的身份标识符；并将δ和δ的签名Sig(δ)=sk_Uk·H(δ)一起发送到CSS。

2) 用户U_i为SA生成授权令牌token={consent, UID, SID, H(σ), time}，其中consent为准许指令；并将令牌token和令牌签名Sig(token)=sk_Ui·H(token)发送给SA。

3) 当查询结束，用户U_i生成撤销信息ξ={revoke, UID, SID, H(σ)}，其中revoke为撤销指令，发送ξ和它的签名Sig(ξ)=sk_Ui·H(ξ)给CSS，CSS将撤销信息添加到授权撤销列表(consent revocation list，CRL)。

步骤5  比较阶段。通过安全比较算法，可以比较2个用不同公钥加密的数据，从而获得决策树节点值。当CSS收到来自SA的查询请求Q={token, Sig(token)}和签名Sig(Q)=sk_SA·H(Q)，先检查CRL，如果授权没有被撤销且请求的签名有效，则进行以下步骤：CSS用重加密密钥rk_Ui→SA加密密文[a_{i, j}]，得到[$\tilde{a}_{i, j}$ ]，通过代理重加密，用户U_i(i∈{1, 2, …, η})委托CSS将用自己公钥加密的密文转化为可以用SA私钥解密的密文。为方便阅读，后文的[a_{i, j}]均表示重加密后的密文[$\tilde{a}_{i, j}$]，其中i∈{1, 2, …, n}, j∈{1, 2, …, l}。

由于决策树的每个决策节点d_k的输入为n维特征向量M=[a₁, a₂, …, a_n]的某个特征值，则所有节点d₁、d₂、…、d_k、…、d_c的输入特征值的下标序列必为a₁、a₂、…、a_n的下标序列(1, 2, …, n)的1个子序列，设其为(i₁, i₂, …, i_k, …, i_c)，其中i_k为节点d_k的输入特征值的下标，即a_ik为节点d_k的输入特征值。根据特征值a_ik与其相应的阈值t_k, 可得到相关布尔函数：

$ f(\boldsymbol{M})=1\left\{a_{i_{k}}<t_{k}\right\} . $

(11)

设t_k的二进制表示为t_k1t_k2…t_kl，对于每个决策节点d_k，输入特征值和其对应阈值，执行安全比较协议，输出比较结果[b]即为某一决策节点上的决策结果，具体的协议过程如下：

1) CSS随机选择b₀∈{0, 1}，计算s=1-2b₀，根据式(1)和(2)对其加密得到s的密文[s]。

2) 对于每个i∈{1, 2, …, l-1}，CSS通过跨域安全加法协议计算由不同公钥加密的特征值[a_i]_pkUi和其对应阈值[t_i]_pkΣ的相加结果[x_i]_pkΣ，具体计算如下所示：

① CSS选取随机数r₁, r₂∈Z_N，随机化[a]_pkUi和[t]_pkΣ为[a+r₁]_pkUi和[t+r₂]_pkΣ。令A=a+r₁，T=t+r₂，则根据式(1)和(2)得A和T的密文为[A]=(X_[A], Y_[A]), [T]=(X_[T], Y_[T])。

② CSS通过式(3)部分解密[A]和[T]得：

$ Y_{[A]}^{\prime}=Y_{[A]}^{\lambda_{1}} \bmod N^{2}=\left(1+A \lambda_{1} N\right) \mathrm{pk}_{U_{i}}^{r \cdot \lambda_{1}} \bmod N^{2}, $

$ Y_{[T]}^{\prime}=Y_{[T]}^{\lambda_{1}} \bmod N^{2}=\left(1+T \lambda_{1} N\right) \operatorname{pk}_{\varSigma}^{r \cdot \lambda_{1}} \bmod N^{2} . $

发送{Y_[A], Y′^[A], Y_[T], Y′_[T]}到CSP。

③ CSP通过式(4)部分解密[A]和[T]得：

$ Y_{[A]}^{\prime \prime}=Y_{[A]}^{\lambda_{2}} \bmod N^{2}=\left(1+A \lambda_{2} N\right) \mathrm{pk}_{U_{i}}^{r \cdot \lambda_{2}} \bmod N^{2}, $

$ Y_{[T]}^{\prime \prime}=Y_{[T]}^{\lambda_{2}} \bmod N^{2}=\left(1+T \lambda_{2} N\right) \mathrm{pk}_{\varSigma}^{r \cdot \lambda_{2}} \bmod N^{2} . $

由式(5)解密得到明文为：

$ A=\left(Y_{[A]}^{\prime} \cdot Y_{[A]}^{\prime \prime}-1\right) / N \bmod N^{2}, $

$ T=\left(Y_{[T]}^{\prime} \cdot Y_{[T]}^{\prime \prime}-1\right) / N \bmod N^{2} . $

用公钥pk_Σ按式(1)和(2)对(A+T)加密得到[A+T]_pkΣ，并将其发送到CSS。

④ 同理CSS按式(1)和(2)加密(r₁+r₂)得到[r₁+r₂]_pkΣ，并按式(6)和(9)计算得到

$ \left[x_{i}\right]_{\mathrm{pk}_{\mathrm{\Sigma}}}=[A+T]_{\mathrm{pk}_{\mathrm{\Sigma}}}\left(\left[r_{1}+r_{2}\right]_{\mathrm{pk}_{\mathrm{\Sigma}}}\right)^{N-1}=[a+t]_{\mathrm{pk}_{\mathrm{\Sigma}}} . $

3) 对于每个i∈[1, l]，随机选取θ_i∈Z_N, 计算

$ y_{i}=\theta_{i} \cdot\left(\left[a_{i}\right]-\left[t_{i}\right]+[s]+3 \cdot \sum\limits_{j<i}\left[x_{j}\right]_{\mathrm{pk}_{\mathrm{\Sigma}}}\right), $

按式(1)和(2)加密y_i得其密文为[y_i]=(X_[yi], Y_[yi])。

4) CSS根据式(3)部分解密[y_i]得

$ Y_{\left[y_{i}\right]}^{\prime}=Y_{\left[y_{i}\right]}^{\lambda_{1}} \bmod N^{2}=\left(1+y_{i} \lambda_{1} N\right) \operatorname{pk}_{\Sigma}^{r \cdot \lambda_{1}} \bmod N^{2} . $

将{Y_[yi], Y′_[yi]}(i∈{1, 2, …, l-1})发送到CSP.

5) CSP根据式(4)部分解密[y_i]得

$ Y_{\left[y_{i}\right]}^{\prime \prime}=Y_{\left[y_{i}\right]}^{\lambda_{2}} \bmod N^{2}=\left(1+y_{i} \lambda_{2} N\right) \operatorname{pk}_{\Sigma}^{r \cdot \lambda_{2}} \bmod N^{2} . $

由式(5)解密得到明文为

$ y_{i}=\left(Y_{\left[y_{i}\right]}^{\prime} \cdot Y_{\left[y_{i}\right]}^{\prime \prime}-1\right) / N \bmod N^{2} . $

6) 对于所有i∈{1, 2, …, l-1}，如果y_i全部为0，则令[b₁]=[1]，否则令[b₁]=[0]，发送[b₁]到CSS。

7) CSS计算决策树节点的布尔值[b]=[b₀⊕b₁]。

步骤6  计算评估结果。将模型表示为线性函数。ec_{k, 1}表示决策树左分支的开销，ec_{k, 0}表示右分支边的开销。P_li表示从根节点到叶节点l_i的路径开销。令左分支的路径开销为[ec_{k, 1}]=[1-b_k]，右分支的路径开销为[ec_{k, 0}]=[b_k]。路径表示为

$ \left\{\begin{array}{l} {\left[P_{l_{1}}\right]=\left[\left(1-b_{1}\right)+\left(1-b_{2}\right)\right],} \\ {\left[P_{l_{2}}\right]=\left[\left(1-b_{1}\right)+b_{2}\right],} \\ {\left[P_{l_{3}}\right]=\left[b_{1}+\left(1-b_{3}\right)+\left(1-b_{4}\right)\right],} \\ {\left[P_{l_{4}}\right]=\left[b_{1}+\left(1-b_{3}\right)+b_{4}\right],} \\ {\left[P_{l_{5}}\right]=\left[b_{1}+b_{3}\right] .} \end{array}\right. $

(12)

对于每个叶节点l_i(i∈{1, 2, …, c+1})，随机选择r_i∈Z_N，CSS使用混合公钥同态加密得到

$ \left[P_{l_{i}}\right]_{\mathrm{pk}_{\Sigma}}=\left[r_{i} \sum\limits_{\substack{1 \leqslant k \leqslant c+1 \\ j \in\{0,1\}}} \mathrm{ec}_{k, j}\right]. $

(13)

例如，当c=4时，b=(b₁, b₂, b₃, b₄)代表每个节点的布尔值，决策树如图 2所示。

将决策树模型转换为线性函数，则加密后的线性函数表示为[H_li]_pkΣ=[r_i·P_li+l_i]，其中i∈{1, 2, …, c+1}是线性函数的个数。通过域转换算法，SA使用自己的私钥解密得到评估结果[P_li]_pkSA和[H_li]_pkSA，具体过程如下：

1) CSS随机选取α∈Z_N，令P_i=([P_li]_pkΣ)^α，由式(8)可得P_i=([P_li]_pkΣ)^α=[α·P_li]_pkΣ，P_i即可表示为P_i=(X_Pi, Y_Pi)。

根据式(3)部分解密P_i得到

$ Y_{P_{i}}^{\prime}=Y_{P_{i}}^{\lambda_{1}} \bmod N^{2}=\left(1+\alpha P_{l_{i}} \lambda_{1} N\right) \operatorname{pk}_{\Sigma}^{r \cdot \lambda_{1}} \bmod N^{2} . $

发送{Y_Pi, Y^′_Pi}到CSP。

2) CSP根据式(4)部分解密P_i得到

$ Y_{P_{i}}^{\prime \prime}=Y_{P_{i}}^{\lambda_{2}} \bmod N^{2}=\left(1+\alpha P_{l_{i}} \lambda_{2} N\right) \operatorname{pk}_{\Sigma}^{r \cdot \lambda_{2}} \bmod N^{2}. $

由式(5)解密得到明文为

$ z_{i}=\left(Y_{P_{i}}^{\prime} \cdot Y_{P_{i}}^{\prime \prime}-1\right) / N \bmod N^{2}. $

用SA的公钥pk_SA加密z_i得[z_i]_pkSA，并将[z_i]_pkSA发送给CSS。

3) CSS计算$P_{l_{i}}=\left(\left[z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}\right)^{N-\alpha}$。输出由公钥pk_SA加密的密文$\left[P_{l_{i}}\right]_{\mathrm{pk}_{\mathrm{SA}}}=\left(X_{P_{l_{i}}}, Y_{P_{l_{i}}}\right)$。

CSS同理加密得[H_li]_pkSA，并发送[P_li]_pkSA和[H_li]_pkSA给SA，SA对[P_li]_pkSA进行解密，如果解密结果全部为0，则对[H_li]_pkSA进行解密得到评估结果。

步骤7  删除阶段。查询完毕后，删除查询信息，即删除标签为H(σ)的特征向量。用户生成Ω=(delete, UID, H(σ))，其中delete为删除指令，并将Ω和签名Sig(Ω)发送给CSS, CSS删除标签为H(σ)的特征向量。

4 正确性分析

在MPDE方案中，跨域安全加法协议用于保证由不同公钥加密的特征值[a_i]_pkUi与其对应阈值[t_i]_pkΣ相加时的安全性，而评估过程中的域转换算法用于将由联合公钥加密的密文转换成可由SA的私钥解密的密文，因此必须保证跨域安全加法协议和评估结果的正确性。

4.1 跨域安全加法协议正确性

对于步骤5协议过程2中跨域安全加法协议的正确性证明如下：

根据式(6)可得：

$ {[A] \leftarrow[a]_{\mathrm{pk}_{U_{i}}} \cdot\left[r_{1}\right]_{\mathrm{pk}_{U_{i}}}=\left[a+r_{1}\right]_{\mathrm{pk}_{U_{i}}},} $

$ {[T] \leftarrow[t]_{\mathrm{pk}_{\Sigma}} \cdot\left[r_{2}\right]_{\mathrm{pk}_{\Sigma}}=\left[t+r_{2}\right]_{\mathrm{pk}_{\Sigma}} .} $

根据式(9)，可计算得到

$ \begin{gathered} {[A+T]_{\mathrm{pk}_{\mathrm{\Sigma}}}\left(\left[r_{1}+r_{2}\right]_{\mathrm{pk}_{\mathrm{\Sigma}}}\right)^{N-1}=} \\ {\left[A+T-\left(r_{1}+r_{2}\right)\right]_{\mathrm{pk}_{\Sigma}}=} \\ {\left[a+r_{1}+t+r_{2}-r_{1}-r_{2}\right]_{\mathrm{pk}_{\Sigma}}=[a+t]_{\mathrm{pk}_{\Sigma}} .} \end{gathered} $

4.2 评估结果正确性

对于步骤6中域转换算法的正确性证明如下：

因为$P_{i}=\left(\left[P_{l_{i}}\right]_{\mathrm{pk}_{\Sigma}}\right)^{\alpha}=\left[\alpha \cdot P_{l_{i}}\right]_{\mathrm{pk}_{\Sigma}}$，所以其解密后明文为：z_i=α·P_li。

公钥pk_SA加密z_i后，由式(8)可得

$ \left[z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}} \leftarrow\left[\alpha \cdot P_{l_{i}}\right]_{\mathrm{pk}_{\mathrm{SA}}}=\left(\left[P_{l_{i}}\right]_{\mathrm{pk}_{\mathrm{SA}}}\right)^{\alpha} . $

则由式(6)、(8)和(9)有

$ \begin{gathered} {\left[P_{l_{i}}\right]_{\mathrm{pk}_{\mathrm{SA}}}=\left(\left[z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}\right)^{-\alpha}=\left[-\alpha \cdot z_{i}\right]_{\mathrm{pk}_{\mathrm{\Sigma}}}=} \\ {\left[-z_{i}+(1-\alpha) z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}=} \\ {\left[-z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}} \cdot\left[(1-\alpha) z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}=} \\ \left(\left[z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}\right)^{N-1} \cdot\left(\left[z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}\right)^{1-\alpha}=\left(\left[z_{i}\right]_{\mathrm{pk}_{\mathrm{SA}}}\right)^{N-\alpha} \cdot \end{gathered} $

5 隐私性保护分析

在MPDE方案中，决策树数据和模型的隐私性主要表现在用户上传数据和云服务器存储数据的语义隐私性、机器学习过程中模型参数隐私性和用户的授权查询隐私性3个方面。

5.1 语义隐私性

在MPDE方案中，用户发送到云存储服务器的数据是通过自己的公钥加密的，只有用户自己的私钥才能进行解密。本文中所有的数据都通过DT-PKC密码系统加密，由文[13]可知DT-PCK在语义上是安全的，服务器无法获取数据。而且叶节点的所有值也都是经过加密后再通过线性方程得到决策结果，服务器无法从加密的结果中推算出分类结果，评估结果的隐私性得到了保障。

在MPDE方案的步骤3中，特征值a_i的二进制a_{i, 1}a_{i, 2}…a_{i, l}中任意1位a_{i, j}的密文为[a_{i, j}]=(A_{i, j}, B_{i, j})，而A_{i, j}=g^{r_{i, j}}modN²，B_{i, j}=(1+a_{i, j}N)·$\mathrm{sk}_{U_{i}}^{r_{i, j}} \bmod N^{2}$，由于r_{i, j}为用户随机选取的秘密值，根据计算离散对数的困难性，敌手即使获取了密文[a_{i, j}]，也无法解密获得最终的明文。因此MPDE方案具有用户数据隐私的保护性。

5.2 模型参数隐私

在MPDE方案的步骤5的安全比较协议中，用户和授权的服务请求方并不能得到每个决策节点的实际比较结果。在交互之后，随机化的路径成本和分类结果被发送给服务代理商，只有正确的评估结果对应为0，其他结果对于服务请求方来说都是随机数。而且只有解密后才能获得正确的分类结果，服务请求方无法获取叶节点的其他值。决策树是存储在CSS中，而CSP在交互的过程中可以通过统计安全比较的次数来推断树节点的数量，为了避免这种信息泄露，添加部分具有随机阈值的虚拟节点，增加安全比较次数，攻击者就无法获取真实决策节点数量。因此MPDE方案具有模型参数隐私的保护性。

5.3 授权查询隐私

由MPDE方案步骤4可知，用户U_i(i∈{1, 2, …, η})通过向云服务器发送授权信息，向SA发送授权令牌，授权SA获取数据的分类结果。在U_i与SA交互过程中的重加密密钥只能由U_i生成，而且不能传递，因此只有获得授权的SA能够与CSS交互，并使用其私钥解密分类结果。授权时间到期后，SA无法再使用U_i提供的数据与CSS进行交互，而且在U_i撤销了SA的权限之后，CSS不再向该SA提供在该用户权限下的服务。因此MPDE方案具有授权查询隐私的保护性。

6 性能分析 6.1 功能对比

MPDE方案在功能上分别与文[9, 11-12]进行对比，如表 1所示。文[9]引入了密钥生成中心，但不支持模型参数隐私保护及语义隐私和授权查询隐私保护、多用户多密钥和授权服务代理商。文[11]的方案支持模型参数隐私保护，但不支持语义隐私和授权查询隐私保护；采用了授权服务代理商机制，减少了用户与云的通信次数，且降低了用户的计算开销，但不支持多用户多密钥。文[12]支持模型参数隐私保护、多用户多密钥和密钥生成中心，但是不支持语义隐私和授权查询隐私保护，没有引入授权服务代理商。而MPDE方案对模型参数的隐私保护能力较强，并且支持语义隐私和授权查询隐私保护、多用户多密钥操作，引入了密钥生成中心，减少参与方之间的交互即减少了通信开销，同时支持授权服务代理商即减小了用户计算开销。

6.2 性能对比

将MPDE方案与文[9, 11-12]在用户、云服务器、服务代理商的计算复杂度和用户与云服务器交互轮数等方面进行了比较，结果如表 2所示。

因为O(cl+2^d)为指数阶复杂度，当d足够大时有O(nl)＜O(cl+2^d)，所以从表 2可知，MPDE方案中用户计算复杂度O(nl)低于文[9, 11-12]方案中的计算开销O(cl+2^d)、O((n+c)l)和O((n+c)l)。同时可以发现，MPDE方案在云服务器端计算复杂度为O(nl)，与文[12]相等，但低于文[11]的O((n+c)l)和文[9]的O((n+c)l+d)。MPDE方案中用户服务器之间交互2轮，少于文[9]中的9轮，与文[11]相同，但比文[12]多1轮，这是由于MPDE方案中采用了服务代理商，因此多了用户向云服务器提供授权信息这一交互环节。对于高性能云服务器而言，增加的开销对其影响较小，同时提供了更好的通信服务。针对服务代理商的计算复杂度，由于文[9]和[12]不支持该服务，因此只比较文[11]和MPDE方案，2个方案中的计算复杂度都为。因此，MPDE方案在计算开销上具有相对较高的效率，且能提供更好的服务。

6.3 实验分析

为了评估MPDE方案的效率，本文在配备Windows 10操作系统、2.95 GHz Intel i7-7500U处理器和8 GB RAM的笔记本上进行了实验。本文比较了8个用户的情况下MPDE方案与文[9, 11-12]方案的用户平均计算时间。将表 2中l设置为64，n设置为8，图 3为当决策节点c的数量从3(d为2)增加到24(d为5)时4个方案中用户的平均计算时间对比。MPDE方案中用户将查询权限和任务委托给服务代理商SA，只需要将加密的数据上传到服务器，无需参与随后的分类过程，即该方案中用户的平均计算时间不随决策节点数的增加而增加。而文[9, 11-12]的3个方案中用户的平均计算时间随决策节点数的增加而增加。因此，MPDE方案的计算时间开销相比其他方案的低。

本文还测试了MPDE方案与文[9, 11-12]方案中完成决策树评估所需的时间和通信开销，并进行了对比。该实验基于UCI(University of California，Irvine)知识库中的2个数据集breast-cancer和spambase，结果如表 3所示。可以看出，在这2个数据集中，MPDE方案的决策树评估时间比文[9, 11-12]方案的都短，且MPDE方案的通信开销低于文[9, 11-12]方案的。图 4和5反映了这4个方案在数据集breast-cancer和spambase上的评估时间和通信开销的聚类对比情况，可以发现MPDE方案的评估时间和通信开销的聚类都要低于其他3个方案。综上，与文[9, 11-12]的方案相比，MPDE方案在真实数据集上决策树评估的时间与通信开销都明显降低。树的节点越多，评估所需的计算通信开销就越高。目前只在低性能的计算机上进行了实验，通过高性能计算机的并行运算将进一步减少运行时间。

7 结论

本文提出了一个多密钥隐私保护决策树评估方案，支持同时对查询、分类结果和决策树模型的隐私保护。方案使用了DT-PKC密码系统，实现了多密钥环境下的隐私保护和安全外包计算。引入KGC，降低了参与方之间的通信开销。同时引入SA，通过先授权后评估的方法，授权的SA可以从云服务器获取分类结果，使模型更接近现实情况，且减少了用户方的计算开销。该方案在保护隐私的同时降低了通信开销和计算开销。通过性能分析和实验对比，在UCI数据集上进行了模拟，结果显示方案具有良好的性能。在接下来的工作中，将进一步优化安全比较协议，减少按位比较的次数，提高决策树评估的效率。并在实验中使用高效能的硬件，将系统部署在拥有更多GPUs核心和更大容量RAM芯片的服务器上。