[发明专利]一种云环境下远程数据完整性认证数据结构及其实现方法

摘要

本发明公开了一种云环境下远程数据完整性认证数据结构的实现方法，其包括利用认证数据结构来认证存放于云端数据的完整性包括是否被修改，是否有数据丢失；在云端服务器不可信的情况下，利用认证数据结构来认证存放于云端数据的下标正确性；利用认证数据结构来支持云端数据的动态更新，所述动态更新包括修改操作、插入操作和删除操作。本发明还公开了一种云环境下远程数据完整性认证数据结构，包括认证二叉树的生成的伪代码模块；证明路径的生成和验证的伪代码模块；节点的修改操作的伪代码模块；节点的插入操作的伪代码模块；节点删除三种情形的操作的伪代码模块。具有降低了在用户端和云端的计算在时间复杂度和存储空间的消耗等优点。

主权项

一种云环境下远程数据完整性认证数据结构的实现方法，其特征在于，包括：在云端服务器不可信的情况下，利用所述云环境下远程数据完整性认证数据结构来认证存放于云端数据的完整性包括是否被修改，是否有数据丢失；在云端服务器不可信的情况下，利用所述云环境下远程数据完整性认证数据结构来认证存放于云端数据的下标正确性；在满足上述的两个条件的情况下，利用所述云环境下远程数据完整性认证数据结构来支持云端数据的动态更新，所述动态更新包括修改操作、插入操作和删除操作；对于每个节点v保存数值x(v)＝{h(mi),r(v),f(v)}:r(v)代表该节点与其父节点在数据块的位置上的差值；在位置上，左子节点小于父节点，右子结点大于父节点；r(v)定义如下：其中i为v的r(v)值,j为v的父节点的r(v)值：f(v)代表该节点与其子节点在数据上的关系，即其包含了子节点的数据签名，这使得一旦子节点的数据发生变化，则该节点的f(v)也将产生变化；f(v)定义如下：h()是一个抗碰撞的哈希函数，︱︱表示前后串联操作，vlchila，vrchild分别代表节点v的左子节点和右子节点；当其中有子节点为空时，则该子节点的f(v)值不加入串联操作；用户端在将数据保存到云端之前将根据上述定义构造一棵认证二叉树，最后生成一个根节点x(root)＝{h(root),r(root),f(root)}，用户端将保存此根节点并删除树的其他部分；在云端则需要构造并保存整棵树；构造整棵认证二叉树的算法为GenRoot(M)→{root}算法；在证明的过程中，用户端需接受云端传来的两个证明数据{mi,πi},mi是第i个数据块的值，π则是由云端对该数据块生成的证明路径，其即对应算法GenProof(mi)→{proofPath}中的proofPath，这里使用π符号使得表达更加简洁,对于1<＝i<＝n，令证明路径πi(V′1)对应的是证明节点,πi(v′k)对应的是根节点；对于1≤j≤k,其中，lchild，rchild分别为vj的左子节点和右子节点；如果lchild或rchild已处于到根节点的路径上，则令r(rchild)＝‑1,f(rchild)＝‑1。