随着计算机技术的快速发展，云计算^[1]已经成为计算机技术的一种应用趋势。由于个人有限的计算资源和通信带宽等的限制，个人无法承担越来越大的计算任务，所以需要寻求一种新的方式将用户从繁重的计算任务中解脱出来。云计算能够将许多分散的计算机连接起来，形成一个巨大的分布式系统，大大增强了计算机的计算能力。用户将个人的数据存储在云服务器，不仅减轻了本地存储带来的存储负担，也使得数据可以被用户随时随地访问。

尽管云计算技术具有诸多优点，但随之而来的问题是如何确保数据的安全性^[2]。用户将个人数据存储在云服务器上，但是云服务器为了自身的经济利益，可能故意删除用户的一部分数据；即使云服务器能够诚实地存储用户数据，也不可避免由于软硬件故障而造成的数据损坏问题。当上述问题发生时，云服务器可能会隐藏这些错误，使用户相信数据仍然被正确地存储在云服务器。为确保用户存储在云服务器上数据的正确性，需要定期地检查云服务器上数据的完整性。

目前，有一些方案^{[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]}已经能够检测远端用户数据的完整性。考虑到用户的计算资源和通信带宽有限的情况，或是有些用户可能无法连接网络，用户如果要检查数据的正确性，可以委托专业的代理服务器进行数据的完整性检查。虽然文献[14]提出了一种代理数据拥有协议，但是这种协议只支持静态数据的存储，不能实现用户的插入、删除和修改操作。

本文基于Merkle Hash树^{[13, 19]}和双线性对^{[13, 14]}技术，对文献[13, 14]的方案进行扩展，提出了一种支持动态操作的代理远端数据完整性审计方案。获得用户授权的代理服务器，代替用户执行数据完整性检查的任务，这不仅大大减轻了用户的负担，而且还能增强用户对远端数据的隐私性保护。另外，本文的方案使用了一种有序的二叉树结构——Merkle Hash树，使得该方案能够很好地支持用户的动态操作。最后，本文对方案进行了安全性分析和性能分析，表明该方案是安全和高效的。

在这一部分中，首先介绍系统模型；然后描述系统的安全模型，即介绍系统模型中存在的安全性问题。

系统模型如图 1所示，包含3个实体——用户、云服务器和代理服务器。

图1

图1 系统模型

在系统模型中，用户将个人数据存储在云服务器上，并删除本地数据副本，这样可大大减轻用户的存储负担。用户将远端数据完整性检查的任务委托给代理服务器，当代理服务器拥有用户的授权并通过授权的验证时，就可以代替用户执行远端数据的完整性检查。然后，代理服务器向云服务器发起数据完整性检查的请求，云服务器生成一个证明并将其返回给代理服务器。最后，代理服务器对证明进行验证，并可将验证的结果告知用户。如果云服务器能够通过数据完整性的验证，就说明用户的数据被正确地存储在云服务器上；否则，就说明用户存储在云服务器上的数据被损坏。

在云存储系统中，不仅要确保用户存储在云服务器上数据的正确性，还要支持用户更新数据的需求。由于云服务器是半可信的，且动态操作存在不安全的问题，所以系统可能会出现如下形式的攻击：

1) 重放攻击和伪造攻击。由于标签的形式为$H(k,i)$，所以更新之后第i个数据块的标签仍然为$H(k,i)$。如果云服务器没有将“数据块-签名”更新为$({{m}_{i}}^{*},{{\sigma }_{{{m}_{i}}^{*}}})$，当代理服务器进行远端数据的完整性检查时，云服务器可以使用已经过期的$({{m}_{i}},{{\sigma }_{{{m}_{i}}}})$和$H(k,i)$计算证明以欺骗代理服务器。为避免插入数据块时需重新计算签名的问题，可以使用数据块${{m}_{i}}$替换索引值i。由于用户没有在本地存储个人数据，所以标签只能由云服务器生成，那么云服务器就可以使用任意组合的聚合“数据块-签名”以通过代理服务器的数据完整性检查。当云服务器使用这种方式应对代理服务器的数据完整性检查时，只需存储一个“数据块-签名”即可通过代理服务器的检查。为防止云服务器伪造标签，需要增加对标签的验证过程，以确保标签和数据块是相对应的。

2) 删除数据块的攻击。云服务器可能预先计算并存储聚合的“数据块-签名”，并将用户存储在云服务器上的“数据块-签名”删除。当代理服务器执行远端数据的完整性检查时，云服务器就可以将预先计算的“数据块-签名”发送给代理服务器，以欺骗代理服务器。

