针对云存储的完整性验证系统通常可以分为两方模型和三方模型，其中两方模型中包含用户(Client)和云存储服务提供商(CSP)，三方模型在两方模型的基础上引入了一个可信的第三方验证者(TPA)，TPA用于为用户承担验证任务，代替用户周期性的对存储在CSP中的数据和文件进行完整性验证。本文提出的方案基于两方模型，如图 1所示。

图  1  两方模型

图中用户指有着数据在线存储需求的云存储服务用户；云存储服务器是由云存储服务提供商管理的一组服务器，具有海量的存储能力和强大的计算能力，对外提供数据存储和访问功能。在本文提出的方案中，用户在对文件进行访问时，同时获取与之对应的辅助认证信息，使用辅助认证信息对正在访问的文件进行完整性验证。本文中对文件的分块处理与文献[14]类似，即按照固定的块大小对文件进行划分，产生认证数据的基本单位是数据块。

在本文提出的协议中，用户将数据提交到云端进行在线存储前，首先需要在本地对文件进行一些处理工作，包括文件的块划分、摘要生成、跳表生成、签名等，完成上述步骤后，用户将文件和辅助认证信息一并提交到云端进行保存，之后用户便删除本地的文件副本和辅助验证信息副本，以减轻本地的存储压力。用户在访问存储在云端的文件时，获取需要访问的部分以及该部分对应的辅助认证信息，使用辅助认证信息对该部分的文件内容进行验证，以便确定该部分文件内容是否正确和完整。

跳表(skip lists)是一种能够快速进行查找、删除和插入的数据结构，跳表的结构如图 2所示。

图  2  跳表的结构

跳表包含若干层，其中每一层均由链表构建，跳表中的每一个结点均包含一个指向右边结点的指针和一个指向下方结点的指针，跳表中最左边一列和最右边一列的结点被称为哨兵结点。跳表中的底层链表有序地存储所有元素，对于某一层S_i和S_i的上一层S_i+1，出现在S_i中的非哨兵结点将以某个概率出现在上一层中，即以一定概率在S_i+1层中生成对应结点，并且哨兵结点所在列的层数不小于任何非哨兵结点所在列。

在跳表中进行查找，从左上角的结点开始，用p表示指向当前结点的指针，p只能向右或者向下移动，查找某个结点的算法描述如下：

found=false;

while(p!= null)

begin

    if(p==target)

    begin

        found=true;

        break;

    end

    else if(p.right!=guard & & p.right < target)

        p=p.right;

    else

        p=p.down;

end

查找过程结束时，p指向目标结点或者小于目标结点的最大结点。

在跳表中插入一个结点时，例如需要插入的结点编号为x，则首先执行查找x的操作，得到一个指向小于x的最大结点的指针，此时再将x结点插入到p所指向的结点的后面，并概率性地产生x结点的上层结点。

执行删除操作时，首先执行查找操作找到小于目标结点的最大结点所在位置，之后删除目标结点以及目标结点所在列的所有结点，该过程与在链表中删除一个结点类似。

标准的哈希函数只有一个输入参数，可交换哈希函数是一种包含多个输入参数的哈希函数，并且当输入参数均保持不变时，任意交换各个参数的输入顺序，函数的输出是一致的。包含2个输入参数的可交换哈希函数满足下述性质：

式中，EH是可交换哈希函数，本文使用的可交换哈希函数包含3个输入参数。

在云存储系统中，由于云存储服务器是半可信的，因此用户存储在云端的文件面临着损坏、篡改甚至被云存储服务提供商有意删除等风险，而云存储服务提供可能会为了维护其自身利益而向用户隐瞒并且试图在文件的完整性被破坏后通过某种方法使得用户不能发现文件的完整性已经被破坏，所以该系统中可能会出现如下形式的攻击：

1) 伪造数据块的攻击。用户在访问某个存储在云服务器中的数据块时，如果云服务器发现该数据块存在丢失、部分丢失或被篡改的情况，云服务器可能会通过某种技术手段伪造一个数据块提供给用户，从而使得用户不能发现完整性已被破坏。

2) 伪造辅助认证信息的攻击。用户在访问某个存储在云服务器中的数据块时，如果该数据块或对应的辅助认证信息存在丢失、部分丢失或者被篡改的情况，云服务器可能会伪造一对对应的数据块和辅助认证信息提供给用户，从而使得用户不能发现完整性已被破坏。

