基于云存储的动态组共享数据完整性验证方案

李秀艳，刘明曦，史闻博，郝旭龙，董国芳+

(1.云南民族大学 电气信息工程学院，云南 昆明 650500；2.东北大学 计算机科学与工程学院，辽宁 沈阳 110819；3.东北大学秦皇岛分校 计算机与通信工程学院，河北 秦皇岛 066004)

0 引 言

云存储服务中最常见的客户之一就是拥有大数据应用的企业用户组[1,2]，它们常需要频繁地访问和更新外包数据，借助云存储服务，企业允许他们的内部员工存储和共享数据，以及企业间的数据共享。但云存储在给企业用户带来便利的同时，也面临着各种安全威胁。

首当其冲的是数据完整性问题，当组用户(group user，GU)在云端进行数据共享时，失去了对数据的直接控制权，存储在云端的数据可能会因为硬件故障或GU的错误行为而失效，GU无法直接知道数据在云存储服务器(cloud service provider，CSP)中是否完整或正确执行[3]。为了实现用户数据的完整性验证，Yang等[4]提出一种高效的云存储审计方案，同时还支持用户的身份隐私和身份的追溯性，但在这个过程中，TPA可能会获得一些数据的相关信息，TPA只是在代表用户检查数据完整性时是可信的，其不应了解任何数据内容的相关信息。虽然现已提出了许多基于不同签名的完整性检查方案[5]，但仍存在许多安全问题[6]。因此，如何确保存储在云端共享数据的完整性成为一个亟待解决的热点问题[7]。除了数据的完整性，数据的可用性和数据可验证删除问题也同样面临着各种安全挑战[8]。特别是数据删除问题，其作为外包数据生命周期的最后一个阶段，直接决定了数据共享能否顺利结束，这对数据安全和隐私保护有着重要的意义。现有的数据删除方案有断开链接、覆盖和消除数据解密密钥3种方式[9-11]。虽然现已可以实现数据删除，但其无法实现数据删除的公开可验证性。此外对于云端数据不仅应该被访问，还应被用户端更新，如数据的插入、修改和删除操作。为了支持数据动态操作，很多研究员提出了一些基于跳表、哈希表、二叉树和Merkle树等数据结构来支持GU数据实时更新的需求[12-14]。但动态的高效性仍然未得到满足。为解决这些问题，本文提出一个基于云存储的动态组共享数据完整性验证方案。其贡献总结如下：

(1)提出一种高效且安全的基于桶的红黑树(bucket-red black tree，B-RBT)动态数据结构，该结构用来支持GU共享数据的动态操作，其在常数时间内完成数据的更新及结构的更新再平衡，实现数据操作的高效性。

(2)提出一个GU共享云数据完整性验证方案。方案基于计数布隆过滤器(counting Bloom filter，CBF)结构实现高效的公开可验证数据删除，其验证过程可在O(1) 时间内完成。还支持批量审计验证操作，不同用户的多个审计任务可以同时进行处理。

(3)通过具体的安全分析，证明了所提方案的正确性和安全性，在实验仿真中，与其它方案进行了对比分析，实验结果表明，本方案是安全且高效的。

1 问题描述

1.1 系统模型

如图1所示，本方案的系统模型由4个实体组成，包括GU、私钥生成器(private key generator，PKG)、TPA和CSP。GU：主要由组管理者(group administrators，GA)和组成员(group members，GM)构成。GA负责管理组成员之间信息的变更情况，有一定的计算和存储能力，负责为GM生成签名。一个组中有多个组成员，合法的组成员是诚实的，其中每个组成员都可以通过云服务器与其它组成员共享数据；PKG：诚信的私钥分发中心，据GU的身份信息，生成系统公共参数和组的身份密钥；TPA：它负责代表GU执行云存储审计，对数据存在诚实好奇性，审计中需要保护数据隐私。CSP：为半诚信实体，负责为GU提供巨大的存储资源和计算资源。通过云存储，企业用户可以享受到数据共享服务。

