一种可扩展的动态数据持有性证明方案_肜丽

1、第 30 卷第 7 期2013 年 7 月计 算 机 应 用 研 究Application Research of ComputersVol 30 No 7 Jul 2013一种可扩展的动态数据持有性证明方案*肜丽1 ，栗磊1 ，李超零2( 1 信阳农业高等专科学校 计算机科学系，河南 信阳 464000; 2 信息工程大学 网络空间安全学院，郑州450004)摘 要: 提出了一种能保护数据隐私的动态数据持有性证明方案，并对方案的安全性进行了证明，性能分析表明该方案具有低存储、计算和传输负载的特点。通过扩展实现了对公开可验证和多副本检查的支持，扩展方案 的特点在于公开验证中不需要可信第三方的参

2、与，而多副本检查可以方便地实现对所有副本的批量检查。关键词: 数据持有性证明; 数据更新; 公开可验证; 多副本检查; 状态表中图分类号: TP302. 7文献标志码: A文章编号: 1001-3695( 2013) 07-2132-04doi: 10 3969 / j issn 1001-3695 2013 07 053Extensible provable data possession scheme with data dynamicsRONG Li1 ，LI Lei1 ，LI Chao-ling2( 1 Dept of Computer Science，Xinyang Agricult

3、ural College，Xinyang Henan 464000，China; 2 Institute of Cyberspace Security，Informa- tion Engineering University，Zhengzhou 450004，China)Abstract: This paper proposed a dynamic provable data possession scheme that could protect data privacy And it proved that the scheme was secure It was also showed

4、that its payload on storage，computation and transfer was low Then，it extended the scheme to support public verifiability and multiple replicas checking The characteristic of the publicly verifiable scheme need not trusted third party，and the multiple replicas checking one can support batch checking

5、very wellKey words: provable data possession; data dynamics; public verifiability; multiple replicas checking; state table能否保证数据的完整性是用户考虑是否采用云存储服务 的主要顾虑之一。一方面，为谋取更大的收益，服务提供商( cloud service provider，CSP) 可能将用户很少访问的数据转移到非在线存储设备上，甚至将其删除以节省存储开销; 另一方面，CSP 可能向用户隐藏由于管理不当或设备故障造成的数据损坏或丢失，以维护自身的信誉和逃避赔偿。此外，云存储

6、服 务面临的各类内外部安全攻击也对数据的完整性造成了极大的威胁。因而，CSP 不仅应该在服务等级协议( service level ag-greement，SLA) 中约定向用户提供的存储服务和安全保证，还应该向数据所有者( owner) 提供一种验证其云端数据完整性的方法。针对该问题，研究人员提出了数据持有性证明( provable data possession，PDP) 来检查存储在云端的数据的完整性。Deswarte 等人1最早提出了远程数据完整性检查( remote动态数据持有性证明方案，并对其进行了扩展，使其实现了对 公开可验证和多副本检查的支持，从而能全面支持上述持有性 检查的关

7、键特性。并且，在公开可验证扩展中不需要借助TPA，降低了方案的复杂性，而在多副本检查扩展中实现了对所有副本的批量检查，提高了检查的效率。上述典型方案与本文方案的性能对比如表 1 所示。其中: “* ”表示方案是否需要 TPA 以支持公开可验证性; “#”表示持有性检查过程中服务器( S) 和验证者( V) 的计算负载; “” 表示服务器和验证者的存储负载; n 为文件的数据块数目; c 为被检查的数据块数目; s 为多副本检查中存储服务器的数目。 表 1 典型方案性能对比 对比项文献6 文献7 文献8 文献10 文献11 本文方案动态性是是是否否是data integrity checking

8、，RDIC) 的方法，但其在以大数据量为特公开可验证性( TPA) *否是( 是)是( 否)是( 是)是( 是)是( 否)点的云环境中造成了极大的运算开销。Ateniese 等人2 第一隐私保护否否是是是是多副本检查否否否否是是次正式定义了 PDP 方案，并使用基于 RSA 的模指运算构造同态标签来实现持有性证明。Juels 等人3 提出了可恢复证明( proof of retrievability，POR) 的概念，并提出了一个基于哨兵的计算负载 ( S / V) #存储负载 ( S / V) O( c) O( c)O( n) O( 1)O( log n) O( log n)O( n) O(

