一个支持错误定位的批处理数据拥有性证明方案∗

庞晓琼,王田琪,陈文俊,2,任孟琦

1(中北大学 大数据学院,山西 太原 030051)

2(中国人民银行 太原中心支行,山西 太原 030001)

1 引 言

数据拥有性证明(PDP)方案使得数据拥有者(或校验者)在没有本地备份的情况下,不需要下载数据,就能以很高的概率远程校验用户存储在服务器上的数据是否完整.目前,大多数数据拥有性证明方案是针对单用户存放在单服务器上的数据进行完整性校验[1-11],但是现实的情境中,云存储提供的服务是面向很多用户的,同时,云服务提供商并不是单一的,每个云服务提供商所拥有的也不仅仅是单个服务器.为了更适应现实,近几年,多用户单服务器[12,13]、单用户多服务器[14,15]、多用户多服务器[16-19]情景下的批处理 PDP方案陆续被提出来.在这些批处理方案中,服务器在计算证明阶段将被挑战数据块的证明按用户或服务器进行聚合计算后,再将聚合证明发送给TPA(third party auditor)校验,极大地降低了通信开销,且有效地减少了TPA校验的计算开销.但是只有当所有用户的数据都是正确存储时,这样的批量处理才能体现出其效率优势,一旦有数据被损毁,批处理校验将不通过,此时定位错误数据所在服务器和所属用户就成为一个亟需解决的问题.最直接的定位错误方法就是对被挑战服务器返回的证明逐一校验,但是这种方法的效率显然不高,并且由于服务器通常返回的是聚合证明,故而目前多用户多服务器环境下的批处理PDP方案中,即使采用逐一校验法,TPA也只能定位错误数据所属用户或所在服务器,无法进行同时定位.因此需要一种有效的方法,在多用户多服务器环境下实现批处理远程数据完整性校验的同时,还能在校验不通过情况下高效地对错误数据定位,即找到错误数据属于哪个用户,且存放在哪个服务器上.

1.1 相关工作

2007年,Ateniese等人[1]首次提出了PDP的定义,并给出了一个支持公开校验的PDP方案.2008年,Ateniese等人[2]提出了一个支持动态数据更新的 PDP方案,但是该方案只支持对文件块的修改、删除和附加操作,并不支持插入,且只能进行有限次校验.2009年,Wang等人[3]利用Merkle哈希树提出了一个全面支持数据动态更新的方案,同时引入了 TPA代替用户验证数据的完整性,但该方案没有考虑用户数据隐私会泄露给 TPA的问题.2010年,Wang等人[4]提出一个保护隐私的PDP方案,解决用户隐私泄露给TPA的问题,但该方案不支持数据动态更新.2011年,Hao等人[5]提出了“针对第三方校验者的隐私性”的安全性定义,并构造了一个在此安全性定义下可证明安全的PDP方案.2015年～2016年,Yu等人[6-9]重点研究了提高PDP方案安全性的问题.2016年～2017年,Yu等人[10,11]提出两种基于身份的PDP方案,消除了PKI庞大的证书管理开销.以上工作都是针对单用户单服务器环境下的PDP方案.

在多用户单服务器环境下,2013年,Wang等人[12]利用BLS短签名构造同态验证标签,提出了一个保护隐私的批处理PDP方案.2014年,Ren等人[13]使用椭圆曲线上的Co-GDH签名构造同态验证标签,提出一个支持数据动态更新的批处理PDP方案.在文献[12,13]中,服务器将被挑战块的证明按用户聚合之后发送给TPA,TPA对所有证明聚合计算后进行批量校验.不同的是,文献[12]在批校验不通过时,TPA会利用二分查找判断哪个用户的数据出错;而文献[13]并未考虑定位错误数据所属用户的问题.

在单用户多服务器环境下,2015年,Wang[14]提出了一个基于身份的分布式批处理PDP方案.2016年,Mao等人[15]利用BLS短签名提出了一个批处理PDP方案.这两个方案中,被挑战服务器将其上所有被挑战数据块的证明聚合计算后发送给 organizer,organizer将所有被挑战服务器发来的聚合证明再次聚合成一个值,并发送给TPA进行校验.文献[14,15]这种交由 organizer统一聚合证明的方式极大地减轻了 TPA的计算开销,但也使得TPA无法定位错误数据所在服务器.

在多用户多服务器环境下,2014年,Liu等人[16]利用双线性对提出一个批处理 PDP方案,并且使用有序的Merkle Hash Tree来抵抗置换攻击.该方案中,被挑战服务器将其上所有被挑战块的证明聚合后发给 organizer,organizer将所有被挑战服务器返回的聚合证明再次聚合并发送给TPA审计,这种交由organizer聚合,再由TPA审计的方式在一次挑战响应中无法实现错误数据定位.2016年,Zhou等人[17]基于CDH假设,利用双线性对提出了一种基于身份的批处理 PDP方案.该方案中,被挑战服务器将其上所有被挑战块的证明聚合后发送给 TPA,TPA将所有被挑战服务器返回的证明再次聚合后进行批量校验.虽然文献[17]并未考虑错误数据定位问题,但是在批量审计不通过的情况下,TPA可以采用最直接的逐一校验方式定位错误数据所在服务器,但无法定位错误数据所属用户.

