0 引言

随着云计算技术(cloud computing)^[1]的快速发展和逐步完善, 越来越多的用户倾向于将复杂的计算资源、存储资源外包给“云端”, 从而极大地减轻了用户的负担.然而“云端”并不是完全可信的, 人们在享受“云端”所带来便利的同时, 对于数据的访问控制也进行了各种尝试, 从不同角度对数据访问控制权限进行研究^[2-4].然而, 将同态加密与谓词相联系的研究却很少.试想如果用户将明文数据直接交由“云端”处理, 无疑会增加数据的安全隐患.为了防止“云端”的恶意篡改和非法用户访问敏感数据, 用户不仅需要对敏感数据进行加密, 更重要的是要设置必要的访问控制策略.在传统的云计算加解密模型中, 无法实现对计算结果的访问控制.在公钥密码体制中, 用户的身份是由数字证书来确认的, 但证书的使用无疑会增加系统的开销, 这将无法体现出云的优势.文献[5]提出了谓词加密(predicate encryption, PE), 因其能够实现对密文更加精细、灵活的访问控制而备受关注.

在谓词加密系统中, 由谓词向量v与主密钥MK生成的密钥sk_v能够解密由属性向量x生成的密文.其中谓词类为$ F = \left\{ {{f_v}|\mathit{\boldsymbol{v}} \in Z_p^n\backslash \left\{ {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over 0} } \right\}} \right\}$, 属性值为x, 满足f_v(x)=1, 当且仅当x·v=0 mod N.在这里我们规定属性值x中的每一项不为0, 即∑x_i≠0 mod N.在PE系统中, 将用户密钥与谓词向量相关联, 密文与属性向量相关联, 当且仅当谓词对于输入的属性向量求值为真时才可能正确解密, 从而能实现对密文的细粒度访问控制.鉴于谓词加密具有优良的访问控制特性, 引起了密码学家的高度关注, 出现了许多这方面的研究成果, 例如IBE(identity-based encryption)^[6-7], ABE(attribute-based encryption)^[8], HVE(hidden-vector encryption)^[9].文献[10]构建了一个谓词加密方案, 在Z₂上实现了加法同态操作.

方案以类同态Paillier方案^[11]为基础, 结合经典文献[12]提出的KP-ABE(key-policy ABE)型密文解密外包设计思想, 构造了一个基于谓词的Paillier型密文解密外包方案.相比文献[12], 该方案在解密时间上有所增长, 但是对密文的访问控制却优于文献[12], 增强了用户数据的安全性, 从而在一定程度上减小了数据泄露的概率, 方案还可以抵抗任何恶意云服务器的攻击.在方案构造中, 部分密文的解密被外包到云上进行, 减小了用户的计算量, 更为重要的是对密文的访问控制策略被隐藏在密文当中, 所以要想完成对密文的正常解密, 要求用户属性必须满足密文策略, 实现了用户对外包计算结果的有效控制.此外, 方案对密文可以进行任意次加法同态操作和一次乘法同态操作.同态加密可以允许用户在不知道明文的情况下对密文进行操作, 从而很大程度上方便了用户.随着同态加密受到越来越多的关注, 涌现出了许多同态加密的研究成果^[13-14].

1 预备知识 1.1 双线性映射

G, G_T是两个阶为p的循环群, g为生成元, 则双线性映射^[15]e:G×G→G_T满足下列性质：

1) 双线性.对任意r, s∈G和a, b∈Z_p, 都有e(r^a, s^b)=e(r, s)^ab.

2) 非退化性.存在r, s∈G, 使得e(r, s)≠1.

3) 可计算性.存在有效的多项式算法对任意r, s∈G_T, 都可以计算出e(r, s).

1.2 访问结构

定义P={P₁, P₂, …, P_n}是秘密共享的参与者集合.访问结构AS是2^p上的一个非空子集, 即AS⊆2^p\{Ø}.访问结构单调性定义如下：∀A, B, 如果A∈AS且A⊆B, 则B∈AS.同时, 对于能重构出共享秘密的子集称为授权集合；反之, 则称为非授权集合.

