一种带权单链表多分支树云数据完整性验证方案.docx

? ? 一种带权单链表多分支树云数据完整性验证方案 ? ? 朱 彧，陈 越，严新成，王晓晶 1(战略支援部队 信息工程大学，郑州 450001) 2(陆军参谋部附属单位，北京 100042) E-mail:619717409@ 1 引 言 云计算作为时下热门的信息技术，通过共享自己的强大集中的资源为用户提供服务，根据用户需求分配资源来完成用户的计算或存储任务，因此越来越多的用户选择使用云计算服务.云存储服务是云计算的核心服务之一，云服务提供商(CSP,Cloud Service Provider)搭建具有强大存储能力的云系统并向用户提供数据存储服务.云存储服务具有低成本、高扩展性、易于运行维护和访问不受时间地点约束等优点.但近年来发生的安全事故表明，其也存在着严重安全隐患.2017年1月31日，Gitlab由于遭受到DDoS攻击，运维人员在修复过程中，执行了错误的命令，导致约300GB的用户数据被删除，近6个小时的用户数据丢失.2018年8月，腾讯云的客户清博数据科技有限公司所属的“前沿数控”平台的一块操作系统云盘发生故障，致其文件系统数据损坏. 这些事故使得用户担心自己存储在云系统中数据的安全，因为一旦数据被存储到云系统上，用户就无法像管理本地数据那样管理云端数据了.云系统可能因为软硬件故障导致数据丢失或损坏，恶意的攻击者可能会破坏或篡改用户数据，云服务提供商也可能丢弃那些长时间未被访问或很少被访问的数据以达到节省存储空间的目的.但云服务提供商出于维护自身声誉或者避免赔偿等目的隐瞒这些事故，并向用户声称数据仍然被完整地存储在云系统中.如何高效灵活地验证存储在云端数据的完整性是亟待研究的问题[1]，而数据完整性验证方案可以很好的解决这个问题. 2 相关工作 数据完整性验证方案根据存储数据是否可恢复分为数据持有性证明(Provable Data Possession,PDP)[2]和数据可恢复证明(Proofs of Retrievability,PoR)[3].PDP能够快速判断数据是否损毁，效率较高.而POR可以在一定程度上恢复损坏的数据，但效率较低.本文的研究主要关注PDP的效率等问题.Ateniese等提出了一种采用概率性策略完整性验证方案[2]，利用RSA签名机制的同态特性将证据聚集成一个小的值，降低了验证过程中的通信开销，但其不能支持动态更新操作.为了支持用户对存储在云系统上的数据进行动态更新操作，研究者们引进动态数据结构组织数据.Erway等引入跳表来组织数据，实现了支持块级全动态更新操作[4]；Wang等采用Merkle哈希树来保证数据块在位置上的正确性，使得方案支持数据的动态更新[5].然而采用动态数据结构会由于数据块的增多消耗很多的时间和空间，在验证过程中需要传递很多的辅助验证信息，增加了通信带宽的开销.为了提高验证效率和减少验证开销，王瑞锦等将跳表数据结构进行改进，引入可达范围记数，以便高效地支持数据块在任意位置的更新操作[6]；Merkle哈希树每个节点对应两个子节点，而李勇等采用的多分支树(large branching tree，LBT)中每个节点对应多个子节点，有效降低了树的高度，简化了数据动态更新过程[7]；方欣等对多分支路径树进行改进，降低了树的高度，优化了存储空间，但并没有考虑到用户多次更新后树的不平衡问题，且采取线性组合计算证据导致用户数据有被不可信第三方获取的风险[8].针对上述问题，本文提出了采用带权单链表多分支树的云数据完整性验证方案(weighted single linked list large branching tree scheme，WSLBTS),以进一步提高验证效率并保护用户数据隐私.其主要贡献如下：1)相对于多分支树，WSLBT将叶节点设置为链表，使得每一叶节点对应多个数据块，进一步降低了树的高度，缩短了构造时间和生成证据的长度；2)提出一种再平衡机制，可维持叶节点链表长度的平衡，提高了节点更新效率；3)采用了随机掩码技术[9]，使得第三方审计(Third Patry Auditor)无法从证据中得到数据的有关信息. 3 相关预备知识 3.1 双线性对 假设G1,G2,GT都是素数阶为p的乘法循环群，g1和g2分别是G1和G2的生成元，则双线性对定义如下： e:G1×G2→GT， 1)双线性：?x∈G1,y∈G2?e(xa,yb)=e(x,y)ab； 2)非退化性：e(g1,g2)≠1； 3)可计算性：e能够被高效地计算. 3.2 数据完整性验证模型 为了减轻用户端的负担，数据完整性验证方案一般引入具有很强计算和存储能力的第三方审计，采用公开验证的方法[10].数据完整性验证方案验证模型构成一般由三个实体构成，分别是用户端、云系统和第三方审计(TPA). 用户