随着网络中群体协作工作活动的增多,如多人协作、云存储共享、远程会议等,用户对云存储数据的安全性和可靠性有了更高的要求。由于公有云中的加密文件具有机密性和完整性,服务器无法直接为用户检索到指定文件,因此数据的可用性大大降低。为解决这一难题,通常采用可搜索加密(searchable encryption,SE)^[1]方法,即数据拥有者将文件及关键字进行加密后上传至云服务器中,当数据使用者需要获取包含某一关键字的文件时,可通过数据拥有者提供的搜索密钥生成令牌递交给服务器进行搜索。该方法由于搜索密钥长度会随文件数量而线性增长,因此无法控制其存储成本。密钥聚合可搜索加密机制(key-aggregate searchable encryption,KASE)^[2]的提出,较好地解决了搜索密钥过多的问题,但由于搜索密钥需要由数据提供者授权,因此无法适用于多用户群协作场景中。基于多用户的可搜索加密^[3-5]方法和群组密钥协商^[6]机制能够为多用户的分享提供支持,数据使用者仅需一个搜索密钥即可搜索多个分享者所提供的加密数据,但这两种方法的缺点是搜索令牌与关键字不具备隐秘性和可靠的安全性^[7],且保密性差,易泄露,容易被他人获取和攻击。Wang等^[8]提出的一种安全的KASE方法能够抵御密钥提取攻击,虽然提高了密钥的安全性,但没有解决群用户间的协作共享和叛逆者可追踪的问题。而在密钥生成过程中,采用非对称群组密钥协商(asymmetric group key agreement,ASGKA)机制^[8]并加入群组用户的身份信息^[10-11],可实现对群组中泄露密钥的用户进行追踪,但无法实现抵御服务器的叛逆。因此,本研究针对现有的可搜索加密技术中存在的问题,采用非对称群组密钥协商协议^[8]和双线性配对方法^[12],构造了一种基于多服务器场景下的加密关键字搜索(multi-server searchable encryption,MSSE)技术。通过关键字与私钥融合,构造搜索令牌,保证了关键字与令牌的隐秘性,实现群用户的身份对等和服务器的可搜索加密; 同时利用多服务器的构造方式,不仅能够对叛逆者进行追踪,还降低了服务器叛逆的风险; 最终通过双线性迪菲-赫尔曼指数(bilinear diffie-hellman exponentiation,BDHE)假设证明了其安全性。

双线性映射定义^[12]为:假定G₁、G₂是两个阶为素数l的乘法循环群,u∈G₁,v∈G₂,且u、v分别是G₁和G₂的生成元。若有双线性配对映射e:G₁×G₂→G₃,则e需要满足以下条件:

1)双线性,对于u、v∈G,a、b∈Z_p(Z_p表示所有素数),都有e(u^a,v^b)=e(u,v)^ab=e(u^b,v^a)成立;

2)非退化性,即e(u,v)≠1成立;

3)可计算性,存在某一算法,在有效时间内计算出G₁×G₂。

通常情况下,如果G₁=G₂=G,则认为配对线性映射e(·,·)是对称的,即e(u,v)=e(v,u)。这是因为对一个生成元g∈G而言,存在整数p、q∈Z_p,满足u=g^p,v=g^q。因此e(u,v)=e(g^p,g^q)=e(g,g)^pq=e(g^q,g^p)=e(v,u)。

本研究提出的多服务器下的关键字可搜索方法的安全性验证,是基于判定性l阶BDHE来证明的,其描述如下:

假设存在一个算法,G是阶为素数l的双线性群,e:G×G→G₃,g和h是G的两个独立生成元,记y_g,α,l=(g₁,g₂,…,g_l,g_l+2,…,g_2l)∈G^2l-1,其中g_i=g^αi,α为未知数。

式(1)中:P_r为概率函数; Z为G₃中任意一个元素; ε为一定值。