在多用户多服务器环境下的批处理PDP方案中,也曾有学者提出错误数据定位的想法.2013年,He等人[18]提出了一个仅能定位出错数据所属用户的批量审计 PDP方案.该方案中,TPA批处理校验不通过后,逐一校验organizer服务器返回的按用户聚合的证明以实现定位.2015年,Shin等人[19]提出了一个仅能定位出错数据所在服务器的批量审计PDP方案,并且只能在单个服务器出错的情境下进行定位.该方案中,被挑战服务器为其上属于不同用户的被挑战块计算一个聚合证明,并发送给 TPA批量审计和错误定位.文献[18,19]不能同时支持定位错误数据所属用户和所在服务器的原因在于:TPA收到的证明都是经过聚合计算之后得到的聚合值,这种“先聚合再审计”的策略使得TPA在审计时无法同时区分这些聚合证明中涉及的数据块所在的服务器和所属的用户,故而在定位错误时只能定位错误数据所属用户或所在服务器.

本文中,我们提出利用定位标签辅助TPA快速定位错误的方法,并在Zhou等人[17]方案的基础上,在多用户多服务器环境下给出了一个具体实现.方案在支持批处理校验的同时,可以在审计到数据出错后,仅通过比较操作实现错误快速定位,同时找到出错数据的拥有者与其所处的服务器.

1.2 贡 献

(1)提出了利用定位标签辅助第三方审计员快速定位错误的方法,并给出一个多用户多服务器环境下支持批处理校验和错误数据定位的数据拥有性证明方案框架.云用户对自己的每个文件块计算相应的数据标签,将其和文件块存储在服务器中,同时对存储在不同服务器上的数据计算定位标签并发送给TPA;TPA接收到多个云用户的审计请求后,可同时对这些用户存储在多个云服务器上的数据进行挑战;在收到被挑战云服务器返回的证明后,TPA基于发送的挑战和服务器返回的证明进行有效性批量验证,若验证不通过,则利用定位标签,确定出错数据的所属用户和存储位置.

(2)给出了一个具体实现.我们的方案是在 Zhou等人[17]基于身份的批处理 PDP方案基础上增加了定位标签生成算法,云用户利用MHT为其数据块构建定位索引表,并将定位索引表发送给TPA.在审计阶段,如果批处理校验不通过,TPA则利用服务器重构的 MHT树根查找定位索引表以定位错误数据所属用户和所在服务器.我们的方案能够实现仅通过一次比较操作,即可判断出特定用户存放在特定服务器上的数据是否遭到破坏.

(3)为了防止服务器在某次审计成功后直接存储用户数据的MHT树根,并利用其在以后的挑战中构造证明欺骗TPA,本方案中,每个用户对其存储在不同服务器上的数据分别用不同的参数值构建λ棵MHT,即对相同数据计算λ个不同的定位标签,在每次挑战时,选用不同的 MHT参数值,要求服务器计算相应的MHT树根.由于服务器无法提前得知每次挑战指定的MHT参数,则其成功欺骗TPA的概率是可忽略的.

(4)方案在随机谕言机模型下是可证明安全的.相对于逐一校验定位错误的方式,我们的方案在实现错误数据定位的能力和效率方面均有优势.另一方面,除了可以一次性完成的额外计算外,因定位功能而在审计阶段增加的计算和通信开销都是可以接受的.

1.3 组织结构

本文第 2节介绍一些相关知识和工具.第 3节介绍系统模型和本文中所使用的符号,并且提出方案框架和安全性定义.第4节是具体方案的构造细节.第5节对方案进行安全性分析和性能分析,并提供实验结果.第6节进行总结.

2 预备知识

2.1 双线性对

设q是一个大素数,群G1和G2是两个阶为q的乘法循环群,设G1的生成元为g,则群G1到G2的一个双线性映射e:G1×G1→G2,满足下面的性质.

(1)双线性:对于任意的u,v∈G1和a,b∈Zq,有e(ua,vb)=e(u,v)ab.

(2)非退化性:e(g,g)的值不等于群G2中的单位元.

(3)可计算性:对任意的u,v∈G1,存在一个有效的算法可以计算e(u,v).

2.2 CDH困难问题

定义1(CDH问题).设q是一个大素数,群G1是一个q阶乘法循环群,G1的生成元为g,CDH问题指的是当a,b未知,三元组已知时,计算gab∈G1.设一个概率多项式时间(PPT)算法A解决群G1上的CDH问题的概率为ε=Pr[gab←A(g,ga,gb)].

定义2.若对于任意PPT算法A,其解决以上CDH问题的概率ε是可忽略的,则称群G1上的CDH问题是困难的.

2.3 Merkle Hash Tree

Merkle Hash Tree(MHT)是一种二叉树,常被用来进行数据验证.数据值做Hash计算后得到的值作为其叶子节点,每个父亲节点的值是由两个子节点的连接值做 Hash计算后得到的.当一个父亲节点只有 1个子节点时,父亲节点的值为单个子节点值做Hash计算后得到的值.

一般来说,一棵MHT的构造方法如图1所示.

Fig.1 Construction diagram of MHT图1 MHT构造示意图

3 定义与模型

3.1 系统模型与设计目标

一个支持批处理和错误定位的数据完整性验证系统(error locating batch provable data possession,简称ELBPDP)包含3类实体:数据拥有者(即用户,DO)、云服务器(CS)、第三方审计员(即校验者,TPA).

· 数据拥有者:在支持批处理和错误定位的数据完整性验证系统中,有多个数据拥有者.每个数据拥有者拥有各自的文档数据,他们将文档数据预处理后对所有数据块计算数据标签,将数据块和数据标签外包给云服务提供商;对存储在各个服务器上的数据计算定位标签,并发送给第三方审计员.

· 云服务器:在本系统中,云服务器的数量也有多个.每个云服务器存储着数据拥有者们提交的文件块及其数据标签.在接收到第三方审计员发送的校验挑战后,云服务器计算并返回证明.

