0 引言

互联网的迅速发展使得网络信息资源越来越丰富, 但在满足用户对信息需求的同时也引发了信息过载问题, 用户往往需要花费大量时间和精力从海量数据信息中筛选出对自己有用的信息.搜索引擎虽然能在一定程度上解决这种问题, 但无法满足用户个性化的需求, 因此个性化推荐系统应运而生.个性化推荐系统是建立在海量数据挖掘基础之上的一种智能平台, 它根据用户个人信息, 比如用户的兴趣特点和购买行为等, 向用户推荐其可能感兴趣的其他信息, 从而为用户提供个性化的信息服务和决策支持, 比如淘宝的购物推荐、Amazon的购书推荐、豆瓣的电影推荐等均是典型的个性化推荐系统应用案例.推荐系统根据推荐算法的不同可分为基于内容的推荐、协同过滤推荐、混合推荐等3类.协同过滤推荐在如今个性化推荐系统中有着广泛的应用, 算法主要可以分为基于记忆^[1-3]和基于模型^[4-6]这两类.基于记忆的协同过滤是根据用户或者项目之间的相似性来进行预测推荐.基于模型的协同过滤与基于记忆的协同过滤不同点在于, 基于模型的算法是对已有数据, 即收集到的用户历史数据信息, 如商品评分、网页浏览记录等, 运用统计学以及机器学习方法进行分析学习, 挖掘用户的偏好和行为, 形成一个预测模型, 该模型能对新数据进行预测并向用户进行结果推荐.

推荐系统往往希望从用户那里获取更多个人信息, 以此来实现更优质的推荐服务, 但随之而来的隐私泄露问题也越来越显著^[7-10].用户在向推荐系统提交数据的时候不希望敏感信息泄露, 因此隐私保护成为推荐系统关注和研究的重点.

为实现隐私保护, 随机扰动技术(Randomized Perturbation Techniques, RPT)^[11]允许用户伪装自己的真实数据, 即在真实数据后加上一个伪随机数再发送给推荐系统.匿名方法也可实现保护隐私, 即允许一个用户拥有多个身份. $K$-匿名模型也应能够防止链接攻击所造成的隐私泄露问题而受到广泛关注.全同态加密技术(Fully Homomorphic Encryption, FHE)^[12]因为能实现数据在密文域上的加法和乘法运算也被引入到很多隐私保护方案中, 但传统的同态加密算法计算量大, 效率不高, 而且无法实现现在大众对计算结果的可验证这一要求.混淆电路技术^[13-14]能对计算结果提供"一次性"可验证计算, "一次性"验证计算是指在重用混淆电路进行多次计算时, 计算方可能重用上一次计算结果来伪造本次计算结果, 因此混淆电路只能提供一次性验证, 不能重用.混淆电路不能重用要求每次计算都要重构混淆电路, 这样会产生大量计算开销, 因此为实现对混淆电路的重用, 文献[15]使用了混淆电路结合全同态加密方法, 但方案中使用的同态加密方法同样使得方案效率较低.文献[16]中使用一种新的数据聚合方法替换了全同态加密, 在实现计算结果可验证的同时提高了系统效率.

本文利用脊回归^[17]对单个用户的大量数据进行回归计算, 使用Yao的混淆电路技术, 实现用户对云端计算出的推荐模型的正确性验证, 使用一种新的具有全同态性质的数据聚合方法AGG^[16], 来替换大多数已有方案中所使用的同态加密方法.本文结合混淆电路与AGG方法, 能在保证用户输入输出隐私前提下实现用户对云端计算出的推荐模型的正确性验证, 并且能减少用户和云端的资源开销.

1 网络架构

本文用到的符号说明如下: [$n$]表示集合{1, 2, $\cdots, n$}; $PPT$表示概率多项式时间; $\oplus $表示加法同态运算符; $GC$表示混淆电路; $G(a)$表示数据$a$的混淆电路输入形式; $OT$表示不经意传输; $CSP$表示加密服务提供者; $DO$表示数据拥有者; 标识$R$表示随机生成.

系统网络架构如图 1所示, 主要由数据拥有者($DO$)、云端、加密服务提供者($CSP$)3方组成.

$DO$是拥有一系列数据$x_i \in {\mathbb{R}}^d, y_i \in {\mathbb{R}}, i\in [n]$但计算资源受限的用户.通过使用本文中第3.1节的数据聚合算法AGG(包括AGG.KGen、AGG.Enc、AGG.Eval、AGG.Dec等4个算法)对数据进行处理, 然后把处理结果发送给云端. $CSP$负责为云端准备能实现回归计算的混淆电路.云端拥有无限计算资源, 与$CSP$交互后在混淆电路中对用户提交的数据执行回归计算, 并产生回归模型的密文形式$\theta _c $.用户通过验证算法对$\theta _c $解密并映射为最终回归模型$\theta $, 该模型能对新输入数据的结果进行预测.本文保证了数据输入数据隐私以及输出模型隐私.