若式(1)成立,则算法有ε的优势来解决判定性l-BDHE假设,算法的输出值为b∈{0,1}。若不存在一个算法,在多项式时间内以至少ε的优势解决l-BDHE假设,则认为l-BDHE假设成立。

基于聚合签名的广播方法(aggregatable signature-based broadcast,ASBB)^[8],既是一种广播方法也是一种认证签名的方法。ASBB利用了解密密钥与签名的二重性和基于认证方式的加密方法,其过程包含了6个多项式时间算法,即系统参数生成、密钥生成、签名、认证、加密和解密算法,算法描述如下:

1)初始化π←λ,输入安全参数λ,输出公共参数π;

2)密钥生成(k_pub,k_sig)←π,输入公共参数π,输出公钥和私钥对(k_pub,k_sig);

3)签名σ←(k_pub,k_sig,s),输入密钥对(k_pub,k_sig)和字串s,输出签名消息σ(s);

4)验证签名(0,1)←(k_pub,σ),输入公钥k_pub和签名消息σ(s),输出0或1,签名认证成功时,输出1,并保留签名信息σ(s),否则退出;

5)加密C_m←(k_pub,m),输入公钥k_pub和需要加密明文m,输出加密后的密文C_m;

6)解密m←(k_pub,σ,C_m),输入公钥k_pub,有效的签名串σ(s)和密文C_m,解密输出明文m。

本研究提出的基于多服务的可搜索加密方法MSSE由8个多项式时间算法构成。

1)初始化系统参数:输入安全参数λ,输出公共参数K_parm;

2)群组密钥协商:利用群协商算法,生成用户身份索引I_id作为输入,输出广播消息(R_i,A_i,{σ_i,j});

3)群组公钥生成:将用户广播消息作为输入,输出群组公共密钥(R,A);

4)用户私钥生成:群组中每个用户i输入公钥(R,A),输出用户私钥k_sig,并验证其私钥的正确性;

5)关键字加密:输入公钥(R,A)及关键字w,输出I_w=<C₁,C₂,C₃>;

6)访问令牌生成:输入用户k_sig和所查找关键字w,输出搜索令牌T_r;

7)服务器匹配令牌:主服务器和辅助服务器分别计算用户提交的令牌消息T_r和参数信息,并遍历服务器所有文件的关键字;

8)返回结果:主服务器计算验证T_r与系统中存储的加密关键字是否匹配,并返回给用户{0,1},0表示未找到包含该令牌关键字的文件,1表示找到包含该令牌关键字的文件。

本研究为MSSE方法定义了一个安全模型,在这个模型中首先要保证加密关键字I_w的设计是安全的,即当I_w上传到服务器后,任何用户无论何种情况下均无法获知关键字w的明文信息。设定攻击者B能够以B_adv的优势获得关键字w的搜索令牌T_w,且攻击者B在没有获取到令牌前无法区分出I_w0和I_w1。下面将通过挑战者C和攻击者B之间的游戏规则,来定义MSSE方法的安全性。挑战者C表示利用MSSE方法所建立的系统,攻击者B表示对该系统进行的攻击行为。

1)初始化:挑战者C通过P_airgen函数算法生成公共参数K_parm;

2)训练:当B询问用户U_i信息时,C使用群组密钥协商协议算法,输出公共参数和群组公钥,并交给B。攻击者B可向挑战者C索要任意用户U_i的搜索令牌I_w;

3)挑战:攻击者B向挑战者C发送两个准备挑战的关键字w₀和w₁。设定攻击者B在挑战前未向C索要过关于w₀和w₁的令牌T_w1和T_w2。挑战者C随机选择一个关键字w_b,加密得到I^*_wb后交给B,其中b∈{0,1};

4)再训练:攻击者B仍然可以继续向C索要组中任意用户任意关键字的令牌T_w,但此时的关键字w≠{w₀,w₁};

