许盛伟　王荣荣　陈　诚

(西安电子科技大学通信工程学院　陕西 西安 710071) (北京电子科技学院　北京 100070)

0　引　言

在数据爆炸的当今社会，数据存储和共享的问题在云技术的来临后而得到了很好的解决。但弊端就是用户消息是明文存储，并没有进行加密保护，云存储管理员可以访问甚至获得用户的数据，这样给用户带来了很大的安全隐患。因此，目前部分云存储中心采用密文存储方式, 密文存储可以预防用户隐私泄露的风险，但是也存在问题。例如：如何实现在云服务器搜索后能找到想要的数据，且不在搜索过程中泄露数据信息内容。并且加密操作破环了原先明文数据的值以及大小关系等，其不再具有可供检索的语义和统计特性，为了解决这些问题，可搜索的加密技术逐渐产生，并引起了人们的广泛关注和大量研究。

Perrig等[1]率先提出可搜索加密技术的概念，正如字面所体现的那样，此技术不仅能实现加密，防止用户数据隐私的泄露，还能通过搜索获得加密数据，具有很好的应用行和适应性。但是存在的不足就是数据搜索者只能检索自己事先存在云上的密文数据。

Boneh等[2]在2004年使用匿名的基于身份的加密方式下设计出了公钥可搜索加密方案(PEKS)，可以实现对其他用户数据进行检索，并在邮件系统中具有很大的应用前景。Goh[3]通过把布隆过滤器运用到文件索引中，提出了Z-IDX方案。2011年Cao等[4]提出了支持多关键字排序的密文检索算法(MRSE)，使用向量内积实现对关键字的相似度进行排序，使得可搜索加密的发展又迈进了一步。

传统的可搜索加密方案几乎都是针对“一对一”[5]的通信方式，即关于关键词的密文与数据查询者是一对一的关系。这种方式很显然不适合关键词密文可被多个用户进行查询的情形。当存储在云上的数据资源想要分享给多个用户时，传统的做法只能是用每一个用户的私钥对数据进行加密。然后通过安全信道将不同的密文结果分别传送给不同的用户，用户通过关键字进行查询获得相应的检索结果。从中可以看出，在这种情况下使用传统的可搜索加密方案，不仅效率不高还会造成资源的浪费，不适合于实际中应用。

2005年Sahai等[6]提出了模糊的基于身份的加密，首次出现了“基于属性的加密(ABE)”这个概念。用户的身份不再使用传统的身份标识，而是将用户所具有的若干属性来表示其身份，这些属性可以使用“且、或、非”的关系联系在一起。基于属性加密(ABE)的实现往往有两种策略方式：一种是密文策略的基于属性加密(CP-ABE)，另一种是密钥策略的基于属性加密(KP-ABE)。2008年Goyal等[7]通过使用“访问树”[8]的概念将KP-ABE转化成CP-ABE，在CP-ABE中通过使用用户的部分属性指定一个访问结构，也就是访问树，然后以此访问结构对数据消息进行加密。在解密过程中，只要解密者具有的属性满足此访问结构就可以完成解密。2011年Waters[9]在标准模型下提出了一个CP-ABE系统，并证明了它在D-H假设下的安全性，在文献[10]中被证明是具有语义安全的。2014年李双等[11]构造了基于属性的可搜索加密方案(ATT-PEKS)，并给出了一致性分析和安全性证明。2016年谭彭超等[13]提出利用带计数器的布隆过滤器可以增加或删除关键字。

然而在上述的基于属性的可搜索加密方案中，文件明文的加密和关键字生成索引过程中都是使用了双线性对运算，增加了运算时间，而且文件的索引一旦生成将不能更改，限制了生成索引的灵活性。针对以上两个问题，本文提出了一种改进的基于属性的可搜索加密算法，文件明文仍使用ABE进行加密，索引和陷门采用对称加密的思想，并通过引入带计数器的布隆过滤器，实现关键字的更新。

1　基础知识

1.1　符号说明

表1　符号说明

1.2　定　义

定义1双线性群

设p、q是素数，G1、G2分别是阶为p、q的乘法循环群，双线性对映射e:G1×G1→G2。如果映射e满足下述性质：

(1) 双线性对于任意的a,b∈Zp和x,y∈G1都有e(xa,yb)=e(x,y)ab。