2 预备知识 2.1 脊回归模型

脊回归是一种适用于共线性数据分析的有偏估计回归方法, 通过对最小二乘法的损失函数增加一个正则化项, 使得回归系数更可靠, 能对高维数据进行处理, 可应用于机器学习领域.

多元线性回归中, 令$\theta \in {\mathbb{R}}^d$, 给定一组输入数据$x_i \in {\mathbb{R}}^d, i\in \left[n \right]$, 一组输出数据$y_i \in {\mathbb{R}}, $ $i\in \left[n \right]$, 则训练一个函数$f_\theta (x)=\theta ^{\text{T}}x$, 使得$y_i \simeq f_\theta (x_i )$的过程称为回归.

求解函数$f_\theta (x)$中参数向量$\theta \in {\mathbb{R}}^d$的每个分量, 等价于最小化损失函数

$ \begin{equation} \label{eq1} F(\theta )=\sum\nolimits_{i=1}^n {(y_i -\theta ^{\text{T}}x_i )^2} +\lambda \left\| \theta \right\|_2^2, \end{equation} $

(1)

而最小化损失函数$F(\theta )$的过程称为脊回归.

对于线性回归模型$y=X\theta +\varepsilon $, 其中, $X=\left( {{\begin{array}{*{20}c} {x_{11} } \hfill&{x_{12} } \hfill&\cdots \hfill&{x_{1d} } \hfill \\ {x_{21} } \hfill&{x_{22} } \hfill&\cdots \hfill&{x_{2d} } \hfill \\ \vdots \hfill&\vdots \hfill&\vdots \hfill&\vdots \hfill \\ {x_{n1} } \hfill&{x_{n2} } \hfill&\cdots \hfill&{x_{nd} } \hfill \\ \end{array} }} \right)$是用户数据矩阵, $y=\left( {{\begin{array}{*{20}c} {y_1 } \hfill \\ {y_2 } \hfill \\ \vdots \hfill \\ {y_n } \hfill \\ \end{array} }} \right)$, $\theta =\left( {{\begin{array}{*{20}c} {\theta _1 } \hfill \\ {\theta _2 } \hfill \\ \vdots \hfill \\ {\theta _d } \hfill \\ \end{array} }} \right)$, $\varepsilon =\left( {{\begin{array}{*{20}c} {\varepsilon _1 } \hfill \\ {\varepsilon _2 } \hfill \\ \vdots \hfill \\ {\varepsilon _n } \hfill \\ \end{array} }} \right)$分别是因变量向量、参数向量、随机残差向量.求解公式(1)的最小值, 等价于求解方程组

$ \begin{equation} \label{eq2} A\theta =b, \end{equation} $

(2)

其中, $A=X^{\text{T}}X+\lambda I, \; b=X^{\text{T}}y$, $\lambda >0$, $I$是$d$阶单位矩阵.

2.2 混淆电路

混淆电路(Garbled Circuits)是Andrew Yao教授于1982年为解决安全多方计算问题而提出的一个概念.在两方计算中, Yao的混淆电路允许分别拥有隐私数据$a_1 $和$a_2 $的两方$A$和$B$, 在半可信环境下计算一个函数$y=f(a_1, a_2 )$, 同时又不泄露各自隐私数据$a_1 $和$a_2 $.

协议执行过程如下: $A$构造一个布尔电路$C$来实现函数$f$的计算功能, 然后把布尔电路的混淆形式即混淆电路$GC$以及入$a_1 $的混淆电路输入形式$G(a_1 )$一同发送给$B$.方案中有且只有电路的构造者$A$知道如何转化得到一个函数输入的混淆形式. $B$收到数据后和$A$进行不经意传输, 使得$A$在不知道关于函数输入$a_2 $任何信息的前提下, 为自己计算出$a_2 $的混淆电路输入形式$G(a_2 )$.然后$B$把$G(a_1 )$和$G(a_2 )$输入混淆电路, 计算出真实结果$f(a_1, a_2 )$的混淆形式并发送给$A$, $A$将混淆结果转换为实际结果$y$, 并将$y$共享给$B$.

2取1不经意传输协议:不经意传输协议是一个选择方$B$和发送方$A$之间的协议.该协议中, 发送方有两个长度为$\lambda $比特的信息$m_0, m_1 \in \{0, 1\}^\lambda $, 选择方有一个长度为1比特的信息$b\in \{0, 1\}$, 然后选择方和发送方经过一系列的交互之后, 选择方从发送方那里获得信息$m_b $, 而此时发送方不知道$b$的具体值, 选择方也不知道$m_{1-b} $的任何信息.

本文中, 混淆电路构造者即加密服务提供者, 推荐系统由云端充当.