9、 1)O( n) O( n)O( n) O( n)O( c) O( c)O( n) O( 1) O( c) O( sc)O( n) O( 1) O( c) O( sc)O( n) O( n)POR 方案。目前，对数据持有性证明的研究主要集中在支持数据动态更新4 8 和公开可验证7 11、保护数据隐私不被泄露给第三方检查者8，10，11( third party auditor，TPA) ，以及对数据多副本的检查11 13等几个方面，但它们大都只针对其中的部分问题展开研究。为此，本文提出了一种能保护数据隐私的 传输负载O( 1)O( 1)O( 1)O( c)O( c)O( 1) 1 数据持有性证

10、明1. 1 符号定义首先，对本文采用的符号和函数运算进行约定，如表 2收稿日期: 2012-11-12; 修回日期: 2012-12-24基金项目: 国家“973”计划资助项目( 2012CB315901) ; 河南省基础与前沿技术研究计划项目( 102300410033)作者简介: 肜丽( 1977-) ，女，河南新野人，讲师，硕士，主要研究方向为信息与网络安全( lichunxiang_01 163 com) ; 栗磊( 1980-) ，男，河南信阳人，实验师，主要研究方向为计算机应用技术; 李超零( 1985-) ，男，四川眉山人，博士研究生，主要研究方向为可信计算、云计算第 7 期肜

11、丽，等: 一种可扩展的动态数据持有性证明方案2133所示。符号描述符号描述Mowner 的外包数据c被挑战的数据块数目数据块的版本数据块标签集数据块标签数据块挑战信息数据块证明信息数据块物理序号数据块逻辑序号n数据块数目vimi单个数据块 ( 1in)Tk安全密码参数ti( sk，pk)公私钥对chalki长度为 k 的随机数PC对 M 加密后的密文数据BNci密文数据块 ( 1in)SN表 2 符号与描述的数据 M、密文数据 C 和标签集 T。3) Query( c) chal执行数据持有性检查时，owner 调用 Query 生成数据块挑战 chal，并将其发送给 CSP。挑战 chal

12、包含两个分别用于随机置换和随机数生成的密钥，以及被挑战的数据块数目。Query 的具体算法如下:Query( c) chal输入: c。步骤: 计算 k1 0，1 k; k2 0，1 k; chal = ( k1 ，k2 ，c) 。输出: chal。keyE ( ) : 0，1 k 0，1 l 0，1 l对称加密算法，如 DES、AES 等。keyH ( ) : 0，1 * 0，1 l带密钥的哈希函数。f( ) : 0，1 * 0，1 k 伪随机数函数。4) Prove( C，chal) P收到挑战信息 chal 后，CSP 利用随机置换函数 key( ) 得到 c 个被挑战数据块的物理序号

13、BN，并利用 fkey( ) 生成 c 个随机数。其中，函数 key( ) 和 fkey( ) 为 owner 和 CSP 共有。fkey( ) : 0，1 0，1 带密钥的伪随机函数。*k最后，CSP 计算两个值C和T，并将其组成数据持有性证据 P。key( ) : 0，1 k 1，2，n 1，2，n 伪随Prove( C，chal) P 的具体算法如下:机置换函数，用于确定每次随机抽取数据块的位置。1. 2 方案描述持有性证明方案由 KeyGen、TagBlock、Query、Prove 和Prove( C，chal) P输入: C，chal。cj = 1步骤: 计算 ij = k1 (

14、j，n) ，aj = fk2 ( j) ( 1jc) ; C = ajcij mod N;Verify五个算法组成。数据存储阶段，owner 利用 KeyGen 完成对密钥的初始化，并利用 TagBlock 对每个数据块加密和生成T =cj = 1 ijtaj mod N; P = ( C，T) 。输出: P。验证标签，最后将密文数据和验证标签一起存储到 CSP 端。进行持有性检查时，owner 利用 Query 生成数据块挑战信息，CSP 根据挑战信息调用 Prove 生成数据持有性证据，并将其返回给 owner。Owner 调用 Verify 验证证明信息的正确性，若验证通过，则 owne

