一种支持动态更新的远程数据完整性验证方法*

赵文强

(武汉市武昌区长虹桥37-1号 武汉 430064)



一种支持动态更新的远程数据完整性验证方法*

赵文强

(武汉市武昌区长虹桥37-1号 武汉 430064)

论文针对云存储中数据外包的特性,提出了一种支持数据动态更新的远程数据完整性验证方案,利用数据更新信息表支持数据的修改、插入、删除等动态操作,在椭圆曲线上的双线性配对算法的基础上设计了一个远程数据完整性验证方案,并对方案的正确性和性能进行了分析,分析表明该文方案是可行的。

云存储; 数据完整性; 数据动态更新

Class Number TP311

1 引言

云存储[1]能够向用户提供以互联网为载体的存储服务平台,使得存储于其上的数据能以服务的形式按需为用户所使用。但在云存储模式下,数据外包存储在云服务器中,超出了数据属主的物理控制范围,不可信的云服务提供商(Cloud Service Provider,CSP)有可能会恶意丢失或删除部分用户极少访问的数据[2],以节省存储空间;而且,为了维护其商业信誉,CSP极有可能向用户隐瞒数据丢失或损坏的事实,使得用户数据的完整性被破坏。解决该问题的一个简单直接的方法就是定期地将所有数据下载到本地,检查其完整性,但该方法会消耗大量的通信带宽和本地存储空间,导致云存储的优势不复存在。因此,本文在云存储模式下设计了一种远程数据完整性[3]验证方法,该方法能够定期地检查存储于云服务器的数据的完整性,并且支持数据的安全动态更新[4]。

2 支持动态更新的远程数据完整性验证方案

2.1 数据更新信息表

为了支持数据的动态更新,如修改、插入、删除等操作,本文为每个文件单独设计了一张数据更新信息表(Data Update Information Table,DUIT)[5]来记录每个数据块的实时状态。

DUIT的初始状态如表1(a)所示。DUIT表的第一行为表头,不包含任何实际数据信息。DUIT表共有四列,其中,Id(i)表示数据块的实际物理索引,是本文ChalGen算法的数据块的唯一标识符;并且在插入或删除操作中,索引i也会相应地改变。BID是数据块的实时逻辑索引,当有插入操作时,BID值会重复。V是数据块的版本号,初始值为0,主要用来记录数据块的修改和删除操作。E被用来记录插入和附加操作,初始值为0。拥有相同实时逻辑索引BID的数据块如果没有被修改,将通过值E来区分。数据拥有者为每个文件维护一张DUIT表以追踪数据当前的状态并且检查外包数据的完整性。

表1 数据更新信息表

2.2 数据完整性验证方案

本文的远程数据完整性验证方案是基于椭圆曲线上的双线性配对算法构造的。因此,下面首先简要介绍双线性配对算法[6]。

假定椭圆曲线上的乘法循环群G1、G2和GT具有相同的阶p、g1和g2分别是G1和G2的生成元,e是一个可计算的双线性映射[7]e:G1×G2→GT,并且具有以下特性:对于任意的u∈G1、v∈G2和所有的a、b∈Zp,有1)可计算性:e(ua,vb)=e(u,v)ab,该特性也蕴含着对于任意u1、u2∈G1和v∈G2,e(u1u2,v)=e(u1,v)·e(u2,v)成立。2)非退化性:e(g1,g2)≠1。3)可计算性,即存在一个有效的算法能够计算出e。

本文详细的远程数据完整性验证方案如下所述。

2) 标签生成算法TagGen[9]:给定一个数据文件F=(m1,m2,…,mn),其中mi∈Zp,i=1,…,n,Owner运行该算法为每个数据块mi计算一个标签σi=(H(wi)·umi)x∈G1,其中,函数H(·):{0,1}*→G1将字符串与G1中的点进行一一映射,wi=name‖BIDi‖Vi‖Ei,name∈Zp为Owner随机选取的,并作为文件F的标识符;BIDi为数据块mi在文件F中的原始索引位置;Vi是mi的更新计数器,初始值为0;Ei记录的是插入操作,对于数据块mi,若其位置处没有插入操作则Ei被置为0。每次当数据块mi处有插入操作发生时,Ei的值就会单调递增,步长为1。将所有数据块的标签集合表示为φ={σi}1≤i≤n。执行完该算法后,Owner将文件F和验证标签集合φ一起发送给CSP,并且在本地删除数据以节省存储空间。与此同时,Owner还会为每个文件F生成一个原始的数据更新信息表DUIT。

3) 质询生成算法ChalGen[10]:在每轮数据完整性审计过程中,Owner都从DUIT表的物理索引值中随机地选取c个非空值I={s1,s2,…,sc}。为不失一般性,本文假定s1≤…≤sc,这可通过一个伪随机排序算法实现。Owner首先为I={s1,s2,…,sc}中的每个si选择一个随机值vi∈Zp,然后将质询Chal={(i,vi)}i∈I发送给CSP。这些质询值指定了在该轮审计过程中被要求抽样检测的数据块。

5) 示证验证算法VerifyProof:Owner运行该算法以验证CSP发送的示证的有效性。如果等式(1)成立,算法输出1,表示所抽样的数据块是完整的;否则输出0,表示数据的完整性被破坏了。

(1)

3 数据更新操作

本文用数据更新信息表DUIT来支持数据的动态更新操作,包括数据的修改操作Modification、删除操作Deletion、插入操作Insertion,各种更新操作的详细过程如下所示。