· 第三方审计员:收到数据拥有者的审计请求后,第三方审计员给各个云服务器发送挑战,并对被挑战服务器返回的证明进行批处理校验.如果校验未通过,则根据定位标签继续确定错误数据块所属的用户和所在服务器,最后将校验结果发送给相应用户.

支持批处理和错误定位的数据完整性验证系统的结构如图2所示.

Fig.2 System model diagram图2 系统模型图

支持错误定位的批处理PDP方案,应满足如下要求.

(1)支持批处理校验:校验者可以一次性批量校验多个用户存储在多个服务器上的数据是否完整.

(2)支持错误定位:在批处理校验失败后,校验者可以同时找出错误数据所属用户与所存储的服务器.

(3)公开审计性:允许第三方审计员验证存储在云服务器上的用户数据的完整性,但是不需要从云服务器上下载全部的数据.

(4)存储完整性:确保云服务器只有真实存储用户的完整数据才能通过校验者的验证.

3.2 符号定义

方案中涉及到的符号含义由表1给出.

Table 1 Table of symbols and notions表1 符号表

3.3 方案框架

定义3.一个支持批处理和错误定位的公开可验证的数据拥有性证明方案ELBPDP=(SetUp,Extract,TagGen,PosTagGen,Challenge,Prove,Verify)包括以下7种算法.

1)Setup(1k)→(params,mpk,msk).以安全参数k为输入,PKG(private key generator)输出公共参数params,主密钥对(mpk,msk),msk仅为PKG所知.

2)Extract(params,msk,IDi)→(ski,pki).以公共参数params、主私钥msk和用户身份IDi为输入,PKG输出用户相应的私钥ski和公钥pki.

3)TagGen(params,IDi,ski,mpk,{Mijk})→({σijk}).以公共参数params、用户身份IDi和私钥ski、主公钥mpk、文件数据块的集合{Mijk}为输入,用户DOi对每个块计算数据标签σijk,并输出数据标签集合{σijk},然后将{Mijk}和{σijk}存储到相应的服务器端.服务器收到数据块和数据标签后校验其可用性.

4)PosTagGen(params,mpk,{Mijk})→{chrij}.以公共参数params、主公钥mpk、文件数据块的集合{Mijk}为输入,用户DOi对其存储在服务器CSj上的数据块计算定位标签chrij,并将所有的定位标签{chrij}发送给校验者TPA.

5)Challenge({i,j,k})→(chal,{chalj}).以所有文件块的索引集为输入,TPA输出总挑战chal,并将chal按服务器划分成若干分挑战{chalj},然后将每个chalj发送给相应的服务器CSj.

6)Prove(params,chalj,{IDi},{σijk},{Mijk})→Pj.收到挑战的服务器CSj以公共参数params、挑战chalj、用户身份集合{IDi}、数据标签集合{σijk}和CSj上所存储的数据块集合{Mijk}为输入,计算证明Pj,并将Pj发送给校验者TPA.

7)Verify(params,chal,{IDi},{Pj},mpk,{chrijt})→{1,{(i,j)}}.以公共参数params、总挑战chal、用户身份集合{IDi}、所有被校验的服务器返回的证明{Pj}、主公钥mpk、定位标签集{chrijt}为输入,TPA批处理校验证明集{Pj}的有效性,以确定各个被校验服务器中的数据保存是否完整.若{Pj}有效,则输出“1”;否则,定位所有出错数据所属用户和所在服务器,并输出其索引对{(i,j)}.

3.4 安全定义

敌手模型:在我们的方案中,考虑校验者即 TPA是诚实且好奇的,它总会按照协议规定执行,因为作为第三方审计,一旦被用户得知会与服务器勾结,对其声誉有极大的损害,但 TPA也有可能对用户的数据有一定好奇心.而云服务器为了更高的利益,可能会删除用户不常用的数据,而且在丢失或损毁用户数据后,会伪造数据标签或者证明企图通过校验,欺骗校验者和用户.综上,我们对敌手模型的设定有其合理性.

定义4.伪造数据标签游戏Dtag-forgeA(k).

1.Setup:挑战者C运行Setup(1k),得到(params,mpk,msk),将(params,mpk)发送给敌手A,msk秘密保存.

2.Query:敌手A适应性的对C做ExtractQuery和TagGenQuery两种询问:

(1)ExtractQuery:敌手A询问IDi的私钥.C运行算法Extract(params,msk,IDi),得到私钥ski,并将其发送给A.C设置一个集合S1={IDi},存放被查询过的用户身份.

(2)TagGenQuery:敌手A询问文件块Mijk的数据标签,C运行算法TagGen(params,IDi,ski,mpk,{Mijk})得到数据标签σijk,并将其发送给A.C设置一个集合I1={(i,j,k,Mijk)},存放被查询过数据标签的文件块.

3.Forge:敌手A对一个身份为的用户所拥有的文件块,伪造出一个数据标签,且

4.如果敌手A输出的数据标签是有效的,则游戏输出为1;否则输出为0.如果Dtag-forgeA(k)=1,则称敌手A赢得了这次伪造数据标签游戏.

定义5.对于任意一个PPT敌手A,如果在一个文件块集上存在一个可忽略的函数negl,使得:则称在这个文件块集上的数据标签是不可伪造的.

定义6.伪造数据标签证明游戏DtagProof-forgeA(k).

1.Setup:与伪造数据标签游戏的Setup阶段相同.

2.Query1:与伪造数据标签游戏的Query阶段相同.