15、r 以一定的概率相信存储于 CSP 的数据是完整的; 否则 owner 认为其数据遭到损坏。01) KeyGen( 1k) ( k ，( sk，pk) )KeyGen 完成对称密钥 k0 和公私钥对( sk，pk) 的生成。其中 k0 用于对数据 M 进行加密，( sk，pk) 用于生成数据块验证标签。KeyGen 的具体算法如下:其中: n 表示此时密文数据的数据块数目，通过置换函数可以在所有数据块中随机选出 c 个块作为被挑战块。5) Verify( sk，V，chal，P) yes，no收到数据持有性证据 P 后，owner 也计算出 c 个被挑战块的 BN 和 c 个随机数。根据计算得

16、到的 BN，owner 查找 S-Table得到 c 个被挑战块的SN，并计算一个值 。比较 和T。若相等，则表示 CSP 正确地持有密文数据 C，输出 yes; 否则，表示密文数据 C 遭到破坏，输出 no。Verify 的具体算法如下:Verify( sk，V，chal，P) Yes，No输入: sk，V，chal，P。KeyGen( 1 k) ( k0 ，( sk，pk) )输入: 1 k。步骤: 计算 ij = k1c( j，n) ，hij= Hsk( f ( vij) SNij) ，aj = fk2( j)( 1jc) ; h = ajhi ; = gC + h mod N; = T

17、是否成立?步骤: 计算 k0 0，1 k; sk 0，1 k; pk = ( N，g) ，其中 N = pq，p 和Nq 是两个大素数，g 是 Z* 的一个生成元。输出: ( k0 ，( sk，pk) ) 。2) TagBlock( sk，pk，k0 ，mi，vi，SNi) ( ci，ti)Owner 将数据 M 划分为固定大小的块 mi( 1in) ，并为每个块初始化一个版本信息 vi = 0，数据块每次被修改后其版本都增加 1。另外，owner 还需要初始化一个状态表( state ta- ble，S-Table) ，该表包含三个字段: BN 表示数据块在块序列中的位置( 物理序号) 、S

18、N 表示数据块的插入顺序( 逻辑序号) 、v 表示数据块的版本。Owner 调用 TagBlock 为每个数据块计算密文和验证标签。TagBlock 的具体算法如下:0iiiii0iiiTagBlock( sk，pk，k ，m ，v ，SN ) ( c ，t )输入: sk，pk，k ，m ，v ，SN 。0步骤: 计算 ci = Ek ( mi ) ，hi = Hsk ( f ( vi ) SNi ) ，ti = gci + hi mod N( 1in) 。输出: ci，ti。Owner 将所有密文块组成密文数据 C = ci | 1 in ，将各数据块的标签组成标签集 T = ti | 1

19、in ，并将 C、T 发送给 CSP 存储。Owner 在本地存储 S-Table，并删除本地存储中j = 1j输出: yes，no 。1. 3 数据更新数据更新操作包括数据块的插入、修改和删除。在该持有性证明方案中，数据更新的关键在于更新 owner 存储的 S-BNSNv110221330440550660BNSNv110221330470540650760BNSNvmodifyBNSNv110110221221330330440441550550660660BNSNvdeleteBNSNv110110221221330330440450550560660Table，以及 CSP 端存储的

20、相应验证标签。在三类数据更新操作中，S-Table 的变化如图 1 所示。insert(a) 数据块插入（b） 数据块修改（c） 数据块删除图 1 数据更新中的 S鄄Table 更新方法当插入一个新数据块时，其 BN 为该块在数据块序列中的序号，SN 为原数据块序列中最大的 SN 值加 1，并设其版本 v为 0。在新的数据块序列中，该块之后的所有数据块的 BN 值都需要加 1，而 SN 和 v 值保持不变。Owner 计算新插入块的验证标签，并将数据块密文和标签一起发送给 CSP 存储。当修改一个数据块时，需要将其版本 v 加 1，加密新的数 2134计 算 机 应 用 研 究第 30 卷据块