1.3 LSSS矩阵访问结构

定义在秘密共享参与者集合P上的线性秘密共享机制^[15](linear secret sharing scheme, LSSS)Π是指：

1) 所有参与者的共享组成一个Z_p上的向量.

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

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

1.4 Paillier方案

Paillier公钥密码^[11]是由Paillier在1999年提出的一种基于高次剩余类问题的加密体制, 该体制具有同态的优良性质, 其良好的同态性质可以用于构造很多实用且高效的密码算法.方案的具体描述如下：

密钥生成算法.输入安全参数γ, 随机选择两个相互独立的大素数p和q, 令gcd(pq, (p-1)(q-1))=1, n=pq, g=n+1, η=φ(n), ϕ=φ(n)-1, 其中φ(n)=(p-1)(q-1).随机选择一个整数g, 其中g∈Zn2*.自定义一个函数L(u)=(u-1)/n, 结合二项式定理(1+n)x=1+nx(mod n2), 可计算出ϕ=(L(gnmod n2))-1mod n.公钥为pk=(n, g), 私钥为sk=(η, ϕ).

加密算法.假设加密者要加密的明文m∈Z_n, 选择一个随机数R∈Z_n^*, 然后计算密文c=g^M·Rⁿmod n².

解密算法.解密者收到密文c后, 使用私钥sk可计算出明文m=L(cⁿmod n²)·ϕmod n.具体解密过程为

$ \begin{array}{l} L({c^n}\bmod {n^2}) \cdot \phi = L({({g^m}{R^n})^n}\bmod {n^2}) \cdot {\eta ^{ - 1}} = \\ L({\left( {1 + n} \right)^{mn}} \cdot {R^{nn}}\bmod {n^2}) \cdot {\eta ^{ - 1}} = m \cdot \eta \cdot {\eta ^{ - 1}} = m\bmod n. \end{array} $

Paillier方案同态性质分析.

给定两个密文E(m₁, pk)=g^m₁R₁ⁿmod n²和E(m₂, pk)=g^m₂R₂ⁿmod n², 其中R₁∈Z_n^*, R₂∈Z_n^*.

1) 加法同态：

$ \begin{array}{l} D(E({m_1}, pk) \cdot E({m_2}, pk)\bmod {n^2}) = \\ D(({g^{{m_1}}}R_1^n)({g^{{m_1}}}R_2^n)\bmod {n^2}) = D(E({m_1} + {m_2}, pk)) = {m_1} + {m_2}. \end{array} $

2) 乘法同态：

$ \begin{array}{l} D(E{({m_1}, pk)^{{m_1}}}\bmod {n^2}) = \\ D({({g^{{m_1}}}{R^n}_1)^{{m_1}}}\bmod {n^2}) = D(E({m_1}{m_2}, pk)) = {m_1}{m_2}. \end{array} $

1.5 安全模型

方案的安全模型引用文献[6].

初始化  运用算法Γ生成公钥参数, 将其传送给敌手B.

步骤1  敌手B对多组谓词向量v对应的密钥sk_v进行询问.

博弈  敌手B输出长度相同的明文消息m₀和m₁及其相应的属性x₀和x₁.假如步骤1中的谓词向量v不满足条件f_v(x₀)=1, f_v(x₁)=1, 则挑战者C用属性x_b随机加密明文m_b, 其中b∈{0, 1}.然后将对应的加密密文c^*发送给敌手B.

步骤2  敌手B按照步骤1的方式不断询问直到谓词向量v满足条件f_v(x₀)=1, f_v(x₁)=1.

猜想  敌手B输出b′, 如果b′=b, 则攻击成功.