5)输出:攻击者B输出b'∈{0,1},作为对C输出结果的猜想。如果b=b',则攻击者B将以B_adv=|P_r[b=b']-1/2|的优势赢得了这场游戏。

图1 可搜索加密示意图
Fig.1 Schematic diagram of searchable encryption

在群协作活动中,用户需要将自己的数据共享给同组的其他用户,同时要求数据内容不会直接暴露给无关的第三者,因此通常采用可搜索加密(SE)方法。如图1所示,用户将共享文件及关键字进行可搜索加密后上传至服务器中,其他用户通过关键字令牌向云服务器请求相应文件。一般情况下,用户通过令牌算法将个人私钥与关键字进行运算生成令牌后递交云服务器,由服务器对令牌和存储的加密关键字进行匹配。如果令牌生成算法采用静态方法来实现,那么将面临着用户在搜索相同关键字时,每次所生成的搜索令牌也均相同,这对恶意攻击者而言,一旦获取解密密钥,即可破解任意加密文件。因此,令牌构造必须采用随机动态生成算法。本研究提出的MSSE方法,其基本思想如下。

首先,考虑到所构造的密钥必须方便群用户间加解密数据,因此采用ASGKA协议构建出群组协商密钥即共享密钥(R,A),便于用户使用共享密钥对原始文件进行加密,同时群组中每个用户U_i都可计算出此共享密钥对应的解密密钥k_sigi,用于解密出云服务器中的加密文件。

其次,由于云服务器存储的内容为加密文件,所以服务器在没有解密密钥的情况下无法为用户检索出其所需文件,即包含用户关键字的文件,因此云服务器的可用性大为降低。为解决这一问题,本研究采用可搜索加密方式提取文件中关键字作为索引,进行加密设计。用户使用个人私钥k_sigi,与一个随机数s和关键字w进行运算,得到一个搜索令牌T_r,递交给服务器进行检索,服务器将接收到的令牌T_r和所存储文件中的加密关键字I_w进行遍历匹配运算,并告知用户检索结果。由于关键字长度可能不一,明文不能暴露,因此在构造T_r前,需要对关键字w进行哈希运算H(w),以保证关键字的隐私。该方式使得服务器可以在未知用户检索内容和所存储信息内容的情况下,实现可搜索加密内容,极大地提高了数据的可操作性。

通常情况下,如果群组中有用户泄露个人私钥,恶意攻击者将通过该私钥解密出加密文件,导致信息泄露。由于本研究采用非对称群组密钥协商,在设计群组公钥和私钥时,群组中每个用户都有唯一身份索引ID,一旦由用户泄露自己的私钥,群组中其他用户可通过该私钥反推出用户ID,锁定泄密者身份。同时,考虑到服务器可能产生叛逆,获取到用户私钥,云服务器中加密文件会暴露无遗,因此在多服务器上采用可搜索加密方法在很大程度上解决了服务器的叛逆性问题。

最后,基于此我们提出了多服务器下的安全可搜索加密方法。该方法实现了群组中叛逆者可追踪,同时可抵御单服务器的叛逆性问题,具有更高的安全性和可靠性。本研究所提出的MSSE方法是基于双服务器的安全搜索协作,即主服务器和辅助服务器共同完成加密搜索任务。其中主服务器用于存放用户存储的加密文件及文件关键字信息,具备计算匹配用户搜索令牌的功能; 辅助服务器用于存放文件关键字索引,协助主服务器计算关键字的匹配参数。

MSSE协议采用了双线性群的思想,首先构造群配对生成函数P_airgen,输入安全参数1^λ,输出元组γ=(p,g₀,G₀,G₁,e₀,H),其中G₀、G₁同是阶为素数p的循环群,g₀是G₀的生成元,映射e₀:G₀×G₀→G₁,H表示对明文的哈希运算。MSSE实现的具体流程如下。

1)生成系统参数K_parm←(1^λ):向群配对生成函数P_airgen输入安全一个参数1^λ,即P_pair(1^λ),生成一个双线性元组γ=(p,G₀,G₁,e₀)。随机选择x'∈G₀,并且X=(x₁,x₂,…,x_k),x_i∈G₀,k为一固定值。系统公开参数设置为:K_parm=(γ,g₀,x',X)。