·修改操作Modification:本文主要用DUIT表中的版本号V来记录数据的修改操作,每次当数据块被修改时,版本号V将单调地递增,步长为1。

·删除操作Deletion:本文以一种较简单的方式处理数据块的删除操作,仅仅改变要被删除数据块的版本号V值,并修改其他数据块的物理索引Id值。

·Deletion(i):当要删除数据块mi时,将其物理索引Id值置为NULL,并将其版本号Vi置为-1。然后Owner将在mi之后的数据块的物理索引Id值逐个更新,将从第i+1个数据块开始的每个数据块的Id值减1,也即j=j-1(j=i+1,…,n)。

·数据插入操作Insertion:本文将附加操作看作插入操作的一种特殊情况,即每次都在文件尾部插入数据。DUIT表中的E域被用来记录插入/附加操作,并用来区分已有数据块与新插入的数据块。

4 方案分析

4.1 方案的正确性

将式(1)的左右两边进行代替变换即可验证其正确性,如下所示。

4.2 性能分析

4.2.1 DUIT的时间复杂度分析

DUIT表可以被看作为一个有序数组,对DUIT的每个操作都可以等价为对一个有序数组的操作。对于数据块mi的更新操作,首先需要定位mi的位置,可以通过二分查找法进行,其时间复杂度为O(logn)。对于数据修改操作,由于只需要更改版本号V的值,其时间复杂度为O(1)。因此,对于数据修改操作,其平均时间复杂度为O(logn)。数据的删除操作需要更改mi的版本号V,并依此更新mi后续数据块的物理索引Id,其时间复杂度为O(n)。故数据删除操作的平均时间复杂度为O(n)。类似的,数据插入操作的平均时间复杂度也为O(n)。批量更新数据的情况与单个数据块更新的时间复杂度相同。

4.2.2 DUIT的存储开销分析

在本文DUIT表的设计中,可以将Id域设置为占4个字节,BID域占4个字节,V域占10个比特,E域占10个比特,则一个表项占用84Bit。如果一个数据块为4KB,则该表可以记录的文件大小为16TB,一个数据块可以修改1024次,在同一块数据后面可以插入1024个新数据块,可以满足大部分应用。对于1GB的文件,如果每个数据块为4KB,则该文件的DUIT占用的额外存储空间大约为2.5MB,可见本文设计的DUIT额外占用的存储空间并不多。频繁地更新操作会导致表项增多,DUIT占用的空间也会增加,但是增幅不大,如将1GB的文件通过插入操作变为2GB,DUIT占用的存储空间只增加到5MB。而且,在云存储模式下,存储资源是相对充裕廉价的,而带宽有时则成为用户体验的瓶颈。因此,消耗少量的存储资源以节省带宽资源是可行的。

5 结语

本文针对云存储中数据外包的特性,提出了一种支持数据动态更新的远程数据完整性验证方案,利用数据更新信息表支持数据的动态操作,利用椭圆曲线上的双线性配对算法设计了一个具体的远程数据完整性验证方案,并分析了方案的正确性和性能,分析表明本文方案是可行的。

[1] 武永卫,黄小猛.云存储[J].中国计算机学会通讯,2009,5(6):44-52.

[2] C Gentry. A Fully Homomorphic Encryption Scheme[D]. Palo Alto, California: Stanford University,2009.

[3] Y Deswarte, J J Quisquater, A Saidane. Remote Integrity Checking: How to Trust Files Stored on Untrusted Servers[C]//Proceedings of International Federation for Information Processing Intergrity and Internal Control in Information Systems,2004:1-11.

[4] C Wang, Q Wang, K Ren, et al. Privacy-Preserving Public Auditing for Data Storage Security in Cloud Computing[C]//Proceedings of 2010 IEEE International Conference on Computer Communication,2010:1-9.

[5] B Wang, B Li, H Li. Public Auditing for Shared Data with Efficient User Revocation in the Cloud[C]//Proceedings of 2013 IEEE International Conference on Computer Communication,2013:2904-2912.

[6] G Ateniese, R Pietro, L Mancini, et al. Scalable and Efficient Provable Data Possession[C]//Proceedings of the 4th International Conference on Security and Privacy in Communication Netowrks, Article No.9,2008.

[7] Q Wang, C Wang, J Li, et al. Enabling Public Verifiability and Data Dynamic for Storage Security in Cloud Computing[C]//Proceedings of 14th European Symposium on Research in Computer Security,2009:355-370.

[8] REN Zhengwei, WANG Lina, WU Qianhong, et al. Data Dynamics Enabled Privacy-Preserving Public Batch Auditing in Cloud Storage[J]. Chinese Journal of Electronics,2014,23(2):297-301.

[9] 冯登国,张敏,张妍,等.云计算安全研究[J].软件学报,2011,22(1):71-83.

[10] 陈海波.公有云中的安全研究[J].中国计算机学会通讯,2012,8(7):15-21.

Remote Data Integrity Verification Scheme with Dynamics Updating

ZHAO Wenqiang

(No. 37-1 Changhong Crossroads, Wuchang District, Wuhan 430064)

On the basis of the issue of outsourced data, a remote data integrith verification scheme which supports data dynamics updating is proposed. A data updating information table is designed to support data transact, insert and delete. A remote data integrity verification scheme based on bilinear pairing algorithm of elliptic curve is proposed. The analysis of the correctrness of the scheme and performance shows that this scheme is feasible.

cloud storage, data integrity, data dynamics

2015年4月5日,

2015年5月31日

赵文强,男,硕士,研究方向:信号与信息处理。

TP311

10.3969/j.issn.1672-9730.2015.10.025