定义敌手B的IND-AH-CPA安全优势为$ Ad{v_{\mathit{\Gamma }, B}}\left( \lambda \right) = |\Pr \left[ {b' = b} \right] - \frac{1}{2}|$, 其中λ是安全参数, 用来确定加密方案中密钥的长度.

定义1  当敌手B在上述交互过程中的优势是可以忽略的, 方案是IND-AH-CPA安全的.

Payload-hiding安全只能保护明文信息不被窃取, 对于其他相关信息是做不到隐私保护的.这在一些保密要求高的应用场合(如属性信息也要求保密)是不适用的.该方案可以达到attribute-hiding安全：可以将明文信息和属性信息同时混淆在加密密文中而不被泄露.相比而言, attribute-hiding在安全性和适用范围上要比payload-hiding有更广泛前景.

1.6 安全假设

方案的安全性假设借鉴了文献[16]中基于双线性映射子群判定问题的扩展.

输入生成元g和安全参数1^λ, 输出元组(N=p₁p₂p₃, G, G_T, e), 其中p₁, p₂, p₃是互不相同的素数.G和G_T均是阶为N的循环群, 定义G_p1, G_p2, G_p3是G的子群.随机选择生成元q∈G_p1.为了便于说明, 引入一个参数h∈G_p1, 由于参数h对于挑战者来说是独立的, 故参数h的引入并不会增加敌手的优势.

假设1  根据生成元g定义：

$ \begin{array}{*{20}{c}} {(N = {p_1}{p_2}{p_3}, G, {G_T}, e) \leftarrow g, }\\ {q, h \leftarrow {G_{{p_1}}}, {X_3} \leftarrow {G_{{p_3}}}, }\\ {D = (G, q, h, {X_3}), }\\ {{T_0} \leftarrow {G_{{p_1}}}, {T_1} \leftarrow {G_{{p_1}{p_2}}}.} \end{array} $

定义算法Λ能够区分某一元素属于G_p1或者G_p1p2的优势为

$ Adv{1_{g, \mathit{\Lambda }}}\left( \lambda \right) = |\Pr [\mathit{\Lambda }(D, {T_0}) = 0\left] { - \Pr } \right[\mathit{\Lambda }(D, {T_1}) = 0]|. $

定义2  对于多项式时间算法Λ, 当Adv1_{g, Λ}(λ)可忽略时, 则满足假设1.

假设2  根据生成元g定义：

$ \begin{array}{*{20}{c}} {(N = {p_1}{p_2}{p_3}, G, {G_T}, e) \leftarrow G, }\\ {q, h, {X_1} \leftarrow {G_{{p_1}}}, {X_2}, {Y_2} \leftarrow {G_{{p_2}}}, {X_3}, {Y_3} \leftarrow {G_{{p_3}}}, }\\ {D = (G, q, h, {X_3}, {X_1}{X_2}, {Y_2}{Y_3}), }\\ {{T_0} = {G_{{p_1}{p_3}}}, {T_1} \leftarrow {G_{{p_1}{p_2}{p_3}}}.} \end{array} $

定义算法Λ能够区分某一元素属于G_p1p3或者G_p1p2p3的优势为

$ Adv{2_{g, \mathit{\Lambda }}}\left( \lambda \right) = |\Pr [\mathit{\Lambda }(D, {T_0}) = 0\left] { - \Pr } \right[\mathit{\Lambda }(D, {T_1}) = 0]|. $

定义3  对于多项式时间算法Λ, 当Adv2_{g, Λ}(λ)可忽略时, 则满足假设2.

假设3  根据生成元g定义：

$ \begin{array}{*{20}{c}} {(N = {p_1}{p_2}{p_3}, G, {G_T}, e) \leftarrow g, k \in {Z_N}, }\\ {q, h \leftarrow {G_{{p_1}}}, {X_2}, {Y_2}, {Z_2} \leftarrow {G_{{p_2}}}, {X_3} \leftarrow {G_{{p_3}}}, }\\ {D = (G, {X_3}, {Z_2}, q, {q^k}{X_2}, h{Y_2}), }\\ {{T_0} = e{{\left( {q, h} \right)}^k}, {T_1} \leftarrow {G_T}.} \end{array} $

定义算法Λ能够区分某一元素是T₀还是属于G_T的优势为

$ Adv{3_{g, \mathit{\Lambda }}}\left( \lambda \right) = |\Pr [\mathit{\Lambda }(D, {T_0}) = 0\left] { - \Pr } \right[\mathit{\Lambda }(D, {T_1}) = 0]|. $

定义4  对于多项式时间算法Λ, 当Adv3_{g, Λ}(λ)可忽略时, 则满足假设3.

2 基于谓词的Paillier型密文解密外包系统模型

在阐述方案构造之前, 首先简要介绍有关基于谓词的密文解密外包主要部分的工作流程模式.该方案主要涉及“云端”和用户两个主体.它们之间的交互过程可以分为两步进行.第一步, 用户给“云端”发送一个转换密钥TK, 主要作用是将外包给“云端”的密文进行必要的转换以方便用户的解密操作.第二步, “云端”利用用户发送的转换密钥TK, 将存储在自己服务器上的密文进行相应的转换, 以满足用户需求, 而后将其回传给用户.

1) “云端”:具有较强的计算和存储能力, 可以为用户提供更为方便快捷的服务, 但是云服务器是属于完全不可信或者半可信的.所以必须对敏感数据进行加密, 并且设定必要的访问控制权限.

2) 用户:具有较弱的计算和存储能力, 倾向于把一些复杂的数据资源交给“云端”来处理, 但希望这些数据不能被云服务器窃取或者篡改.