2)群组密钥协商(Ri,Ai,{σi,j})←(Iid1,Iid2,…,Iidn):记群组中n个参与者,分别为U1,U2,…,Un,令Iid1,Iid2,…,Iidn表示每个用户的身份信息,其中Iidi=(si1,si2,…,sik),i=1,…,n。群组中每个用户Ui分别独立选择随机数ai、ri∈Zp,计算并广播Ri=g-ri0,Ai=e0(g0,g0)ai; 计算用户特征标识,即f(Iidj)=x',j=1,2,…,n; 计算每个用户身份Iidj信息的签名,即σi,j=gai0·fri(Iidj),j=1,2,…,n; 每个用户广播信息(Ri,Ai,{σi,j}j=1,2,…,n,j≠i)如以下矩阵所示:

3)群组公钥生成(R,A)←(R_i,A_i):为生成群用户的公钥,每个用户U_i应该先确认其n个信息-签名对是否有效,即验证下列等式是否成立,

e₀(σ_j,i,g₀)·e₀(R_j,f(I_idi))=A_j。

如果所有的信息-签名对均是有效的,则计算公钥(R,A),

。

4)用户私钥生成k_sigi←(R,A,f(I_idi)):通过既定的广播信息σ_j,i,每个用户U_i计算个人私钥k_sigi,

同时验证该私钥是否满足

e₀(k_sigi,g₀)·e₀(R,f(I_idi))=A。(2)

若式(2)成立,则接受该私钥k_sigi作为搜索密钥和解密密钥;

5)关键字加密I_w←(k_sigi,w,t,H):数据提供者随机选择t∈Z_p,对关键字w进行哈希运算H(w),并加密为I_w,

6)访问令牌生成T_r←(w,k_sigi,s):数据使用者U_i随机选择s∈Z_p,使用自己的私钥k_sigi生成关键字w的搜索令牌T_r=(k_sigi)^H(w)s,并将随机数分为s=s_main+s_aid,得到T_r,main=(T_r,s_main,f(I_idi)),T_r,aid=s_aid,将两个参数分别递交给主服务器和辅助服务器。

7)服务器匹配令牌(Cs2,Cs3)←(smain,said):辅助服务器接收到Tr,aid后,遍历计算文件关键字Csaid2和Csaid3,并将结果传递给主服务器。主服务器计算:

8)返回结果(0,1)←(I_w,T_r):主服务器判别下列等式是否成立,

e₀(T_r,C₁)·e₀(f(I_idi),C^s₂)=C^s₃。(3)

若式(3)成立,则表示搜索到加密关键字,并返回结果1; 否则,表示未查询到该加密关键字,返回结果0。

根据MSSE的方案描述,服务器在最终判别令牌T_r与存储的加密关键字I_w是否匹配需通过验证式(4)是否成立。

e₀(T_r,C₁)·e₀(f(I_idi),C^s₂)=C^s₃。(4)

证明:

结果显示服务器能够依据用户提供的检索令牌,匹配出服务器中对应的加密关键字,即验证了MSSE算法能够实现可搜索加密方法。

本研究可实现叛逆者追踪,如果群组中有参与者将个人私钥k_sig透露给攻击者,那么群中任何其他用户U_j均可通过计算式(5)来找出泄密者,

e₀(k_sig,g₀)·e₀(R_i,f(I_idi))=A_i。(5)

因此,通过遍历群组I_id,如果存在I_idi使式(5)成立,则群组中泄密者即为该用户。

定理 假设n-BDHE问题是难以解决的,则上述多服务器的可搜索加密方法是安全的。