对于任意的x1,x2,y∈G1，有e(x1x2,y)=e(x1,y)e(x2,y)。

(2) 非退化性存在x,y∈G1使得e(x,y)≠1，其中1是G2的单位。

(3) 可计算性存在有效的多项式时间算法对任意的x,y∈G1，计算e(x,y)的值。

定义2[10]访问结构

P={P1,P2,…,Pn}为一个实体集合，A⊆2p是2p的一个非空子集，对于任意的B,C如果当B∈A且B⊆C时，有C∈A，那么称A⊆2p是单调的。一个访问结构A是P={P1,P2,…,Pn}的一个非空子集，即A⊆2p{Φ}。那么A的子集合称为授权集合，非A的子集合被称为非授权集合。

定义3[10]访问树

用T表示一颗访问树，树中的每个非叶子结点具有子节点和阈值的，用numx表示结点x的子结点的数目，用kx表示结点x的阈值，并且:0≤kx≤numx；当kx=1时，表示“或”门；当kx=numx时，表示“与”门。树中的每一个叶子节点表示一个属性，即kx=1。除此之外，parent(x)代表结点x的父结点。att(x)表示叶子结点x所代表的属性值。对树中每个结点的子结点进行编号1～num，其中编号的函数用index(x)来表示。

定义4[10]满足访问树

用T表示一颗访问树，其根节点用R来表示，那么访问树T可以表示成TR，则Tx表示以x为根结点的子树。当属性集合S满足访问树Tx时，就有Tx(S)=1。可以通过递归遍历的方式来计算Tx(S)的值。若x是叶子结点，当且仅当att(x)∈S时，有Tx(S)的值为1。若x是非叶子结点时，则计算它的所有子结点x′的Tx′(S)，那么至少有Kx的子结点值为1时，Tx(S)的值为1。

1.3　带计数器的布隆过滤器

布隆过滤器(Bloom Filter)是现在计算机中应用广泛的数据结构，它由一个很长的二进制向量(或者说是包含多位的位数组)和若干个独立的哈希函数组成，它通过使用哈希函数将一个元素映射到一个二进制向量中，可以用来检查元素是否属于此集合。其原理是位数组+K个独立的哈希函数，初始状态时，Bloom Filter是一个包含m位的全部为0的位数组，例如像S={x1,x2,…,xn}这样一个n个元素的集合，Bloom Filter使用K个相互独立的哈希函数，他们分别将集合中的元素映射到{1,2,…,m}的范围内，对任意一个元素x第i个哈希函数映射的位置hi(x)就会被置为1(1≤i≤k)。若一个位置经过映射被置为1，那么该位置的值就为1，后续操作将不再影响该位置的值，如图1所示。

图1　布隆过滤器结构

如果一个集合中的元素经过这些哈希函数的映射后的所有位都是1，那么就可以认为该元素是属于这个集合的，若存在映射后的位置不为1，也就是0，那么就判定此元素是不属于这个集合的。因为可能好几个关键字通过哈希函数会映射到同一个位置上变为1，删掉此关键字可能会影响其他的关键字，但是通过使用counting Bloom filiter就可以实现这个操作。

带计数器的布隆过滤器可以支持关键字的增加和删除操作，当多个关键字wi(i=1,2,…)通过k个相互独立的哈希函数映射到同一个位置时，对应位置的数将不再是1而是多个映射结果的和，其原理如图2所示。其中，x1,x2为原先已经存在的关键字，x3为向过滤器中新插入的关键字。

图2　带计数器的布隆过滤器结构

1.4　应用模型

本方案的应用模型为面向云存储的可搜索加密系统，主要适用的场景是存放公共通知、消息共享、电子邮件、电子公文等的云存储系统。云存储数据为容量小且安全性要求较高的应用云存储数据。系统包括第三方云存储服务器、数据拥有者以及数据检索者。数据拥有者先将文件进行加密然后选择关键字进行特定的处理后作为文件的加密索引，最后将加密索引和密文一同上传到云存储服务器。数据检索者如果想获得所需要的文件，那么在获得认证权限后，将要搜索的关键字通过特定方式生成查询向量，加密后生成查询陷门，并把陷门发送给云存储服务器，服务器在收到查询陷门后，通过查询机制返回给用户相应的密文文件。应用模型如图3所示。