3.Challenge:挑战者C生成一个包含c*组数据的挑战chal*,其中至少有 1个,使得,且.挑战者C将挑战chal*发送给A.

4.Query2:与伪造数据标签游戏的Query阶段相似,设置一个集合S2={IDi}存放本阶段被查询过的用户身份,设置一个集合I2={(i,j,k,Mijk)}存放本阶段被查询过数据标签的文件块.挑战chal*中至少存在 1个,使得,且.

5.Forge:敌手A针对挑战chal*,伪造出一个证明.

6.如果敌手A输出的数据标签证明是有效的,则游戏输出为1;否则输出为0.如果DtagProof-forgeA(k)=1,则称敌手A赢得了这次伪造数据标签证明游戏.

定义7.对于任意一个PPT敌手A,如果在一个文件块集上存在一个可忽略的函数negl,使得:

则称在这个文件块集上的数据标签证明是不可伪造的.

4 具体方案

方案的具体细节如下.

1)Setup(1k)→(params,mpk,msk):输入一个安全参数k,PKG执行以下操作.

PKG选择两个阶为q的乘法循环群G1和G2,q是一个大素数且满足q>2k,取G1的生成元为g,在群G1和G2上选择一个双线性映射e:G1×G1→G2.

PKG选择4个密码学Hash函数H1、H2、H3、H4和一个伪随机函数f,其中,:(H1和H3、H2和H4分别是不同的Hash函数),.

3)TagGen(params,IDi,ski,mpk,{Mijk})→({σijk}):用户DOi执行以下操作.

DOi随机选取,对自己的每个文件块计算,并计算.令文件块的数据标签为.

DOi将其所有的文件块{Mijk}和相应的数据标签{σijk}按服务器索引发送给相应的服务器.每个服务器收到用户发送的数据块和数据标签后,通过校验下面的等式是否成立来确定数据标签是否可用:

4)PosTagGen(params,mpk,{Mijk})→{ait,chrijt}.

用户DOi随机选择.

设存储DOi数据的服务器索引集合为Ji,且DOi在服务器CSj(j∈Ji)上存储的文件块块数为Nij.用户DOi对每一个服务器CSj(j∈Ji),分别以ait(1≤t≤λ)为 MHT参数,对其存储在CSj上的Nij个数据块构建λ棵 MHT.每棵树用TRijt(1≤t≤λ)表示,TRijt的根节点用Rijt表示.

例如,用户DO1在服务器CS1上共存放了 4 个数据块M111、M112、M113、M114,使用a1t(1≤t≤λ)作为参数,TR11t的构建如图3所示,树的根为R11t.

Fig.3 MHTTR11tconstructed byDO1 with the data block stored inCS1 and parametera1t图3DO1以a1t为参数,针对CS1上的数据块构建的MHTTR11t

DOi令.

设服务器共有η个.DOi构建一张定位索引表,其中,若不存在,即j∉Ji,则令将定位索引表发送给校验者.定位索引表见表2.

Table 2 Table of locating indexes constructed byDOi表2 用户DOi构建的定位索引表

校验者接收用户DOi发来的审计请求,请求为DOi所有数据块的索引集{(i,j,k)},包括用户索引i、存储DOi数据的服务器CSj索引j∈Ji、存放在CSj上的块索引k.收到多个云用户的审计请求后,TPA将所有审计请求做并集,得到总的审计请求集合.

校验者从总的审计请求集合Q中选出c个块进行校验,令表示被选中的c个块,构建索引集合I={(in,jn,kn)|n=1,…,c}.

校验者令总挑战chal=(I,K,α).

设被挑战的数据块所在服务器的索引集合{j}用U表示,校验者将挑战chal按被挑战服务器的不同,划分成|U|个分挑战{chalj},有.每个,其中,并且.

校验者将chalj发送给服务器CSj.

Prove-DataTag:收到挑战chalj的服务器CSj计算(此处{rn}表示服务器CSj对其收到挑战chalj中所有块分别计算的伪随机函数值构成的集合),对chalj中涉及的每一个用户,计算,得到集合,其中,Oj表示Ij中包含的所有云用户的索引集合.然后,CSj利用标签计算.

Prove-PositionTag:服务器CSj针对每个被挑战的用户DOi(i∈Oj),对存储在其上的所有数据块Mijk,以αj中与DOi的数据块索引对应的aiτ为参数,按照如图3所示的方法重构相应的 MHT,表示为TRijτ,其树根为Rijτ.所有Oj中云用户的数据块构建的MHT树根和与其对应的用户、服务器索引构成集合{(i,j,Rijτ)|i∈Oj}.

7)Verify(params,chal,τ,{IDi},{Pj},mpk,{chrijt})→{1,{(i,j)}}.

设校验者生成的总挑战中所涉及的用户DOi的索引集合{i}用O表示.校验者收到所有被挑战服务器发回的证明后,先计算(此处{rn}表示 TPA对总挑战中所有被挑战块分别计算的伪随机函数值构成的集合),然后校验等式(2)是否成立:

· 若等式(2)成立,则说明批处理校验通过,即总挑战中涉及的云用户的数据审计结果为验证通过,校验者输出1;

· 若等式(2)不成立,则对云服务器CSj(j∈U)返回的集合中的每个元素(i,j,Rijτ),TPA利用(i,j)和τ,查询定位索引表Indexi中第τ行、第j+1列中的值并校验等式(3)是否成立:

若不成立,则输出相应的(i,j).

5 正确性、安全性及性能分析

5.1 正确性证明

定理1.若校验者和服务器都是诚实的,那么服务器返回的关于数据标签的证明就可以通过TPA的批处理校验.