在这一部分中，首先介绍协议的基本方案，然后介绍协议的动态操作的算法。

假设考虑的数据对象是集合M，包含n个数据块，即$M=\{{{m}_{1}},{{m}_{2}},\cdots ,{{m}_{n}}\}$，其中${{m}_{i}}\in {{Z}_{p}}^{*}$并且$p$是一个大素数。基本方案由6个算法组成，下面介绍具体构造。

1) $\text{SetUp}({{1}^{\lambda }})\to k$。用户选择一个随机数$x\in {{Z}_{p}}^{*}$作为私钥，计算$X={{g}^{x}}$作为公钥，从而得到密钥对$(x,X)$。同理，云服务器得到密钥对$(y,Y)$，代理服务器得到密钥对$(z,Z)$。用户、云服务器和代理服务器分别计算$\hat{e}{{(Y,Z)}^{x}}$、$\hat{e}{{(X,Z)}^{y}}$和$\hat{e}{{(X,Y)}^{z}}$，从而得到系统中三方共享的一个密钥k。根据双线性对^{[13, 14]}的知识可知，显然有等式$k=\hat{e}{{(g,g)}^{xyz}}=$$\hat{e}{{(Y,Z)}^{x}}=\hat{e}{{(X,Z)}^{y}}=\hat{e}{{(X,Y)}^{z}}$成立。用户还需要生成一个授权$a$，这个授权描述了代理服务器具有的执行远端数据完整性检查的权限。为确保上述授权的完整性，用户需要对其进行签名，记为${{\sigma }_{a}}$。远端数据完整性检查包含对授权的验证，当验证通过后才允许代理服务器执行后续的步骤。

2) $\text{TagGen}(M)\to (\Phi ,{{\sigma }_{R}})$。给定数据集合$M=\{{{m}_{1}},{{m}_{2}},\cdots ,{{m}_{n}}\}$，用户选择一个随机数$u\in {{G}_{1}}^{*}$，用于对数据块进行签名，所以用户的公钥为$(X,u)$，私钥为x。用户计算数据块的标签和签名，具体步骤如下：

① 计算标签${{T}_{{{m}_{i}}}}=H(k,{{m}_{i}})$，用于生成签名和构造MHT。② 计算数据块的签名${{\sigma }_{{{m}_{i}}}}={{({{T}_{{{m}_{i}}}}{{u}^{{{m}_{i}}}})}^{x}}$，并记签名的集合为$\Phi ={{\{{{\sigma }_{{{m}_{i}}}}\}}_{1\le i\le n}}$。③ 对MHT的根$R$和$a$分别进行签名得到${{\sigma }_{R}}={{(H(k,R))}^{x}}$和${{\sigma }_{a}}={{(H(k,a))}^{x}}$。另外，数据集合$M$的标签用${{T}_{M}}=\text{name}||n||R||\text{Si}{{\text{g}}_{x}}(\text{name}||n||R)$表示，以便记录数据对象的相关信息。

用户将$\{M,{{T}_{M}},\Phi ,{{\sigma }_{R}},a\}$发送给云服务器，并且删除本地个人数据的副本。云服务器收到用户发送的数据后，将其存储在云服务器上。另外，用户需要将$\{a,{{\sigma }_{a}}\}$发送给代理服务器，以便用于执行远端数据的完整性检查。为确信云服务器诚实地应对代理服务器的数据完整性检查，用户和代理服务器需要存储${{T}_{M}}$，并且每一次更新操作之后都需要重新计算并存储${{T}_{M}}$。

3) $\text{SignVerfiy}(a,{{\sigma }_{a}})\to \{1,0\}$。代理服务器收到用户发送的$(a,{{\sigma }_{a}})$，执行验证算法验证等式$\hat{e}({{\sigma }_{a}},g)\overset{?}{\mathop{=}}\,\hat{e}(H(k,a),X)$是否成立。如果等式成立，代理服务器就接受$(a,{{\sigma }_{a}})$；否则，代理服务器将拒绝$(a,{{\sigma }_{a}})$，并要求用户发送新的$(a,{{\sigma }_{a}})$。

4) $\text{CheckTag}({{\sigma }_{R}})\to \{1,0\}$。当云服务器收到用户的存储请求之后，执行算法以验证标签的正确性。为了提高验证的效率，只需要验证MHT的正确性，验证过程如下：

