0 引言

云计算(Cloud Computing)^[1]概念的提出，将信息产业的发展带入了快车道。云服务在给用户提供海量存储服务和强大计算能力的同时，也推动了经济的发展，但云计算伴生的安全问题也日益凸显。Kaufman^[2]指出，云的安全问题被认为是云服务实际应用面临诸多困难中最大的挑战，也是云服务亟待解决的最大难题。

如果用户以明文形式将敏感数据保存到云服务器，由于云端可能会复制甚至篡改这些信息，而用户根本无法得知云端的非授权行为，从而造成不可估计的损失，所以云是不能被无条件信任的。为了防止敏感数据的恶意泄露和非法访问，用户可以以密文形式对数据进行外包。

传统的云计算加解密模型无法实现对计算结果的细粒度访问控制。Shamir^[3]在1984年提出了基于身份的加密(Identity-Based Encryption，IBE)，用户的公钥由与其身份相关的唯一标识生成，访问时服务器端不需要再查询用户的公钥证书。基于属性的加密(Attribute-Based Encryption，ABE)由Sahai等^[4]提出，可以看作是对IBE的推广，在这种加密体制中，用户的密钥和密文与属性关联起来，只有属性满足访问控制策略时，用户才能合法解密，从而实现了对密文的细粒度访问控制。基于属性的加密体制具有良好的特性，引起了国内外密码学家的高度重视，近年来涌现出了大量相关研究成果^[5-8]，同时它也被广泛运用到云计算安全算法的设计^[9-11]当中，成为云计算中数据保护的重要工具。

本文基于由Boneh、Goh和Nissim提出的经典的类同态BGN^[12]方案，利用文献[8]提出的CP-ABE(Ciphertext-Policy Attribute-Based Encryption)型密文解密外包设计，构造了一个基于属性的BGN型密文解密外包方案。在本文的构造中，部分密文的解密过程被外包到云上进行，大大降低了用户的计算量；用户的私钥与属性相关联，访问控制策略被嵌入到密文当中，当且仅当用户属性满足密文策略时才能正常解密，从而实现了对云计算结果的访问控制。同时，该方案支持对密文进行任意次加法同态操作和一次乘法同态操作。

1 预备知识 1.1 双线性映射

G和G_T是两个阶为p的乘法循环群，g为群G的生成元，则双线性映射e:G×G→G_T满足下列性质：

1) 双线性性：对任意u, k∈G和a, b∈Z_p，都有e(u^a, k^b)=e(u, k)^ab。

2) 非退化性：存在u, k∈G，使得e(u, k)≠1。

3) 可计算性：存在有效算法使得对任意u, k∈G，都可以计算出e(u, k)。

1.2 访问结构

假设{P₁, P₂, …, P_n}是秘密共享的参与者集合，定义P=2^{{P₁, P₂, …, P_n}}，访问结构Γ是{P₁, P₂, …, P_n}的非空子集，即Γ⊆P\{∅}。访问结构的单调性定义如下：如果A∈Γ且A⊆B，则B∈Γ。同时，称该子集为一个授权子集，不能重构出共享秘密的子集为非授权子集。

1.3 线性秘密共享机制矩阵访问结构

一个定义在秘密共享参与者集合P上的线性秘密共享机制(Linear Secret Sharing Scheme，LSSS)^[13]Π是指：

1) 所有参与者的份额组成一个Z_p上的向量。

2) 存在一个l×n的矩阵M，它是一个关于Π的共享生成矩阵。M的第i行对应实体ρ(i)，其中i=1, 2, …, l，ρ是从{1, 2, …, l}到P的映射函数。随机选择列向量v=(s, y₂, y₃, …, y_n)∈Z_pⁿ，其中s是共享秘密，那么M·v就是利用Π得到的关于s的l个共享组成的向量，并且(M·v)_i属于实体ρ(i)。