证明:等式(2)的右边可以进行如下变换:

则等式(2)的右边就等于:

故等式(2)成立.证毕. □

5.2 安全性分析

定理2[17].如果CDH问题是困难的,则在随机谕言机模型下,不存在一个PPT敌手能够以不可忽略的概率赢得伪造数据标签游戏.

证明:令B的输入为(g,gx,gy)∈G3,其中,G1为q阶乘法循环群,g为生成元.B作为挑战者,想要通过与敌手

1A进行交互得到gxy∈G1,模拟过程如下.

1.Setup:B选择一个q阶乘法循环群G2,在群G1和G2上选择一个双线性映射e:G1×G1→G2,随机选择,设置mpk=gx,将(G1,G2,q,g,e,mpk,{vl})发送给敌手A.

2.H1-Query:A可以随时查询随机谕言机H1,B需要构建维护一张H1列表H1-list={(IDi,bi,ai,H1(IDi))}来存储对A的回应.当A对IDi查询H1,B回应方法如下:

1)若H1-list中有包含元素IDi的元组,则B读取四元组(IDi,bi,ai,H1(IDi)),并将H1(IDi)发送给A.

2)若H1-list中没有包含元素IDi的元组,则B根据bi的值对A进行回应,其中,bi由B通过二项分布Pr[bi=0]=δ,Pr[bi=1]=1-δ确定.

a)若bi=0,B随机选择一个,计算;

b)若bi=1,B随机选择一个,计算.

B将(IDi,bi,ai,H1(IDi))加入表H1-list中,并将H1(IDi)发送给A.

3.H2-Query:A可以随时查询随机谕言机H2,B需要构建维护一张H2列表H2-list={(IDi,H2(IDi))}来存储对A的回应.当A对IDi查询H2,B回应方法如下.

1)若H2-list中有包含元素IDi的元组,则B读取二元组(IDi,H2(IDi)),并将H2(IDi)发送给A.

2)若H2-list中没有包含元素IDi的元组,则B随机选择一个H2(IDi)发送给A,然后将二元组(IDi,H2(IDi))加入表H2-list中.

4.H3-Query:A可以随时查询随机谕言机H3.B需要构建维护一张H3列表H3-list={(mpki,zi,H3(mpki))}来存储对A的回应.当A对mpki查询H3,B回应方法如下.

1)若H3-list中有包含元素mpki的元组,则B读取三元组(mpki,zi,H3(mpki)),并将H3(mpki)发送给A.

2)若H3-list中没有包含元素mpki的元组,则B随机选择,计算,并将H3(mpki)发送给A.然后,B将三元组(mpki,zi,H3(mpki))加入表H3-list中.特别地,当mpki=mpk时,B将相应的元组记为(mpk,z,H3(mpk)=gz).

5.ExtractQuery:A可以随时查询随机谕言机Extract.B需要构建维护一张表Extract-list={(IDi,ski)}来存储对A的回应.当A对IDi查询谕言机Extract,B回应方法如下.

1)若Extract-list中有包含元素IDi的元组,则B读取二元组(IDi,ski),并将ski发送给A。

2)若Extract-list中没有包含元素IDi的元组,则B查找H1-list中是否有包含元素IDi的元组,若没有,则B生成一个H1(IDi)的查询,使得四元组(IDi,bi,ai,H1(IDi))存在.B根据bi的值对A进行回应.

a)若bi=0,则B计算,并将ski发送给A.然后,B将(IDi,ski)加入表Extract-list中;

b)若bi=1,则B报告失败,并终止模拟.

6.TagGenQuery:A可以随时查询随机谕言机TagGen.B需要构建维护一张表TagGen-list={(i,j,k,Mijk,σijk)}来存储对A的回应.当A对(i,j,k,Mijk)查询谕言机TagGen,B回应方法如下.

1)若TagGen-list中有包含元素(i,j,k,Mijk)的元组,则B读取五元组(i,j,k,Mijk,σijk),并将σijk发给A.

2)若TagGen-list中没有包含元素(i,j,k,Mijk)的元组,则B查找H1-list中是否有包含元素IDi的元组,若没有,则B生成一个H1(IDi)的查询.然后,B查找H2-list中是否有包含元素IDi的元组,若没有,则B生成一个H2(IDi)的查询.然后,B查找H3-list中是否有包含元素mpk的元组,若没有,则B生成一个H3(mpk)的查询.B根据bi的值对A进行回应.

a)若bi=0,则B随机选择Sijk∈G1,计算:

并将σijk发送给A.然后,B将五元组(i,j,k,Mijk,σijk)加入表TagGen-list中.可以验证,(i,j,k,Mijk,σijk)满足等式(1),即σijk为数据块(i,j,k,Mijk)的有效标签.

b)若bi=1,则B报告失败,并终止模拟.

7.Forge:敌手A对一个身份为的用户所拥有的文件块伪造数据标签,要求敌手A之前并未对进行过ExtractQuery,且未对进行过TagGenQuery.B查找H1-list中是否有包含元素的元组,若没有,则B生成一个的查询.然后,B查找H2-list中是否有包含元素的元组,若没有,则B生成一个的查询.然后,B查找H3-list中是否有包含元素mpk的元组,若没有,则B生成一个H3(mpk)的查询.B根据bi的值做如下操作.

B可得到:

B计算.

令E表示事件B求解出gxy,经过上面分析可知:在A进行nEQ次ExtractQuery和nTQ次TagGenQuery时模拟未终止,且A对数据块成功地伪造出有效的数据标签;同时,在对进行H1-Query时,若元组中,则事件E发生.若敌手A赢得伪造数据标签游戏的概率ε不可忽略,则不可忽略,即B解决群G1上的CDH问题的概率不可忽略.当δ=(nEQ+nTQ)/(nEQ+nTQ+1)时,取得最大值.证毕. □