① 存储用户的数据，并诚实地构造MHT以得到根$\hat{R}$。② 判断等式$\hat{e}({{\sigma }_{R}},g)\overset{?}{\mathop{=}}\,\hat{e}(H(k,\hat{R}),X)$是否成立。如果等式成立，云服务器就接受用户的存储请求；否则将拒绝用户的存储请求，并要求用户重新发送数据。

5) $\text{GenProof}(M,C,\Phi )\to P$。假设代理服务器选择的挑战集为$C=\{(i,{{v}_{i}})\}$，即代理服务器为执行远端数据完整性检查而发送的随机系数，其中$i\in \{{{s}_{1}},{{s}_{2}},\cdots ,{{s}_{c}}\}\subseteq \{1,2,\cdots ,n\}$且假设${{s}_{1}}\le {{s}_{2}}\le \cdots $$\le {{s}_{c}}$。在发送挑战之前，代理服务器需要将${{T}_{M}}$发送给云服务器，表明将对数据集合$M$执行完整性检查。代理服务器将$C$和$(a,{{\sigma }_{a}})$发送给云服务器，云服务器首先需要验证代理服务器授权的合法性。验证通过后才允许代理服务器执行数据的完整性检查，否则将拒绝代理服务器的请求。算法的执行过程如下：

① 判断等式$\hat{e}({{\sigma }_{a}},g)\overset{?}{\mathop{=}}\,\hat{e}(H(k,a),X)$是否成立，如果成立则执行步骤2)，否则结束。② 计算$m=\sum\limits_{i={{s}_{1}}}^{{{s}_{c}}}{{{v}_{i}}{{m}_{i}}}$和$\sigma =\prod\limits_{i={{s}_{1}}}^{{{s}_{c}}}{{{\sigma }_{{{m}_{i}}}}^{{{v}_{i}}}}$。③ 生成辅助信息集合${{\{{{\Delta }_{i}}\}}_{{{s}_{1}}\le i\le {{s}_{c}}}}$，该信息用于构造MHT。④ 输出证明P=$\{m,\sigma ,{{\{{{T}_{{{m}_{i}}}}{{\Delta }_{i}}\}}_{{{s}_{1}}\le i\le {{s}_{c}}}},{{\sigma }_{R}}\}$，并将$P$返回给代理服务器。

6) $\text{VerifyProof}(C,P)\to \{1,0\}$。当代理服务器收到证明$P$时，就执行下面的验证过程：

① 使用${{\{{{T}_{{{m}_{i}}}},{{\Delta }_{i}}\}}_{{{s}_{1}}\le i\le {{s}_{c}}}}$构造MHT，生成根$R$。②判断等式$\hat{e}({{\sigma }_{R}},g)\overset{?}{\mathop{=}}\,\hat{e}(H(k,R),X)$是否成立；如果等式成立则执行步骤③，否则输出“0”并结束。③ 判断等式$\hat{e}(\sigma ,g)\overset{?}{\mathop{=}}\,\hat{e}(\prod\limits_{i={{s}_{1}}}^{{{s}_{c}}}{{{T}_{{{m}_{i}}}}^{{{v}_{i}}}\cdot {{u}^{m}}},X)$是否成立；如果成立则输出“1”，否则输出“0”。

对于远端数据，动态操作包括3种类型——插入(insert)、修改(modify)和删除(delete)。假设数据集合$M$、签名$\Phi $和${{\sigma }_{R}}$签名已经生成，并存储到云服务器上，同时云服务器已经成功构造MHT。动态操作协议包含3个角色，将分4个步骤进行，下面详细介绍其过程。

1) 生成更新操作的消息。该步骤生成更新操作的消息，即执行算法$\text{PrepareUpdate}()$，下面将分3种情况进行描述。

插入操作：假设用户想在第i个位置上插入一个新的数据块${{m}^{*}}$，那么需要将更新请求的消息${{M}_{u}}=(\text{Insert},i,{{m}^{*}},{{\sigma }_{{{m}^{*}}}})$发送给云服务器，其中数据块的标签和签名分别为${{T}_{{{m}^{*}}}}=H(k,{{m}^{*}})$和${{\sigma }_{{{m}^{*}}}}={{({{T}_{{{m}^{*}}}}{{u}^{{{m}^{*}}}})}^{x}}$，i表示数据块插入的位置。

修改操作：修改操作的过程和插入操作类似，只需将更新消息修改成${{M}_{u}}=(\text{Modify},i,{{m}^{*}},{{\sigma }_{{{m}^{*}}}})$，即将第i个位置的数据块修改为${{m}^{*}}$。

