可验证混合存储属性基多关键字密文检索方案

曹素珍,杜霞玲,杨小东,刘雪艳,汪 锐

(西北师范大学 a.计算机科学与工程学院; b.数学与统计学院,兰州 730070)

0 概述

2000年,SONG等人[1]给出可搜索加密的概念,即加密方建立关键字安全索引并与数据密文存储到云服务器平台,用户可通过陷门查询包含关键字的密文数据,实现对密文数据的直接操作,但采用对称密钥加密数据,需专门的安全信道传输对称密钥。文献[2]改进了SONG等人的工作,采用解密方的公钥加密数据,无需专门的安全信道传输密钥。文献[3]在云环境下提出了支持多服务器多关键字的可搜索加密方案,多个服务器共同配合用户一次性提交的多个关键字搜索请求,提高了密文检索的效率。文献[4]提出了支持搜索结果验证的公钥可搜索加密方案,虽然该方案指出满足多用户请求的云存储环境,但公钥密码体制中每一对公私钥是对应的,公钥加密的数据仅由其对应的私钥才可解密,无法真正实现多用户间的数据共享。

2005年,SAHAI等人[5]给出了基于属性的加密方案，加密者用属性定义访问控制策略,并在密文中嵌入该策略，只有属性满足访问控制策略的用户,方可获得相应的数据,开启了研究多用户数据共享的新研究领域。文献[6]结合属性加密技术与可搜索技术,构造了基于属性的可搜索加密方案。文献[7-8]提出了可验证的属性基单关键字可搜索加密方案,但都无法抵抗关键字猜测攻击。文献[9-10]提出了能够有效抵抗关键字猜测攻击的属性基可搜索方案,但该方案未对检索结果进行验证。近年来,新的支持可验证的多关键字搜索的属性基可搜索加密方案相继被提出[11-12],但均未考虑属性钥失效的非法用户越权访问的问题。文献[13]提出了支持属性撤销的可搜索加密方案,但该方案计算开销过大。文献[14]提出了密文策略的属性撤销可搜索加密方案,但该方案的搜索时间与属性个数线性正相关。文献[15]在文献[13]的基础上改进了文献[14]的不足,但该方案需要完全可信的第三方验证搜索结果的正确性。

鉴于区块链技术具有防篡改、公开验证、去中心化等特点[16]。文献[17]提出了基于区块链的单关键字可搜索加密方案。文献[18-19]基于区块链构造了可搜索加密方案,但均不支持细粒度的用户访问。

本文提出一种混合存储属性基多关键字密文检索方案。通过将关键字索引与数据密文分别存储到区块链和云服务器上,使数据检索空间缩小,易于快速地在海量数据中查找所需数据，密钥加密后,即可在公开信道传输。在此基础上，通过属性版本号撤销用户,以防止属性变化身份失效的非法用户继续访问数据。

1 预备知识

1.1 符号说明

符号含义说明如表1所示。

表1 符号含义说明Table 1 Description of symbol meaning

1.2 双线性映射

设G1和GT分别是两个阶为素数p的乘法循环群,其中,g为G1的一个生成元,则双线性映射e:G1×G1→GT满足以下3个性质:

2)非退化性:e(g,g)≠1。

3)可计算性:对于群G1中的任意两个元素g1、g2,存在有效算法计算e(g1,g2)。

1.3 与门访问结构

在属性基密码体制中,与门访问控制策略通常被定义为用户属性与访问控制结构之间的关联关系,具体描述为:全局属性集合U={x1,x2,…,xn},访问控制结构At={At1,At2,…,Atn},当且仅当xi=Ati,i∈[1,n]时,称属性满足访问控制结构。

1.4 安全性理论假设

本文方案的安全性基于HDH问题、MDDH问题和CDH问题,具体定义如下:

2 基本方案

本文方案包含的实体主要有以下5个部分:

1)数据属主:用对称密钥加密文档,并上传到云服务器,提取关键字生成索引,并上传到区块链。

2)云服务器:只存储文档密文。

3)授权机构:生成系统公共参数和主密钥。

4)区块链:存储关键字索引信息,生成下载数据令牌。

5)数据用户:生成陷门值,解密相应文件。其中,云服务器是诚实但好奇的;区块链是完全可信的存储设备,方案中仅用于存储关键字索引。