线性重构性：假设Π是一个关于访问结构Γ的LSSS，令授权集S∈Γ，定义I={i:ρ(i)∈S}且I⊆{1, 2, …, l}，那么就一定会存在这样的一个常数集{w_i∈Z_p}_i∈I，使得$\sum\limits_{i \in I} {{w_i}{M_i} = } \left( {1,0, \cdots ,0} \right)$成立，从而有$\sum\limits_{i \in I} {{w_i}{M_i}v = } s$；而对于非授权集，则不存在这样的{w_i∈Z_p}_i∈I。

1.4 BGN方案

BGN方案^[12]能够支持任意次加法同态操作，在双线性映射下又能支持一次乘法同态操作，是同态加密概念^[14]被提出后的首个类同态加密方案，2010年Gentry等^[15]又在格上实现了BGN方案。方案描述如下：

密钥产生算法：输入安全参数τ∈Z⁺，运行算法G(τ)得到元组(q₁, q₂, G, G₁, e)，令n=q₁q₂，随机选择两个生成元$k,u\xleftarrow{R}G$，并令h=u^q₂，那么h就是群G的q₁阶子群的随机生成元。系统公钥PK=(n, G, G₁, e, k, h)，私钥SK=q₁。

加密算法：明文空间为{0, 1, …, T}(T＜q₂)，随机选择$r\xleftarrow{R}\left\{ 0,1,\cdots n-1 \right\}$，输入明文消息m和公钥PK，输出密文C=k^mh^r∈G。

解密算法：输入密文C及私钥SK，计算C^q₁=(k^mh^r)^q₁=(k^q₁)^m，利用Pollard's lambda算法^[16]解密以k^q₁为底C^q₁的离散对数即可恢复出明文消息m；同时，解密算法的时间复杂度为$O\left( \sqrt{T} \right)$。

BGN方案的同态性质分析：

1) 加法同态：

$C = {C_1}{C_2}{h^r} = {k^{{m_1}}}{h^{{r_1}}} \cdot {k^{{m_2}}}{h^{{r_2}}} \cdot {h^r} = {k^{{m_1} + {m_2}}}{h^{{r_1} + {r_2} + r}} \in G$

(2) 乘法同态：

令k₁=e(k, k)，h₁=e(k, h)，则k₁的阶为n，h₁的阶为q₁，并且一定有β∈Z使得h=k^βq₂，计算

$\begin{array}{l} C = e\left( {{C_1},{C_2}} \right)h_1^r = e\left( {{k^{{m_1}}}{h^{{r_1}}},{k^{{m_2}}}{h^{{r_2}}}} \right)h_1^r = \\ \quad \quad k_1^{{m_1}{m_2}}h_1^{{m_1}{r_2} + {m_2}{r_1} + \beta {q_2}{r_1}{r_2} + r} = k_1^{{m_1}{m_2}}h_1^{\tilde r} \in {G_1} \end{array}$

其中$\tilde r = {m_1}{r_2} + {m_2}{r_1} + \beta {q_2}{r_1}{r_2} + r$在Z_n上均匀分布。经过双线性映射后得到新的密文为C∈G₁，由于不存在有效算法使得e:G₁×G₁→G成立，所以这个方案只允许进行一次同态乘法运算。

1.5 基于属性的密文解密外包模型

基于属性的密文解密外包方案由Green，Hohenberger和Waters ^[8]提出。该方案针对传统的基于属性的加密方案增加了一个转换算法，将解密过程部分外包给第三方服务器，解密者只需对第三方服务器反馈的部分密文进行少量简单的运算即可以获知明文。这种外包设计思想充分利用了当下云计算强大的计算能力，大大提高了解密效率。传统的基于属性的加密模型和基于属性的密文解密外包模型分别如图 1所示。

在图 1(a)所示的传统的基于属性的加密模型中，解密者必须全部下载ABE密文才能进行解密运算，其存储开销与计算开销显然是十分巨大的。针对上述缺点，文献[8]设计了图 1(b)所示的外包模型，将ABE密文外包给云等第三方服务器，云再将计算得到的部分密文发送给解密者，解密者只需要下载少量数据并进行简单运算即可得出明文，这一过程的存储开销与计算开销相比传统模型将会减小很多。具体而言，针对经过加密存放在云服务器的原始ABE密文，解密者向云服务器发送一个转换密钥TK，云服务器利用转换密钥对原始ABE密文进行转换运算，得到部分解密的ABE密文，反馈给解密者，解密者只需利用私钥进行一次指数运算即可获知明文消息。