3 基于谓词的Paillier型密文解密外包方案

本小节主要介绍该方案的具体实现过程, 通过将Paillier方案与密文解密外包思想相结合, 构造了基于谓词的Paillier型密文解密外包方案, 可以实现对云计算结果的访问控制.方案主要由以下5个算法构成.

初始化算法(π, U).输入安全参数π和属性空间U, 其中U={0, 1}*.随机选择阶为N、生成元为β的群G, F是一个由{0, 1}*映射到G的哈希函数.另外, 随机选择系数$\alpha , a\in {{Z}_{N}}, {{\left\{ {{t}_{i}} \right\}}_{i=1, \cdots , n}}\xleftarrow{r}{{Z}_{n}} $且a≠ti, g∈Zn2*.公钥是

$ PK = \{ g, {g_1} = {g^a}, e{\left( {g, g} \right)^\alpha }, {\{ {T_i} = {g^{{t_i}}}\} _{i = 1, \cdots , n}}, F\} , $

主密钥MK=(g^α, PK).

加密算法(PK, m, (M, ρ)).输入公钥参数PK和明文消息m.加密时随机选择列向量w=(s, y₂, …, y_n)∈Z_Nⁿ, 秘密共享参量为s.定义访问结构为(M, ρ), 其中M是一个l×n的矩阵, ρ是与M行元素属性相关的函数.计算λ_i=M_i·v, 其中i=1, 2, …, n, M_i是M的第i行元素所组成的向量.再随机选择ρ, R∈Z_n^*, r₁, …, r_l∈Z_N.定义一个由G_T映射到(0, 1)的哈希函数H, 其中对于任意的ρ均有H(ρ)≠0.选择属性向量x={x₁, x₂, …, x_n}, 输出密文为CT,