加密服务提供者把外包计算函数$f$表示为混淆电路的具体步骤如下:如图 2(a), 首先为电路中的每根输入电线$w_x $分配两个随机密钥$w_x^0, w_x^1 \in \{0, 1\}^\lambda $, $\lambda $是安全参数, $w_x^0 $表示电线$w_x $的输入比特值$b_x =0$, $w_x^1 $表示电线$w_x $的输入比特值$b_x =1$; 然后构造电路中每个门的混淆形式, 如图 2(b)所示, 假设电路中门$g$的输入电线为$w_i $和$w_j $, 输出电线为$w_k $, 则为门$g$计算4个密文, 具体是

$ \begin{align} r_{00} =E_{w_i^0 } (E_{w_j^0 } (w_k^{g^{(0, 0)}} )), \quad r_{01} =E_{w_i^0 } (E_{w_j^1 } (w_k^{g^{(0, 1)}} )), \end{align} $

(3)

$ \begin{align} r_{10} =E_{w_i^1 } (E_{w_j^0 } (w_k^{g^{(1, 0)}} )), \quad r_{11} =E_{w_i^1 } (E_{w_j^1 } (w_k^{g^{(1, 1)}} )), \end{align} $

(4)

其中$E$代表混淆电路中的对称加密算法.

因为每个门的4个密文均采用随机排列, 即第一个密文$r_{00} $并不对应门$g$输入的比特值(0, 0), 这样就很好地隐藏了电路的结构.这4个随机排列的密文的集合就称作对电路中门$g$的混淆.

云端接收到数据拥有者发送过来的密文数据后, 和加密服务提供者进行一系列交互, 获得混淆电路以及密文数据得混淆电路输入形式.对于电路中的一个门, 比如$g_1 $, 云端可以用$g_1 $的两个输入电线上获得的两个随机秘钥唯一解密门$g_1 $4个密文中的一个, 其他的3个密文无法解密.而解密出的这个值即为门$g_1 $的输出电线所对应的随机秘钥, 也即门$g_1 $的输出电线所连接的下一个门$g_2 $的输入电线上的随机密钥, 可直接用于门$g_2 $的4个随机排列密文的解密.云端按照这种方式对电路中的门依次逐门向后计算, 直到获得电路最终输出的随机秘钥, 这个过程即实现了公式(2)的求解.然后把输出结果$\theta _c $解密后映射成真实输出结果$\theta $, 即外包函数$f$的最终计算结果.

2.3 大整数分解难题假设

大整数分解问题, 即每个正整数$N$都可以唯一表示成它的素因子的乘积, 即

$ \begin{align} N=p_1^{\alpha _1 } p_2^{\alpha _2 } \cdot \cdot \cdot p_s^{\alpha _s }, \quad \alpha _{\text{i}} >0, \quad i=1, \cdots, s, \end{align} $

(5)

其中$p_i $是$N$的素因子, $p_i <p_j (i<j)$.

给定2个大素数$p$和$q$, 容易求出它们的乘积$N$, 但若在不知道$\phi (N)=(p-1)(q-1)$的情况下, 要找出$N$的素因子$p$和$q$使得$N=pq$, 在多项式时间($PPT$)内是不可行的.即给定$N=pq$, 其中$p$, $q$是位数为$\lambda $的大素数, 即$\left| {p} \right|=\left| q \right|=\lambda $, 对于任意概率多项式时间($PPT$)的敌手$A$的优势${\text{Adv}}_A^{\text{IFP}} $, 存在一个可忽略的函数negl$(\lambda )$满足

$ \begin{equation} {\text{Adv}}_A^{\text{IFP}} ={\text{Prob}}\left[{s\leftarrow A(N)\wedge (s\in \{p, q\})} \right]\le {\text{negl}}(\lambda ). \end{equation} $

(6)

本文中第3.1节AGG算法的安全性是基于大整数分解难题假设的.由于云端只知道公开的大整数$N$, 很难从大整数$N$分解出$p$和$q$, 云端不知道$p$和$q$也就无法知晓明文的相关信息, 所以也就保证了方案的安全性.

2.4 可验证外包计算

可验证外包计算由以下4个算法组成(KeyGen, ProbGen, Compute, Verify).

(1) KeyGen$(f, \lambda )\to (PK, SK)$:秘钥生成算法, 输入安全参数$\lambda $和函数$f$, 由密钥生成算法随机产生公私钥对($PK$, $SK$), 公钥$PK$由云端执行计算时使用, 私钥$SK$由$DO$保存.

(2) ProbGen($SK, x)\to (\sigma _x, \tau _x )$:输入私钥$SK$以及函数$f$的输入$x$, 用私钥$SK$将$x$转化为$\sigma _x $并公开给云端进行外包计算, $\tau _x $是验证秘钥, 由$DO$保存.