本文对跳表的改进主要有3点：

定义1 定义跳表中的子结点。对于跳表中的结点i，定义其左边的结点j和下面的结点k为结点i的子结点，如果结点j是所在列的顶层结点，则称j是i的实子结点，否则称j是i的虚子结点。

定义2 跳表中的底层非哨兵结点存储2个哈希值，分别称为contentHash和nodeHash。跳表中的其他结点只存储nodeHash，其中contentHash直接通过使用哈希函数对数据块计算摘要得到。

定义3 跳表中的结点不再存储对应的数据块的索引，而是存储以该结点为祖先结点的底层结点数量。

根据定义1可知本文所使用的跳表的根结点为右边哨兵结点的顶层结点，该跳表的结构如图 3所示，其中虚线框代表的是虚子结点，虚线箭头为父结点指向虚子结点的指针，方框内“+”和“-”为哨兵结点。

图  3  改进的跳表结构

在该跳表中，底层结点中的contentHash用于存储数据块的摘要值。假设当前结点是i，i的左子结点是j，i的下子结点是k，计算i结点的nodeHash时，根据下面所定义的依赖关系进行。

1) 若k==null，即i是底层结点。

① 如果i是哨兵结点，并且j是虚子结点：

② 如果i是哨兵结点，并且j是实子结点：

③ 如果i不是哨兵结点，并且j是虚子结点：

④ 如果i不是哨兵结点，并且j是实子结点：

2) 若k!=null，即i是非底层结点。

① 如果j是虚子结点：

② 如果j是实子结点：

式中，φ是一个特定的字符串。根据上述依赖关系可知，在本文所使用的跳表中，信息的流向所构成的结构为树状结构，并且该树状结构的根结点为跳表的右上方结点。

根据定义3，本文使用的跳表中不记录数据块在文件中的索引，而使用可达范围计数来确定跳表结点与数据块的对应关系，因此在某个位置新加入一个结点后，不需要对该结点之后的每一个结点进行修改，只需要修改从新加入结点到根结点这一条路径上所经过的结点的可达范围计数，该路径的平均长度为log(n)，因此能够更高效的对动态操作提供支持。使用可达范围计数标识数据块与结点对应关系的跳表结构如图 4所示。其中椭圆型框图代表数据块，其中的数字代表数据块索引；跳表中各个结点中的数字代表可达范围计数。对于结点i以及其左子结点j和下子结点k，如果j是虚子结点，则i的计数等于k的计数；如果j是实子结点，则i的计数等于j与k的计数之和。

图  4  使用可达范围计数的跳表结构

在图 4所示的跳表中进行查找某个数据块对应的结点时，指针p开始时指向根结点，查找算法如下：

if(p.reachableCount < target)

    return null;

while(p.down!= null)

begin

    if(p.left.isReal==false)//是虚子结点

      p=p.down;

    else if(p.left.reachableCount > =target)

      p=p.left;

    else

    begin

      target=target-p.left.reachableCount;

      p=p.down;

end

end

if(p.right==null)//是右边的哨兵结点

    p=p.left;

steps=p.reachableCount-target;

for(1:steps)

    p=p.left;

return p;

在执行查找操作时，可以使用栈来记录过程中经过的结点路径，使用该路径可以得到目标结点对应的辅助认证信息。在该跳表中执行数据块的插入和删除操作时，首先执行查找操作，其余部分与基础跳表的操作方法类似，在此不再赘述。

假设用户需要提交到云服务器进行保存的文件是M，M包含n个数据块，即$ M = \{ {m_1}, {m_2}, \cdots, {m_n}\} $，基本方案由3个步骤组成。

1) $ {\rm{SetUp}}({1^\lambda }) \to (H, {\rm{EH}}, {\rm{sk}}, {\rm{pk}}) $。用户选择随机数$ x \in {Z_p}^* $，得到用户私钥$ {\rm{sk}} = (x, g) $，其中g是群G的生成元，G是基于椭圆曲线构造的乘法循环群，G的阶数为p。用户根据私钥计算公钥$ {\rm{pk}} = (y, g) $，其中$ y = {g^x} $，根据双线性对的性质^[15]，有等式$ e(y, g) = e{(g, g)^x} = e(g, y) $成立。同时用户还需要选择在协议中使用的哈希函数和可交换哈希函数；

