0 引言

1984年,Shamir^[1]提出基于身份的密码学。该密码体制使用标识用户身份的字符串来代替公钥,大大减轻了公钥管理上的负担。2005年,Goyal等^[2]提出基于身份的模糊加密方案,2006年确定为基于属性的密码学(Attribute-Based Encryption,ABE)。属性密码学由基于身份的密码学发展而来,其私钥的生成同样由密钥生成中心(Key Generation Center,KGC)完成,因此恶意的KGC可以利用主密钥解密密文,即存在密钥托管问题。而克服密钥托管问题的方法主要有三种,分别为分布式方法、用户秘密值法和可追踪法。分布式方法本质是通过多个机构共同生成密钥,进而解决KGC叛变的问题。而用户秘密值法中的密钥是在用户和KGC之间完成交互后生成的,KGC没有秘密值,只能生成部分私钥,无法完成解密。可追踪法可以对KGC进行追踪并向仲裁者证明不诚实的KGC。文献^[3]结合上述方法,构造了一个可追责的属性加密方案,方案中密钥的生成由KGC和属性机构(Attribute Authority,AA)共同完成,并且密钥中嵌入了秘密信息,能实现对恶意用户及机构的追责。

多线性映射是继双线性映射之后的又一数学工具,具有更加灵活的编码方式,其天然支持多跳、多用户、多层次的优良性质在密码学中具有良好应用场景。2003年,Boneh等^[4]首次提出了多线性映射的若干应用,2013年Garg等^[5]提出了第一个实例化的多线性映射,之后利用该工具构造的密码学方案^[6-7]越来越多,而其本身在安全性^[8]上也不断发展,2015年,文献^[9]提出的改进方案解决了所有先前已知的在文献^{[5, 7]}上的攻击,尤其是“零测试攻击”。

Garg等^[10]利用该工具构造了一个基于属性的加密方案,将访问控制规则由布尔方程扩展到通用多项式电路,通过多线性映射实现了任意输出,提高了访问结构的灵活性并能够抵抗回溯攻击,其输出结果中只有一个未知量。因其良好的性质,之后基于多线性映射的属性密码学在实用性和安全性上得到了深入研究。Gorbunov等^[11]利用格上LWE(Learning With Errors)问题构造了一个支持电路结构的属性加密方案,其密文量与解密电路深度相关。2014年,Attrapadung等^[12]和Garg等^[13]分别提出了电路结构下的全安全属性加密方案,其密文量分别与布尔变量的数量、解密电路的尺寸相关。Dragan等^[14]利用“链式多线性映射”来减小加密函数映射时的有限域跨度,提高映射效率,构造了支持通用电路的短密钥属性加密方案。Boneh等^[15]利用“全密钥同态加密技术”将属性向量x利用函数引入到加密过程中,其密钥仅仅与输出电线的矩阵相关,从而构造了一个短密钥的加密方案,同时该方案也实现了短密文,但解密密钥的数量随解密电路的输入个数呈二次关系,且该方案的安全性是基于多线性映射Diffie-Hellman指数假设,并非标准困难问题假设。2015年,Chandran等^[16]将原先的解密策略深度l分别设置为l_OR和l_AND两种,加密时对应不同类型的门电路生成密钥,二者之间建立了转化关系,将多线性映射的分级减少为(l_AND+1)或(l_OR+1)级,以此来提高计算效率。Datta等^[17]利用文献^[18]中的技术,在多线性映射上构造全域哈希,生成一个加密输入串的哈希值,该哈希值是加密后密文的一部分,改变了以往方案必须在密文中为每一属性生成一个群元素参数的情况,使得密文量仅仅为两个群元素长度,更加紧凑,而哈希值的数据量远小于群元素的长度,可以省略不计。该方案在解密电路中,一个群元素就可以充分提供给每一个输入电线。这点远小于先前所有的多线性构造的方案。2016年,Brakerski等^[19]利用LWE问题构造了一个半自适应安全的属性加密方案,该方案实现了公共参数固定,且支持无界多项式长度。

总体而言,目前基于多线性映射的属性加密方案效率偏低,其原因可分为两方面:其一,多线性映射的底层构造效率不高;其二,方案的设计过于直接,没有针对多线性映射的特性来设计出适合的访问结构。在密码方案设计中,当通过优化内部结构提高效率遇到困难后,本文尝试借助外部技术来提高效率。

云计算作为新型的商业计算模式,其终极目标是为人们提供一种集计算、服务和应用为一体的公共设施。其中,外包计算是主要服务之一,人们可以将复杂的运算外包给云服务器,云服务器计算完毕后将结果返回给用户,这为用户带来经济和效率上的巨大提高。2011年,Green等^[20]将外包技术应用于属性密码学的解密中,之后涌现出了许多研究成果^[21-24]。上述以通用电路作为访问结构的方案中,用户解密时的大量计算代价都付出在解密密钥按照电路类型不同所进行的分级生成上,该计算代价由电路结构的参数设置直接决定,那么用户提供电路参数给云服务器,通过云服务器完成分级计算并对密文进行转换,这样在解密时便可以有效减轻终端用户的负担。