2 基于属性的BGN型密文解密外包方案

本章提出一种基于属性的BGN型密文解密外包方案，通过将BGN方案与基于属性的密文解密外包思想相结合，构造了能够实现对云计算结果访问控制的外包方案。方案由以下五个子算法组成：

初始化算法：输入安全参数λ和属性空间U，其中U={0, 1}^*，运行算法G(λ)生成元组(q₁, q₂, G, G₁, e)，并且G, G₁都是阶为n=q₁q₂的群，e:G×G→G₁是双线性映射。随机选择生成元$k,u\xleftarrow{R}G$，并令h=u^q₂，显然h是群G的q₁阶子群生成元。再随机选择阶为p的素数阶群G′和G_T^′，令g为群G′的一个生成元，e′:G′×G′→G_T^′是双线性映射。随机选择由{0, 1}^*映射到G′的哈希函数F和由G_T^′映射到(0, 1) 的哈希函数H。另外，随机选择系数α，a∈Z_p，则算法的主密钥MSK=(g^α, PK)，输出公钥：

$PK = \left( {n,g,k,h,e,e'{{\left( {g,g} \right)}^\alpha },{g^a},F,H,G,{G_1}} \right)$

加密算法：输入公钥PK，对明文消息m进行加密。访问结构是LSSS访问结构(M, ρ)，其中M是一个l×n的矩阵，ρ是与M行元素属性相关的函数。加密时随机选择向量v=(s, y₂, y₂, …, y_n)∈Z_pⁿ，秘密共享参量为s。计算λ_i=M_i·v，其中i=1, 2, …, n，M_i是M的第i行元素所组成的向量。算法再随机选择R, r₂, …, r_l∈Z_p，输出密文CT：

$\left\{ {\begin{array}{*{20}{l}} {c = {k^{mH\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}}{h^R},C' = {g^s}}\\ {\left( {{C_1} = {g^{a{\lambda _1}}} \cdot F{{\left( {\rho \left( 1 \right)} \right)}^{ - {r_1}}},{D_1} = {g^{{r_1}}}} \right)}\\ \vdots \\ {\left( {{C_l} = {g^{a{\lambda _l}}} \cdot F{{\left( {\rho \left( l \right)} \right)}^{ - {r_l}}},{D_l} = {g^{{r_l}}}} \right)} \end{array}} \right.$

密钥产生算法：输入主密钥MSK和属性S，随机选择t′∈Z_p，输出：

$SK' = \left( {PK,K' = {g^\alpha }{g^{at'}},L' = {g^{t'}},{{\left\{ {{K_x}^\prime = F{{\left( x \right)}^{t'}}} \right\}}_{x \in S}}} \right)$

算法随机选择z∈Z_p，并令t=t′/z，输出转换密钥TK：

$PK,K = {K'^{\frac{1}{z}}} = {g^{\left( {\frac{a}{z}} \right)}}{g^{at}},L = {L'^{\frac{1}{z}}} = {g^t},{\left\{ {{K_x}} \right\}_{x \in S}} = {\left\{ {{{K'}_x}^{^{\frac{1}{z}}}} \right\}_{x \in S}}$

私钥即为SK=(q₁, z, TK)。

转换算法(外包到云上进行):解密者输入转换密钥TK=(PK, K, L, {K_x}_x∈S)和待解密密文CT=(c, C′, C₁, …, C_l)，如果属性S不满足访问结构(M, ρ)，则输出⊥；反之定义I⊂{1, 2, …, l}，满足I={i:ρ(i)∈S}，存在常数集{ω_i∈Z_p}_i∈I，对于{λ_i}中所有的值，$\sum\limits_{}^{i \in I} {{\omega _i}{\lambda _i} = s} $。通过转换算法计算：

$\begin{array}{l} Q = e'\left( {C',K} \right)/\left( {e'\left( {\prod\limits_{i \in I} {C_i^{{w_i}},L} } \right) \cdot \prod\limits_{i \in I} {e'\left( {D_i^{{w_i}},{K_{\rho \left( i \right)}}} \right)} } \right) = \\ \quad \quad e'{\left( {g,g} \right)^{\frac{{s\alpha }}{z}}}e'{\left( {g,g} \right)^{sat}}/\left( {\prod\limits_{i \in I} {e'{{\left( {g,g} \right)}^{ta{\lambda _i}{w_i}}}} } \right) = \\ \quad \quad e'{\left( {g,g} \right)^{\frac{{s\alpha }}{z}}} \end{array}$

算法最后输出部分密文CT′=(c, Q)。

解密算法：输入私钥SK=(q₁, z, TK)和密文CT，如果密文不是部分密文，那么必须先运行转换算法将其转换为部分密文。如果转换算法输出为⊥，则解密算法也输出⊥。反之，利用(z, Q)计算出e′(g, g)^sα=Q^z，而后解密者再利用部分私钥q₁计算c^q₁=(k^{mH(e′(g, g)αs})h^R)^q₁=(k^{H(e′(g, g)αs})q₁)^m，通过Pollard's lambda算法解密以k^{H(e′(g, g)αs})q₁为底c^q₁的离散对数即可恢复出明文消息m。其中，最终步骤利用Pollard's lambda算法进行的解密过程与BGN方案的解密过程是一样的。

3 方案分析 3.1 同态性质分析

本文方案是基于类同态BGN方案，所以它满足任意次加法同态和一次乘法同态性质，详细分析如下：

1) 加法同态：对于两个部分密文c₁=k^{m₁H(e′(g, g)αs})h^R₁∈G和c₂=k^{m₂H(e′(g, g)αs})h^R₂∈G，计算：

$\begin{array}{l} c' = {c_1}{c_2}{h^R} = \left( {{k^{{m_1}H\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}}{h^{{R_1}}}} \right) \cdot \left( {{k^{{m_2}H\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}}{h^{{R_2}}}} \right){h^R} = \\ \quad \quad {k^{\left( {{m_1} + {m_2}} \right)H\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}}{h^{{R_1} + {R_2} + R}} \in G \end{array}$

属性满足密文策略的合法解密者可以求出e′(g, g)^sα的值，进而利用解密算法即可算出m₁+m₂。

2) 乘法同态：令k₁=e(k, k)，h₁=e(k, h)，则k₁的阶为n，h₁的阶为q₁，并且一定有β∈Z使得h=k^βq₂，计算：

$\begin{array}{l} c' = e\left( {{c_1},{c_2}} \right)h_1^R = \\ \quad \quad e\left( {{k^{{m_1}H\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}}{h^{{R_1}}},{k^{{m_2}H\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}}{h^{{R_2}}}} \right)h_1^R = \\ \quad \quad k_1^{{m_1}{m_2}H{{\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right)}^2}}h_1^{R + \left( {{R_1}{m_2} + {R_2}{m_1}} \right)H\left( {e'{{\left( {g,g} \right)}^{\alpha s}}} \right) + \beta {q_2}{R_1}{R_2}} \in {G_1} \end{array}$

同理，合法解密者能够算出m₁m₂。由于不存在有效算法使得e:G₁×G₁→G成立，所以本文方案只能进行一次乘法。

3.2 安全性分析

本文将从以下两个方面分析方案的安全性：一是证明方案在子群判定问题困难假设下满足语义安全；另一方面，在随机预言机模型下分析方案的属性安全。

3.2.1 语义安全分析

定义1 子群判定问题。定义算法G，输入安全参数τ∈Z⁺，输出元组(q₁, q₂, G, G₁, e)，其中G, G₁都是阶为n=q₁q₂的群，e:G×G→G₁是双线性映射。输入参数τ，算法G运行如下：

1) 生成两个随机的τ比特的素数q₁, q₂，令n=q₁q₂∈Z。

