基于分治表的云存储数据完整性审计方案

符庆晓

（福建师范大学数学与信息学院 福建省福州市 350117）

目前，随着云存储存储普及，越来越多的公司以及机构，为了减少本地数据存储和维护所带来的经济负担，都选择将数据外包。然而，由于对数据的物理控制不足，云中的所外包的数据并不是可信的。为了解决云数据的安全问题，研究者专注于设计远程数据检查(RDC)技术来减少云数据的安全威胁。但现有的RDC 方法使用不同的数据结构(如二叉树)来证明外包数据的完整性。但是这种数据结构只能审计普通文件大小，因为更新大型文件中的少量数据块需要重新平衡大量数据块，这会给审计人员带来明显的计算的开销。另一方面，与需要极少更新操作的归档数据相反，一些特定应用程序(如WhatApp)的大型数据，这些数据需要频繁更新。所以使用传统的数据结构来支持这种频繁更新操作，将会导致大量的计算成本。为了解决云存储服务的动态数据完整性检验方案存在的安全和效率问题，本文利用分治表和双线性对技术，提出基于分治表的动态数据完整性审计方案。

1 相关工作

外包数据审计近年成为研究课题热门。2007年Ateniese 等[1]年提出使用可证明数据方案来审计外包数据。其中主要为使用同态标签和块标签生成单个标签。但该方案造成较大计算成本。Wang等[2]提出基于双线性聚合签名和Merkle 哈希树的动态远程数据审计方案，其方案实现隐私保护公共审计和多用户环境下的批量验证，然而造成数据拥有者较高计算成本。为了降低审计过程中开销，文献[3]提出基于代数签名(Algebraic Signature)云存储中数据完整性审计，该方案可以降低外包数据审计过程中的数据拥有者和云服务器的计算消耗。但该方案无法支持云存储数据动态更新。文献[4]提出基于代数签名和Merkle 哈希树的云存储数据审计方案。由于更新需要重新平衡Merkle 哈希树，会造成较大的计算成本开销。

为此，文献[5]中提出基于代数签名数据完整性验证方案。为了减少数据审计过程中数据拥有者计算开销，该方案采用将云存储数据完整性审计工作授权第三方审计者完成。文献[5]在支持数据动态更新方面，提出Record Table(RTable)数据结构以支持外包数据动态更新，然而删除或者插入数据块(i)，必须移动其余(n-i)，这样会造成严重的计算负载。

为了更好支持云存储数据动态更新问题，本文提出的外包数据审计方案是对文献[5]提出方案进行改进，提出一种基于分治表的动态外包数据审计方案。

本方案提出一种Divide Conquer Table 数据结构(DCT)以支持外包数据的动态更新。其中DCT 数据结构在更新操作时，可以很好提高外包数据更新操作的效率，减少外包数据更新所带来计算消耗。

2 预备知识

本节介绍系统模型以及安全模型和双线性对的基本知识。

2.1 系统模型

系统模型包括3 个实体：用户，数据拥有者(DO)，云存储提供商(CSP)，第三方审核员(TPA)。

（1）数据所有者（DO）：指有存储需求的用户，与远程CSP建立通信，并将加密数据上传至云存储服务器中。

（2）云存储提供商（CSP）：该实体负责备份用户数据并生成证据作为收到的质询的响应。

（3）第三方审核员（TPA）：审核外包数据及其验证由TPA完成。

2.2 双线对基本知识

假设G1和GT是具有相同素数阶p 的2 个循环乘法群。令g 是群G1的一个生成员，那么双线对映射:G1×G1→GT满足以下性质：

（1）双线对性：任意g1,g2∈G1和任意a,b∈zp*，都有

（2）非退化性：存在g1,g2∈G1，使得

（3）可计算性：对所有g1,g2∈G1，存在一个高效的算法计算(g1,g2)。

3 云存储数据完整性方案

3.1 基本操作

3.1.1 设置阶段（1）KeyGen(1λ)→(sk,pk).用户选择2个随机数sk∈zp* 和u∈G1,并且计算pk=gsk,那么私钥为sk，公钥为（pk，u)。

（2）TagGen(F,sk)→(FID,T).DO 为每 个F[l]数据块构 造向量vl=(h(ml1),h(ml2),…h(mln) ),其中，l∈{1,2,…,s}.然后，用户为每个每个F[l]数据块计算一个同态标签其中BN 表示数据块逻辑索引，FID 表示文件F 唯一的标识。通过上述的计算，用户生成一个同态标识集合T={Tl|l∈{1,2,…s}}。

（3）用户将{F,FID,T}发给CSP，并删除该文件的本地备份。

3.1.2 质询阶段

审计者选择集合{1,2,…s}的一个子集I={s1,s2,…sc},并选择一个随机数k∈ZP*; 计算一个系数al=fk(l),其中f()是一个伪随机函数。