21、并重新计算其验证标签，最后将新的密文块和标签发送给CSP 存储。当删除一个数据块时，owner 只需要删除S-Table 中该块的对应条目，并将该块之后的所有数据块的 BN 值减 1，最后向CSP 发送删除该密文块和相应标签的数据更新请求。2 安全性证明，表 S-Table。其中，密钥存储量可以忽略，S-Table 为 owner 的主要存储负载。以 Snum表示一个物理序号 BN 或逻辑序号 SN 的字段大小，Sv 表示一个版本号 v 的字段大小，则 owner 的存储负载为n( 2Snum + Sv) 。CSP 的存储负载为标签存储量，以 St 表示单个标签的大小，则 CSP 的存储负载为

22、 nSt。取 N = 1024bit，以 1 GB 的数据按 4 KB 进行分块为例进行计算。由于 N取值为 1024 bit，因而单个标签的大小 St = 128 Byte。1 GB 数据将被划分为 218 个 4 KB 大小的块，因而 S 的取值应为 3num假设存在一个多项式时间的攻击敌手 它与 owner 按特定方式进行一场数据持有性游戏。在大整数分解问题困难性假 设的基础上，如果敌手赢得了该游戏，则表明它正确地拥有所 有的密文数据块和验证标签。定理 在大整数分解困难性问题的假设下，上述数据持有性证明方案是安全的。证明 首先，定义如下的数据持有性游戏:a) 建立。Owner 调用 Ke

23、yGen 算法完成密钥的初始化，并将公钥发送给敌手。b) 问询。敌手自适应地选择数据块作为密文块进行问询。敌手将选择的密文块 ci( 1in) 发送给 owner，owner 调用 TagBlock 算法为收到的密文块计算验证标签 ti ( 1 in) ，并为这些密文块初始化一个状态表 S-Table，最后将所有标签返回给敌手。敌手还可以修改某些密文块，并要求 owner 重新计算验证标签。c) 挑战。用户生成一个挑战信息 chal 并将其发送给敌手，要求敌手根据该挑战生成一个数据持有性证据 P。d) 伪造。敌手根据挑战信息 chal、密文块 ci 和标签 ti( 1in) 计算一个证据 P，

24、并将其返回给 owner。e) 验证。Owner 调用 Verify 算法验证敌手返回的证据 P 是否正确。若验证通过，则敌手赢得了本次数据持有性游戏， 表明其正确地持有所有的密文块和标签。在该游戏中，敌手返回的数据持有性证据 P = ( C，T) ，owner 计算的验证信息 = gC + h mod N。其中:Byte。令 S = 2 Byte，则每个数据块可以被修改 216 次。从而，vowner 的存储负载为 218 ( 6 Byte + 2 Byte) = 2 MB，占数据量的 0 19% ; CSP 的存储负载为218 128 Byte = 32 MB，占数据量的 3 12% 。可

25、见，该方案中 owner 和CSP 都具有低存储负载的特点，并且数据分块越大，它们的存储负载越低。3. 2 计算负载数据存储阶段，owner 的主要运算包括初始化密钥、加密数据块和生成数据块验证标签。其中，密钥初始化的计算复杂度 为 O( 1 ) ，数据块加密和验证标签生成的计算复杂度都为O( n) 。但对于一个数据文件，owner 只需要在将其存储到云服务器时进行一次加密和标签生成操作，数据持有性检查的效率 主要取决于检查过程中 owner 和 CSP 的计算负载。以 T 和 Tf 分别表示一次 key( ) 和 fkey( ) 运算的开销，Tmul、Tadd 和 Texp分别表示一次模乘、