图3　方案应用流程图

2　方案设计

2.1　数据拥有者使用ABE公钥加密算法加密文件

(1) 初始化：选取阶为素数p，生成元为g双线性群G1，随机选择α,β∈Zp。可得属性集加密算法的公钥为：PK←(G1,g,h=gβ,e(g,g)∂)主密钥为：MSK←(β,gα)。

(2) 产生私钥：把用户的属性集S和主密钥MSK作为输入，产生用户私钥为：

其中:r∈Zp,rj∈Zp。

(3) 密文的加密：使用公钥PK和访问树T加密文件明文消息M，得到密文E。

通过自上而下遍历的方式为访问树中的每个结点选择它的多项式qx，qx的阶数dx与这个结点的阈值kx需满足dx=kx-1。毋容置疑从根节点R进行qx的选择，任取s∈Zp，并令qR(0)=s，其他dR个点的值进行可以任取，那么通过kx个值就可以求得多项式qR。同理，使用相同的方法可以获得子结点的qx，qx(0)=qparent(x)(index)，树T中结点的集合用Y表示，所以，递归结束后文件密文为：

2.2　数据拥有者对关键字进行加密生成文件索引和陷门

下面使用带计数器的布隆过滤器采用对称加密的思想对关键字行加密，作为文件的索引，可以高效跟踪文件的关键字[14]。

(1) 生成对称密钥Sk={S,M1,M2}，m：布隆过滤器的数组长度。首先随机选择m+2维的矩阵M1、M2和长度为m+2的0、1字符串。

(4) 陷门匹配。将要搜索查询的陷门提交给服务器后，服务器将自动和数据库中的索引进行匹配，匹配过程如下：

Q′(I′)T+Q″(I″)T=

(r′Q,r′,t)·(I,εi,1)T=

r′(IQ+εi)+t

(5) 服务器返回结果。

(4)中r′(IQ+εi)+t越大，则服务器使用最大匹配的原则，根据相似度的匹配结果进行排序，返回排好序的文件。

2.3　对文件密文的解密运算

当用户接收到文件后，所要做的就是解密操作，对于基于属性加密的解密算法如下：

通过递归遍历的方式当输入密文E和一个结点x，当输出为群G2上的一个值时，结果正确，否则结果终止。

当x为叶子结点时，令i=att(x)，若i不属于用户私钥对应的属性集时，解密终止。若i是属于用户私钥对应的属性集时，解密如下：

e(gr,gqx(0))=e(g,g)rqx(0)

通过上述分析，我们得到了结点的解密方法DecryptNode。所以，当解密密文时，当解密密文时，只需要求出根结点R的DecryptNode值即可。所以，当TR(S)=1时，S为用户属性集合。得到DecryptNode(E,R)=e(g,g)rs，接下来就可以恢复明文了。

3　方案分析

3.1　正确性分析

若将{w1,w2,…,w6}的加密索引与{w7,w8,w9}的加密索引相加，其结果等同于{w1,w2，…,w9}的加密索引，现证明如下：

则：

当S[j]=0时，Q′[j]、Q″[j]、Q[j]三者相等，则：

Q[j]·(I[j]+Ii[j])T=QI

遍历每个j(j=0,1,…,m+1)，结果同样也为QI。

同理可证：当在关键字集中删除一些关键字时，结果也成立。

上述计算结果标明，利用带计数器的布隆过滤器产生的索引确实可以实现关键字的更新。

3.2　安全性分析

3.2.1关键字安全

当云存储服务器为“honest-but-curious”时，用户能够在服务器上进行检索。方案中，当用户在检索时关键字的门限值以及关键词索引都是通过布隆过滤器经过伪随机函数加密并填充后形成的向量，一个索引可以产生2(m+2)个未知量，M1、M2有2(m+2)2个未知量，所以服务器只能判断出该文件是否包含该关键字，但是却不能获得该关键字的具体信息。而且通过在末尾添加随机数可以达到一种混淆，预防了关键字数目的攻击。

3.2.2密文的保密性

3.2.3明文的保密性

3.3　效率分析

表2为几种方案与本文方案在计算过程中的运算代价比较。其中n代表属性中元素的个数，y代表hash函数个数，文献[10]是基于属性的加密方案，文献[12]是基于属性的可搜索加密方案。