删除操作：对于删除操作而言，只需将更新消息修改成${{M}_{u}}=(\text{Delete},i)$，即将第i个位置的数据块删除。

最后，当更新请求的消息${{M}_{u}}$生成之后，用户就将其发送给云服务器，以便执行更新操作。

2) 执行更新操作。当云服务器收到更新请求的消息后，将会执行算法$\text{ExecUpdate}()$，下面详细介绍其过程。

① 云服务器计算标签${{T}_{{{m}^{*}}}}=H(k,{{m}^{*}})$。② 插入数据块时，云服务器计算$h({{T}_{{{m}^{*}}}})$作为MHT的叶子结点，并将其插入到相应的位置，如图 2所示；同时云服务器需要存储数据块${{m}^{*}}$和签名${{\sigma }_{{{m}^{*}}}}$。修改数据块时，云服务器将MHT的第i个叶子结点替换为$h({{T}_{{{m}^{*}}}})$，同时将数据块${{m}_{i}}$和其签名${{\sigma }_{{{m}_{i}}}}$分别替换为${{m}^{*}}$和${{\sigma }_{{{m}^{*}}}}$。删除数据块时，云服务器将MHT的第i个叶子结点删除，同时删除数据块${{m}_{i}}$和其签名${{\sigma }_{{{m}_{i}}}}$。③ 云服务器更新MHT，得到新的根${R}'$，最终生成证明${{P}_{u}}=({{\Delta }_{i}},{{T}_{{{m}_{i}}}},{{\sigma }_{R}},{R}')$，并将其返回给用户。

图2

图2 MHT的结构

3) 验证更新操作。当用户收到云服务器发送的证明${{P}_{u}}$后，将执行算法$\text{VerifyUpdate}()$，验证云服务器是否正确地执行更新操作，过程如下：

① 用户使用$\{{{\Delta }_{i}},{{T}_{{{m}_{i}}}}\}$构造MHT的根$R$，并判断等式$\hat{e}({{\sigma }_{R}},g)\overset{?}{\mathop{=}}\,\hat{e}(H(k,R),X)$是否成立；如果等式不成立，则输出“0”并结束，否则执行步骤②。② 用户根据3种不同的动态操作，分别更新MHT并生成新的根${R}''$，然后比较${R}''$和${R}'$是否相等；如果不相等，则输出“0”并结束，否则执行步骤③。③ 用户对${R}'$进行签名得到${{\sigma }_{{{R}'}}}={{(H(k,{R}'))}^{x}}$，并将其发送给云服务器，最后系统输出“1”。

4) 执行数据的完整性检查。当上述3个过程都正确执行以后，代理服务器就可以向云服务器发起挑战，执行远端数据的完整性检查。如果云服务器通过完整性检查，用户就可以删除本地数据；否则，需要执行多次远端数据的完整性检查，以确信云服务器上的个人数据没有被损坏。

这一部分将分析方案的安全性，解决方案中存在的安全性问题。

本文方案将会移除标签中的数据块索引值i，即将$H(k,i)$替换为$H(k,{{m}_{i}})$，这样在对数据进行更新时，$H(k,{{m}_{i}})$会发生改变，MHT也会随之发生改变。$H(k,i)$可以被系统中任意一个合法的实体生成，而本文方案中的$H(k,{{m}_{i}})$却只能由云服务器生成，所以需要验证标签是否被恶意的云服务器伪造。

在验证数据块的正确性之前，需要对标签的正确性进行验证。如果标签通过验证，则说明云服务器没有伪造标签，可继续进一步的数据完整性验证；否则，说明云服务器伪造了标签，将结束验证的过程。因为用户将数据存储在云服务器或是执行更新操作后，都对MHT的根进行重新签名，所以云服务器无法对MHT的根进行伪造。根据抗碰撞Hash函数的单向性可知，云服务器伪造的标签不能以一个不可忽略的概率通过代理服务器的验证。同理，如果云服务器使用过期版本的数据块替换最新版本的数据块，将不能通过代理服务器对标签的验证过程。

为防止云服务器使用任意组合的聚合“数据块-签名”欺骗代理服务器，需要对数据块对应的标签进行验证。假设云服务器已经通过上述的验证过程，当代理服务器随机地选择${{s}_{c}}$个数据块以执行完整性检查时，那么聚合的数据块数量就存在$C_{n}^{1}+$$C_{n}^{2}+\cdots +C_{n}^{n}={{2}^{n}}-1$种组合。同时代理服务器向云服务器发送了${{s}_{c}}$个随机系数，所以云服务器需要存储的数据块数量将远远大于n。通过上述分析可知，如果云服务器想要通过预先计算聚合数据块的方式通过代理服务器的验证是不现实的。