假设 攻击者B在τ时间内以ε的优势攻破多服务器加密关键字搜索机制,那么就存在一个挑战者C可以在τ'=τ+O(n²τ_exp)时间内,以ε相同大小的优势解决判定性n-BDHE问题。

证明:创建一个参数为(g,h,g₁,…,g_n,g_n+2,g_2n,Z)的MSSE系统,作为挑战者C对n-BDHE问题的挑战。C的目标是通过扮演攻击者B来攻击n-BDHE假设,这场安全策略游戏过程如下:

1)挑战者C随机选择一个向量Y=(y₁,y₂,…,y_k),y_i∈Z_p,令g₀=g,x'=g_n,X=(x₁,x₂,…,x_k),x_i=(g^y_i),其中i∈{1,2,…,k}。输入系统安全参数λ,调用P_airgen(1^λ)函数,生成公开参数K_parm=(p,G,G_T,e₀,x',X),并将参数交给攻击者B;

2)挑战者C计算群组公钥,令

挑战者C随机选择i^*∈{1,2,…,n},a_i,r_i∈Z^*_p,令S^*_i=(1,…,i^*-1,i^*+1,…,n)。计算

对i≠i^*,计算

于是,就可以得到

因此,对于所有j≠i(i∈{1,2,…,n}),以下等式成立:

e₀(σ_j,i,g)·e₀(R_j,f(I_idj))=A_j。

3)挑战者C计算出群组公钥(R,A),并交给攻击者B,令

4)攻击者B可以尝试性地向挑战者C索要任何用户U_i所生成关键字w的令牌,即挑战者C可计算出

T_r=(k_sigi)^H(w)s。

5)攻击者B生成一对准备挑战的密文{w₁,w₂},挑战者C随机生成b∈{0,1},并计算出w_b加密后的信息I^*_wb,

I^*_wb=<C^*₁=h,C^*₂=h^rH(w_b),C^*₃=(Z·e₀(g,h)^a)^H(w_b)>。

6)攻击者B输出对具体值b的猜测b',如果挑战者C判别出b'=b,则Z=e₀(g_n+1,h)。令h=g^t,如果Z=e₀(g_n+1,h)成立,则有

由于a_i,r_i在Z^*_p上是均匀分布的,故攻击者无法区别出上述模拟过程与真实过程的差异,即两者是相同的,所以挑战者C能够以和攻击者B相同的优势来解决n-BDHE假设。故本方法是安全的。

从时间复杂性方面来分析本研究提出的MSSE方法,其主要计算成本在广播消息(R_i,A_i,{σ_i,j}_{j={1,2,…,n},j≠i})的生成和运算。计算σ_i,j需要O(n²)个双线性群G中的指数计算,而计算R_i、A_i分别需要O(n)个G中的指数计算。假设G中的一个指数计算的时间复杂性为τ_exp,那么MSSE方法的时间复杂性为τ'=τ+O(n²τ_exp),式中τ为系统原有的时间复杂性。同时,对现有的可搜索加密方法与本方法进行性能比较,结果见表1。

表1 MSSE方法与现有可搜索加密方法的功能对比
Table 1 Functional comparison between MSSE and existing searchable encryption approaches

本研究基于ASGKA协议提出了一个多服务器的安全可搜索加密方法MSSE,并验证了其正确性和安全性。选用双服务器的加密令牌匹配设计,提高了信息存储的安全性和加密搜索的安全性,解决了在单一的云存储服务器中由于服务器的叛变问题所导致云加密信息被攻击者破解的难题。关键字w的哈希运算加密和令牌的随机数构造,使得关键字和令牌也具备了安全性,无法被攻击者解密。因此,MSSE在服务器的叛变问题上具有较高的安全性,攻击者无法直接读取到用户请求的数据内容及明文信息; 同时,还可以对群组中密钥泄露者追踪,锁定其身份。