图1 系统模型

该系统模型主要包括GU共享数据审计模型和动态数据删除可验证模型。GU共享数据审计模型可描述如下：首先GU对共享数据文件进行分块和盲处理，接着对盲数据块进行签名发送给TPA，在TPA收到签名后对数据签名进行存储。当GU有审计需求时，TPA代表GU执行审计的挑战响应过程来验证数据存储的完整性；动态数据删除可验证模型描述如下：首先是GU将动态请求和动态数据签名发送给GU，GU更新特定的数据结构之后将动态请求和数据发送给CSP，CSP收到后在工作表中更新数据。当GU成员变更时，相应的在CSP中共享的数据也随之变更，特别是当一些数据块不需要时，CSP为GU删除不需要的数据块并返回验证删除结果。

1.2 威胁模型

我们考虑的安全挑战如下：首先是数据隐私泄露，CSP是半诚信实体，一方面，CSP由于硬件或软件错误或者外部攻击而修改甚至删除数据时，CSP会隐瞒数据被破坏的事实，向GU返回不正确或不完整的验证结果。另一方面，CSP可能会将数据转移给其它服务器，与其它企业共享数据，以实现经济利益；其次是资源耗尽攻击，外部攻击者或过期的GU尝试从验证信息中获取数据信息，通过发送频繁的动态更新操作来消耗云端的存储资源或将私有信息进行存储，从而增大GU的支付开销。

1.3 设计目标

(1)审计高效性：在GU请求动态操作、审计操作和删除验证期间，系统的通信开销和计算开销小，整个审计过程时延低，在发送请求后可以快速获知操作结果。数据结构检索和更新速度越快，审计效率高。

(2)数据删除可公开验证：为了保证CSP能永久的删除用户不需要的数据块，应该赋予GU验证删除结果的能力。如果CSP恶意保留数据，没有执行数据删除命令并真实地生成删除证据，那么GU会检测到恶意的数据保留。

(3)批量审计：TPA单独执行审计任务的效率很低。由于来自不同用户的多个审计任务可能正在等待同时处理，由此可以引入批处理审计来提高审计效率。

(4)数据隐私：审计中TPA无法检索出用户身份信息或数据信息，为了保护外包数据的敏感信息，在将外包数据存储到云服务器之前，需对其进行盲化，保护数据隐私安全。

2 预备知识

2.1 双线性映射对

2.2 困难假设

离散对数问题[8]：对素数p阶的乘法循环群， 给定其生成元g和Y=gx∈， 计算x∈p值是很困难的；计算Diffie-Hellman问题：对素数p阶的乘法循环群， 随机选取其中一个生成元g， 给定(g,ga,gb)∈， 在未知a,b∈p的情况下，计算值gab是很困难的。

2.3 布隆过滤器

布隆过滤器(Bloom filter，BF)是用于查询集合D中是否包含指定的元素[15]。BF可看作是一个m位的数组，在初始阶段数组中的每个位置都设为0，接着将集合D={d1,d2,…,dn} 元素di通过k个相互独立的哈希函数H={h1,h2,…,hk} 映射到数组中，对每个元素di∈D， 把数组中相应元素哈希值的位置设置为1。

2.4 红黑树

红黑树是一个自平衡的二叉查找树[16]，每个节点拥有一个附加的属性表示其颜色，可以是红色或者黑色。它通过对节点进行旋转或者重新着色来保持树的平衡。在动态操作过程中，它的插入和删除操作时间复杂度都为O(1)，查找的时间复杂度最坏为O(logn)。红黑树的属性使得一棵n个结点的RBT始终保持了logn的高度。

2.5 混 淆

3 所提动态数据结构B-RBT

3.1 符号说明

表1定义了方案中使用的符号定义。

表1 符号说明

3.2 B-RBT结构