2) $ {\rm{GenSL}}(M, H, {\rm{EH, sk}}) \to ({\rm{SL}}, \sigma ) $。用户对文件M进行分块处理，得到数据块集合$ M = \{ {m_1}, {m_2}, \cdots, {m_n}\} $，并产生跳表SL，SL的底层结点数量为n+2，包含2个哨兵结点和n个非哨兵结点。之后用户使用哈希函数H计算数据块集合中每一个元素的摘要指，并将摘要值按顺序写入跳表底层非哨兵结点的contentHash中。最后用户使用可交换哈希函数EH计算SL中每一个结点的nodeHash值，并使用私钥sk对根节点r的nodeHash值进行签名，得到签名值σ。完成上述步骤后，用户将$ ({\rm{SL}}, \sigma ) $和文件M提交到云存储服务器进行在线存储；

3) $ {\rm{Verify}}({m_i}, {\eta _i}, \sigma, H, {\rm{EH}}, {\rm{pk}}) \to {\rm{true/false}} $。当用户访问数据块集合中的某个数据块m_i时，云存储服务器一并向用户返回数据块m_i、辅助验证信息η_i和根结点的签名σ。辅助验证信息是一个集合，包含从m_i所对应的跳表结点到根节点所在路径上的所需nodeHash，根据跳表的性质，该集合的大小平均为log(n)，因此根据2.1节中定义的依赖关系，可以使用m_i和辅助验证信息η_i计算出根节点r′。用户计算出r′后，使用数字签名σ验证r′的合法性，如果验证通过则系统返回true，否则返回false。

在本方案中，动态操作包括3种类型：数据块的修改(update)、插入(insert)和删除(delete)。假设认证结构SL和签名σ已经生成并提交到云存储服务器中进行保存，下面介绍动态操作过程。

1) 用户产生操作消息。用户执行算法GenOPMsg()，下面对不同的操作类型进行描述。

修改操作：假设用户对索引为x的数据块进行修改，得到新数据块${m'_x} $，则用户产生消息$ ({\rm{update}}, x) $，并将消息发送至云存储服务器。

插入操作：假设用户需要在文件中的x位置新插入一个数据块m_x，则用户使用特定概率计算新插入数据块在跳表中对应的结点所在列的层数L，并将消息$ ({\rm{insert}}, x, L) $发送至云存储服务器。

删除操作：假设用户需要删除文件中的第x个数据块，则用户产生消息(delete, x)并发送至云存储服务器。

2) 更新SL与签名。云存储服务器在接收到用户的动态操作请求后，根据消息内容返回所需的辅助认证信息，以便用户对SL进行更新和对新的SL签名，下面详细介绍其过程。