具体的系统模型如图1所示。

图1 本文系统模型

3 具体方案

本文具体方案如下:

6)Search(InW,Tk)→I:区块链上的搜索者执行,输入搜索陷门Tk和索引InW。首先,搜索者通过式(1)检验陷门中用户身份与索引中用户身份是否相同;然后,通过式(2)检验陷门中关键字与索引中关键字是否相同;若式(1)和式(2)同时成立,则将I=(I1,I2,…,IN)返回给用户;否则输出⊥。

(1)

(2)

7)Dow(GP,I)→CT:云服务执行。输入公共参数GP、索引I。云服务器计算式Enck(di)=Ci⊕H5(IDdi)，并将所得结果Enck(di)返回给用户。

8)Verify(R,CT):用户输入CT和R,计算式(3)验证搜索结果的正确性,若等式成立转入步骤(9);否则,输出⊥。

(3)

9)Dec(CT)→(D):用户执行,输入搜索密文Enck(di),用户属性钥sk。首先,身份为IDui用户通过计算H1(F′H1(IDui)),恢复出Li=F″⊕H1(F′H1(IDui))。若用户的属性满足访问结构,则可通过式(4)计算得到E,进而通过式(5)和式(6)计算得到对称密钥k,解密出原始密文;否则终止算法。

(4)

(5)

(6)

4 安全性分析

4.1 抗用户合谋攻击

在用户的私钥中同时嵌入用户属性和用户版本号。因版本号的不同,即使拥有相同属性集合的用户,他们的私钥也不会相同。用户间私钥合谋生成搜索陷门,该陷门也无法通过区块链上搜索者的验证,用户间合谋也得不到额外信息,本文方案满足抗用户间的合谋攻击。

4.2 私钥传输

定理1若HDH问题是困难的,则本文方案私钥的传输无需安全信道。

证明根据HDH问题的定义:已知gv和gH1(IDui),在v和H1(IDui)未知的前提下,判断H1(gvH1(IDui))是否为群G中的元素是困难的。进而,求解私钥组件Li=sk2⊕H1(gvH1(IDui))是困难的,因此私钥的传输无需安全信道。

4.3 对称密钥安全性

文档上传云服务器前,先用传统的对称算法加密,再用属性加密算法加密对称密钥。本文方案基于MDDH问题确保对称密钥的安全性。

定理2若MDDH问题是困难的,则本文方案在随机预言模型下对称密钥是安全的。

证明挑战者B输入MDDH问题的实例(g,gπ,e(g,g)φ,Z)和群参数(g,p,e,G,GT),目标是计算Z=e(g,g)πφ挑战者B和敌手A进行如下游戏模拟:

初始化:A提交挑战访问结构A*=Λi∈IW*Ai给挑战者B,运行系统建立算法,将公共参数GP=返回给A。

4)H3询问:B维护一个初始为空的列表L3=。A向B询问R3∈GT的H3值,B首先查找R3是否在表L3中。若是,则将相应的h3值返回给A;否则随机选取d3∈{0,1}λ,令h3=d3,并添加到表L3中,然后发送h3给A。

5)H4询问:B维护一个初始为空的列表L4=。A向B询问R4∈{0,1}λ的H4值,B首先查找R4是否在表L4中。若是,则将对应的h4值返回A;否则随机选取d4∈{0,1}λ,令h4=d4,并添加到列表L4中,然后返回h4给A。

询问阶段1:

2)解密询问:敌手A做访问结构At*下的解密询问,B应答如下:

(1)若A的属性Atts满足访问结构At*,B以⊥应答;否则,转到步骤(2)。

询问阶段2:敌手A可以重复进行阶段1的询问。

猜测:A输出关于b的猜测b′∈{0,1},若b=b′,则B能判断出e(g,g)πφ=Z;否则e(g,g)πφ≠Z。

证毕。

4.4 陷门的不可区分性

定理3若CDH假设成立,则本文方案满足陷门的不可区分性。

证明假设存在一个多项式时间敌手A能够以不可忽略的优势εA攻破本文方案,则挑战者B可以利用A以不可忽略的优势εB解决CDH问题。

初始化:A向B提交要挑战的访问策略A*=Λi∈IW*Ai,其中IW*表示属性下标,即属性索引值。