定理3[17].如果CDH问题是困难的,则在随机谕言机模型下,不存在一个PPT敌手能够以不可忽略的概率赢得伪造数据标签证明游戏.

证明:令B的输入为,其中,G1为q阶乘法循环群,g为生成元.B作为挑战者,想要通过和敌手A进行交互得到gxy∈G1,模拟过程如下.

1.Setup:B选择一个q阶乘法循环群G2,在群G1和G2上选择一个双线性映射e:G1×G1→G2,随机选择,选取伪随机函数,设置mpk=gx.将(G1,G2,q,g,e,f,mpk,{vl})发送给敌手A.

2.B对H1-Query、H2-Query、H3-Query、第1阶段Extract-1Query、TagGen-1Query的回应方式与定理2证明中的回应方式相同.

3.Challenge:令S1表示第 1阶段被Extract-1Query过的用户身份IDi的集合,集合I1存放第 1阶段被TagGen-1Query的(i,j,k,Mijk).B生成挑战chal*=(I*,K*,α*),其中,,,其中至少有1个,且对于相同的,至少有1个块将挑战chal*发送给A.

4.第2阶段Extract-2Query,TagGen-2Query与定理2中ExtractQuery,TagGenQuery相同,并令S2表示第2阶段被Extract-2Query过的用户身份IDi的集合,集合I2存放第 2阶段被TagGen-2Query过的(i,j,k,Mijk).需保证挑战chal*中至少有1个,且对于相同的,至少有1个块.

5.Forge:敌手A针对挑战chal*,伪造证明.B在H1-list中查找,对于不存在列表中的,B对其做H1-Query.B在H2-list中查找,对于不存在列表中的,B对其做H2-Query.B在H3-list中查找是否有(mpk,z,gx),若没有,则B对mpk进行H3-Query.B根据的值做如下操作.

B计算.

令E表示事件B求解出gxy,经过上面的分析可知,在A进行nEQ次ExtractQuery和nTQ次TagGenQuery未终止,且A针对挑战能够成功伪造出可通过校验的数据标签证明;同时,对进行H1-Query时,其中至少有1个,则事件E发生.设敌手A赢得伪造数据标签证明游戏的概率为ε,则B解决群G1上的CDH问题的概率为时,取得最大值.证毕. □

定理4.如果Hash函数是抗碰撞的,则不存在一个PPT敌手能够以不可忽略的概率伪造出通过TPA校验的定位标签证明.

证明:被挑战服务器在每次挑战时都会收到TPA发来的重构MHT的参数.由于每次挑战用于定位的MHT根标签所使用的参数不同,使得服务器无法提前预知、计算并存储叶子节点,所以收到挑战的服务器都需要根据挑战中MHT参数集{αj}重新计算相应的MHT根值作为证明.在MHT中,叶子节点是参数与文件块连接后做Hash运算得到的,而根值是由所有叶子节点经过多层计算Hash值得到的,所以,若Hash函数是抗碰撞的,则要在不知道参数与文件块值的情况下伪造出可通过校验的根值的概率是可以忽略的.证毕. □

此外,要说明的是,为了实现错误定位,且使得用户端不额外存储多余的信息,有些信息,如用户数据块所存储的服务器和所有用户数据的定位索引表,TPA都是知道的.而定位索引表中的元素是每个用户存储在不同服务器上的数据所构成的MHT树根,若Hash函数是抗原象攻击的,则TPA无法得知用户原始数据块值.

5.3 性能分析

在下面的分析中,n表示所有云用户的文件块总数,c表示TPA选中的被挑战块的数量,n1表示c个被挑战块所属用户的数量,n2表示c个被挑战块所在的服务器的数量,η表示所有云服务器的数量,γ表示所有云用户的数量,s表示每个数据块的分区数,λ表示每个用户对其存放在一个服务器上的数据所构建的 MHT数量.cj表示被挑战服务器CSj上被挑战的块数,有1≤cj≤cmax=c-n2+1.假设云用户DOi总共将mi个文件块存储到多个服务器中,服务器CSj上共存储了m′j个文件块.

方案的通信轮数为1轮,在此一轮通信中既实现了批处理校验,又能实现错误数据的定位功能.

1.关于通信复杂度

在初始阶段,云用户除了将文件块{Mijk}和相应的数据标签{σijk}发送给服务器以外,为了实现对其错误数据进行定位,还需要将定位索引表发送给TPA,每个用户的定位索引表中包含λ(η+1)个Zq中的元素.

在挑战阶段,TPA发送总挑战chal=(I,K,α),其中,I中包括3c个整数,K中包含c个Zq中的元素,α中也包含c个Zq中的元素.综上,挑战阶段的通信复杂度为O(c).

2.关于存储复杂度

服务器存储着用户的数据块和相应的数据标签,与其他方案相似.TPA需要存储所有用户发来的数据块定位标签,共有γ张定位索引表,包含γλ(η+1)个Zq中的元素,存储复杂度为O(γλη).

3.关于计算复杂度

云用户:除了为每个数据块计算相应的数据标签以外,为了实现错误定位,额外地,云用户需要对其存储在不同服务器上的数据块分别构建λ棵MHT.含有Nij个叶子节点的MHT最多需要做次Hash运算.拥有mi个数据块的云用户DOi最多计算次 Hash,因此,DOi计算定位标签的时间复杂度为O(λmi),这项工作是一次性的.