(3) Compute($PK, \sigma _x )\to \sigma _y $:给定$PK$以及输入$\sigma _x $, 云端计算$\sigma _y =f(\sigma _x )$, 计算结果$\sigma _y $是函数真实输出$y$的密文形式.

(4) Verify$(SK, \tau _x, \sigma _y )\to y\cup \bot $:利用私钥$SK$以及验证秘钥$\tau _x $, 对云端计算结果$\sigma _y $进行验证, 若验证通过则输出最终结果$y$, 反之则输出终止符$\bot $.

2.5 安全模型

可验证外包计算方案($VC$)应该保证计算的正确性以及安全性.

定义1(正确性)  对于任意的外包函数$f$, 秘钥生成算法产生相应的公私钥对$(PK, SK)\leftarrow {\text{KeyGen}}(f, \lambda )$, $\forall x\in {\text{domain}}(f)$, 若执行$(\sigma _x, \tau _x )\leftarrow {\text{ProbGen}}(SK, x)$和$\sigma _y \leftarrow {\text{Compute}}(PK, \sigma _x )$, 均有$y=f(x)\leftarrow {\text{Verify}}(SK, \tau _x, \sigma _y )$成立, 则可验证外包计算方案($VC$)是正确的.

若恶意的云端不能让验证算法Verify接受一个错误的结果, 即给出外包函数$f$以及函数的输入$x$, 恶意云端无法让验证算法Verify输出一个结果$\hat {y}$, 满足$\hat {y}\ne f(x)$, 则可以说可验证外包计算方案是安全的.

具体的安全性博弈${\text{Game}}_{A, VC}^{\text{Verif}} (f, \lambda )$定义是

$ (PK, SK)\buildrel R \over \longleftarrow {\text{KeyGen}}(f, \lambda ), $

对于$i=1, \cdots, q, $

$ \begin{align*} x_i &\leftarrow A(PK, x_1, \sigma _1, \cdots, x_i, \sigma _i ), \\ (\sigma _i, \tau _i )&\leftarrow {\text{ProbGen}}(SK, x_i ), \\ (i, \hat {\sigma }_y )&\leftarrow A(PK, x_1, \sigma _1, \cdots, x_q , \sigma _q ), \\ \hat {y}&\leftarrow {\text{Verify}}(SK, \tau _i, \hat {\sigma }_y ), \end{align*} $

如果$\hat {y}\ne \bot $, 并且$\hat {y}\ne f(x_i )$, 则输出1, 否则输出0.上述中$\lambda $是安全参数, $q={\text{poly}}(\lambda )$表示敌手$A$可以对挑战者$C$的随机预言机进行询问的次数, poly$(\cdot )$是一个多项式.

定义2(安全性)  若对于任意概率多项式时间($PPT$)的敌手$A$的优势Adv$_{A, VC}^{\text{Verif}} (f, \lambda )$, 存在一个可忽略的函数negl$(\lambda )$满足

$ \begin{equation} \label{eq5} {\text{Adv}}_{A, VC}^{\text{Verif}} (f, \lambda )={\text{Prob}}\left[{{\text{Game}}_{A, VC}^{\text{Verif}} (f, \lambda )=1} \right]\le {\text{negl}}(\lambda ), \end{equation} $

(7)

即让验证算法Verify接受一个错误的结果的概率是可忽略的, 此时则可说明可验证外包计算方案是安全的.式(7)中$\lambda $是安全参数.

可验证外包计算使得数据能够被正确计算, 但在云计算中, 数据拥有者的输入输出隐私也需要得到保护.在这里输入数据的隐私由Game$_{A, VC}^{\text{Priv}} (f, \lambda )$来定义, 具体过程为

$ \begin{align*} (PK, SK)&\buildrel R \over \leftarrow {\text{KeyGen}}(f, \lambda ), \\ (x_0, x_1 )&\leftarrow A^{O^{{\text{ProbGen}}(SK, \cdot )}}(PK), \\ (\sigma _0, \tau _0 )&\leftarrow {\text{ProbGen}}(SK, x_0 ), \\ (\sigma _1, \tau _1 )&\leftarrow {\text{ProbGen}}(SK, x_1 ), \\ b&\buildrel R \over \leftarrow \{0, 1\}, \\ {b}'&\leftarrow A^{O^{{\text{ProbGen}}(SK, \cdot )}}(PK, x_0, x_1 , \sigma _b ), \end{align*} $

其中$O^{{\text{ProbGen}}(SK, \cdot )}$是随机预言机.

如果${b}'=b$, 输出1, 否则输出0.输出数据的隐私定义与输入数据隐私定义相同, 此处不再赘述.

定义3(隐私性)  若对于任意概率多项式时间($PPT$)的敌手$A$的优势Adv$_{A, VC}^{\text{Priv}} (f, \lambda )$, 存在一个可忽略的函数negl$(\lambda )$满足