在GU共享数据审计方案中，一方面，GU的变更会带来庞大的数据量变动，另一方面，共享数据支持常规的数据动态更新也会带来数据的存储变更，这无疑对模型中参与的各实体都会带来庞大的计算开销和通信开销。特别对于半诚信的CSP来说，数据的增加或删除对其带来的开销是巨大的。我们解决这些问题的核心是提出一个高效的数据结构来支持组共享数据的动态更新和数据删除的公共可验证。

3.2.1 结构描述

B-RBT是一种平衡搜索树，可以在最坏情况下以常数时间达到树的再平衡状态。具体来说，该结构不是在查找树的叶子节点中存储单个键组成，而是由每个叶子中存储由多个键组成的有序列表的桶构成。本方案提出的B-RBT并不需要全局重建技术，对于树中节点的删除，不需要像传统红黑树一样进行全局重建。由此该结构所需要的空间和时间更少。B-RBT结构的规则如下：①每个结点都有颜色，红色的为红结点，黑色的为黑结点；②根节点是黑色的；③每个叶节点都是黑色的桶；④如果一个节点是红色的，且父节点也是红色的，那么它的子节点都是黑色的，即所有路径上最多存在两个连续的红节点；⑤从任意节点开始到其叶节点的每条路径上黑结点的数量最多相差1。

B-RBT结构如图2所示，每个节点都有一个额外的比特位表示其颜色，每个节点都有由多个键构成的桶、左子指针、右子指针、父指针和颜色位这5个属性值。该结构将元素插入到桶中而不是内部树节点中，每个树节点存储一个路径值，该值小于或等于存储在其右子树的桶中的键，而大于其左子树中桶的键。并在单个桶增大到一定值时对桶进行分割，当相邻的两个桶减小到一定值时对桶进行合并。每个桶都包含一个头部，它将桶连接到树节点上，并存储关于桶的其它信息，例如桶的大小。对于存储桶的大小，我们的方案保存与Elmasry等[18]提出的桶阈值一致，即每个桶中的键数必须在0.5H～2H范围内。分割操作可能会导致需要在树中添加一个新的节点，并且可能会打破原来B-RBT的平衡状态。我们的目的是维护在每个桶的头中指向第一个、中间和最后一个列表节点的指针，让每个更新操作都会调用一个修复过程，并在下一次分割或合并违反树平衡状态之前修复，保证在此之前对这些指针的正确设置。

图2 B-RBT结构

由于BF只允许对元素进行插入和查询操作。它的缺陷是不支持元素的删除操作。为了实现动态更新和数据删除可验证问题，本文采用CBF。其使用一个计数器单元计数来替换BF中每个位的位置，它允许对CBF执行插入、修改和删除操作。设定CBF由m个计数器组成，元素集合D′={d′1,d′2,…,d′n}⊂S， 对于每个元素d′i∈U, 使用k个相互独立哈希函数H={h1,h2,…,hk} 将其映射到CBF的k个位置上，如图3所示。当CBF执行插入或删除操作时，对应的计数器将增1或减1。

图3 CBF结构

3.2.2 动态更新

本方案的数据结构支持高效的数据更新，具体过程如下：

(1)数据插入：首先GU先向TPA发送插入数据请求，并附带上盲数据块及生成数据签名，TPA收到后把要插入的数据块签名存储在B-RBT数据结构中，操作如下：假如GU想插入的数据块为BI={x,y}， 首先在指定桶B的指定位置插入新的列表节点，并调用桶B的修复过程。当桶超过最大阈值时，如果修复指针PK还未到达根节点R处，则重复调用B的修复过程，直到PK到达R。接着将桶B分成两个桶 {B1,B2}， 将 {B1,B2} 新的父节点B12以红色节点的形式添加到树中。并使两个新桶的指针指向新插入的节点。最后再为两个桶中的一个调用修复过程。完成签名存储后，把请求发送给CSP，CSP选取k个相互独立的哈希函数对需插入的数据块进行散列到CBF中，CBF对数据信息进行更新，在散列结果相应位置增加1，即CBF[{h1(x),h2(x),…,hk(x)},{h1(y),h2(y),…,hk(y)}]=+1并在CSP中存储这些数据记录。