26、模加和模幂运算的开销，并以 TH 表示一次 Hkey( ) 运算的开销。数据持有性检查阶段，owner 需要生成挑战信息 chal、计算 c 个被挑战块的位置和随机参数以及验证值 ，则其主要计算负载为 c( T + Tf + TH ) + cTmul + ( c 1) Tadd + Texp ，计算复杂度为 O( c) 。数据持有性证明过程中，CSP需要计算 c 个被挑战块的位置和随机参数以及生成证据 P，其主要计算负载为 c ( T + Tf ) + ( 2c 1 ) Tmul + ( c 1 ) Tadd +cTexp ，计算复杂度为 O( c) 。数据更新过程中，owner 的主要计算负

27、载为数据块标签的生成，其计算复杂度为 O( 1) ，而 CSP只需要对密文和标签集进行存储更新即可。C =ajccj，ajci mod N h =j = 1ccajhj = 1j = 1cij3. 3 传输负载传输负载是指为进行数据持有性证明，在数据存储、持有T =tij mod N = ( gcij + hij) ajmod N = g aj( cij + hij)mod N性检查和数据更新阶段的额外传输开销。数据存储阶段，额外j = 1j = 1cj = 1 = gC + h mod N = g aj cij + ajhij mod Nijjjijij当敌手正确地持有所有密文块和标签时，c

28、ij = cij，hij = h ，a = a ( 1jc) ，则 = T成立。当敌手丢失或窜改了部分密文块 c 或部分标签 t ( 1jc) ，若其希望通过持有性验证，则必须伪造出合适的 C或 T使得 = T成立，即敌手能伪造出合适的值 A 或 B，使得 A B 且 gA = gB mod N。因此， A B = k( N) 成立，从而 A B 可以用来分解大整数 N。因而，在大整数分解困难性问题假设的基础上，敌手能赢得上述数据持有性游戏，则其必须正确持有所有的密文块和标签。证明完毕。3 性能分析3. 1 存储负载存储负载是指为进行数据持有性证明，在 owner 和 CSP 端存储的除原数据

29、或数据密文外的数据存储量。Owner 将数据存储到 CSP 端后，需要在本地存储对称密钥、公私钥对和状态的传输开销为标签集的传输量 nSt。持有性检查阶段，由于挑战信息 chal 只包含数据块数目和两个随机密钥，持有性证据 P 也只包含两个模 N 的余值，因而都只需要几百字节的数据传输量。数据更新过程中，进行数据块插入和修改时，owner 需要向 CSP 发送一个验证标签，其数据传输量为 St ，而执行数据块删除时 owner 只需要向 CSP 发送一个包含被删除块序号的请求消息。4 可扩展性4. 1 公开可验证由于验证标签的计算采用了 owner 的私钥，并且 S-Table保存在本地存储器

30、中，因而上述持有性证明方案只适用于数据 所有者 owner 进行检查的情况，不能支持公开可验证性。为此，本文对该方案进行了扩展，使得所有被授权访问数据的用 户都可以进行数据持有性检查。扩展后的数据存储架构如图2 所示。第 7 期肜 丽，等: 一种可扩展的动态数据持有性证明方案2135数据存储、更新、密文 C持有性检查标签集 TownerCSPS鄄Table云存储服务器组管理、密钥分发数据访问、持有性检查s cVerify: hzi = Hsk( f( vi ) zSNi ) ( 1 zs，1 jc) ，h = jjjajhzij 。z = 1 j = 1用户组图 2 支持公开可验证的数据存储架

31、构公开可验证扩展的关键在于:a) Owner 建立和管理一个授权用户组，该组内的所有用户都可以访问 owner 存储在云中的数据。Owner 能以一种安全的方式向组内的所有用户分发数据解密密钥及其他共享密钥，如 通过广播加密方法14。b) 修改标签生成算法 TagBlock 中哈希值 hi = Hsk ( f( vi) SNi) 的计算方法，将 owner 的私钥 sk 替换为 owner 和组用户间的一个共享密钥，从而组用户可以根据数据块的版本和逻辑序 号计算其对应的哈希值。c) Owner 将状态表 S-Table 的一个副本与数据密文和验证标签一起存储在 CSP 端，并要求 CSP 在每