$ \begin{equation} \label{eq6}{\text{Adv}}_{A, VC}^{\text{Priv}} (f, \lambda )=\left| {{\text{Prob}}\left[{{\text{Game}}_{A, VC}^{\text{Priv}} (f, \lambda )=1} \right]-\frac{1}{2}} \right|\le {\text{negl}}(\lambda ), \end{equation} $

(8)

则说明可验证外包计算方案是隐私保护的.式(8)中$\lambda $是安全参数.

3 方案构造

如图 3所示, 系统主要由数据拥有者($DO$)、加密服务提供者($CSP$)、云端3方组成. $x_i \in {\mathbb{R}}^d, y_i \in {\mathbb{R}}, i\in [n]$表示数据拥有者的第$T_i $条数据.数据拥有者想要训练一个模型$\theta $使得$y_i \simeq f_\theta (x_i )=\theta ^{\text{T}}x_i $, 以此实现对新数据$x$所对应的结果$y$的预测.首先数据拥有者加密处理自身数据$(x_i, y_i )$后发送给云端, 然后云端与加密服务提供者进行一系列交互并执行回归算法, 最终计算结果为$\theta $的密文形式$\theta _c $, 数据拥有者验证并解密后获得真实结果$\theta $.

方案具体过程如下.

首先, 云端向$CSP$发送一个说明文档, 请求构造一个实现外包计算函数$f$的混淆电路.说明文档包含数据$x_i $的维度$d$、$x_i $和$y_i $的取值范围, 以及用来表示一个数的整数和小数部分的比特数等信息. $CSP$构造相应的混淆电路发送给云端.

其次, 对于第$T_i $条数据$(x_i, y_i )$, $DO$使用第3.1节介绍的数据加密方法AGG对其进行计算, 得出$c_i ={\text{AGG}}(A_i ;b_i )$, 其中$A_i =x_i x_i^{\text{T}}, b_i =x_i y_i $. $DO$把$c_i $发送给云端, 云端聚合所有$DO$发送过来的密文, 然后并把$\hat {c}={\text{AGG}}(A;b)$发送给$CSP$, 其中$A=\sum\nolimits_{i=1}^n {A_i } +\lambda I, b=\sum\nolimits_{i=1}^n {b_i } $. $CSP$将$\hat {c}$的混淆电路输入形式$G(\hat {c})$发送给云端.

云端输入$G(\hat {c})$到$GC$中, 按照第2.2节$GC$的计算流程, 在$GC$中求解密文形式的公式(2), 即求解$\theta _c =A_c^{-1} b_c $, 其中$A_c^{-1}$和$b_c $分别为$A^{-1}$和$b$的密文形式.最终得出$\theta $的密文形式$\theta _c $. $DO$验证并解密$\theta _c $得到最终所需模型$\theta $.

3.1 数据聚合算法AGG

隐私保护数据聚合算法AGG是一种对称同态加密方法, 支持密文域上的加法和乘法运算, 可用于替换公钥全同态加密算法, 主要应用在用户对数据的加密处理以及云端计算混淆电路过程中.第3.2节可验证外包计算方案中有可验证外包计算算法调用AGG算法的具体步骤. AGG主要由AGG.KGen, AGG.Enc, AGG.Eval, AGG.Dec等4个算法组成.

(1) AGG.KGen:输入安全参数$\lambda $, 输出2个哈希函数$H_0, H_1 :\{0, 1\}^\ast \to \{0, 1\}^{2\lambda }$, 令公开参数$PP=(H_0, H_1 )$.

(2) AGG.Enc:数据拥有者随机选择2个位数为$\lambda $比特的大素数$p$和$q$作为隐私数据, 即$\left|p\right|=\left| q \right|=\lambda $, 计算大整数$N=pq$并公开$N$.这里选定的大素数$p$和$q$将用于AGG.Dec算法中利用中国剩余定理对云端返回的计算结果进行解密的步骤中.云端只知道公开的大整数$N$, 很难对大整数$N$进行分解求解出$p$和$q$, 所以也就能保证方案的安全性.

对于第$T_i $条数据$({A}_i {;b}_i )$, 用$\overrightarrow{\mathit{\boldsymbol{m}}}=(m_1, \cdots, m_{d^2+d} )^{\text{T}}$表示$({A}_i {;b}_i )$中的数据.对于$\overrightarrow{\mathit{\boldsymbol{m}}}$中的每个分量$m_{i\in [d^2+d]} $, 数据拥有者随机选择$U_i^{\text{add}}, U_i^{\text{mul}} \in _R { \mathbb{Z}}_N $并对数据进行如下处理.

$ \begin{equation} \label{eq7} m_{i, p} \equiv m_i \bmod p, \quad m_{i, q} \equiv m_i \bmod q, \end{equation} $

(9)

其中,