(2)数据删除：其过程和插入操作相似，GU还需要对数据进行混淆生成混淆标签，然后再生成数据签名和动态请求。为了数据删除的可验证，我们对需删除的数据块先发送修改请求，对TPA和CSP中存储的数据进行修改后，再相应的发送删除请求。TPA将数据块签名从B-RBT中删除具体操作如下：假如GU想删除的数据块为BD={a，b}， 首先从桶B的删除所需列表节点，并调用两次桶B的修复过程。当桶小于最小阈值时，若修复指针PK还未到达根节点R处，则重复调用B的修复过程，直到PK到达R。如果桶B的同级桶B′的大小超过最小阈值时，B将从B′中借用一个节点，并对B′调用两次修复过程。若桶B的同级桶B′的大小不会超过最小阈值时，B和B′进行合并为一个新桶B″，合并时将右桶的键放到左桶的尾部，B″的父节点是原B或B′的祖父节点。若删除的父桶为黑色，则将B″标记为双黑色。在签名删除后，把请求发送给CSP，CBF在相应位置减1，即CBF[{h1(x),h2(x),…,hk(x)}，{h1(y),h2(y),…,hk(y)}]=-1， 并在CSP中更新这些数据记录。

(3)数据修改：修改操作是将已存储在CSP中的某些数据信息进行更正，具体操作和插入及删除一致，可看成是先对原有数据进行删除操作后，再把新的数据进行插入来完成。

3.2.3 数据删除验证

方案支持共享数据删除的可公共验证，验证CSP端是否诚实按照GU的需求永久删除不必要的数据块。如果CSP没有执行数据删除命令并真实地生成证据，那么GU很可能会检测到恶意的数据保留。方案的数据删除采用数据覆盖的思想，将覆盖操作伪装成数据更新操作，GU通过验证数据删除证据来检查共享数据的删除结果。具体操作如下：首先GU向CSP发送一个数据删除验证请求，CSP返回删除的数据证明，GU通过验证其是否有效来确定CBF的有效性。当验证通过后GU接着验证CBF中删除的数据块的哈希值对应的位置是否为0，若为0则说明删除的数据块已不在CBF中，GU终止验证并返回成功。若验证不成功，则GU接着验证CSP中对应删除请求的数据块中是否有混淆标签的标志，若存在混淆标志，则说明CSP没有按照GU请求执行数据删除操作，返回数据删除验证失败，否则返回数据删除验证成功。

4 协议设计

4.1 完整性审计协议

我们将详细描述GU数据共享审计方案协议，该协议由数据上传、完整性验证两个阶段构成。具体内容如下：

(1)KeyGen(sk,k,T1,T2,g)： PKG为GU生成公钥和密钥参数。首先，GA随机选择一个非对称加密密钥对 (ssk,pk) 和α,k∈P作为系统私钥的一部分，系统密钥为sk={α,ssk}。 PKG为GM和GA生成私钥GMID和GAID， 即GUID={GMID,GAID}。 接着GA随机选取g,μ∈1， 让y=gα,α∈P，T1和T2为授权的开始时间和结束时间。最后GA生成系统全局参数PK={g,y,H,e,μ,pk}, 其中H{0,1}*→1为单向哈希函数。

(2)GUBlind(mi,k1,GUID,Fname)： 首先GA把名为Fname的文件F分成n块，即F={m1,m2,…,mn}， 接着使用密钥种子k1∈P计算盲数据块m′i=(mi‖i)+BF,i∈[1,n]， 其中致盲因子BF=fk1(GUID‖Fname)。 最后将盲数据F′={m′1,m′2,…,m′n} 和盲因子BF发送给CSP。

(4)CSPStorage(F′,BF)： CSP收到盲数据F′后，存储通过验证的真实数据块，即计算m={mi}1≤i≤n={m′i}1≤i≤n-BF， 若对于每个数据块mi与数据块序号i相对应，则CSP对数据块mi进行存储。

4.2 数据动态协议