被挑战服务器:计算的证明包含两部分:(1)用于批处理校验的部分,需要做cj次伪随机函数运算、2cj次指数运算、2(cj-1)次群中乘法运算、s·cj次普通乘法运算,最多s·(cj-1)次普通加法运算;(2)用于定位错误的部分,最多需要进行次Hash运算.

TPA:批处理校验包括c次伪随机函数运算、n1次指数运算和3次双线性对运算,最多n1(s-1)·(n2-1)+c次普通加法运算、最多s·min(n1n2,c)次普通乘法运算、2(n2-1)+(n1-1)次群中乘法运算.若批处理校验不通过,则再对服务器返回的树根一一进行对比校验,判断某一用户存放在某一服务器上的数据是否遭到损毁,只需一次比较操作.

下面将我们的方案与其他多用户多服务器环境下支持批处理校验的方案进行比较.从效率和是否支持错误定位方面,我们的方案与He等人[18]、Shin等人[19]和Zhou等人[17]的方案进行对比的结果见表3.

Table 3 Comparison of efficiency and location function表3 效率及定位功能比较

其中,Cexp表示群G1上单个指数运算的开销,CH表示单个Hash函数运算的开销,Cpar表示一个双线性对运算的开销,Cper表示一个伪随机函数运算的开销,CmG表示群上单个乘法运算的开销,CdG表示群上单个除法运算的开销,CmZ表示单个普通乘法运算的开销,CaZ表示单个普通加法运算的开销,Tcpr表示一次比较的时间开销.因为文献[18]中每个用户的数据都会被挑战且被挑战的块索引相同,令c′表示一个被挑战用户被挑战的块数,即c=c′·n1.

4个方案中,审计阶段都仅需1轮通信,我们的方案在1轮通信中不仅能够实现批处理校验,还能在校验不通过情况下定位错误数据所属用户和所属服务器;而文献[18]只支持定位错误数据的拥有者;文献[19]只支持定位错误数据所在服务器,并且仅适用于只有 1个服务器的数据被损毁的情景.我们的方案是基于查找的方式定位错误数据,判断特定用户存储在特定服务器上的数据是否出错仅需一次比较操作;而文献[18,19]都是利用计算的方式来实现错误数据定位,文献[18]判断特定用户的数据是否损毁需要O(c′)次指数运算,文献[19]定位唯一的数据被损毁服务器需要次乘法运算.

在我们的方案中,为了计算定位标签,用户需要为其数据块构建 MHT,服务器在计算证明时需要重构 MHT,所以相对于其他方案,在用户端和服务器端分别增加了2λmi和2mj′次Hash运算.由于Hash运算的速度很快,所以增加的计算对总体的计算开销影响并不显著.为了定位错误,相对于文献[17-19],TPA需要额外存储γ张定位索引表,总共γλ(η+1)个Zq中的元素,而TPA进行批处理校验的计算量相对于文献[17]来说并没有增加.

5.4 仿真实验

我们首先对云用户、服务器和 TPA各自计算的时间开销进行了仿真实验,然后对两种定位错误方式的定位效率进行了对比.PC硬件配置为Intel Core2Duo处理器、4G内存,操作系统为Ubuntu 16.04 LTS 32位,利用PBC库[20]、GMP库[21]和Miracl库[22],使用gcc编译执行.实验中,使用PBC库中a.param参数设置双线性对,构造MHT时采用SHA-256.

1.用户计算数据标签TagGen和定位标签PosTagGen的计算开销

用户将文件分块后,对每个数据块计算相应的数据标签,然后对存储在不同服务器上的数据块计算定位标签.在实验中,我们设置每个数据块4KB,每个分区 20B,通过设置不同的文件大小来观察 TagGen和 PosTagGen的计算开销.令用户文件大小为5MB～40MB,相应的数据块数为1 250～10 000,设置步长5MB.TagGen的计算开销与λ=64和λ=128时PosTagGen的计算开销实验结果如图4所示.

Fig.4 Computational cost of TagGen &PosTagGen for increased size of files图4 文件大小增加时TagGen和PosTagGen的计算开销

从实验结果可以看出,TagGen的时间随着文件大小的增长(数据块数增长)呈线性增长,与性能分析结果一致.特别地,当文件大小为5MB(40MB)时,TagGen的时间为13.6s(121.7s).PosTagGen的计算开销与文件大小(数据块数量)和λ值是相关的:当λ值固定时,PosTagGen的计算开销随着数据块数量增加而增大,基本呈线性增长,实验结果与性能分析相符合.进一步观察,当λ=64,文件大小为 5M(40M)时,PosTagGen的时间为 5.5s(66.5s).当λ=128,文件大小为 5MB(40MB)时,PosTagGen的时间为 11.0s(133.0s).TagGen与 PosTagGen的计算开销较大,耗费的时间显著高于其他操作耗费的时间,但是对于一个文件来说都仅需计算 1次.表4为当λ=64和λ=128时,TPA进行校验的不同时间间隔所能支持的错误定位有效期.

Table 4 Error locating period of validity for different verification time interval表4 不同校验时间间隔下,支持错误定位的有效期

2.服务器计算证明Prove-DataTag、Prove-PositionTag和TPA批量校验数据标签证明Verify的计算开销

在挑战响应阶段,收到挑战的服务器需要计算数据标签的证明 Prove-DataTag和定位标签的证明 Prove-PositionTag,而TPA需对被挑战服务器返回的数据标签证明进行批量审计.