3.1.3 回应阶段

3.1.4 验证阶段

收到响应消息后,审核员可以通过以下方法检查外包块的完整性：

3.2 动态数据分治表操作

云存储数据更新是数据审计的一个重要的特征[6][7]，允许数据所有者(DO)在不需要下载数据的情况下，对外包数据进行更新。本小节将描述提出的数据结构DCT(分治表)，此数据结构可以高效地进行动态数据的更新操作。

方案中提出DCT(分治表)，DCT 由3 个部分组成:

（1）IN:IN 是数据块的索引值,存储数据块的具体物理地址。

（2）BN:BN 是数据块的逻辑编号，存储数据块的逻辑地址。

（3）TIME:TIME 为数据块完成更新后相对系统的时间。

数据修改：

假设文件块F[l]的需要修改为F^'' [l],则具体过程为：

（1）首先在DCT 中，通过比较l 和每个DCT 的范围来查找数据[l]的位置[p]。

（2）修改,TIME=SYSTIME。

（3）更新vl''=(h(ml1''),h(ml2''),…h(mln''))。

（5）将(FID,l,F''[l],Tl'')发给CSP。

数据插入：

假设文件块F*[l+1]插入在F[l]后面，则具体过程为：

（1）首先在DCT 中，通过比较l 和每个DCT 的范围来查找数据块[l]的位置[p]。

（2）在数据块[l]的位置[p]后创建一行位置(IN*,BN*,TIME*),IN*=l+1,BN*=Max(LN)+1,TIME*=SYSTIME。

（5）将当前DCT 的最大范围，以及其后DCT 的最小和最大范围均增加1。

（6）将(FID,l+1,F*[l+1],T*l+1)发给CSP。

数据附加：

假设需要增加新的文件块F[s+1]到文件F 后面，则具体过程为：

（1）首先在最后一张DCTlast,在表尾增加新的一行(IN',BN',TIME')。

（2）IN'=s+1,BN'=Max(BN)+1,TIME'=SYSTIME。

（3）修改最后一张D&CTlast的上界UBlast=UBlast+1，既是最后一个DCT 的最大范围增加1。

（4）vs+1=(h(m[s+1][1]),h(m[s+1][2]…) h(m[s+1][n]))。

（6）将(FID,s+1,F[s+1],Ts+1)。

数据删除：

假设需要删除文件块F[l],具体的过程为：

（1）首先根据DCT 最小和最大范围找到存储的数据块[l]，然后在DCT 中确定该块的位置[p]。

（2）删除该表的第[p]行，该表第[p]行后面的行需要向上移动。

（3）将当前DCT 的最大范围，以及其后DCT 的最小和最大范围均减1。

4 算法正确性分析

本节对云存储数据审计算法正确性进行分析。当云存储供应商(CSP)接收到质询消息时，会生成(μ,σ)作为一个证据消息，并发送给审计者。审计者能够判定CSP 是否诚实地使用的数据块和标签计算证据P.如果CSP 和审计者能够诚实地按方案进行计算，那么CSP 生成的证据P 就能够通过审计者的数据完整性检查。

证明：

私钥为sk，公钥为（pk，u)

证毕

5 实验分析

本方案的实验性能分析，主要分析包括：动态数据更新的计算成本：DO 对外包数据执行修改、插入、附加和删除更新操作所需的时间计算成本。实验配置为Intel Core i5-8250U CPU @ 1.6GHz以及8GB RAM 的PC，使用Eclipse 开发工具并使用JAVA 语言实现本方案的算法。

本文所提的方案算法与文献[5]提出的外包数据动态更新算法进行比较。实验中，DO 对外包文件F 大小为1GB 进行动态更新，外包文件F 包含125000 个数据块，每个数据块8KB。实验中更新数据块数从100 到1000 递增，间隔为100，每次更新数据块随机抽取。实验结果如图1 所示，可以看出本文提出的外包数据更新算法方案高效性。文献[5]提出的动态数据更新方案，插入或者删除数据块F[i]，然后需要移动(n-i)次，这样会造成更新操作极大的计算负载。而本文所提方案可以在更新操作中，插入或者删除数据块F[i]，只需更改移动1 次，从而可以很大程度上降低数据拥有者DO 计算负载。

图1 显示出在更新不同数据块的计算成本，实验的结果表明本文所提出方案可以显著降低更新数据的计算成本开销。

图1：更新外包数据块时间成本

6 结论与未来研究

本文提出了一种用于云存储数据的高效审计方案，提出的数据结构设计的分治表能够地支持动态数据操作，例如附加、插入、修改和删除等操作。然而本文在数据加密基础没有考虑数据冗余性，所以在接下来将研究外包数据在加密基础上的去冗余性。