$ \begin{array}{*{20}{c}} {\left\{ \begin{array}{l} c = {g^{m/H(e(g, g)}}^{ - r{x_i})} \cdot {R^n}\bmod {n^2}, \\ C' = {g^{rs}}, \\ ({C_1} = {g^{a{\lambda _1}}} \cdot F{\left( {\rho \left( 1 \right)} \right)^{ - {r_1}}}, {D_1} = {g^{{r_1}}}), \cdots , \\ ({C_l} = {g^{a{\lambda _l}}} \cdot F{\left( {\rho \left( l \right)} \right)^{ - {r_l}}}, {D_l} = {g^{{r_l}}}), \end{array} \right.}\\ {{c_1} = {{({g^{ - 1}}_1{T_i})}^{r{x_i}}}, } \end{array} $

(1)

最终是密文形式

$ C = (c, {c_1}). $

(2)

密钥产生算法(MK, S).输入主密钥MK和属性S, 随机选择ε, t∈Z_N^*, h∈G_p1.输出$SK' = (PK, K' = {g^{ - \frac{{{x_i}}}{s}}}{g^{\frac{{at'}}{r}}}, L' = {g^{t'}}, {\{ K{'_x} = F{\left( x \right)^{t'}}\} _{x \in S}}) $.谓词向量为v={v₁, …, v_n}, 生成解密密钥$ s{k_v} = \{ {\{ {d_i} = {({h^{s{v_i}}}g)^{\frac{1}{{a - {t_i}}}}}\} _{i = 1, \cdots , n}}\} $.令t=t′/ε, 输出转换密钥TK：

$ \begin{array}{*{20}{c}} {PK, K = K{'^{1/\varepsilon }} = {g^{ - {x_i}/s\varepsilon }}{g^{at/r}}, L = L{'^{1/\varepsilon }} = {g^{(t'/\varepsilon )}} = {g^t}, }\\ {{{\{ {K_x}\} }_{x \in S}} = {{\{ K{'}_{x}^{1/\varepsilon }\} }_{x \in S}}.} \end{array} $

私钥为SK=(ε, TK, sk_v).

转换算法(TK, CT).输入转换密钥TK=(PK, K, L, {K_x}_x∈S)和密文CT=(C, C′, C₁, …, C_l), 如果属性S不满足访问结构(M, ρ), 则输出⊥；反之定义I={i:ρ(i)∈S}, 且I⊆{1, 2, …, l}, 存在常数集{ω_i∈Z_p}_i∈I, 对于{λ_i}中所有的值, ∑_i∈Iω_iλ_i=s.运用转换算法计算.

$ \begin{array}{l} Q = e\left( {C'', K} \right)/(e(\mathop \prod \limits_{i \in I} C_i^{{w_i}}, L) \cdot \mathop \prod \limits_{i \in I} e(D_i^{{w_i}}, {K_{\rho (i)}})) = \\ e{\left( {g, g} \right)^{ - r{x_i}/\varepsilon }}e{\left( {g, g} \right)^{sat}}/(\mathop \prod \limits_{i \in I} e{\left( {g, g} \right)^{ta{\lambda _i}{w_i}}}) = e{\left( {g, g} \right)^{ - r{x_i}/\varepsilon }}, \end{array} $

(3)

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

解密算法(SK, CT).输入私钥SK=(ε, TK, sk_v)和密文CT, 假如密文CT不是部分密文, 则需要先运行转换算法(TK, CT), 将其转换为部分密文.转换算法(TK, CT)输出为⊥时, 则解密算法也输出⊥.反之, 利用(ε, Q)计算出Q^ε=e(g, g)^rx_i, 再利用解密密钥sk_v, 结合Euler函数计算

$ \begin{array}{l} L({c^\eta }\bmod {n^2}) \cdot \phi \cdot H(e({c_1}, {d_i})) = L({\left( {1 + n} \right)^{m/H(e(g, g)}}^{ - r{x_i}}) \cdot {R^n}{)^\eta }\\ \bmod {n^2} \cdot {\eta ^{ - 1}} \cdot H(e({(g_1^{ - r}T_i^r)^{{x_i}}}, {({h^{s{v_i}}}g)^{\frac{1}{{a - {t_i}}}}})) = \\ (m\eta /H(e{\left( {g, g} \right)^{ - r{x_i}}})) \cdot {\eta ^{ - 1}} \cdot H(e{\left( {g, g} \right)^{ - r{x_i}}} \cdot e{\left( {g, h} \right)^{sr\sum {x_i}{v_i}}}) = \\ (m/H(e{\left( {g, g} \right)^{ - r{x_i}}})) \cdot H(e{\left( {g, g} \right)^{ - r{x_i}}} \cdot e{\left( {g, h} \right)^{sr\sum {x_i}{v_i}}}). \end{array} $

(4)

只有当接收方的谓词向量满足x·v=0 mod N, 才可恢复出明文消息.根据哈希函数的抗碰撞性质, 如果非法解密者不能满足x·v=0 mod N, 则无法计算获得明文.

4 方案分析 4.1 安全性分析

本方案在子群判定问题困难假设下达到了语义安全.同时, 需要注意的是, 密文属性的泄露不会影响密文的安全.因为即使攻击者拿到密文的属性向量x, 即攻击者能够算出e(g, g)^-rx_i的值, 但是攻击者得不到谓词向量v的值, 无法满足f_v(x)=1, 从而不能正确解密得到明文m.另一方面, 攻击者即使同时拿到了属性向量x和谓词向量v, 满足f_v(x)=1.但攻击者如果得不到随机参数ε, 攻击者也不能正常解密而得到明文m.综上所述, 只有当攻击者得到谓词密钥才能解密嵌套了属性向量x的密文, 同时得到随机参数ε从而获得访问控制权限, 才能真正攻击成功.

为了证明该方案的安全性, 采用文献[16]的方法.证明先前定义的两种结构.

半功能密文：定义g₂为群G_p2的生成元, c∈Z_N, {z_i∈Z_N}_{i=1, …, n}, {c_i=(g^r_ix_ig₂^cz_i)^a-t_i}_{i=1, …, n}.

半功能密钥：随机选择d∈Z_N和${\{ {y_i} \in {Z_N}\} _{i = 1, \cdots , n}}, {\{ {d_i} = {(h{g^{s{v_i}}}g_2^{d{y_i}})^{\frac{1}{{a - {t_i}}}}}\} _{i = 1, \cdots , n}} $.

正常密钥能够解密正常密文和半功能密文, 同时正常密文可以由正常密钥和半功能密钥解密.当使用半功能密钥解密半功能密文时, 结果的等式中多出e(g₂, g₂)^{cd∑y_i·z_i}.只有满足∑y_i·z_i=0时, 半功能密钥才能够解密半功能密文.

基于以上分析, 可以通过证明以下Game^[15]的不可区分性而达到证明该方案的安全性.

Game₀中密文为半功能密文, 密钥均为正常密钥.

Game_real实际加密环境过程中使用的均为正常密文和正常密钥.

Game_k中前k次对半功能密钥查询, 大于k次的均是对正常密钥查询.

Game_final中密文为半功能密文, 而密钥为半功能密钥.

引理1  假设存在多项式时间敌手A, 满足Adv_A^Game_real-Adv_A^Game₀=ε, 那么存在多项式时间敌手B能够以ε优势解决假设1.

证明  敌手B将(G, q, h, X₃, T)作为算法初始化输入, 随机选择a∈Z_N, t_i∈Z_N, i=1, …, n.公共参数和算法初始化公开参数相同.敌手B模拟Game_real, Game₀与敌手A进行交互.

使用谓词向量v, 敌手B能够通过主密钥MK生成相应的正常解密密钥.

敌手A选择等长的明文(m₀, m₁)及相应的属性(x₀, x₁), 敌手B将假设1嵌入到挑战密文中, 而后使用掷硬币的方式进行加密, 生成密文形式为

$ {c^*} = \{ c = {g^{m/H(e\left( {T, g} \right) - \Sigma x_i^b}}) \cdot {R^n}\bmod {n^2}, {\{ {c_i} = {T^{x_i^b(a - {t_i})}}\} _{i = 1, \cdots , n}}\} . $

如果T∈G_p1, 即T=g^r, 则密文c^*为正常密文.如果T∈G_p1p2, 即T=g^rg₂^c, 则密文c^*为半功能密文.故敌手B能够利用A的输出以优势ε解决假设1.

引理2  假设存在多项式时间敌手A满足Adv_A^Game_k-1-Adv_A^Game_k=ε, 那么就存在多项式时间敌手B能够以ε优势解决假设2.

证明  敌手B将(q, h, X₃, T, Y₂Y₃, X₁X₂)作为算法的输入, 随机选择a∈Z_N, t_i∈Z_N, i=1, …, n.公共参数和引理1中公开参数相同.敌手B模拟Game_k-1, Game_k与敌手A进行交互.

使用谓词向量v, 当敌手B在查询次数大于k的情况下, 能够利用MK生成正常解密密钥, 而在查询次数小于k的情况下, 则生成半功能密钥.随机选择s, d∈Z_N, 生成的半功能解密密钥表示为

$ {\{ {d_i} = {({h^{s{v_i}}}g{({Y_3}, {Y_3})^{d{y_i}}})^{\frac{1}{{a - {t_i}}}}}\} _{i = 1, \cdots , n}}. $

当进行第k次查询时, 敌手B利用T, 生成的半功能解密密钥表示为${\{ {d_i} = {({h^{s{v_i}}}{T^{{v_i}}})^{\frac{1}{{a - {t_i}}}}}\} _{i = 1, \cdots , n}} $.

若T∈G_p1p3, 则上述密钥d_i为正常解密密钥.若T∈G_p1p2p3, 即T=g^sg₂^dg₃^f, 根据剩余定理可知上述密钥d_i为半功能解密密钥.由于敌手B不知道N的分解, 因此敌手B必须借助A来解决假设2.

敌手A选择等长的明文(m₀, m₁)及相应的属性(x₀, x₁), 敌手B通过使用掷硬币的方式进行随机加密, 密文形式为

$ {c^*} = \{ c = {g^{m/H(e\left( {{X_1}{X_2}, g} \right)\Sigma x_i^b}}) \cdot {R^n}\bmod {n^2}, {\{ {c_i} = {({X_1}{X_2})^{x_i^b(a - {t_i})}}\} _{i = 1, \cdots , n}}\} . $

令X₁X₂=g^rg₂^c, 则根据剩余定理可知这些元素实际不属于G_p1, G_p2的子群, 故该密文为半功能密文.B能够利用A的输出以优势ε解决假设2.

引理3  假设存在多项式时间敌手A满足Adv_A^Game_q-Adv_A^Game_final=ε, 那么就存在多项式时间敌手B能够以ε优势解决假设3.

证明  敌手B将(q, X₃, Z₂, g^rX₂, hY₂, T)作为输入, 随机选择a∈Z_N, t_i∈Z_N, i=1, …, n.公共参数为PK={g, hY₂, g₁=g^a, {T_i=g^t_i}_{i=1, …, n}}.参数N的分解不被A所获知, 故A无法正确区分hY₂和h.敌手B模拟Game_q, Game_final与敌手A进行交互.

使用谓词向量v进行密钥查询, 敌手B随机选取s, y′_i∈Z_N, 生成半功能密钥为

$ {\{ {d_i} = {({h^{s{v_i}}}{Y_2}gZ_2^{{y_i}})^{\frac{1}{{a - {t_i}}}}}\} _{i = 1, \cdots , n}}\} . $

令Y₂=g₂^f, Z₂=g₂^d, 设置y_i=y′_i+f/d, 则上述密钥d_i为半功能密钥.

敌手A选择等长的明文(m₀, m₁)及相应的属性(x₀, x₁), 敌手B将假设3嵌入挑战密文中, 而后使用掷硬币的方式进行随机加密, 密文形式为$ {c^*} = \{ c = {g^m} \cdot {R^n} \cdot {T^{ - \Sigma x_i^b}}, {\{ {c_i} = {({g^r}{X_2})^{x_i^b(a - {t_i})}}\} _{i = 1, \cdots , n}}\} $.

如果T=g^{m/H(e(g, h)r)-m}, 则上述密文c^*为半功能密文；如果T∈G_T, 则上述密文c^*为随机明文的加密的半功能密文, 因此能够模拟Game_final, 故B能够利用A的输出以优势ε解决假设3.

定理1  如果上述的3个假设均为困难问题, 则该方案为IND-AH-CPA安全.

证明  如果上述的假设为困难问题, 则由以上的分析可知Game_final与实际加密环境是不可区分的.在Game_final中挑战密文是不会泄漏关于B的任何信息.故敌手A攻击该该方案成功的概率几乎可以忽略不计, 方案可达到IND-AH-CPA安全.

4.2 性能分析

本方案相比于文献[12]中Green的方案, 改进之处是能够支持对外包密文的同态操作, 更重要的是方案的安全性并不完全取决于属性参数, 属性参数的泄露并不会对密文造成致命的影响.这意味着即使敌手获得了相关属性参数而没有掌握用户事先随机设定的参数时, 敌手仍然是无法攻击成功的, 从而在很大程度上增强了用户数据的安全性.

Green等人在文献[12]中提出了基于属性的密文解密外包思想, 并构造了一个密文策略外包方案.为了更好地展示方案的优缺点, 我们将在完全密文长度、完全密文解密时间、部分密文长度和部分解密时间分别与文献[12]和文献[17]进行比较.表 1中l表示线性秘密共享机制LSSS中l×n矩阵中的行数, k表示密文序列长度.P、E_G分别表示在G中计算线性最大时间和求模幂运算的最大时间, E_T表示在G_T中计算模的最大时间, 在计算时间中忽略了起非主导作用操作所消耗的时间.通过分析表 1可以得出如下结论：本方案在全密文长度和外包解密时间上比Green方案略长.然而, 方案在访问控制上却可以优于Green方案, 安全性不仅仅取决于单一的属性变量, 提高了用户数据的安全性, 从而达IND-AH-CPA安全.具体的比较结果如表 1所示.

4.3 同态性质分析

方案可以满足任意次加法同态和一次乘法同态运算.假设两个部分密文分别为E(m₁, PK)=g^{m₁/H(e(g, g)rx_i)}·R₁ⁿmod n²和E(m₁, PK)=g^{m₂/H(e(g, g)rx_i-})·R₁ⁿmod n², 具体分析如下.

1) 加法同态

$ \begin{array}{l} E({m_1}, PK) \cdot E({m_2}, PK) = {g^{{m_1}/H(e{{\left( {g, g} \right)}^{ - r{x_i}}})}} \cdot R_1^n \cdot {g^{{m_2}/H(e{{\left( {g, g} \right)}^{ - r{x_i}}})}} \cdot R_2^n = \\ {g^{\left( {{m_1} + {m_2}} \right)/H(e{{\left( {g, g} \right)}^{ - r{x_i}}})}}{({R_1}{R_2})^n} = E({m_1} + {m_2}, PK). \end{array} $

如果解密者想要求出式中e(g, g)^-rx_i的值, 则属性必须满足密文策略, 而后通过解密算法求出m₁+m₂,

$ E({m_1}, PK){g^{{m_2}}} = {g^{{m_1}e{{\left( {g, g} \right)}^{ - r{x_i}}}}}{R^{{n_1}}}{g^{{m_2}}}\bmod {n^2} = E({m_1} + {m_2}, PK). $

2) 乘法同态

$ \begin{array}{l} E{({m_1}, PK)^{{m_2}}} = {({g^{{m_1}/H(e{{\left( {g, g} \right)}^{ - r{x_i}}})}} \cdot R_1^n)^{{m_2}}}\bmod {n^2} = \\ {g^{{m_1}{m_2}/H(e{{\left( {g, g} \right)}^{ - r{x_i}}})}} \cdot {(R_1^{{m_2}})^n}\bmod {n^2} = E({m_1}{m_2}, PK). \end{array} $

与加法同态类似, 只有满足密文策略的解密者才能正确解密.

5 结束语

本文通过将谓词向量引入到类同态Parllier方案中, 构造了一个适用于云计算环境的外包方案.方案通过将谓词向量隐藏在密文中的举措, 有效地解决了用户对云计算结果的访问控制问题, 而且外包过程中将复杂的计算任务交由云服务器来完成, 很大程度上减轻了用户的开销, 提高了外包密文的解密效率.需要更进一步的工作是探索密文解密外包与全同态加密方案的有机结合, 构造一个云环境下访问控制性能更好的全同态密文解密外包方案.