我们详细描述动态数据删除方案的协议，主要由数据更新和数据可删除验证两个阶段构成，具体如下：

(1)DataInsertion(BI)： 假设GU想在文件F中的数据块mi之后插入一个新的数据块mj， 首先GU发送插入的数据块信息BI={I,i,mj,T1,T2,GUID,δj} 给TPA，其中I代表操作类型为插入，i为插入数据块的位置，δj=(H(j‖T1,T2)μmj)α为插入的数据块签名。接着TPA在B-RBT结构中插入数据签名后，把 {I,i,mj,T1,T2,GUID} 发送给CSP，CSP验证后在mi之后存储该数据块。

5 协议安全分析

本节利用博弈假设的方法，证明了所提出的方案满足审计的可靠性、正确性、有效性和数据删除的不可否认性。

定理1 审计可靠性：CSP只有真正存储GU的完整数据，才能通过TPA验证，否则不能通过验证。

定理2 数据删除的不可否认性：对GU不再需要的数据进行删除时，具有对数据删除的公开可验证性。这意味着GU和CSP都无法成功否认自己的行为，相互诽谤。

定理3 审计正确性：只有CSP诚实地生成有效的标签证明TGU和有效的数据证明DCSP才能通过TPA验证，否则不能通过验证。

证明：根据双线性映射对的特点，推导验证方程的正确性可证明如下

从推导可以看出只有标签证据TGU和数据证据DCSP同时有效，才能通过TPA验证。

定理4 数据隐私安全：TPA或CSP不能在获得的数据中提取GU的原始数据。在数据上传阶段，CSP不能从盲数据中获取GU的真实数据，在审计阶段，TPA不能从数据签名和动态请求中获取GU的真实数据。

证明：数据隐私安全是指敌手在没有相应的数据解密密钥的情况下无法获得任何原数据信息。首先在数据上传阶段，盲数据块m′i和其中的致盲因子BF是由GU随机选取密钥种子生成的随机函数，且各盲数据块间是相互独立生成的，CSP对其也是随机接收的，由此CSP想从中提取出真实数据信息F可作为一个DL问题，而解决DL问题的概率可以忽略不计。其次在审计阶段，可通过如下等式验证

定理5 动态操作有效性：在动态操作过程中，半诚实的CSP必须按动态请求的要求来执行，失效的GU无法通过发送频繁的动态更新操作来消耗CSP的存储资源，无论是篡改或虚假执行动态请求操作都通过TPA的验证。

6 性能分析

6.1 计算开销

方案主要从审计过程和数据删除验证两个方面来对计算成本进行详细分析。首先在审计过程中，包括GU数据上传审计验证两个阶段。本方案与Zhang等[2]提出的基于身份的用户撤销共享审计方案(IURS Audit)、Zhang等[12]提出的支持匿名用户撤销的共享动态数据审计方案(URSD Audit)和Xue等[22]提出的基于身份的云存储用户公共审计方案(IBP Audit)在计算开销上进行对比，开销细节见表2。本方案在GU数据上传阶段有较明显的优势，在审计阶段本方案比其它3个方案开销都低，IURS Audit和IBP Audit需要计算额外的累加、幂操作和乘运算，URSD Audit需要额外计算配对、哈希和乘运算。其次在数据删除验证过程中，主要包括数据块的删除和数据块删除验证两个阶段。本方案还与Yang等[19]提出的支持数据跟踪的公开可验证删除方案(TVD Scheme)、Yang等[7]提出的可公开验证的高效细粒度数据删除方案(FGVD Scheme)和Hao等[23]提出在基于云的物联网中的一种安全、细粒度的外包数据删除方案(SFGD Scheme)进行对比分析，开销细节见表3。本方案相比于TVD Scheme和FGVD Scheme在删除和验证阶段具有显著优势，与SFGD Scheme相比本方案开销略低，在删除验证阶段本方案开销略低，其它3个方案需要进行额外的哈希操作或者验证操作。

6.2 通信开销