表2　本文方案与原方案效率对比表

本文构造的方案与传统的PEKS(带关键词的公钥加密方案)一样，即需要存储文件密文还需要存储关键字索引。从运算时间上来看，现有的PEKS方案在加密文件和关键词以及服务器检索过程中大量使用双线性对运算。而本文提出的改进算法是在文件加密时使用了基于属性的双线性对运算，在关键字加密和生成查询向量过程中，使用了带计数器的布隆过滤器进行Hash运算以及向量的简单相乘运算，运算时间较少，索引向量和查询向量中的关键字数量对搜索时间几乎没影响。通过表2就可以看出，与文献[12]相比，本方案在双线性对运算和指数运算上，计算量减少。文献[10]只能实现对数据进行加解密，故计算量最少。本文方案与文献[10]相比，实现了密文的可搜索，对关键字和陷门进行了加密，但是计算量却是只有少许的增加，对运算时间几乎没影响。所以总体来说，本文方案节约了运算时间，提高了效率。

4　结　语

本文提出的改进算法借鉴了对称加密的思想，对文件进行了基于属性的公钥加密。通过发现文献[13]中的方案的算法错误，并进行了修改，将其应用到本方案中，在关键字加密以及生成陷门阶段，利用布隆过滤器并分裂生成索引向量和搜索查询向量。然后利用对称密钥进行加密生成加密索引和查询陷门，舍弃了先前使用的对关键字也使用公钥加密算法的思想，归避了使用双线性对运算。服务器在进行查询时，只需进行查询向量和加密索引的相乘运算即可，降低了服务器检索的时间消耗，提高了算法的执行效率。并且采用带计数器的布隆过滤器，允许用户对已构建的文件索引进行增加和删除，可以实现动态更新文件索引中的关键字，并保证了数据的隐私性。

在文件中对于明文的加密继续使用CP-ABE算法，将文件明文用访问树进行加密，即使服务器是不可信的，其数据也是安全的。所以，根据ABE加密算法可以实现一对多的通信优势，数据拥有者不用关心谁可以解密密文，只要解密者的私钥属性满足访问树即可。

[1] Song D X, Wagner D, Perrig A. Practical Techniques for Searches on Encrypted Data[C]// IEEE Symposium on Security and Privacy. IEEE Computer Society, 2000:44.

[2] Dan B, Crescenzo G D, Ostrovsky R, et al. Public Key Encryption with Keyword Search[M]// Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:506-522.

[3] Goh E J. Secure Indexes[J]. Submission, 2004.

[4] Cao N, Wang C, Li M, et al. Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data[J]. IEEE Transactions on Parallel & Distributed Systems, 2011, 25(1):222-233.

[5] 马明军, 杨亚涛, 王培东,等. 基于属性的可认证搜索加密方案[J].计算机工程与设计,2016,37(2):358-362.

[6] Sahai A, Waters B. Fuzzy Identity-Based Encryption[M]// Advances in Cryptology—EUROCRYPT 2005. Springer Berlin Heidelberg, 2005:457-473.

[7] Goyal V, Jain A, Pandey O, et al. Bounded Ciphertext Policy Attribute Based Encryption[M]// Automata, Languages and Programming. DBLP, 2008:579-591.

[8] 李新, 彭长根, 牛翠翠. 隐藏树型访问结构的属性加密方案[J]. 密码学报, 2016, 3(5): 471-479.

[9] Waters B. Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization[M]// Public Key Cryptography—PKC 2011. Springer Berlin Heidelberg, 2011:53-70.

[10] Bethencourt J, Sahai A, Waters B. Ciphertext-Policy Attribute-Based Encryption[C]// IEEE Symposium on Security and Privacy. IEEE Computer Society, 2007:321-334.

[11] 李双, 徐茂智. 基于属性的可搜索加密方案[J]. 计算机学报, 2014(5):1017-1024.

[12] 李双. 访问控制与加密[M]. 机械工业出版社, 2012.

[13] 谭彭超,张应辉,郑东.支持关键字更新的可搜索加密方案[J].桂林电子科技大学学报,2016,36(1):44-47.

[14] 李经纬, 贾春福, 刘哲理,等. 可搜索加密技术研究综述[J]. 软件学报, 2015, 26(1):109-128.