本文在文献^[17]的基础上,借鉴了文献^[15]和^[18]中构造全域哈希的技巧,实现了短密文；利用用户设置秘密值的方法,使得私钥由用户和KGC共同生成,降低了密钥对KGC的依赖,解密时只有通过用户自己独有的秘密值才能最终解密出明文；引入外包计算,用户解密前,发送转换密钥给云服务器,云服务器对密文进行转换,之后用户验证外包计算正确性,利用自己的私钥和秘密值解密转换密文,最终获得明文。

1 预备知识 1.1 多线性映射与困难性问题

多线性映射的实例化描述:群生成器Γ(1^λ,k),生成群组G=(G₁,G₂,…,G_k),其中每个群的阶p均大于2^λ,g_i为G_i的生成元,这里如果存在着这样一个映射集合{e_i,j:G_i×G_j→G_i+j|i,j≥1,i+j≤k}满足以下条件:

1) 双线性性:映射满足如下的关系式e_i,j(g_i^a,g_j^b)=g_i+j^ab:a,b∈Z_p。

2) 非退化性:对于每一个合法的i和j,都可以计算得到e_i,j(g_i,g_j)=g_i+j。

3) 群组里所有映射都可以被有效计算。

那么就称G为一个多线性映射群^[8]。

定义1 k阶多线性映射判断Diffie-Hellman(k-Multilinear Decisional Diffie-Hellman,k-MDDH)问题:运行群生成器Γ(1^λ,k),随机选取,c₁,c₂,…,c_k∈Z_p,计算,C₁=g₁^c₁,C₂=g₁^c₂,…,C_k=g₁^c_k,Q₀=g_k^o(j),其中$o\left( j \right)=\prod\limits_{j=1}^{k}{{{c}_{j}}}$,给出关于群G=(G₁,G₂,…,G_k)的相关描述σ_b=(G,g₁,C₁,C₂,…,C_k,Q_b,S),其中,设Q₁为G_k中的随机群元素,判断Q_b是Q₀还是Q₁是困难问题。

1.2 电路模型

本文的电路模型沿用文献^[25]的定义并作适当改造。为了不失一般性,本文所考虑的电路仅仅为单调电路,即电路分层,且“或门”和“与门”都有两个扇出。本文模型的电路只有一个输出门。首先定义6元组f=(n,l,q,A(w),B(w),GateType),这里的n代表输入个数,q表示门的数量,l表示电路深度。本文定义输入电线的集合为Input={1,2,…,n},电路门的集合为Gates={n+1,n+2,…,n+q},全部的电线集合为W=Input∪Gates,其中输出电线为n+q。定义A(w)和B(w)两个函数,分别代表电线w的第一和第二个输入。定义GateType为电路门类型函数,用以表示AND门和OR门。对于任何电路w∈Gates,为保证f非周期,有w>B(w)>A(w)。

定义depth(w)为层数函数,表示|w|与w到输入电线的最短路径的长度之和。对于所有w∈Gates,如果depth(w)= j,那么有depth(A(w))=depth(B(w))= j-1,对于输入x∈{0,1}ⁿ,定义函数f_w(x)为电线w对应输入x在电路f的值。

1.3 电路结构下的外包属性加密安全模型

沿用文献^[20]对外包属性加密的相关描述,结合电路访问结构给出外包属性加密的定义。输入串用x表示,访问结构用f表示,定义 (I_enc,I_key)为加密操作的输入和密钥生成的输入,在密钥策略(Key Policy,KP)ABE中,有(I_enc,I_key)=(x,f),那么外包KP-ABE的安全模型由五部分算法组成。

Setup(λ,n,l):输入安全参数和电路结构相关设置,输出公共参数PP和主密钥MSK。

Encrypt(PP,M,x):加密算法输入安全参数PP,加密输入串x∈{0,1}ⁿ,明文M,输出密文CT。

KeyGen_out(PP,MSK,f):密钥生成算法输入主密钥MSK,解密策略f,输出私钥SK和一个转换密钥TK。

Transform(TK,CT,x):密文转换算法输入转换密钥TK,密文CT和字符串x。如果有f(x)=1,即x符合解密条件,执行转换,输出部分解密密文即转换密文CT^*;否则输出⊥。

Decrypt_out(PP,SK,CT^*):解密算法输入私钥SK,转换密文CT^*,验证转换密文正确性,正确则输出明文M;否则输出⊥。

定义2 如果攻击者不能在多项式时间内以不可忽略的概率赢得以下游戏,那么称该方案具有选择性安全。

Init:攻击者A将挑战访问结构f公布,并将挑战输入串x发送给挑战者B,B利用x生成挑战密文。在后面的询问过程中,要求访问结构均不为f。