32、次数据更新后同步更新 S-Table。Owner 仍然在本地存储一个 S-Table 结构以方便数据更新操作。d) 当组用户进行数据持有性检查时，CSP 需要将被挑战数据块的 S-Table 条目作为持有性证据的一部分返回，从而组用户可以利用共享密钥计算哈希值 hij ，完成对持有性证据的验证。4. 2 多副本检查为保证数据的可靠性和可用性，CSP 通常在 SLA( service level agreement) 中承诺对数据进行多副本存储，即在位于不同地理位置的多个服务器上存储数据，以提高容灾抗毁和数据可 恢复的能力。为此，数据持有性证明应该实现对所有副本的检 查，以确认各数据副本均被正确

33、持有，并可以在对某副本的持 有性检查失败时，利用其他副本及时恢复该副本的数据。此 外，由于 owner 根据存储量和存储时间向 CSP 付费( 如按 GB / 月计费) ，通过多副本持有性检查，owner 可以确定 CSP 确实存储了所有副本，自己得到了所付费用相应的全部存储服务。为实现对数据的多副本检查，必须解决三个关键问题:a) 如何使得 CSP 的不同服务器所存储的副本各不相同， 若各服务器存储相同的副本，则 CSP 可以在只存储一个副本的情况下声称其存储了所有副本。将各服务器的编号与 M 连接后采用相同密钥加密，可以在简化密钥管理工作的情况下得 到不同的数据副本。b) 如何实现对所有副

34、本的批量检查。由于上述数据持有性证明方案的验证标签具有同态性，因而可以方便地实现对所 有副本的批量检查。c) 如何实现对各副本的数据更新。当插入或修改某个数据块时，先加密得到不同的数据块副本并计算出相应的多个验 证标签，从而可分别更新各数据副本。多副本检查算法的关键 步骤如下:设有 s 个副本，Fid 表示数据标志TagBlock: czi = Ek0 ( Fidzmi) ，hzi = Hsk ( f( vi) z SNi ) ，tzi =gczi + hzi mod N ( 1zs，1in) 。 j zij zijProve: C = s c a c mod N，T = s c taj mo

35、d N。5结束语本文首先提出了一种能保护数据隐私的动态数据持有性证 明方案，证明了该方案的安全性，并对其存储、计算和传输负载 等性能开销进行了分析。其次，对方案进行了扩展，使其实现了 对公开可验证和多副本检查的支持。下一步将在此基础上研究 数据共享应用中的持有性证明问题，使一个用户组中的每个用 户都可以存储和更新数据，并对数据的完整性进行检查。参考文献:1 DESWARTE Y，QUISQUATER J J，SAIDANE A Remote integrity checkingC/ / Proc of the 6th Working Conference on Integrity and In

36、ternal Control in Information Systems New York: Springer US， 2003: 1-112 ATENIESE G，BURNS R，CURTMOLA R，et al Provable data posses- sion at untrusted storesC/ / Proc of the 14th ACM Conference on Computer and Communications Security New York: ACM Press， 2007: 598-6093 JUELS A，KALISKI B S Pors: proofs

37、 of retrievability for large filesC/ / the 14th ACM Conference on Computer and Communications Security New York: ACM Press，2007: 584-5974 ZHU Yan，WANG Huai，HU Ze-xing，et al Dynamic audit services for integrity verification of outsourced storage in cloudsC/ / Proc of ACM Symposium on Applied Computin

38、g New York: ACM Press， 2011: 1550-15575 ZHENG Qing-ji，XU Shou-huai Fair and dynamic proofs of retriev- abilityC/ / Proc of the 1st ACM Conference on Data and Applica- tion Security and Privacy New York: ACM Press，2011: 237-2486 LIU Fei-fei，GU Da-wu，LU Hai-ning An improved dynamic provable data possession modelC/ / Proc of IEEE International Conference on Cloud Computing and Intelligences Systems 2011: 290-2957 WANG Qian，WANG Cong，REN Kui，et al Enabling public audi- tability and data dynamics for storage security in cloud computingJ IEEE Trans on Parallel and Distributed Systems，2011，22( 5