2) 生成满足1.1节中定义的双线性映射群G, G₁，其生成元为g，阶为n。

3) 输出(q₁, q₂, G, G₁, e)。

子群判定问题定义为：给定元组(q₁, q₂, G, G₁, e)和元素x∈G，如果x的阶是q₁，则输出“1”，否则输出“0”。也即在不清楚n的分解情况下，判定元素x是否属于G的一个子群。对于算法敌手$\mathscr{A}$，解决该问题的优势定义为：

$\begin{array}{l} SD{\rm{ - }}Ad{v_{{\rm{\mathscr{A}}}}}\left( \tau \right) = \left| {{\rm{Pr}}\left[ {{\rm{\mathscr{A}}}\left( {n,G,{G_1},e,x} \right) = 1:} \right.} \right.\left( {{q_1},{q_2},G,} \right.\\ \left. {\left. {{G_1},e} \right) \leftarrow G\left( \tau \right),n = {q_1}{q_2},x \leftarrow G} \right] - {\rm{Pr}}\left[ {{\rm{\mathscr{A}}}\left( {n,G,{G_1},} \right.} \right.\\ \left. {e,{x^{{q_2}}}} \right) = 1:\left( {{q_1},{q_2},G,{G_1},e} \right) \leftarrow G\left( \tau \right),n = {q_1}{q_2},\\ \left. {\left. {x \leftarrow G} \right]} \right| \end{array}$