修改操作：云存储服务器返回原数据块m_x所对应的辅助认证信息η_x。用户接收到η_x后，使用$ {m'_x} $计算摘要值并将其作为第x个跳表结点的contentHash，再根据辅助认证信息η_x计算得到根节点的nodeHash，并对其签名。

插入操作：云存储服务器在SL中的第x个位置新插入一列结点，该列的高度为L。此时新插入结点的contentHash和nodeHash均为空值，然后执行查找算法find(x)并得到辅助认证信息η_x，云存储服务器将η_x返回给用户，用户使用m_x计算摘要值并将其作为第x个跳表结点的contentHash，再根据辅助认证信息η_x计算得到根节点的nodeHash，并对其签名。

删除操作：云存储服务器将目标结点x所在列删除，目标结点后面的结点将占据第x个位置。此时云存储服务器执行算法find(x)得到第x个节点的辅助认证信息η_x，并将η_x与删除第x个数据块后、在文件中的索引变更为x的数据块m_x返回给用户。用户根据m_x和η_x计算得到SL根结点的nodeHash并对其签名。

3) 提交更改。如果用户执行的是修改操作，则向云存储服务器提交$ ({m'_x}, \sigma ') $；如果执行的是插入操作，则向云存储服务器提交$ ({m_x}, \sigma ') $；如果执行的删除操作，则向云存储服务器提交$(\sigma ') $。

本协议的攻击类型主要有数据块伪造攻击和辅助认证信息伪造攻击两种，下面分别对其进行简要的安全性分析。

1) 数据块伪造攻击。假设在用户对数据块m_x进行完整性验证时，云存储服务器伪造了一个数据块$ {m'_x} $并且${m'_x} \ne {m_x} $，云存储服务器向用户返回$ ({m'_x}, {\eta _x}, \sigma ) $，假设该三元组能够通过验证，则等价于云存储服务器有能力找到$ {m_1} \ne {m_2} $，使得$ {\rm{Hash}}({m_1}) = {\rm{Hash}}({m_2}) $，但根据哈希函数的单向性和抗碰撞性，这个问题是一个困难问题，因此上述三元组不能以不可忽略的概率通过用户的验证，本协议能够抵抗数据块伪造攻击。

2) 辅助认证信息伪造攻击。假设云存储能够用不合法的数据块$ {m'_x} $代替合法数据块m_x计算出非法的SL根节点nodeHash并对其签名，并且该非法签名和非法的SL根结点nodeHash能够通过用户的公钥验证，则等价于云存储服务器能够在没有私钥的情况下产生合法签名，根据数字签名的定义，可知该问题是一个困难问题，因此云存储服务器无法以不可忽略的概率产生合法签名，本协议能够抵抗辅助认证信息伪造攻击。

将本文算法与另外3种针对云存储环境的数据完整性验证方案进行性能对比，之后将本文的方案与文献[14]的方案进行模拟分析实验。本文所提出的协议与文献[14]中所提出的方案在初始化阶段均需生成辅助认证信息，而产生辅助认证信息的时间复杂度均为O(n)，且产生的认证结构中所包含的节点数量的期望值均为文件块数量的2倍，因此该部分不做性能测试。

设n代表用户需要存储在云服务器中的文件包含的数据块数量，本文与PDP方案、文献[10]和文献[14]方案的性能分析对比结果如表 1所示。

为支持动态操作，需要使用能够支持动态操作的认证性数据结构，本文方案使用的是前面介绍的跳表。在验证时，从根结点到目标结点的平均路径长度是logn，因此验证时的计算复杂度是O(logn)，如表 1所示。

下面将本文的方案与文献[14]中的方案进行模拟对比实验。实现环境的配置为：主频为3.2 GHz的双核CPU台式计算机，8 GB内存，64位Windows 7操作系统，编码所用的开发语言为Java，使用的密码学工具库为jPBC v2.0.0。

对于日志文件，在文件的尾部追加内容是一种常态操作。本文测试的场景为连续向文件尾部追加数据块，测试开始前用大小为1 GB的文件产生认证结构，文件块的大小设置为8 KB，通过在文件的尾部追加不同数量的文件块以造成认证结构出现不同程度的不平衡。测量在不同程度的不平衡状态下，为每一个追加的文件块进行结构调整所消耗的平均时间，测试结果如图 5所示。

图  5  连续在末尾追加数据块

从理论分析而言，本文所提出的协议在执行尾部追加操作时，为每一个追加的文件块进行结构调整的平均时间复杂度为O(logn)。从上述测试结果可知，在向文件尾部进行连续追加文件块的场景中，本文提出的协议性能优于文献[14]中的方案。

测试向文件中随机插入文件块，测试前先用1 GB大小的文件产生认证结构，文件块的大小设置为8 KB，测试在文件中随机插入不同数量的文件块后，平均插入每一个文件块时，调整认证结构所消耗的时间，测试结果如图 6所示。测试结果显示本文方案与文献[14]中的方案性能相近。

图  6  在随机位置插入数据块

测试不平衡状态下验证的时间消耗，首先在云端存储大小为1 GB的文件块和对应的认证结构，文件块的大小设置为8 KB，通过在原始文件尾部追加不同数量的文件块以造成认证结构出现不同程度的不平衡后，对最后一个文件块进行完整性验证以观察在不同程度的不平衡下，验证所需要的时间，测试结果如图 7所示。从测试结果可知，在不平衡状态下，本文所提出的方案在验证时的性能优于文献[14]中的方案。

图  7  对尾部数据块进行完整性验证

云存储中的数据安全问题是不可回避的问题，而数据的完整性验证是保护数据安全的重要手段之一，因此面向云存储和量子存储的完整性验证方法和协议成为了近几年的研究热点之一^[15-16]。本文基于改进的跳表提出一种适用于两方模型的云存储数据完整性验证协议，理论分析和模拟实验证明该协议具有较高的效率，但该方案没有考虑验证任务的代理问题，今后的工作将是对验证任务的代理问题进行研究。