在这一部分中，首先对执行远端数据完整性检查的5种方案进行性能比较，然后对本文和文献[14]的方案进行模拟分析。

假设n表示用户总的数据块数量，b表示损坏的数据块数量，c表示代理服务器向云服务器发起远端数据完整性检查时选择的数据块数量，那么可以计算出5种方案的检查概率都相等，如表 1所示。由于要支持动态操作，所以需要引入能够支持动态操作的数据结构，本文使用的是MHT。如果修改某个数据块，那么只会影响验证路径上结点的hash值，MHT的这种优点将大大降低更新操作的复杂度。

表1

表1 执行远端数据完整性检查的方案性能比较

表1 执行远端数据完整性检查的方案性能比较 PDP[3] DPDP[5] 文献[13] PPDP[14] 本文的方案 是否支持动态操作 × √ √ × √ 是否支持代理 × × × √ √ 检测概率 $1-{{\left( 1-\frac{b}{n} \right)}^{c}}$ $1-{{\left( 1-\frac{b}{n} \right)}^{c}}$ $1-{{\left( 1-\frac{b}{n} \right)}^{c}}$ $1-{{\left( 1-\frac{b}{n} \right)}^{c}}$ $1-{{\left( 1-\frac{b}{n} \right)}^{c}}$ 用户的存储复杂度 $O(1)$ $O(1)$ $O(1)$ $O(1)$ $O(1)$ 云服务器端的存储复杂度 $O(n)$ $O(n)$ $O(n)$ $O(n)$ $O(n)$ 云服务器端的计算复杂度 $O(1)$ $O(\log n)$ $O(\log n)$ $O(1)$ $O(\log n)$ 验证的计算复杂度 $O(1)$ $O(\log n)$ $O(\log n)$ $O(1)$ $O(\log n)$

下面将本文的方案和文献[14]的方案进行模拟分析比较，其中程序编码主要基于版本0.5.11的PBC库，并且使用BLS^{[20, 21]}作为签名方案。模拟环境的配置如下：一台装有Ubuntu 13.10操作系统的计算机，主频为1.9GHz的Intel Core 2 Duo CPU和2 GB RAM，文件系统为ext4。需要说明的是，两种方案需要在相同的环境下进行多次模拟计算，所以本文进行了10次测试。

为了实现远端数据的完整性检查，需要对数据进行预处理，其中最主要的步骤是对数据块进行签名，预处理的时间如图 3a所示。从图中可以看出，当数据块长度取64 KB或是128 KB时，预处理的时间将变得很小并且减小不再明显。

图3

图3 性能分析

当代理服务器向云服务器发起远端数据完整性检查后，云服务器需要生成证明并将其返回给代理服务器，然后代理服务器判断证明的正确性。由于本文的方案需要支持动态操作，所以执行完整性检查的时间将会增大，如图 3b所示。两种方案会出现这种差别，主要原因是本文的方案为抵御重放攻击和伪造攻击，需要对MHT的构造进行验证。

云服务器生成证明后，需要将证明返回给代理服务器以便验证远端数据的正确性，证明的长度曲线如图 3c所示。考虑到预处理的时间和执行完整性检查的时间，数据块的长度不能选取的太小。从图中可看出，数据块长度可选取为64 KB或是128 KB，这样在证明的长度基本不变的情况下，执行完整性检查的时间将会变得更加合理。

通过上述分析，表明用户将数据存储在云服务器上，并将远端数据的完整性检查委托给代理服务器，可以大大减轻用户的负担。本文中为能够支持用户的动态操作而使用了MHT，虽然增加了计算和通信的开销，但是如果适当地选取数据块的长度，可使方案变得非常高效。

为确保用户的数据被正确地存储在云服务器上，用户需要做远端数据的完整性检查。但是当用户没有能力执行完整性检查任务时，就可以将该任务委托给代理服务器。本文提出的支持动态操作的代理远程数据审计协议，代理服务器能够代替用户执行远端数据的完整性检查。在本文的方案中，为支持动态操作而引入MHT，不但能很好支持用户的动态操作，而且可以大大减轻云服务器检验数据标签的签名的负担。最后，通过安全性分析和性能分析，说明本文的方案是安全和高效的。但是，本文没有给出安全性证明，所以未来需要进一步证明方案的安全性。