$ \begin{equation} \label{eq8} 1\equiv q^{-1}q\bmod p, \quad 1\equiv p^{-1}p\bmod q. \end{equation} $

(10)

数据拥有者计算密文分量

$ c_{1, i} =q^{-1}qm_{i, p}^p +p^{-1}pm_{i, q}^q +U_i^{\text{add}} \bmod N, $

(11a)

$ c_{2, i} =(q^{-1}qm_{i, p}^p +p^{-1}pm_{i, q}^q )U_i^{\text{mul}} \bmod N. $

(11b)

当对$\overrightarrow{ \mathit{\boldsymbol{m}}}=(m_1, \cdots, m_{d^2+d} )^{\text{T}}$中的每个分量$m_i $均计算出密文之后, 数据拥有者计算并公开

$ \begin{equation} U_T^{\text{add}} =\sum\limits_{i=1}^{d^2+d} {U_i^{\text{add}} } \bmod N, \quad U_T^{\text{mul}} =\sum\limits_{i=1}^{d^2+d} {U_i^{\text{mul}} } \bmod N, \end{equation} $

(12)

然后计算密文

$ \begin{align*} c_i =(c_{1, i}, c_{2, i}, c_{\text{ram}}^{\text{add}}, c_{\text{ram}}^{\text{mul}} ), \end{align*} $

其中,

$ \begin{align*} c_{\text{ram}}^{\text{add}} =H_0 (p\parallel U_T^{\text{add}} ), \quad c_{\text{ram}}^{\text{mul}} =H_0 (p\parallel U_T^{\text{mul}}). \end{align*} $

(3) AGG.Eval:云端收集完$T_n $条数据后, 与加密服务提供者进行一定的交互之后, 在密文上计算$A\theta =b$.计算结果$\theta _c =A_c^{-1} b_c $为最终计算模型$\theta $的密文形式.计算$\theta _c $过程中所需要的加法和乘法计算操作为

$ c_T^{\text{add}} =\sum\limits_{i=1}^{d^2+d} {c_{1, i} } -U_T^{\text{add}} \mod N \notag\\ \ \ \ \ =q^{-1}q\sum\limits_{i=1}^{d^2+d} {m_{i, p}^p } +p^{-1}p\sum\limits_{i=1}^{d^2+d} {m_{i, q}^q }\!\!\!\!\!\mod N \notag\\ \ \ \ \ =q^{-1}q\Big(\sum\limits_{i=1}^{d^2+d} {m_{i, p}}\Big)^p +p^{-1}p\Big(\sum\limits_{i=1}^{d^2+d} {m_{i, q}}\Big)^q\!\!\!\!\!\mod N, $

(13a)

$ c_T^{\text{mul}} =\mathop \prod \limits_{i=1}^{d^2+d} c_{2, i} (U_T^{\text{mul}} )^{-1}\bmod N \notag\\ \ \ \ \ =\mathop \prod \limits_{i=1}^{d^2+d} (q^{-1}qm_{i, p}^p +p^{-1}pm_{i, q}^q )\!\!\!\!\!\mod N\notag \\ \ \ \ \ =q^{-1}q\Big(\mathop \prod \limits_{i=1}^{d^2+d} m_{i, p} \Big)^p +p^{-1}p\Big(\mathop \prod \limits_{i=1}^{d^2+d} m_{i, q} \Big)^q\!\!\!\!\!\mod N, $

(13b)

$ c_3^\theta =H_1 (\theta _c \parallel c_{\text{ram}}^{\text{add}} \parallel c_{\text{ram}}^{\text{mul}}). $

(13c)

同时把计算结果$c_A =(\theta _{\text{c}}, c_3^\theta )$发送给数据拥有者, 其中$\theta _c =A_c^{-1} b_c $, $A_c^{-1}$和$b_c $分别为$A^{-1}$和$b$的密文形式.

(4) AGG.Dec:数据拥有者接收到云端发送过来的数据后, 验证

$ \begin{align*} c_{\text{ram}}^{\text{add}} =\, &H_0 (p\parallel U_T^{\text{add}} ), \\ c_{\text{ram}}^{\text{mul}} =\, &H_0 (p\parallel U_T^{\text{mul}} ), \\ c_3^\theta =\, &H_1 (\theta _c \parallel c_{\text{ram}}^{\text{add}} \parallel c_{\text{ram}}^{\text{mul}} ) \end{align*} $

是否成立, 若不成立则输出终止符$\perp$, 若成立则说明计算保证了数据完整性, 并进行后续解密计算

$ \theta _c \bmod p=\theta _{c, p} \bmod p, $

(14a)

$ \theta _c \bmod q=\theta _{c, q} \bmod q. $

(14b)

$\theta _c $是由一系列$c_T^{\text{add}}, c_T^{\text{mul}} $计算求得, 对$c_T^{\text{add}}, c_T^{\text{mul}} $进行单独求解时满足

