基于字典分级和属性加权的密文排序检索方案.pdf

第41卷第2期2024年3月新疆大学学报（自然科学版中英文）Journal of Xinjiang University(Natural Science Edition in Chinese and English)Vol.41,No.2Mar.,2024基于字典分级和属性加权的密文排序检索方案王 娟，努尔买买提黑力力(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 830017)摘要：可搜索加密支持用户在不解密原始数据的前提下对加密数据执行检索操作.现有的多关键词排序可搜索加密方案,其索引和陷门构建的时间成本通常依赖于由全局关键词字典张成的向量空间.为了减少用户端的计算开销和通信成本,进一步提升数据使用者对检索结果的满意度,提出了一种支持细粒度访问控制的多关键词密文排序检索方案.该方案首先设计基于互信息的字典剥离机制差异化全局字典中的关键词,得到两个信息量不同的附属子字典,进一步在低维子字典空间上生成索引和陷门;其次,引入文档访问策略中属性的权重,将其作为排序标准之一,使数据使用者获得更为相关的结果;最后,检索时利用筛选向量对数据进行初次过滤并借助属性匹配完成二次剔除,从而避免检索过程中不必要的计算.关键词：可搜索加密;多关键词排序检索;安全 K-近邻算法;字典分级;属性加权DOI：10.13568/ki.651094.651316.2023.02.11.0002中图分类号：TP309文献标识码：A文章编号：2096-7675(2024)02-0246-011引文格式：王娟，努尔买买提黑力力 基于字典分级和属性加权的密文排序检索方案J 新疆大学学报(自然科学版中英文)，2024，41(2)：246-256英文引文格式：WANG Juan，NUERMAIMAITI HeililiCiphertext ranked search scheme based on dictionaryclassification and attribute weightingJJournal of Xinjiang University(Natural Science Edition in Chinese andEnglish)，2024，41(2)：246-256Ciphertext Ranked Search Scheme Based on DictionaryClassification and Attribute WeightingWANG Juan,NUERMAIMAITI Heilili(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)Abstract：Searchable encryption supports users to perform search operations over encrypted data withoutdecrypting the original data.The time cost of index and trapdoor construction of existing multi-keyword rankedsearchable encryption schemes usually depends on the vector space formed by the global keyword dictionary.Toreduce computation overhead and communication cost on the users side and further enhance users satisfactionwith search results,this paper proposes a multi-keyword ranked search scheme that supports fine-grained accesscontrol.The scheme first designs a dictionary-stripping mechanism based on mutual information,through which thekeywords in the global dictionary are differentiated into two subsidiary sub-dictionaries with different informationentropy,which further generates indexes and trapdoors in the low-dimensional sub-dictionary space.Secondly,theweight of attributes in the document access policy is considered as one of the ranking criteria so that data usersachieve more relevant results.Finally,the filtering vector filters the data for the first round,and the attributematching is used to complete the second round of elimination to avoid unnecessary computation during the search.Key words：searchable encryption;multi-keyword ranked search;secure K-nearest neighbor algorithm;dictionaryclassification;attribute weighting收稿日期：2023-02-11基金项目：国家自然科学基金“基于密码的外包数据访问控制中的防信息推理研究”（61862059）作者简介：王娟（1995），女，硕士生，从事信息安全与密码学的研究，E-mail：通讯作者：努尔买买提黑力力（1976），男，博士，教授，主要从事信息系统安全、访问控制、云存储安全等的研究，E-mail：第2期王 娟，等：基于字典分级和属性加权的密文排序检索方案2470引 言随着云计算的普及,越来越多的公司和个人通过将海量的隐私数据加密后放置在云端以实现综合成本代偿.可搜索加密技术1的出现为密文数据的检索问题提供了一种可行的解决思路.Cao等2将文档向量和检索向量分别刻画成二进制向量,并基于坐标匹配和安全K-近邻算法(K-Nearest Neighbor,KNN)实现了加密云数据上的多关键词排序检索,为后续可搜索加密在多关键词排序检索方面的发展奠定了基础.相较于文献2中对向量的二进制描述,Sun等3通过引入带余弦相似性度量的词频-逆文档频率向量空间模型,获得了更为准确的检索结果.Fu等4实现了加密云数据上的多关键词排序并行检索.Xia等5设计了一种支持多关键词排序和文档增删改等动态更新操作的方案.Zhang等6提出允许用户进行协作式个性化检索方案,有效缓解了云服务器的性能瓶颈.Li等7结合基于多项式的访问策略和改进的安全KNN算法提出了一种高效且保护隐私的多关键词排序检索方案.Fu等8构造了一种基于中心关键词的语义扩展排序检索方案,在检索功能和效率之间取得了良好的平衡.杨旸等9将域加权评分引入文档评分中,并通过创建标记向量,实现了快速的多关键词语义排序检索.徐光伟等10设计了一种支持语义扩展的可搜索加密方案.Zhang等11消除了传统模糊检索方案中需预定义相似度阈值的局限性.Tahir等12基于概率陷门设计了一种支持模糊排序检索的可搜索加密方案,该方案能够抵抗区分性攻击.文献13和14提出的支持多关键词模糊检索的方案不需要预定义关键词集,在降低存储开销的同时提高了检索精度.Liu等15利用同态保序加密算法加密索引和检索向量,并通过匹配文档标记向量和查询标记向量提出了一种快速准确的可搜索加密方案.上述支持多关键词排序检索的可搜索加密方案大多数依靠全局关键词字典生成索引和陷门,故用户端需承担较大的计算代价和通信成本.此外,这些方案未涉及对加密云数据细粒度的访问控制,而对外包数据细粒度的访问控制是必要的.因此,本文结合密文策略属性加密方案(Ciphertext Policy Attribute Based Encryption,CP-ABE)提出一种基于字典分级和属性加权的多关键词密文排序检索方案.首先,提供一种基于互信息的字典剥离机制,将原始全局字典分割为主次两种关键词字典.其中生成的主关键词字典内含全局字典中的全部或绝大部分信息量,即相较于次关键词字典,主关键词字典可能会泄露数据拥有者外包文档集中更多的重要或敏感信息.构建索引和陷门时,通过只加密主文档索引向量和主检索向量来降低计算代价,进而减少通信成本.其次,排序时除关键词得分外需考虑文档访问策略中属性的权重,使数据使用者获得更为相关的结果.最后,检索过程中利用筛选向量对数据进行初次过滤并借助属性匹配完成二次剔除,确保数据使用者能解密返回的全部检索结果,实现细粒度访问控制的同时提高检索效率.1预备知识1.1属性加权定义1(极小集)满足访问树T的最小属性集合称为极小集16.定义2(文档属性集簇)由满足给定文档f的访问树T的极小集组成的集合.定义3(属性权重)若文档fi的访问树Ti包含属性aj,那么定义属性aj在fi的文档属性集簇中的频率为属性aj在fi中的属性权重.对于文档fi的访问树Ti,如图1所示.fi的文档属性集簇包含四个元素,分别是:Ti,1=a,b,x,Ti,2=c,d,x,Ti,3=c,e,x,Ti,4=d,e,x.图 1文档 fi的访问树 Ti由于属性a出现在文档fi的文档属性集簇中的频次为1,所以其属性权重为1/12.其余属性的权重同理可得,如图2所示.248新疆大学学报（自然科学版中英文）2024年图 2属性权值1.2向量空间模型本文使用信息检索中常用的词频-逆文档频率(Term Frequency-Inverse Document Frequency,TF-IDF)加权向量空间模型来量化关键词与文档之间的相关性.文档索引向量的每一维是字典中对应关键词的TF-IDF值,关键词w在文档f中的TF-IDF值计算公式如下:tf-idf(w,f,F)=(1+lnfw,f)ln(1+mnw).其中:fw,f表示关键词w在文档f中出现的次数,m表示文档集F中文档的数量,nw表示在整个文档集F中包含关键词w的文档数量.1.3主要符号说明本方案所用主要符号说明见表1.表 1主要符号说明符号说明F明文文档集,F=f1,f2,fmCF加密文档集,CF=cf1,cf2,cfmW全局关键词字典,W=w1,w2,wnSD主关键词字典SD次关键词字典ISD,CISD主文档索引向量集和其加密形式ISD次文档索引向量集IA属性索引向量集FS文档筛选向量集fW检索关键词集TSD,CTSD主检索向量和主陷门TSD次检索向量TA属性检索向量QS检索筛选向量Y文档访问策略集,Y=Y1,Y2,Y系统属性描述,=a1,a2,atini1,2,n2方案的系统架构和工作流程2.1系统架构本方案系统架构主要包括五个不同的实体,分别是可信权威机构(Trusted Authority,TA)、数据拥有者(Data Owner,DO)、数据使用者(Data User,DU)、私有云服务器(Private Cloud Server,PRCS)以及公有云服务器(Public Cloud Server,PUCS),如图3所示.(1)TA负责生成加解密相关的公共参数和主私钥,并根据用户属性列表为其生成属性密钥.(2)DO基于互信息将全局关键词字典剥离为两个附属子字典,即主关键词字典和次关键词字典,前者用于创建文档的主索引向量,后者用于创建文档的次索引向量,并为每个文档导出其对应的文档筛选向量.再采用不同的对称密钥对文档进行加密,并为文档集中的文档制定各自的访问策略,进一步利用CP-ABE算法加密用第2期王 娟，等：基于字典分级和属性加权的密文排序检索方案249于加密文档的对称密钥.最后外包加密文档集和加密主文档索引向量集上传至公有云服务器,将对称密钥密文集、次文档索引向量集和文档筛选向量集上传到私有云服务器,并通过安全信道发送检索密钥给数据使用者.(3)DU首先根据两个关键词子字典构建相应的主陷门和次检索向量;其次为检索关键词集生成检索筛选向量;最后将次检索向量、检索筛选向量与用户属性列表上传至私有云服务器,并将主陷门上传至公有云服务器以启动检索请求.(4)PRCS首先借助文档筛选向量和检索筛选向量进行初次筛选得到初始候选文档ID集;其次根据访问策略和用户属性对初始候选文档ID集完成二次过滤;最后私有云计算初始相关度,将其与最终候选文档ID集一同提交给公有云服务器.(5)PUCS执行存储和检索操作,并通过计算最终候选文档集的相关度分数对文档进行排序,向DU返回最相关的前k个文档.图 3系统架构2.2安全模型本文所提方案假设私有云服务器是一个完全可信的实体.此外,将公有云服务器看作是一个诚实但好奇的第三方,这意味着公有云服务器能够诚实地执行存储和检索操作,但同时对检索请求中的隐私信息感到好奇,并试图对其进行推断和分析以获得额外的信息.不失一般性,本方案采用如下两种在可搜索加密210,1314中被广泛使用的具有不同攻击能力的威胁模型.(1)已知密文模型:该模型中,公有云服务器仅可知加密文档集、加密主文档索引向量集和主陷门.(2)已知背景模型:该模型中,公有云服务器除拥有上述模型中的固有信息外,还能获取比已知密文模型中更多的背景知识,例如某些相关的统计信息等.利用这些附加的背景知识,公有云服务器可以结合已知检索陷门信息进行统计分析攻击,进而推测甚至以较高概率识别某些关键词.3方案设计下面给出本文方案的详细构造过程.为了突出本文方案的工作,不再赘述关于CP-ABE相关算法的具体细节,请参阅文献16.3.1初始化(1)Setup(1l)(PK,MSK):TA生成公共参数PK和主私钥MSK.(2)DicGen(F,W)(SD,SD):由于全局关键词字典W中不同关键词包含的信息量存在差异,某个关键词相对于字典中的其它关键词可能拥有更多的信息量,因此DO通过调用字典剥离算法:DicGen算法将全局关键词字典W分割为两部分,即主关键词字典SD和次关键词字SD.这种做法使得主关键词字典SD包含原始全局关键词字典W中的全部或绝大部分信息量.假定主关键词字典SD中包含n1个关键词,次关键词字典SD中包含n2个关键词,那么n1+n2=n.下面根据无监督最小冗余-最大相关标准(UmRMR)17设计DicGen算法对全局关键词字典W进行划分,具体细节250新疆大学学报（自然科学版中英文）2024年见算法1.其中:H(wi)表示关键词wi的信息熵,I(wi;wj)表示关键词wi和关键词wj的互信息,Rel表示相关度,Red表示冗余度,h表示数据拥有者根据其需求指定的一个分级阈值.3.2密钥生成(1)KeyGen0(MSK,PK,Au)SKu:TA使用公共参数PK和主私钥MSK为拥有属性集Au的用户u生成属性密钥SKu.(2)KeyGen1(1)SKii,gSK:DO生成用于加密明文文档集F的对称密钥集SKii和三元组安全检索密钥gSK=S,M1,M2,其中S 0,1n1+d+1为n1+d+1维随机二进制向量,M1和M2均为(n1+d+1)(n1+d+1)维的随机可逆矩阵,其中:n1为主关键词字典的规模,d为可调节的虚拟关键词扩展维数.算法1DicGen(F,W)(SD,SD)Input:明文文档集F,全局关键词字典WOutput:主关键词字典SD,次关键词字典SDSD=,SD=;for i=1 to n do计算H(wi);for j=i+1 to n do计算I(wi;wj);endendfor t=1 to n do计算Rel(wt)=(1/n)nPi=1I(wt;wi);endfor t=1 to n dofor i=1 to n do计算:H(wt|wi)=H(wt)I(wt;wi);Rel(wt|wi)=H(wt|wi)/H(wt)Rel(wt);Red(wi;wt)=Rel(wt)Rel(wt|wi);endendfor all wiW doscore(wi)=(1/n)nPs=1I(wi;ws);endl1=arg max1inscore(wi);SD=wl1,W=W wl1;for i=1 to n1 doUmRMR(wi)=Rel(wi)(1/|SD|)PwtWRed(wi;wt);p=arg max1inUmRMR(wi)|wiW;if UmRMR(wp)h thenSD=SDSwp,W=W wp;endendSD=W;return SD,SD第2期王 娟，等：基于字典分级和属性加权的密文排序检索方案2513.3索引构建(1)IndexBuild1(SD,F)CISD.(a)对于明文文档集F=f1,f2,fm中的每个文档fi,DO构建文档fi对应的n1维初始主文档索引向量I0SDi,若文档fi包含主关键词字典SD中的关键词wj,则I0SDij=tf-idf(wj,fi,F),否则I0SDij=0.根据需求向I0SDi中填充一个d维随机值向量,并将第n1+d+1维取值为1,得到主文档索引向量ISDi=(I0SDi,1).(b)DO使用随机二进制向量S将主文档索引向量ISDi分割为两个向量ISDi,ISDi,其中ISDi和ISDi的维数均为n1+d+1维,ISDi具体按照如下规则进行分割:ISDij=rand(),ISDij=ISDijISDij,if Sj=1,ISDij=ISDij=ISDij,if Sj=0.其次对上述分割后的向量ISDi和ISDi利用M1和M2进行加密得到CISDi=MT1ISDi,MT2ISDi.最后将加密主文档索引集CISD=CISD1,CISD2,CISDm上传至PUCS.(2)IndexBuild2(SD,F)ISD:对于明文文档集F=f1,f2,fm中的每个文档fi,DO构建文档fi对应的n2维次文档索引向量ISDi.若文档fi包含次关键词字典SD中的关键词wk,则ISDik=tf-idf(wk,fi,F),否则ISDik=0.将次文档索引向量集ISD=ISD1,ISD2,ISDm上传至PRCS.(3)FScreen(SD,SD,F)FS:根据文献9的标记思想,DO基于主关键词字典SD和次关键词字典SD为文档集F=f1,f2,fm中的每个文档fi生成n维文档筛选向量FSi=(FSi,FSi).其中:FSi是一个n1维向量,FSi是一个n2维向量.若fi包含SD中的关键词wj,则FSij=1,否则FSij=0;若fi包含SD中的关键词wk,则FSik=1,否则FSik=0.将文档筛选向量集FS=FS1,FS2,FSm上传至PRCS.3.4数据加密Encrypt(F,SKii,PK,Y)(CF,CSKii):DO选择对称密钥集SKii中的密钥,对明文文档集F=f1,f2,fm中的所有文档进行对称加密(如AES),得到加密文档集CF=cf1,cf2,cfm上传至PUCS.利用文档访问策略集Y=Y1,Y2,Y中的访问策略和公共参数PK加密对应文件的对称密钥,得到对称密钥密文集CSKii上传至PRCS.3.5陷门生成(1)TrapdoorGen1(SD,fW)CTSD.(a)DU创建检索关键词集fW对应的n1维初始主检索向量T0SD.若fW包含主关键词字典SD中的关键词wj,则T0SDj=1,否则T0SDj=0.其次生成一个d维随机二进制向量对其进行填充,其中取值为1的位置的个数为v,并使用随机数r对填充后的向量进行缩放,最后将第n1+d+1维取值为随机值t,得到主检索向量TSD=(rT0SD,r,t).(b)DU使用随机二进制向量S将其主检索向量TSD分割为两个向量TSD,TSD,其中TSD和TSD的维数均为n1+d+1维,TSD具体按照如下规则进行分割:TSDj=rand(),TSDj=TSDjTSDj,if Sj=0,TSDj=TSDj=TSDj,if Sj=1.对上述分割后的主检索向量TSD和TSD利用M11和M12进行加密,生成主陷门CTSD=M11TSD,M12TSD发送至PUCS.(2)TrapdoorGen2(SD,fW)TSD:DU创建fW对应的n2次检索向量TSD.若fW包含次关键词字典SD中的关键词wk,则TSDk=1,否则TSDk=0.将次检索向量TSD上传至PRCS.(3)QScreen(SD,SD,fW)QS:根据文献9的标记思想,DU基于主关键词字典SD和次关键词字典SD为fW生成n维检索筛选向量QS=(QS,QS).其中:QS是一个n1维向量,QS是一个n2维向量.若fW包含SD中的关键词wj,则QSj=1,否则QSj=0;若fW包含SD中的关键词wk,则QSk=1,否则QSk=0.将检索筛选向量QS发送至PRCS.252新疆大学学报（自然科学版中英文）2024年3.6密文检索(1)Search0(FS,QS,Y,Au)FID:PRCS通过运行Search0算法进行双重筛选得到最终候选文档ID集FID.Search0算法具体细节见算法2.其中:FID0表示初步筛选得到的初始候选文档ID集,FID表示二次过滤后得到的最终候选文档ID集.算法2Search0(FS,QS,Y,Au)FIDInput:文档筛选向量集FS,检索筛选向量QS,文档访问策略集Y,用户属性列表AuOutput:最终候选文档ID集FIDFID=,FID0=;for all FSiFS doif FSi&QS 6=0 thenFID0=FID0SIDfi;endendfor all IDfjFID0doifAu满足访问策略YjY thenFID=FIDSIDfj;endendif FID=thenreturn;elsereturn FID;end(2)Score0(FID,YFID,Au,ISD,TSD)Score0:在CP-ABE场景下,文档对应的属性访问策略中,不同的属性实际上具有不同的重要程度;用户通过自己拥有的属性来访问检索返回的数据;因此,可以利用文档访问策略中的属性权重和数据使用者拥有的属性来衡量文档和使用者之间的相关性.所以除关键词的相关性得分外,访问策略包含的属性也应作为评估相关性的依据之一.PRCS为文档集F=f1,f2,fm中每个文档fi根据它对应的访问策略生成一个t维属性索引向量IAi.若文档fi对应的访问策略中包含属性aj,则IAij为aj的属性权重,否则IAij=0.其次根据DU的属性列表Au为其生成一个t维属性检索向量TA.若属性列表Au包含aj,则TAj=1,否则TAj=0.PRCS利用次文档索引向量ISDi与属性索引向量IAi和次检索向量集TSD与属性检索向量TA,按如下方式计算最终候选文档ID集FID中文档fi的初始相关度:Score0(fi,fW)=(ISDiTSD)+(IAiTA).最后PRCS将最终候选文档ID集FID和对应的初始相关度分数集Score0上传至PUCS.(3)Search1(CISD,CTSD,FID,Score0,k)CFfW:PUCS首先根据DU提交的主陷门CTSD与最终候选文档ID集FID对应的加密主索引向量子集,按如下方式计算文档fi与检索fW中间相关度:Score1(fi,fW)=MT1ISDi,MT2ISDiM11TSD,M12TSD,=(MT1ISDi)TM11TSD+(MT2ISDi)TM12TSD,=ISDiTSD.计算文档fi与检索fW的最终相关度分数如下:Score(fi,fW)=Score0(fi,fW)+Score1(fi,fW),=(ISDiTSD+ISDiTSD)+(IAiTA).第2期王 娟，等：基于字典分级和属性加权的密文排序检索方案253最后,PUCS对最终候选文档集中文档的相关度分数进行排序评估,将最相关的前k个文档密文CFfW返回给DU.3.7数据解密Decrypt(SKu,CSKii,CFfW)FfW:DU利用属性私钥SKu解密从PRCS接收的对称密钥密文子集CSKii,得到对称密钥子集SKii,然后对称解密由PUCS返回的检索密文结果CFfW,得到前k个明文文档FfW.4理论分析和试验测试现有很多多关键词密文排序检索方案是基于MRSE2中的方法构建并与之进行试验对比的,不失一般性,本研究主要与原始多关键词密文排序检索文案进行各方面性能对比与试验测试.4.1性能对比将本文方案与原始多关键词密文排序检索方案MRSE2进行性能对比.其中:m表示外包文档的数量,n和n1分别表示全局关键词字典和主关键词字典的大小.如表2所示,由于n1n,所以本文方案索引构建和陷门生成的时间成本以及DO和DU之间的通信成本相对更低.表 2性能对比方案索引构建陷门生成DO 和 DU 之间的通信成本MRSE2O(mn2)O(n2)O(n2)本文方案O(mn21)O(n21)O(n21)4.2安全性分析下面基于可搜索加密中普遍采用的两种安全模型210,1314,即已知密文模型和背景模型给出安全性分析.定理1本方案在已知密文模型下是安全的.证明(1)文档的机密性.DO采用传统的对称加密算法如AES对拟外包至云端的明文文档集进行加密,将加密文档集发送到PUCS存储.由于AES输出的密文不会泄露任何关于明文的有用信息,因此只要PUCS不能访问对称加密密钥,就可保证外包敏感数据集的安全性.而对称加密密钥集使用CP-ABE算法加密后被发送到完全可信的PRCS存储,因此只有当属性满足预定的访问策略时,才能接收到PRCS返回的对称密钥密文,进而正确解密得到相应的对称密钥,所以敏感数据集隐私可以得到很好的保护.(2)索引和陷门的机密性.加密主文档索引向量由完全受信任的DO构建,主陷门由授权的DU生成.安全KNN这种向量加密模型在已知密文模型26,8,10,14下被证明是安全的,在没有检索密钥先验知识的情况下,主文档索引向量和主检索向量经过一系列处理后,任何实体都不能通过分析它们对应的密文来恢复明文.此外,由于PRCS是完全可信的实体,所以次文档索引向量和次检索向量以及它们对应的筛选向量都可以确保私密性.(3)陷门的不可链接性.在主陷门生成阶段,随着主检索向量分割过程中不确定性的引入,每个主检索向量被随机地处理成两个不同的向量.这意味着即使是相同的检索操作,生成的主陷门也是不同的.此外,主文档索引向量扩展维中虚拟关键词的添加会给相关度分数增加一定程度的噪音,这将进一步弱化检索请求之间的联系,从而保证主陷门的不可链接性.定理2本方案在已知背景模型下是安全的.证明关键词的隐私性.在已知背景模型中,PUCS除拥有上述已知密文模型中的固有信息外,还可以尝试许多方法扩大自身知识面,获取更多的背景知识,例如与数据集相关的统计信息等.根据文献2-6,8,10,14,通过向主文档索引向量中填充足够数量的虚拟关键词并为其分配随机值,可以限制PUCS对关键词作出高概率声明的能力,在已知背景模型下提供关键词的隐私保证.因此,本方案在已知背景模型下是安全的.4.3试验测试我们在Windows 10(Intel Core i5 CPU 2.30 GHz,RAM 4 GB)PC机上基于真实数据集征求意见稿(Requestfor Comments,RFC,https:/www.rfc-editor.org/retrieve/bulk/)上使用Python(nltk库和sklearn库等)语言评估了本方案的索引构建效率、陷门生成效率、检索效率以及准确度,并使用Java(JPBC库)语言评估了访问控制成本.数据集RFC包含8 649篇关于互联网开发的文档,本文选用1 050篇文档作为试验数据,并从中提取关254新疆大学学报（自然科学版中英文）2024年键词生成全局关键词字典进行各项试验测试.在本文方案中,分级阈值h是影响文档索引构建耗时的一个关键性因素,它是DO根据自己的需求指定的阈值.从图4(a)可以明显看出,随着分级阈值h取值逐渐增大,索引构建耗时逐渐减小.这主要是因为主关键词字典的长度取决于分级阈值h的大小,分级阈值h越大,主关键词字典尺寸越小,从而导致索引构建耗时越少.在索引创建阶段,每个文档索引向量的加密步骤都需要经过一次向量拆分操作和两次矩阵乘法操作.MRSE方案在不考虑全局关键词字典内部关键词信息量差异的情况下,文档索引向量和分割向量的维数均为n+d+1,且两个可逆矩阵的规模均为(n+d+1)(n+d+1),其中n表示全局关键词字典的长度.而本文方案基于互信息将全局关键词字典剥离为两个附属子字典后,此时待加密文档索引向量和分割向量的维数均转为n1+d+1,且两个可逆矩阵的规模均转为(n1+d+1)(n1+d+1),其中n1表示主关键词字典的长度,且有n1n.当分级阈值h取0.009时,从图4(b)和图4(c)能够观察到两种方案的索引构建耗时都随字典长度和文档数量的增加而增加.但相比未区分关键词信息量的MRSE方案,本文方案由于对全局关键词字典进行了前期处理,使得待加密文档索引向量在较低维的空间中生成,因而索引构建耗时少于MRSE方案,实现了更高的加密计算效率.图 4索引创建时间由于分级阈值h的大小决定了主关键词字典的尺寸,而主关键词字典的尺寸又影响主检索向量的维数.所以,与索引构建类似,陷门生成时间也与分级阈值h有关.从图5(a)可以观察到,分级阈值h越大,陷门生成耗时越少.在陷门生成阶段,与索引构建过程类似,陷门生成也需要经过一次向量拆分操作和两次矩阵乘法运算.图5(b)和图5(c)比较了当分级阈值h取0.009的情况下,本文方案与MRSE方案陷门生成时间的损耗差异,从图5(b)可以观察到,两种方案的陷门生成时间主要受限于关键词字典的长度,字典尺寸越大,陷门生成时间越长,而与检索关键词的数量几乎无关,如图5(c)所示.原因在于检索向量的维数依赖于字典长度,当字典长度固定时,不同数量的检索关键词生成的检索向量维数是相同的,从而陷门生成加密计算时间消耗一致.但相比而言,本文方案陷门生成时间成本低于MRSE方案,这主要是由于本文方案用于构造待加密检索向量的主关键词字典尺寸为n1而非n,其中n为全局关键词字典的尺寸,且n1 n,所以DU仅需花费更少的时间来进行检索向量的加密.图 5陷门生成时间在检索阶段,云服务器需要根据DU提交的检索请求计算相关度分数并对其进行排序.我们以50个文档为第2期王 娟，等：基于字典分级和属性加权的密文排序检索方案255一个区间距离制定相应数据集的访问策略,系统属性描述集中设置20个属性.由于MRSE没有涉及细粒度的访问控制,本文假设它采用了与我们一致的访问控制以统一基准.从图6(a)可以观察到,检索的时间成本随文档数量的增加而增加,但本文方案的检索时间成本相对低于MRSE的检索时间成本.这是因为PRCS借助筛选向量对数据进行初次过滤后,PUCS只需接触一部分相关数据即可,有效地避免了对整个数据集的检索操作,降低了相关度计算和排序的时间消耗.图6(b)展示了在不同数量访问策略下的访问控制时间成本,PRCS可以利用属性匹配为DU排除不同密级的数据集中其无法访问的部分,确保DU能够解密返回的全部检索结果.图 6检索时间由于主文档索引向量扩展维中虚拟关键词的插入以及主检索向量扩展维中随机二进制向量的添加将在相关度分数的计算中生成一定程度的噪音,干扰后期排序结果的真实性,所以DU接收到的文档中会丢失一部分真Topk文档,并残存一部分伪Topk文档.在本文,不失一般性,我们采用度量PK=k/k,并在比较中将标准差分别设置为=0.04和=0.05来对返回结果的准确度进行评估,其中k表示返回的真正的Topk文档数量.如图7所示,本文检索的准确度在=0.04和=0.05下都达到了90%及以上,这表明了检索的有效性.此外,可以观察到,检索的准确度图 7准确度受标准差的影响.当=0.04时,检索的准确度高于=0.05时的准确度,即标准差越小,准确度越高.5结 论本文提出了一种基于字典分级和属性加权的多关键词密文排序检索方案.方案与传统基于全局关键词字典的多关键词密文排序检索方案相比,利用本文提出的字典剥离机制降低了索引和陷门构建的时间开销,减少了数据使用者和数据拥有者之间的通信成本.其次,引入了文档访问策略中的属性权重,排序时同时考虑关键词得分和属性得分,使得返回的检索结果与数据使用者更相关.最后,在检索过程中利用筛选向量和属性匹配过滤无关文档,更有效地实现了加密云数据的多关键词细粒度排序检索.理论分析和试验结果表明,所提方案是安全的,且能够降低索引和陷门生成的计算代价以及用户间的通信成本,提高检索效率.鉴于实际应用场景中数据使用者提供的检索关键词可能会存在输入错误或仅在语义上与文档相关的情形,故也可以在本文方案的基础上进行功能拓展,使检索结果更加贴合数据使用者的心理预期.此外由于传统方法中虚拟关键词的填充虽然保证安全性,但会影响检索结果的准确率,因此在未来的工作中,我们将研究浅同态加密在密文检索领域中的应用,以提高检索的准确性与安全性.参考文献：1SONG D X，WAGNER D，PERRIG APractical techniques for searches on encrypted dataC/Proceeding 2000 IEEE Symposiumon Security and PrivacyBerkeley，CA，USAIEEE，2000：44-552CAO N，WANG C，LI M，et alPrivacy-preserving multi-keyword ranked search over encrypted cloud dataJIEEE Transactionson Parallel and Distributed Systems，2014，25(1)：222-233256新疆大学学报（自然科学版中英文）2024年3SUN W H，WANG B，CAO N，et alPrivacy-preserving multi-keyword text search in the cloud supporting similarity-based rank-ingC/Proceedings of the 8th ACM SIGSAC Symposium on Information，Computer and Communications SecurityHangzhou，ChinaACM，2013：71-824FU Z J，SUN X M，LIU Q，et alAchieving efficient cloud search services：Multi-keyword ranked search over encrypted clouddata supporting parallel computingJIEICE Transactions on Communications，2015，98(1)：190-2005XIA Z H，WANG X H，SUN X M，et alA secure and dynamic multi-keyword ranked search scheme over encrypted clouddataJIEEE Transactions on Parallel and Distributed Systems，2016，27(2)：340-3526ZHANG Q，WANG G J，LIU QEnabling cooperative privacy-preserving personalized search