定义2 称算法$\mathscr{G}$满足子群判定假设，对任意多项式时间算法敌手$\mathscr{A}$解决上述子群判定问题的优势SD-Adv_{$\mathscr{A}$}(τ)是可以忽略不计的。

证明 本文方案的安全性是建立在敌手算法$\mathscr{A}$不能攻破子群判定问题的假设基础上。假设存在某一算法$\mathscr{A}$能够以优势ε攻破本文方案的语义安全性，那么就一定存在敌手算法$\mathscr{A}$能够以优势ε解决子群判定问题假设。详细的证明过程如下：

1) 敌手算法$\mathscr{A}$随机选择g∈G，将公钥(n, G, G₁, e, g, x)发送给算法。

2) 算法$\mathscr{B}$随机挑选两个明文消息m₀, m₁发送给敌手算法$\mathscr{A}$，算法$\mathscr{A}$返回随机挑战密文C=g^m_bx^r∈G，其中$b\xleftarrow{R}\left\{ 0,1 \right\},r\xleftarrow{R}\left\{ 0,1,\cdots ,n-1 \right\}$。

3) 算法$\mathscr{B}$输出关于b的猜测b′，如果b=b′，算法$\mathscr{A}$输出“1”，否则输出“0”。

如果元素x是在群G中均匀分布，那么挑战密文C在群G中也是均匀分布，与b的选择无关，即Pr|b=b′|=1/2；如果x是群G的q₁阶子群中的元素，那么根据假设就有Pr|b=b′|>1/2+ε，所以SD-Adv_{$\mathscr{A}$}(τ)>ε，这就意味着敌手算法$\mathscr{A}$解决子群判定问题假设的优势ε是不可忽略的，与困难问题矛盾。

因此，方案在子群判定问题困难假设下达到了语义安全。

3.2.2 属性安全分析

对方案的属性安全分析借鉴文献[8]的方法，其安全模型如下：

Setup：挑战者运行初始化算法，将安全参数及公钥PK发送给敌手算法$\mathscr{A}$。

Phase 1：挑战者新设一个空表T和一个空集D，并设置初始指针j=0。敌手算法$\mathscr{A}$被允许重复以下任意查询。

·Create(S)：挑战者设置指针j:=j+1，运行密钥产生算法得到一组与属性S相关的密钥对(SK, TK)，挑战者将该密钥对存储在表T中，并记录为(j, S, SK, TK)。算法最终将转换密钥TK发送给敌手算法$\mathscr{A}$。针对同一属性S，这一过程可以被重复查询。