建立阶段:挑战者B运行系统建立算法,输出公共参数GP。挑战者B通过抛掷硬币游戏选择ξ∈{0,1},如果ξ=1,则T=gabc;否则,T为群G中的一个随机值。

询问阶段1:

敌手A选择任意属性集Atts*和身份IDu*,进行密钥和陷门询问:

询问阶段2:敌手A可以重复进行阶段1的询问。

猜测:敌手A输出ξ对ξ′∈{0,1}的猜测。当ξ=ξ′时,挑战者B输出1,表示T=gabc;否则输出0,表示T是G中的随机值,挑战者解决困难问题的概率计算如下:

1)当输出为1时,表明敌手A得到关键字<ω0,ω1>的有效密文。此时,敌手A的优势为:εA=Pr[ξ′=ξ|T=gabc]=ε+1/2。

2)当输出为0时,表明T是群G中的一个随机值。此时,敌手A的优势为:εA=Pr[ξ′=ξ|T∈GT]=1/2。

根据步骤1)和步骤2)得出挑战者B的优势为:

因此,挑战者B能够以不可忽略的优势ε/2解决CDH问题。

5 性能分析

为更全面地阐述本文方案的性能,从功能特性、计算开销以及实验仿真等方面对比分析本文方案与具有代表性的支持属性撤销可搜索加密[13-15]方案的优劣势。

5.1 功能特征对比

从表2可以看出,相比于文献[13-15]方案,本文方案在支持用户撤销的基础上,加密了用户属性私钥,可使其在公开信道传输;同时,将索引和密文分开存储,易于提高检索效率。另外,相比于文献[13]方案,本文方案支持多个关键字同时检索,易于快速检索所需数据。其中,√为支持,×为不支持。

表2 功能特征对比

5.2 计算开销对比

通过理论数值分析,对比本文方案与文献[13-15]方案。假设关键字个数对计算开销的影响相同,仅考虑耗时长的指数运算和对数运算,忽略哈希运算和异或运算,对比结果如表3所示。其中:|U|代表全局属性个数;|S|代表用户属性个数;|R|代表满足搜索要求的密文文件数;E代表群G上的指数运算;ET代表群GT上的指数运算;P代表对数运算。

表3 计算开销对比

从表3中系统建立、密钥生成、加密、陷门生成、搜索等开销可以看出,本文方案和文献[15]方案均优于文献[13-14]方案;另外,本文方案的解密计算开销远远低于文献[14]方案,为恒定值。与文献[15]方案相比,本文方案系统建立开销与用户个数线性相关,但本文方案的密钥生成、加密及陷门生成开销低于文献[15]方案,搜索开销高于文献[15]方案,但也为恒定值。

5.3 实验仿真

实验环境为:Intel®CoreTMi5-2400 @ 3.10 GHz的处理器、4 GB的内存、Windows10 x64的操作系统,调用jpbc-2.0.0库。设定关键字空间大小为1 000,用户属性个数取10、20、30、40、50、60。数值模拟对比本文方案与文献[13-15]的加密和搜索阶段的时间开销。实验结果如图2、图3所示。

图2 加密时间与属性个数的关系

图3 搜索时间与属性个数的关系

从图2可以看出,文献[13-15]方案的加密时间开销,随着属性个数的增加线性增长，而本文方案加密阶段采用耗时少的哈希函数运算、异或运算,并对用户属性进行聚合,使得加密时间恒定,与属性个数无关。从图3可以看出,文献[13-14]方案的搜索时间与属性个数正相关,而本文方案和文献[15]方案的搜索时间恒定,与理论分析结果保持一致。

6 结束语

云服务器在属性基可搜索加密方案中执行关键字搜索、用户撤销等操作时,存在搜索效率低、用户隐私泄露等问题。本文通过引入区块链技术,将属性可搜索加密中的索引与密文文档分开存储,同时对密钥进行加密,使其在公开信道传输。此外,在密钥中同时嵌入用户版本号和用户属性,及时撤销由属性变化引起用户身份失效的非法用户,防止隐私泄露。效率分析结果表明,该方案搜索时间与属性个数无关。下一步将在区块链环境下,通过隐藏访问策略实现属性基可验证的多关键字密文搜索。