对于通信开销主要针对动态更新过程，由于各数据结构不同，以及存储位置不同，则导致它们的通信开销也不同。开销细节见表4。本方案的通信成本比Liu等[24]提出的基于Merkle哈希树多级索引结构的动态数据隐私保护云审计方案(MI-MHT Scheme)略低，与Yu等[20]提出的基于动态索引表的云存储公共审计方案(DIT Scheme)和Qi等[21]提出的基于秩的Merkle AVL树实现云存储动态和批量更新拥有验证方案(RB-MAT Scheme)相比有较明显的优势，此外数据结构存储在TPA端，比起存储在CSP端，需要更低的通信成本。

表2 审计过程开销对比

表3 数据删除验证过程开销对比

表4 动态更新通信开销对比

6.3 实验分析

在实验中，对本文提出的动态组共享数据完整性验证方案从审计验证过程、动态更新操作和数据可验证删除的时间开销进行性能评估。实验在配置为Intel Core i5-9300H CPU，8 GB RAM的笔记本电脑上进行，并搭建Linux虚拟机，利用C语言进行编译，算法是基于双线性配对的密码(PBC)库和GNU多精度算法(GMP)，采用MNT d159椭圆曲线，p中的一个元素的大小为160位，安全参数设置为80位。选用SH3-keccak256作为安全哈希函数。实验步骤如下：①审计阶段时间开销：首先是数据上传阶段，主要的开销源于配对和求幂操作。在实验中总的处理2000个数据块，观察数据块从400增加至2000间隔为200的时间开销，如图4所示。图4(a)看出时间成本随数据块大小线性增加，同时，本方案的时间开销比IURS Audit、URSD Audit和IBP Audit方案的时间开销都低；其次是证明验证阶段，审计阶段的计算开销可分为挑战生成和证明验证过程。其中数据挑战的开销可忽略不计，我们选取数据块从900到3600间隔为300的时间开销，图4(b)显示了审计验证的时间开销，本方案的时间开销比方案IURS Audit和IBP Audit的时间开销低，比IURS Audit的开销略低；②数据更新阶段时间开销：图5展示了对数据更新的插入和修改操作的时间开销，我们选取数据块从30到300间隔为30的时间开销。本方案的B-RBT数据结构与DIT Scheme、RB-MAT Scheme和MI-MHT Scheme进行对比，本方案的时间开销更低。其中B-RBT结构和DIT Scheme对数据块的插入和修改时间复杂度均为O(1)， 但

图4 审计阶段时间开销

图5 更新阶段时间开销

图6 验证删除阶段时间开销

DIT Scheme查找的时间复杂度均为O(logn)。 其次RB-MAT Scheme和MI-MHT Scheme的结构时间复杂度均为O(logn)， 其需要花费的时间开销较大；③数据删除验证阶段时间开销：我们选取数据块从30到300间隔为30的时间开销，如图6所示。本方案在数据删除和删除验证两个阶段的开销都比TVD Scheme的开销低。在数据删除阶段，与FGVD Scheme和SFGD Scheme相比，本方案的时间开销更低，FGVD Scheme需额外的哈希和生成签名开销，SFGD Scheme需额外的哈希和生成签名开销。在删除验证阶段，本方案采用的CBF数据结构复杂度为O(1) 有更低的时间开销。

7 结束语

本文提出一个基于云存储的动态组共享数据完整性验证方案，为企业组用户提供高效的数据共享和完整性验证支持。为了解决共享云数据完整性验证中存在的数据隐私安全性、动态更新高效性和数据删除的可验证性问题，首先GU对共享数据进行盲处理操作保证其它实体无法获取真实的数据信息，保证数据的隐私安全；其次为了实现动态高效性需求，提出B-RBT数据结构来支持数据的动态操作；接着为实现对GU不再需要的数据信息进行有效的数据删除，提出CBF数据结构来高效支持GU数据删除的可公共验证性。根据实验对比结果的表明，我们的共享数据审计方案是有效的，其具有更低的时间开销。