服务器Prove-DataTag的计算开销与TPA批量审计Verify的计算开销均与TPA选取的挑战块数量有关,所以我们在同样的条件下对这两个计算进行了仿真.实验中,我们设置了10个用户和10个服务器,每个用户拥有10 000个数据块,每个数据块4KB,每个分区20B,每个用户将其10 000个数据块均匀地存储到10个服务器上,这样,每个服务器上存储着10个用户的10 000个数据块.若云服务器的数据块损毁率为1%,则TPA挑战其上的300个(460个)数据块,就能以95%(99%)的概率检测出该服务器的损毁数据行为[23].因此,在TPA随机均匀选取10个服务器上的挑战块的情况下,我们对总挑战块数为3 000～4 600(相应的每个服务器上被挑战块数为300～460),以步长为200,进行了实验,结果如图5所示.

Fig.5 Computational cost of Prove-DataTag by single server &Verify by TPA for increased number of total challenged blocks图5 总挑战块数增加时,单个服务器Prove-DataTag和TPA Verify的计算开销

从实验结果可以看出,服务器Prove-DataTag的计算开销随着其上被挑战块数量的增加而增长.这主要是因为当其上被挑战块数增加时,服务器需要为增加的挑战块的数据标签做群上的指数运算.随着总挑战块数的增加,TPA批量校验数据标签证明 Verify的计算开销增长并不明显.这是因为增加的操作只是一些伪随机函数和普通加法运算,实验结果与性能分析结果一致.进一步观察,当总挑战块数为 3 000(4 600)个时,服务器 Prove-DataTag的时间为2.7s(4.1s),TPA Verify的时间仅为53ms(54ms).

被挑战服务器计算定位标签证明Prove-PositionTag的计算开销与该服务器上被挑战用户的所有数据块数有关.我们对其中最坏的情况进行了模拟,即数据存放于该服务器上的所有用户均有数据块被TPA挑战,所以被挑战服务器需对其上存储的所有数据块进行重构MHT的操作.我们令被挑战服务器存储的数据块数为5 000～12 000,步长为1 000,对单个被挑战服务器计算定位标签证明Prove-PositionTag(即重构MHT)的计算开销进行测试,结果如图6所示.

从实验结果可以看出,服务器重构MHT的计算开销随着该服务器上存储的数据块数增加而增长,且增长趋势基本呈线性,与性能分析结果一致.由于Prove-PositionTag的计算是重构MHT树,所做的都是Hash操作,因此即使是在最坏情况下,重构MHT的时间也是较快的.当服务器上存有5 000(12 000)个数据块,且所有其上用户都有数据块被挑战时,服务器Prove-PositionTag的时间为0.42s(1.34s).

Fig.6 Computational cost of Prove-PositionTag by single server for its increased number of stored blocks图6 存储的数据块数增加时,单个服务器Prove-PositionTag的计算开销

3.TPA定位错误时间比较

在本节中,我们对两种定位错误方式的定位效率进行对比:逐一校验方式和利用定位标签辅助定位的方式.为了使对比结果更合理,我们同样是在 Zhou等人方案[17]的基础上实现逐一校验定位错误,并设置相同的环境参数.但需要说明的是,逐一校验方式使得Zhou等人的方案只能定位错误数据所在服务器.

在实验中,我们设置10个用户和100个服务器,每个用户拥有100 000个数据块,每个数据块4KB,每个分区20B,每个用户将其 100 000个数据块均匀存储到 100个服务器上,这样,每个服务器上就存储着 10个用户的10 000个数据块.在TPA随机均匀选取每个被挑战服务器上10个用户的300个挑战块的情况下,令被挑战服务器个数为10～100,模拟两种定位错误方法的计算开销,实验结果如图7所示.

Fig.7 Time comparison of location errors by TPA图7 TPA定位错误时间比较

从实验结果可以看出,随着被挑战服务器数量的增加,逐一校验方式定位错误服务器的时间耗费呈线性增长趋势,而利用定位标签定位错误数据所属用户和所在服务器的计算开销增长并不明显.这是因为逐一校验方式中,TPA针对每个被挑战服务器返回的证明单独校验,每次校验都需要做多个指数运算和双线性对运算;而利用定位标签的方式只涉及比较操作.在被挑战服务器个数为 10(100)时,定位标签方式仅需 0.059s(0.087s),而逐一校验方式则需0.523s(4.652s).显然,随着被挑战服务器个数的增加,使用定位标签辅助错误定位的效率显著优于逐一校验的方式.

6 总 结

本文主要研究了批处理 PDP方案在批量审计不通过情况下的错误数据定位问题.提出了利用定位标签辅助第三方审计员快速定位错误的方法,并在多用户多服务器环境下给出了一个具体实现,在批处理校验不通过的情况下,仅通过比较操作就能同时定位错误数据所属用户和所在服务器.我们对方案的正确性和安全性进行了证明,并对方案的性能进行了理论分析和仿真实验.性能分析结果表明,我们的方案在定位错误数据的能力和效率方面均高于其他具有单一定位功能的方案.实验结果也表明,利用定位标签辅助错误定位的效率显著优于逐一校验的方式,且实现错误定位功能的额外计算开销是可接受的.

在本文方案中,预先设定的 MHT数量使得本方案不适合进行无限次的错误定位.为了缓解次数限制问题,有两种可行的解决办法.

(1)不要求每次校验都返回树的根值.仅当批处理校验发生错误后,校验者给服务器再次发送挑战,要求服务器提供相应树的根值.

(2)对服务器建立分级制度,校验者在挑战时可设立一个状态标识,若状态为“1”,则要求返回根值;若为“0”则不要求.对信誉好的服务器,可以适当减少其返回根值的次数.