$ c_T^{\text{add}} \!\!\!\!\!\mod p=q^{-1}q\Big(\sum\limits_{i=1}^{d^2+d} {m_{i, p}} \Big)^p\!\!\!\!\!\mod p=\sum\limits_{i=1}^{d^2+d} {m_{i, p}} \!\!\!\!\!\mod p, $

(15a)

$ c_T^{\text{add}} \!\!\!\!\!\mod q=p^{-1}p\Big(\sum\limits_{i=1}^{d^2+d} {m_{i, q}} \Big)^q\!\!\!\!\!\mod q=\sum\limits_{i=1}^{d^2+d} {m_{i, q} } \!\!\!\!\!\mod q, $

(15b)

$ c_T^{\text{mul}} \!\!\!\!\!\mod p=q^{-1}q\Big(\mathop \prod \limits_{i=1}^{d^2+d} m_{i, p} \Big)^p\!\!\!\!\!\mod p=\mathop \prod \limits_{i=1}^{d^2+d} m_{i, p} \!\!\!\!\!\mod p, $

(15c)

$ c_T^{\text{mul}} \!\!\!\!\!\mod q=p^{-1}p\Big(\mathop \prod \limits_{i=1}^{d^2+d} m_{i, q} \Big)^q\!\!\!\!\!\mod q=\mathop \prod \limits_{i=1}^{d^2+d} m_{i, q} \!\!\!\!\!\mod q. $

(15d)

公式(15)中, 用户对公式(13)中云端计算出的信息进行模$p$和模$q$时能实现对密文的解密, 所以不难看出AGG算法具有加法同态性质和乘法同态性质, 实现了数据在密文形式上的计算.所以用户可以直接对云端计算结果$\theta _c $进行模$p$和模$q$解密处理, 如公式(14), 然后可利用中国剩余定理对公式(14)进行求解计算, 恢复出明文信息$\theta _c'$, 即

$ \begin{equation} \theta_c'=qM_p'\theta _{c, p}+pM_q' \theta _{c, q} \bmod N, \end{equation} $

(16)

其中, $M_p', M_q'$的定义是

$ M_p' q=1\bmod p, $

(17a)

$ M_q' p=1\bmod q. $

(17b)

最后可利用可验证外包计算方案中的$SK$将$\theta _c '$映射成最终结果$\theta $.

3.2 可验证外包计算方案

可验证外包计算方案调用了第3.1节介绍的数据加密方法AGG, 由以下4个算法组成(KeyGen, ProbGen, Compute, Verify).