·Corrupt(i)：如果在表T中存在第i项记录，即指针j≥i，那么挑战者就可得到该记录(j, S, SK, TK)的内容，并且修改D:=D∪{S}，而后将私钥SK发送给敌手算法$\mathscr{A}$；如果在表T中不存在第i项记录，则输出⊥。

·Decrypt(i, CT)：如果在表T中存在第i项记录，那么挑战者就可得到该记录(j, S, SK, TK)的内容，并且挑战者将输入(SK, CT)进行解密得到的解密结果发送给敌手算法$\mathscr{A}$；如果在表T中不存在第i项记录，则输出⊥。

Challenge：敌手算法$\mathscr{A}$提交两个长度相等的消息m₀和m₁，此外敌手算法$\mathscr{A}$再选择一个访问结构(M^*, ρ^*)，满足对于所有的S∈D，f(S, (M^*, ρ^*))≠1。挑战者以抛掷硬币的方式随机选择m_b，并且在访问结构(M^*, ρ^*)下加密m_b，将得到的密文CT^*发送给敌手算法$\mathscr{A}$。

Phase 2：以上的Phase 1过程可以重复进行，但是敌手算法$\mathscr{A}$不能：

·从挑战密文中直接获得私钥，算法$\mathscr{A}$不能在Challenge中出现f(S, (M^*, ρ^*))=1的情况，也即是说在Corrupt这一步的查询中，满足f(S, (M^*, ρ^*))=1的属性S不能被添加到D中。

·查询得到了正确结果，也即Decrypt查询应在Phase 1中完成，除了当查询结果为m₀或者m₁时，挑战者用消息test来代替回答。

Guess：敌手算法$\mathscr{A}$输出关于b的猜测b′。

在上述的安全游戏中，敌手算法$\mathscr{A}$的安全优势定义为$Ad{v_{{\rm{\mathscr{A}}}}} = \left| {\Pr \left[ {b' = b} \right] - \frac{1}{2}} \right|$。

定义3 如果敌手算法$\mathscr{A}$在上述安全游戏中多项式时间内优势可以忽略不计，那么方案就在随机预言机模型下满足属性安全。

证明 在现实攻击中，由于满足访问结构的属性S都被排除在属性集合D之外，当敌手算法$\mathscr{A}$对转换密钥TK及私钥SK进行查询时，得不到能够正确解密的相关密钥，只可能以等概率猜测b，即敌手算法$\mathscr{A}$的安全优势多项式时间内优势可以忽略不计。

因此，方案就在随机预言机模型下满足属性安全。

3.3 性能分析

Green等在文献[8]中提出了基于属性的密文解密外包思想，并构造了一个密文策略的外包方案; Gentry等在文献[15]中利用容错学习问题(Learning With Errors，LWE)构造了一个BGN型的类同态加密方案。将本文构造的方案与文献[8, 15]中的方案分别进行对比，主要比较方案类型、是否支持同态操作、是否支持访问控制、密文尺寸、解密时间开销等，结果如表 1、表 2所示。通过表 1可以看出，相比文献[8]中的密文策略外包方案，本文方案能够支持对外包的密文进行同态操作，包括任意次加法同态和一次乘法同态操作。表 2中，m代表明文空间大小，E代表进行一次指数运算所耗费的最大时间。通过表 2可以看出，与文献[15]中利用容错学习问题构造的BGN型类同态方案相比，本文方案能够实现对加密结果的解密权限的控制，并且本文方案在密文尺寸和解密时间上都优于文献[15]的方案。

4 结语

本文通过将基于属性的密文解密外包的思想引入到BGN方案中，构造了一个适用于云计算环境的基于属性的BGN型密文解密外包方案；通过利用基于属性加密的方法，解决了云计算结果访问控制问题，并且解密过程的外包大幅度降低了用户的计算量，提高了用户解密效率。进一步的工作是探索基于属性的密文解密外包与全同态方案的结合，构造效率更高、更加实用的云环境下全同态基于属性的密文解密外包方案。