一种基于多服务器的安全可搜索加密方法

吴 凯,王海江,魏贵义,陈 力

(1.浙江科技学院 a.机械与能源工程学院;b.信息与电子工程学院,杭州 310023;2.浙江工商大学 计算机与信息工程学院,杭州 310018)

随着网络中群体协作工作活动的增多,如多人协作、云存储共享、远程会议等,用户对云存储数据的安全性和可靠性有了更高的要求。由于公有云中的加密文件具有机密性和完整性,服务器无法直接为用户检索到指定文件,因此数据的可用性大大降低。为解决这一难题,通常采用可搜索加密(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)假设证明了其安全性。

1 预备知识

1.1 双线性映射

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

1)双线性,对于∀u、v∈G,a、b∈Zp(Zp表示所有素数),都有e(ua,vb)=e(u,v)ab=e(ub,va)成立;

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

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

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

1.2 复杂性假设

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

假设存在一个算法B,G是阶为素数l的双线性群,e:G×G→G3,g和h是G的两个独立生成元,记yg,α,l=(g1,g2,…,gl,gl+2,…,g2l)∈G2l-1,其中gi=gαi,α为未知数。

|Pr[B(g,h,yg,α,l,e(gl+1,h))=0]-Pr[B(g,h,yg,α,l,Z)=0]|≥ε。

(1)

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

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

1.3 基于聚合签名的广播机制

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

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

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

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

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

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

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

2 模型定义

2.1 方案模型

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

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

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

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

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

5)关键字加密:输入公钥(R,A)及关键字w,输出Iw=;

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

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

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

2.2 安全模型

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

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

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

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

3 具体方案

3.1 基本思想

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

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

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

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

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

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

3.2 方案描述

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

1)生成系统参数Kparm←(1λ):向群配对生成函数Pairgen输入安全一个参数1λ,即Ppair(1λ),生成一个双线性元组γ=(p,G0,G1,e0)。随机选择x′∈G0,并且X=(x1,x2,…,xk),xi∈G0,k为一固定值。系统公开参数设置为:Kparm=(γ,g0,x′,X)。

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

e0(σj,i,g0)·e0(Rj,f(Iidi))=Aj。

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

4)用户私钥生成ksigi←(R,A,f(Iidi)):通过既定的广播信息σj,i,每个用户Ui计算个人私钥ksigi,

同时验证该私钥是否满足

e0(ksigi,g0)·e0(R,f(Iidi))=A。

(2)

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

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

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

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

(3)

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

3.3 正确性证明

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

(4)

证明:

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

3.4 叛逆者追踪

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

e0(ksig,g0)·e0(Ri,f(Iidi))=Ai。

(5)

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

3.5 安全性证明

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

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

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

1)挑战者C随机选择一个向量Y=(y1,y2,…,yk),yi∈Zp,令g0=g,x′=gn,X=(x1,x2,…,xk),xi=(gyi),其中i∈{1,2,…,k}。输入系统安全参数λ,调用Pairgen(1λ)函数,生成公开参数Kparm=(p,G,GT,e0,x′,X),并将参数交给攻击者B;

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

计算

于是有

对i≠i*,计算

于是,就可以得到

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

e0(σj,i,g)·e0(Rj,f(Iidj))=Aj。

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

那么

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

Tr=(ksigi)H(w)s。

6)攻击者B输出对具体值b的猜测b′,如果挑战者C判别出b′=b,则Z=e0(gn+1,h)。令h=gt,如果Z=e0(gn+1,h)成立,则有

3.6 性能分析

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

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

4 结 语

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