(1) KeyGen$(f, \lambda )\to (PK, SK)$:按照第2.2节的方法, 加密服务提供者把外包计算函数$f$构造成一个混淆电路, 为电路中的每根电线$w_x $分配2个随机密钥$w_x^0, \;w_x^1 \in \{0, 1\}^\lambda $, $w_x^0 $表示电线$w_x $的比特值$b_x =0$, $w_x^1 $表示电线$w_x $的比特值`$b_x =1$, $\lambda $是安全参数.然后按照第2.2节的方法为每个门$g$计算4个密文$r_{00}, r_{01}, r_{10}, r_{11} $, 则这4个密文的集合即为$PK$, $PK=\cup _g (r_{00}, r_{01}, r_{10}, r_{11} )$, 而私钥$SK$则是为每条电线选择的随机秘钥, $SK=\cup _i (w_i^0, w_i^1 )$.

(2) ProbGen$(SK, x)\to (\sigma _x, \tau _x )$:数据拥有者调用AGG.KGen算法生成公共参数$PP=(H_0, H_1 )$, 并生成隐私数据$p$, $q$.令$\sigma _x ={\text{AGG.Enc}}(PP, \cup w_i )$, 其中$\cup w_i $代表输入$x$的每个比特值所对应得随机秘钥的集合. $\tau _x =\{p, q\}$.

(3) Compute$(PK, \sigma _x )\to \sigma _y $:云端首先计算AGG.Enc$(PP, r_i )$, 并根据加密服务提供者构造的电路计算$D_w (D_{w'} (r))$, 其中$D$是混淆电路中加密算法$E$所对应的解密算法, $w, {w}', r$是电路的输入.然后云端在密文上反复计算AGG.Eval$(GC, {\text{AGG.Enc}}(PP, w_i ), r_i )$, 即等价于在混淆电路中的逐门向后计算.最终的计算结果为$\sigma _y ={\text{AGG.Enc}}(PP, w_z )$, 其中$w_z $代表函数输出结果的二进制表示形式.

(4) Verify$(SK, \tau _x, \sigma _y )\to y\cup \bot $:数据拥有者收到云端发送过来结果$\sigma _y $后, 调用AGG.Dec算法对$\sigma _y ={\text{AGG.Enc}}(PP, w_z )$进行解密得到$w_z $, 使用$SK$把电路输出电线上的值$w_z $映射解密成真实结果$\theta $.若解密或者映射失败, 则输出终止符$\bot $.

如文献[15]中介绍, 电路中使用的对称加密算法$E$有一个有效可验证的范围, 即给定加密秘钥$k$以及密文$r$, 存在一个机制$M$, 可以有效地确定密文$r$是否落在用秘钥$k$加密的密文范围之内, 若$r\in \mbox{Range}_\lambda (k)$, 则$M(k, r)=1$.而每个电路对应的4个密文中只有一个满足$M(k, r)=1$, 即只有一个密文能被正确解密作为下一个门电线上的输入密钥.

本文方案中, 需要把第3.1节数据加密算法的加法以及乘法同态性质应用到机制$M$上, 然后云端计算$c_i ={\text{AGG.Enc}}(PP, M(k, r_i ))$, 因为只有一个$r$满足$M(k, r)=1$, 所以只有一个$c_i $对应正确的$r$.之后云端用第3.1节数据加密算法计算$D_i ={\text{AGG.Enc}}(PP, D_k (r_i ))$.最后, 云端计算$c_g ={\text{AGGEnc}}(PP, \sum\nolimits_i {M(k, r_i )D_k (r_i )} )$作为门$g$输出电线上正确秘钥的密文形式.

4 安全性分析

Yao的混淆电路方案是可证明安全的^[16], 在这里对本文第3.1节数据加密方法的安全性进行分析.

输入数据隐私性:数据拥有者加密处理自身数据为

$ \begin{align*} c_{1, i} =q^{-1}qm_{i, p}^p +p^{-1}pm_{i, q}^q +U_i^{\text{add}} \bmod N, \quad c_{2, i} =(q^{-1}qm_{i, p}^p +p^{-1}pm_{i, q}^q )U_i^{\text{mul}} \bmod N. \end{align*} $

密文$c_{1, i}, c_{2, i} $中的$m_{i, p}, m_{i, q} $分别是数据$m_i$在模$p$, $q$的作用下产生的, 即数据$m_i $经过了一次盲化处理, 其中$p$和$q$是大整数$N$的素因子, 且均由数据拥有者秘密保存.同时为了防止数据在计算过程中被恢复, 随机选择$U_i^{\text{add}}, U_i^{\text{mul}} $对密文进行二次盲化.敌手能正确猜测出数据$m_i $的概率等价于敌手知道$c_i =(c_{1, i}, c_{2, i}, c_{\text{ram}}^{\text{add}}, c_{\text{ram}}^{\text{mul}} )$的概率.

输出数据隐私性:假设有一个敌手$A$有不可忽略的优势$\varepsilon ^{', {\text{ploy}}(\lambda )}$破解第3.1节的加密方案, 其中ploy$(\lambda )$表示敌手可以向预言机进行询问的次数, $\lambda $表示安全参数, 则存在一个模拟器$B$能调用敌手$A$的能力以概率$\varepsilon \ge \varepsilon ^{', {\text{ploy}}(\lambda )}-\frac{{\text{ploy}}(\lambda )}{2^{\lambda -1}}$破解大整数分解难题, 即能以不可忽略的概率$\varepsilon $对大整数$N$进行因式分解求解出秘密信息$p$, $q$.而实际上不存在这样的模拟器$B$能以不可忽略的优势破解大整数分解难题, 所以加密方案是安全的.

5 效率分析

本文中AGG算法使用的是对称同态映射, 即加密和解密使用的都是相同的密钥$p$和$q$, 对数据$(A_i ;b_i )$只需要乘法和加法以及模$N$运算, 没有涉及对任何一个数据分量$m_i $的公钥加密运算.而文献[17]中的方案, 数据拥有者使用公钥加法同态加密算法Paillier^[18]对数据进行预处理$c_i =E_{PK_{\text{CSP}} } (A_i ;b_i )$, 需要对$(A_i ;b_i )$中的每个数据分量$m_i $执行一次公钥加密运算$g^{m_i }r^N\bmod N^2$, 即在$Z_{N^2} $上执行指数级运算, 效率自然会比AGG对称同态加密方法低.与此同时, 本文中云端执行的混淆电路计算也基于AGG对称同态加密算法基础之上, 比基于混淆电路和公钥全同态加密的隐私保护方案效率要高.所以假如本文使用混淆电路结合全同态加密方法, 则效率不会有使用混淆电路结合AGG时效率高.

6 结论

本文提出了一个实现高效可验证的隐私保护推荐系统的3方模型, 即数据拥有者、加密服务提供者、云端的3方模型.在保护数据隐私的同时实现用户对云端计算出的推荐模型的正确性验证, 并且利用一个新的数据处理方法AGG代替全同态加密, 提高了系统效率.

本文方案目前是针对单个用户数据进行计算, 如何同时对多用户数据进行计算是今后要研究的课题之一.