Setup:挑战者运行系统建立算法,将公共参数传递给攻击者。

Phase1:挑战者B可以进行任意多项式次数的解密密钥询问,要求其选取的输入串满足f(x^*)=0。A可重复进行下述询问。

①Create(I_key):挑战者设置j := j+1(j初始值为0),利用I_key运行外包密钥生成算法获得(SK,TK)，然后将转换密钥TK返回给敌手。可以对相同输入进行重复询问。

②Corrupt(i):对于第i个输入,挑战者设置D:=D∪{I_key},将私钥SK返回给敌手。

③Decrypt(i,CT):对于第i个输入,挑战者获得其对应f_i的值,并将解密算法的输出返回给敌手。

Challenge:敌手发送两个等长的消息M₀、M₁。挑战者随机选取b∈{0,1},利用I_enc,加密消息M_b,将密文CT^*发送给A。

Phase2:重复Phase1中的相关询问。

Guess:敌手输出对b的猜测b′。若b=b′,则攻击者赢得游戏,定义获胜概率为:Adv(A)=2Pr[b=b′]-1。

2 外包属性加密方案

本文提出了一个基于多线性映射的属性加密方案,算法构造如下:

1) 系统建立(1^λ,n,l)。

密钥生成中心输入安全参数1^λ,长度为n的布尔输入解密电线,最大深度为l的电线,KGC运行如下算法:

a) 运行G(1^λ,k=n+l+1),输出一个阶为p的群序列G=(G₁,G₂,…,G_k+2),对应的生成元依次为g₁,g₂,…,g_k+2,其中p>2^λ,定义哈希函数H:G₁×G_k+1→{0,1}^Δ,Δ表示明文长度。

b) 随机地选取元素α∈Z_p,设置随机元素对(a_1,0,a_1,1),(a_2,0,a_2,1),…,(a_n,0,a_n,1)∈Z_p²,计算ε=g_l+2^α,A_i,β=g₁^a_i,β,这里i=1,2,…,n且β∈{0,1}。

c) 公布公开参数PP,其中包含群序列的相关描述以及ε和{A_i,β}_{i=1,2,…,n; β∈{0,1}},保留主密钥MSK=g_l^α。

2) 加密(PP,x,M)。

加密者输入公共参数PP,一个加密输入字符串x=x₁x₂…x_n∈{0,1}ⁿ,满足f(x)=1,明文消息M∈{0,1}^Δ,加密者执行如下步骤:

a) 随机选取s∈Z_p,计算C=g₁^s,R=H(C,e(ε,A_1,x1,A_2,x2,…,A_n,xn)^s),C′=R⊕M。

b) 输出密文CT=(x,C,C′)。

3) 密钥生成(PP,MSK,f)。

KGC将公共参数PP,主密钥MSK,以及解密电路用户的描述函数f=(n,l,q,A(w),B(w),GateType)一起输入。电路有n+q条,其中{1,2,…,n}是n条输入电线,{n+1,n+2,…,n+q}是q个门(q表示门的数量),电线n+q为输出电线,生成过程如下:

a) 用户自己随机选取秘密值t∈Z_p,保留秘密值t,计算T=g₁^t,将计算好的T传递给KGC。

b) KGC收到T后为用户生成部分私钥SK₁:选择随机r₁,r₂,…,r_n+q∈Z_p,作为每条电线w∈{1,2,…,n+q}对应的随机r_w值,生成用户部分私钥SK₁=e(T,g_l^αg_l^-r_n+q)=g_l+1^t(α-r_n+q)。

c) 用户生成转换密钥TK:为每一个电线w构造转换密钥组件。密钥的结构取决于w的类型,分别为输入电线、或门、与门。对应的密钥生成如下:

① 输入电线。如果w∈{1,2,…,d},对应为第w条输入。选择随机r_w∈Z_p,计算转换密钥TK′_w=e(A_w,1,g₁,T)^r_w=g₃^r_wa_w,1t。

② 或门。电线w∈Gates,满足GateType(w)=OR,且深度j=depth(w),随机选取μ_w,ν_w∈Z_p,转换密钥TK′_w为K_w,1=e(g₁^μ_w,T)=g₂^μ_wt,K_w,2=e(g₁^ν_w,T)=g₂^ν_wt,K_w,3=e(g_j^{r_w-μ_wr_A(w)},T)=g_j+1^{t(r_w-μ_wr_A(w))},K_w,4=e(g_j^{r_w-ν_wr_B(w)},T)=g_j+1^{t(r_w-ν_wr_B(w))}。

③与门。电线w∈Gates,满足GateType(w)=AND,且深度j=depth(w),随机选取μ_w,ν_w∈Z_p,生成转换密钥TK′_w为

K_w,1=e(g₁^μ_w,T)=g₂^μ_wt

K_w,2=e(g₁^ν_w,T)=g₂^ν_wt

K_w,3=e(g_j^{r_w-μ_wr_A(w)-ν_wr_B(w)},T)=g_j+1^{t(r_w-μ_wr_A(w)-ν_wr_B(w))}

将生成的部分私钥SK₁和转换密钥TK=(f,{K_w}_{w∈{1,2,…,n+q}})发送给用户,用户的全部私钥SK为(SK₁,t),其中秘密值t由用户自己掌握。

4) 外包转换计算。

用户将自己的属性字符串x以及转换密钥TK发送给云服务器,服务器首先判断用户属性字符串x是否满足解密条件f(x)=1,若不成立,终止服务；若成立则针对用户所选的密文开始为用户提供服务,即对密文进行转换。

a) 从PP中提取{A_i,xi},这里定义函数$\delta \left( x \right)=\prod\limits_{i=1}^{n}{{{a}_{i,{{x}_{i}}}}}$,计算D=e(A_1,x1,A_2,x2,…,A_n,xn)=g_n^δ(x)。

b) 针对输入电线、或门、与门3种情况,对应操作分别如下:

① 输入电线。当w∈{1,2,…,n},对应的第w条输入如果有x_w= f_w(x)=1,则计算${{E}_{w}}=e\left( \text{T}{{{\text{{K}'}}}_{w}},{{A}_{1,{{x}_{1}}}},{{A}_{\text{2},{{x}_{\text{2}}}}},\cdot \cdot \cdot ,{{A}_{w-1,{{x}_{w-1}}}},{{A}_{w+1,{{x}_{w+1}}}},\cdot \cdot \cdot ,{{A}_{n,{{x}_{n}}}},C \right)=$$e\left( g_{3}^{{{r}_{w}}{{a}_{w,{{x}_{w}}}}t},g_{1}^{{{a}_{1,{{x}_{1}}}}},g_{1}^{{{a}_{\text{2},{{x}_{\text{2}}}}}},\cdot \cdot \cdot ,g_{1}^{{{a}_{w-1,{{x}_{w-1}}}}},g_{1}^{{{a}_{w+1,{{x}_{w+1}}}}},\cdot \cdot \cdot ,g_{1}^{{{a}_{n,{{x}_{n}}}}},g_{1}^{s} \right)=$$g_{n+4}^{{{r}_{w}}s\delta \left( x \right)t}$。

②或门。当电线w∈Gates,满足GateType(w)=OR,且深度j=depth(w),如果f_w(x)=1,则检查是否f_A(w)(x)=1,成立则计算

$\begin{align} & {{E}_{w}}=e\left( {{E}_{\text{A}\left( w \right)}},{{K}_{w,1}} \right)e\left( {{K}_{w,3}},C,D \right) \\ & =e\left( g_{n+j}^{s{{r}_{\text{A}\left( w \right)}}\delta \left( x \right)},g_{2}^{{{\mu }_{w}}t} \right)e\left( g_{j+1}^{{{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}}},g_{1}^{s},g_{n}^{\delta \left( x \right)} \right)=g_{n+j+2}^{{{r}_{w}}s\delta \left( x \right)t} \\ \end{align}$

如果f_A(w)(x)=0,那么必须满足f_B(w)(x)=1,且f_w(x)=1。计算E_w=e(E_B(w),K_w,2)e(K_w,4,C,D)=g_n+j+2^r_wsδ(x)t。

③与门。电线w∈Gates,满足GateType(w)=AND,且深度j=depth(w),如果f_w(x)=1,f_A(w)(x)= f_B(w)(x)=1。继续对密钥进行分级计算,则

$\begin{align} & {{E}_{w}}=e\left( {{E}_{\text{A}\left( w \right)}},{{K}_{w,1}} \right)e\left( {{E}_{\text{B}\left( w \right)}},{{K}_{w,2}} \right)e\left( {{K}_{w,3}},C,D \right)= \\ & e\left( g_{n+j}^{s{{r}_{\text{A}\left( w \right)}}\delta \left( x \right)},g_{2}^{{{\mu }_{w}}t} \right)e\left( g_{n+j}^{{{r}_{\text{B}\left( w \right)}}s\delta \left( x \right)},g_{2}^{{{\nu }_{w}}t} \right)e\left( g_{j+1}^{t\left( {{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}}-{{r}_{\text{B}\left( w \right)}}{{\nu }_{w}} \right)},g_{1}^{s},g_{n}^{\delta \left( x \right)} \right) \\ & =g_{n+j+2}^{{{r}_{w}}s\delta \left( x \right)t} \\ & {C}''=e\left( D,C \right)=g_{n+1}^{s\delta \left( x \right)} \\ \end{align}$

将计算后的转换密文CT′=(C,C′,C",E_n+q)发送给解密者。

5) 解密(CT′,SK,PP)。

用户获得CT′后,计算$\hat{E}=e\left( \text{S}{{\text{K}}_{1}},{C}'' \right)=g_{k+1}^{t\left( \alpha -{{r}_{n+q}} \right)s\delta \left( x \right)}$,$E=\hat{E}{{E}_{n+q}}=g_{k+1}^{t\alpha s\delta \left( x \right)}$,验证等式e(C",ε)^t=e(E,g₁)是否成立,若不成立,说明服务器计算错误；否则计算C′⊕H(C,E^1/t)=M,恢复出明文M。

3 方案分析 3.1 正确性分析

1) 外包计算的验证。

$\begin{align} & e{{\left( {C}'',\varepsilon \right)}^{t}}=e{{\left( g_{n+1}^{s\delta \left( x \right)},g_{l+2}^{\alpha } \right)}^{t}}=g_{k+2}^{s\delta \left( x \right)\alpha t}=e\left( g_{k+1}^{s\delta \left( x \right)\alpha t},{{g}_{1}} \right) \\ & =e\left( E,{{g}_{1}} \right) \\ \end{align}$

2) 解密。

$\begin{align} & E=\hat{E}{{E}_{n+q}}=e\left( \text{S}{{\text{K}}_{\text{1}}},{C}'' \right){{E}_{n+q}}=g_{k+1}^{t\left( \alpha -{{r}_{n+q}} \right)s\delta \left( x \right)}g_{k+1}^{{{r}_{n+q}}s\delta \left( x \right)t}=g_{k+1}^{t\alpha s\delta \left( x \right)} \\ & {C}'\oplus H\left( C,{{E}^{\text{1/}t}} \right)=H\left( C,g_{k+1}^{\alpha s\delta \left( x \right)} \right)\oplus M\oplus H\left[ C,{{\left( g_{k+1}^{\alpha s\delta \left( x \right)t} \right)}^{1/t}} \right] \\ & =M \\ \end{align}$

3.2 安全性分析

定理1 对于深度为l,输入个数为n的单调电路,利用k-MDDH困难性假设,证明方案在选择明文攻击(Chosen Plaintext Attack,CPA)下的不可区分性(Indistinguishability,IND)。对于任意概率多项式时间(Probabilistic Polynomial Time,PPT)敌手A,存在一个概率算法B,对于任何一个安全参数λ,有Adv_A^{ABE,s-IND-CPA}(λ)=Adv_B^k-MDDH(λ)成立。

证明 假设存在一个概率多项式敌手A以不可忽略的优势攻击方案,构造一个PPT算法B试图去解决一个k-MDDH问题的实例。B被给定的挑战实例为σ_b=(PP_MLM,g₁,C₁,C₂,…,C_k,Q_b,S),其中S=g₁^S,C₁=g₁^c₁,C₂=g₁^c₂,…,C_k=g₁^c_k,B仍然扮演挑战者,与A进行如下交互:

初始化 A公布挑战加密字符串x₁^*=x^*x₂^*…x_n^*∈{0,1}ⁿ以及访问结构f=(n,l,q,A(w),B(w),GateType)给B。

系统建立 判断β与x_i^*的关系,若β=x_i^*,则B随机选择z₁,z₂,…,z_n∈Z_p,设置a_i,β=c_i,A_i,β=C_i=g₁^c_i,保留c_i;若β≠x_i^*,则为每一个i,取a_i,β=z_i,同样计算A_i,β=g₁^z_i。B随机选取ξ∈Z_p,计算$\alpha =\xi +\prod\limits_{h=1}^{l+1}{{{c}_{n+h}}}$,定义函数$\vartheta \left( u,v \right)=\prod\limits_{h=u}^{v}{{{c}_{h}}}$,其中要求u和v都为正整数,这样α的值可表示为$\alpha =\xi +\vartheta \left( n+1,n+l+1 \right)$。然后挑战者B计算ε=e(C_n+1,C_n+2,…,C_n+l+2)g_l+2^ξ=g_l+2^α,传递公共参数PP和哈希函数H给A。

询问阶段1与询问阶段2 攻击者A通过加密字符串x^*和访问结构f向挑战者B询问解密密钥,要求f(x^*)=0,算法选择随机值t∈Z_p,判断输入的i是否满足f_i=1,若满足,生成用户部分私钥SK₁=e(T,g_l^αg_l^-r_n+q)=g_l+1^t(α-r_n+q),用户计算转换密钥TK=(f,{K_w}_{w∈{1,2,…,n+q}})。判断输入的i是否满足f_i=0,满足则由下至上为每个电线生成转换密钥组件,B的选取变化取决于电线w的类型,分别为输入电线、或门和与门。

① 输入电线。这里w∈{1,2,…,n},对应的第w条输入,若x_w^*=1,则B选择随机r_w∈Z_p,计算转换密钥TK′_w=e(C_w,g₁,g₁^t)^r_w=g₃^r_wa_w,1t；若x_w^*=0,则B计算${{r}_{w}}=\vartheta \left( n+1,n+2 \right)+{{\eta }_{w}}$,这里的η_w∈Z_p且由B随机选取,计算转换密钥$\begin{align} & \text{T}{{{\text{{K}'}}}_{w}}={{\left( e\left( {{C}_{n+1}},{{C}_{n+2}},T \right)g_{3}^{{{\eta }_{w}}} \right)}^{{{z}_{w}}}}= \\ & g_{3}^{\left( \vartheta \left( n+1,n+2 \right)+{{\eta }_{w}} \right){{z}_{w}}t}=g_{3}^{{{r}_{w}}{{a}_{w,1}}t} \\ \end{align}$。

② 或门。电线w∈Gates,满足GateType(w)=OR,且深度j=depth(w),若x_w^*=1,f_A(w)(x^*)=1或f_B(w)(x^*)=1,B随机选取μ_w,ν_w,r_w∈Z_p,转换密钥TK′_w为：

$\begin{align} & {{K}_{w,1}}=e\left( g_{1}^{{{\mu }_{w}}},T \right)=g_{2}^{{{\mu }_{w}}t} \\ & {{K}_{w,2}}=e\left( g_{1}^{{{\nu }_{w}}},T \right)=g_{2}^{{{\nu }_{w}}t} \\ & {{K}_{w,3}}=e\left( g_{j}^{{{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}}},T \right)=g_{j\text{+}1}^{t\left( {{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}} \right)} \\ & {{K}_{w,4}}=e\left( g_{j}^{{{r}_{w}}-{{\nu }_{w}}{{r}_{\text{B}\left( w \right)}}},T \right)=g_{j\text{+}1}^{t\left( {{r}_{w}}-{{\nu }_{w}}{{r}_{\text{B}\left( w \right)}} \right)} \\ \end{align}$

由于自下而上生成,r_A(w)和r_B(w)已经被B选择到对应的门,因此B可以生成K_w,3=e(C_n+1,C_n+2,…,C_n+j,T)^-b_wg_j+1^r_w。同理可得K_w,4=g_j+1^{t(r_w-ν_wr_B(w))}。

若f_w(x^*)=0,f_A(w)(x^*)=0且f_B(w)(x^*)=0,则B随机选取ψ_w,φ_w,η_w∈Z_p,设置μ_w=c_n+j+1+ψ_w,ν_w=c_n+j+1+φ_w,${{r}_{w}}\text{=}\vartheta \left( n+1,n+j+1 \right)+{{\eta }_{w}}$,转换密钥TK′_w为：

$\begin{align} & {{K}_{w,1}}=e\left( {{C}_{n+j+1}},T \right)g_{2}^{{{\psi }_{w}}}=g_{2}^{{{\mu }_{w}}t} \\ & {{K}_{w,2}}=e\left( {{C}_{n+j+1}},T \right)=g_{2}^{{{\nu }_{w}}t} \\ & {{K}_{w,3}}=e{{\left( {{C}_{n+j+1}},{{g}_{j-1}},T \right)}^{-{{\eta }_{\text{A}\left( w \right)}}}} \\ & e{{\left( {{C}_{n+1}},{{C}_{n+\text{2}}},\cdots ,{{C}_{n+j}},T \right)}^{-{{\psi }_{w}}}}\centerdot g_{j+1}^{{{\eta }_{w}}-{{\psi }_{w}}{{\eta }_{\text{A}\left( w \right)}}} \\ & =g_{j\text{+}1}^{t\left( {{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}} \right)} \\ \end{align}$

同理可得K_w,4=g_j+1^{t(r_w-μ_wr_B(w))}。

按照自下而上的顺序,由挑战者B设置电线w的第一个输入为${{r}_{\text{A}\left( w \right)}}=\vartheta \left( n+1,n+j \right)+{{\eta }_{\text{A}\left( w \right)}}$,同样设置第二个输入为${{r}_{\text{B}\left( w \right)}}=\vartheta \left( n+1,n+j \right)+{{\eta }_{\text{B}\left( w \right)}}$,故有

$\begin{align} & {{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}}=\left( \vartheta \left( n+1,n+j \right)+{{\eta }_{\text{B}\left( w \right)}} \right)- \\ & \left( {{c}_{n+j+1}}+{{\psi }_{w}} \right)\left( \vartheta \left( n+1,n+j \right)+{{\eta }_{\text{A}\left( w \right)}} \right) \\ & ={{\eta }_{w}}-{{c}_{n+j+1}}{{\eta }_{\text{A}\left( w \right)}}-{{\psi }_{w}}\left( \vartheta \left( n+1,n+j \right)+{{\eta }_{\text{A}\left( w \right)}} \right) \\ \end{align}$

③与门。电线w∈Gates,满足GateType(w)=AND,且深度j=depth(w)。若f_w(x^*)=1,f_A(w)(x^*)=1且f_B(w)(x^*)=1,B随机选取μ_w,ν_w,r_w∈Z_p,r_A(w)和r_B(w)是由B选择的随机值。转换密钥TK′_w为:

$\begin{align} & {{K}_{w,1}}=e\left( g_{1}^{{{\mu }_{w}}},T \right)=g_{2}^{{{\mu }_{w}}t} \\ & {{K}_{w,2}}=e\left( g_{1}^{{{\nu }_{w}}},T \right)=g_{2}^{{{\nu }_{w}}t} \\ & {{K}_{w,3}}=e\left( g_{j}^{{{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}}},T \right)=g_{j\text{+}1}^{t\left( {{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}} \right)} \\ & {{K}_{w,4}}=e\left( g_{j}^{{{r}_{w}}-{{\nu }_{w}}{{r}_{\text{B}\left( w \right)}}},T \right)=g_{j\text{+}1}^{t\left( {{r}_{w}}-{{\nu }_{w}}{{r}_{\text{B}\left( w \right)}} \right)} \\ \end{align}$

若f_w(x^*)=0,讨论f_A(w)(x^*)和f_B(w)(x^*)的值是否为0。

如果f_A(w)(x^*)=0,那么B随机选取ψ_w,φ_w,η_w∈Z_p,设置${{r}_{w}}\text{=}\vartheta \left( n+1,n+j+1 \right)+{{\eta }_{w}}$,转换密钥TK′_w=(K_w,1,K_w,2,K_w,3)分别为:

$\begin{align} & {{K}_{w,1}}=e\left( {{C}_{n+j+1}},T \right)g_{2}^{{{\psi }_{w}}}=g_{2}^{{{\mu }_{w}}t}, \\ & {{K}_{w,2}}=e\left( {{C}_{n+j+1}},T \right)=g_{2}^{{{\nu }_{w}}t} \\ & {{K}_{w,3}}=e{{\left( {{C}_{n+j+1}},{{g}_{j-1}},T \right)}^{-{{\eta }_{\text{A}\left( w \right)}}}} \\ & e{{\left( {{C}_{n+1}},{{C}_{n+\text{2}}},\cdots ,{{C}_{n+j}},T \right)}^{-{{\psi }_{w}}}}\centerdot \\ & e{{\left( {{C}_{n+1}},{{C}_{n+\text{2}}},\cdots ,{{C}_{n+j}},T \right)}^{-{{\psi }_{w}}}}\centerdot g_{j+1}^{{{\eta }_{w}}-{{\psi }_{w}}{{\eta }_{\text{A}\left( w \right)}}-{{\phi }_{w}}{{r}_{\text{B}\left( w \right)}}}= \\ & g_{j\text{+}1}^{t\left( {{r}_{w}}-{{\mu }_{w}}{{r}_{\text{A}\left( w \right)}}-{{\nu }_{w}}{{r}_{\text{B}\left( w \right)}} \right)} \\ \end{align}$

无论是否f_B(w)(x^*)=1,挑战者B总能够计算出g_j+1^r_B(w)。如果f_B(w)(x^*)=0,那么B设置r_B(w)为r_B(w)=(c_n+1,c_n+j)+η_B(w),故可以计算出e(C_n+1,C_n+2,…,C_n+j,T)g_j+1^-η_B(w)=g_j+1^r_B(w)。

因为f(x^*)= f_n+q(x^*)=0,r_n+q为输出门,挑战者B设置${{r}_{\text{B}\left( w \right)}}=\vartheta \left( {{c}_{n+1}},{{c}_{n+j}} \right)+{{\eta }_{\text{B}\left( w \right)}}$。将密钥碎片分级生成到输出门后,将最终计算出的部分解密密钥SK₁=g_l+1^t(α-r_n+q)以及转换密钥TK=(f,{K_w}_{w∈{1,2,…,n+q}})给A。

挑战阶段 输入电路结构f,A发送两个长度相等的挑战明文M₀^*,M₁^*∈G_k给B。B随机选择b∈{0,1},计算C₁^*=g^s,利用生成部分挑战密文C′^*=H(Q_be(,ε,C₁,C₂,…,C_n,g_l^ξ))⊕$M_{b}^{*}=H\left( {{Q}_{{\bar{b}}}}g_{k}^{\xi \bar{s}\vartheta \left( 1,n \right)} \right)$⊕M_b^*,则挑战密文CT^*=(x^*,C′^*,C^*),将CT^*传递给A。

猜测阶段 B最终从A获得对b的猜测,当i=n+p,即电路为输出电路时,随机选择η_n+p,计算${{r}_{n+p}}\text{=}\vartheta \left( n+1,n+l+1 \right)+{{\eta }_{n+p}}$,若得到$\nabla =g_{k}^{s\prod\limits_{j=1}^{k}{{{C}_{j}}}}$,那么有式(1)$g_{k}^{t\left( \alpha -{{r}_{n+q}} \right)s\delta \left( x \right)}=g_{k}^{t\left( \varepsilon +\prod\limits_{i=n+1}^{n+l+1}{{{C}_{i}}}-\left( \vartheta \left( n+1,n+l+1 \right)+{{\eta }_{n+p}} \right) \right)s\delta \left( x \right)}=g_{k}^{t\left( \varepsilon -{{\eta }_{n+q}} \right)s\delta \left( x \right)}$,式(2)$\text{S}{{\text{K}}_{\text{1}}}=e\left( g_{\text{1}}^{t},g_{l}^{\alpha }g_{l}^{-{{r}_{n+q}}} \right)=g_{l+1}^{t\left( \varepsilon -{{\eta }_{n+q}} \right)}$,如果Δ是随机的群元素,那么式(1)、式(2)不成立。如果b=b′,则B输出b′=1,进行猜测$\nabla =g_{k}^{s\prod\limits_{j=1}^{k}{{{C}_{j}}}}$;否则输出b′=0,猜测Δ为随机的群元素。如果存在这么一个攻击者A,可以用概率为$\partial $的优势攻破本文方案,那么有$\Pr \left[ \left( \left\{ {{g}^{{{C}_{i}}}} \right\}_{i=1}^{k},\nabla ={{Q}_{\text{0}}} \right)=1 \right]=\partial +1/2$,若Δ为随机的群元素,那么敌手A无法区分出关于明文的任何信息,也就有$\Pr \left[ \left( \left\{ {{g}^{{{C}_{i}}}} \right\}_{i=1}^{k},\nabla ={{Q}_{1}} \right)=1 \right]=1/2$。故A以不可忽略的概率攻破本文方案等价于攻破k-MDDH困难性假设。证毕。

3.3 效率分析

整个算法在通信过程中,影响效率的主要因素是通信量和运算量,效率分析也从这两个方面进行对比。为了便于描述,令n和q分别表示输入个数和门的数量，用|G|表示群G中元素的长度,用|Z|来表示有限域Z_q^*中元素的长度。

1) 通信量分析。

通信量的分析主要通过对比各方案中公共参数、私钥、密文的大小来体现,具体比较如表 1所示。

通过对比,可得本文方案将私钥量减少为|G|+|Z|,私钥长度较短且固定,方案中的转换密钥量为(n+4q)|G|,部分私钥SK₁的大小为|G|,KGC传递给用户的密钥量为二者之和,即为(n+4q+1)|G|,故KGC实际传递的密钥量与文献^[17]持平。在公共参数长度上,本文方案与文献^{[13, 17]}相比,持平或略有降低,与文献^{[10, 15, 12]}对比,分别有n|G|和(n-3)|G|的增加,但该环节的通信主要由密钥生成中心执行,故对加解密用户效率上的影响较小。

本文方案中密文量为|G|+|Z|,为使密文量对比更加直观,结合具体数值对其进行分析,这里以椭圆曲线中的标准参数设置^[25]为依据,令|Z|=192b,|G₁|=384b,其他群G_i中元素的长度参照该值计算(公共参数的量和私钥量也可采用此法直观比较,不再赘述)。将本文方案与其他方案的密文量对比如表 2所示。

由表 2可知,当对参数合理取值后,本文的密文量最小且恒定为576b。本文方案与其他方案相比的密文量减少率如表 3所示。

由表 3可清晰发现本文方案在密文量方面与已知方案对比,最小减少了25%,有效降低了密文的通信和存储代价。

2) 运算量分析。

本文涉及众多类型的运算,其中多线性映射运算的代价最高,且远远大于指数及标量乘运算,故主要比较多线性映射运算的次数来体现运算量的大小。这里列出各方案中密钥生成、加密、解密时的运算量,具体比较如表 4所示。

通过表 4中数据可得,本文方案密钥生成算法的运算量与其他方案相比，基本持平或略有降低,加密算法的运算量持平。解密算法的运算量有大幅降低,其多线性运算的次数仅为常数3,在同类方案中解密效率最高,体现了引入云服务外包解密后,用户在解密效率上的巨大提升。随着电路结构复杂度的提高,n和q的值逐渐加大,其他方案用户的解密代价呈线性增长,而本文方案仍保持不变,故解密优势更加明显(Attrapadung方案^[12]和Garg方案^[13]以牺牲效率为代价换取安全性上的提高,故本文方案效率更高)。

4 结语

本文结合云计算所提供的外包服务,提出了一种基于多线性映射的外包属性加密方案,并在标准模型中,利用k-MDDH假设,证明了方案在选择属性下的安全性。该方案与已有方案相比,私钥由用户和密钥生成中心共同完成,降低了私钥对KGC的依赖,有效缓解了密钥托管问题；密文量和私钥量都固定且有明显降低,设置合理参数后,其密文量降低25%,有效节约了密文和私钥的通信、存储代价,解密时多线性运算次数为3,解密效率远高于其他方案,且随着属性的增多,电路结构逐渐复杂,方案的解密优势更加明显,该方案适用于计算能力有限的小型移动设备。