0 概述

近年来, 云计算^[1]的快速发展为用户降低了大量的本地存储空间并减轻了数据管理负担^[2], 使用户能够通过不同设备在不同位置方便地访问云端数据, 并且可以随时分享这些数据。但是, 由于用户未在物理端对数据进行存储, 因此该模式面临外部威胁, 如云数据的存储安全性问题。云存储安全必须保证用户能够存储数据并且无需担心是否要验证其完整性, 因此, 高效验证云数据的完整性非常重要^[3]。

云端存储的各种数据效用不同, 一些数据会被经常性查看, 而一些数据几乎不会被查看。以私有云为例, 用户将日常生活中用到的数据在云端备份, 如书籍压缩包、视频压缩包等资料常会在首次存进云盘后被查看, 然后就几乎不会再被查看, 也不会被更新。高频率访问的数据种类有限, 通常为用户拍摄的照片、电影和音乐等。在云数据的硬件存储中, 会根据数据访问频率及规律将存储的数据分为热数据、温数据和冷数据, 其中, 冷数据所占比例高达80%^[4]。

一般数据的机密性通常由数据加密^[5]和匿名机制^[6]等方法来保证, 在云存储技术出现后, 研究者提出新的方法来保障云数据的安全性。现有的数据完整性验证方案主要分为数据可恢复性证明(POR)方案^[7]和数据持有性证明(PDP)方案^[8]两类。在POR方案中, 用户不仅可以验证远程数据的完整性, 而且可以通过使用纠删码来完整地恢复损坏的云端数据。与POR方案相比, 由于PDP方案未使用纠删码, 因此其效率更高。

为达到更高的验证效率, 现有多数PDP方案使用同态验证标签(Homomorphic Verifiable Tags, HVTs), 主要包括基于MAC^[9]、基于RSA^[10]和基于BLS^[11]3种PDP完整性验证方案。其中, MAC只能进行有限次验证且辅助信息过多。在相同的安全强度下, BLS签名^[12]具有较短的签名位数, 约为160 bit, 相比RSA签名的1 024 bit要少很多, 此外, 其具有同态的特性, 能够将多个签名聚合为一个^[13], 这也减少了整个验证过程的计算代价和通信开销。基于BLS签名的方案采用轻量级第三方审计模型, 满足云存储轻量级设计要求, 降低了用户的计算负担。

在云存储技术快速发展的背景下, 云数据的日益增长使用户有了新的需求, 数据不再是静态形式, 而需要经常进行插入、删除等动态操作, 因此, PDP方案的设计不能仅局限于解决静态数据的完整性验证问题。文献[14]提出动态数据持有性证明(Dynamic Provable Data Possession, DPDP)方案, DPDP方案对PDP方案的较大改进是支持动态数据操作, 近年来研究者通过不断改进现有的DPDP方案, 使其性能得到不断提升。目前主流的DPDP方案都使用认证数据结构(Authenticated Data Structure, ADS)进行完整性审计, 如基于默克尔哈希树(Merkle Hash Tree, MHT)^[15-16]、基于跳表^[17]、基于多分支树(Large Branching Tree, LBT)^[18]等多种DPDP完整性验证方案。对于数据的隐私保护, 文献[19]采用随机掩码技术提高方案的安全性, 并采用索引表机制实现数据的动态更新, 减少了计算和通信开销。

由于多数云数据不需要动态更新, 因此为提高审计效率, 可以考虑对不涉及动态更新的数据使用PDP验证方案, 从而省去较多的验证环节。本文提出一种数据混合HPDP方案, 对无需进行动态操作的数据选择PDP验证, 而需要更新的数据则使用效率较高的LBT方案, 从而降低计算开销和通信负担, 提高验证效率。

1 云平台数据完整性验证方案模型 1.1 预备知识

双线性映射的定义为:e:G×G→G_T, 其中, G和G_T为GDH(Gap Diffie-Hellman)群, 即乘法循环群, 该双线性映射具有以下性质:

1) 双线性:

$ \forall x, y \in G \Rightarrow e\left(x^{a}, y^{b}\right)=e(x, y)^{a b} $

(1)

2) 可计算性:e存在并且能够高效计算。

3) 非退化性:

$ \forall x \in G, x \neq 0 \Rightarrow e(x, x) \neq 1 $

(2)

1.2 方案模型

本文方案模型使用混合验证策略, 其为文献[20]方案的改进。如图 1所示, 该模型由数据所有者(Data Owner, DO)、云服务供应商(Cloud Service Provider, CSP)和第三方审计(Third Party Auditor, TPA)组成。其中, DO负责对数据初始化, 委托TPA对数据进行审计; CSP提供数据的存储服务, 管理DO的数据, 具有较强的计算存储能力, 并且应答TPA发来的挑战, 返回证明给TPA; TPA是由用户委托的完整性审计实体, 负责向CSP发起挑战信息并且验证CSP返回的证明是否正确, 然后将审计结果返回给DO。对于静态数据文件, DO在进行初始化时采用基于BLS-PDP的完整性验证方案; 对于动态数据文件, DO在进行初始化时选择基于LBT-DPDP的数据完整性验证方案。

数据审计过程通常分为以下3个阶段:

1) Setup阶段。数据的拥有者预处理文件, 先执行密钥生成算法生成公私钥对, 再将文件分块, 利用标签生成算法生成元数据。将处理后的文件发送到云服务器, 删除本地存储的文件副本。

2) Challenge阶段。数据的拥有者向第三方审计发起验证请求, 第三方审计随机生成要验证的数据块的下标, 向云服务器发起挑战。

3) Check-proof阶段。云服务器收到挑战后运行证明算法生成证明并返回给第三方审计。第三方审计使用验证算法来验证返回的证明是否正确, 将验证结果0/1(0代表数据被破坏, 1代表数据完好)返回给数据的拥有者。

2 云数据完整性混合验证方法 2.1 方案设计

本文方案在设计时考虑的重点是对于整个云存储性质的判定, 考虑用户存储数据的类型以及使用云存储的场景, 通过了解用户对于存储的具体要求制定相应的存储策略, 从而在用户进行数据审计时选取合适的审计方案。本文为每个用户提供2种审计方案, 用户在进行数据预处理上传时选择一种审计方案来进行预处理。如果上传一些静态文件, 后续不需要进行插入、删除和修改操作, 直接使用BLS-PDP方案处理数据; 如果是动态文件, 则使用LBT-PDP方案。

为对不同类型的数据进行相应的审计, 可以采用分区存储或者标记的方法。本文使用分区存储的方法将云存储分为动态存储区和静态存储区。在用户发起挑战请求时, 如果选取的数据在静态存储区, 使用BLS-PDP方案进行验证, 反之则使用LBT-DPDP方案验证。

整个方案模型仍按第三方审计模型设计, 只是用户端的数据处理方式有所不同。DO会根据上传数据的类型来选择不同的验证方案, 选定验证方案后对数据进行相应的初始化处理并上传到CSP, 在数据进行完整性验证时也会按照方案的不同执行不同的审计流程。对于数据初始化阶段, 2种方案只存在很小的差别。对于挑战-应答阶段, 大致流程基本相同, 但具体细节不同, LBT-DPDP方案的计算开销与通信代价更大。此外, LBT-DPDP方案中还存在数据动态操作阶段。本文方案的整体流程如图 2所示。

2.2 方案描述

本文方案为混合验证方案, 由PDP方案实现静态数据审计, 由DPDP方案实现动态数据审计。

1) 静态审计

对于静态数据, 不涉及动态操作, 需要考虑的是审计的开销, 在这种情况下, 使用BLS-PDP方案更能节省系统的计算代价与通信开销; 针对数据量大、数据更新频繁的动态数据, 显然使用LBT-DPDP方案更合适。静态审计的具体步骤如下:

(1) KeyGen(1^k)→(pk, sk)。在系统初始化时, 由DO在本地执行。1^k为输入的安全参数, 返回一对公私钥(pk, sk)。

(2) TagBlock(sk, F)→{T}。TagBlock(·)算法由DO执行, 生成元数据T, 即同态签名标签集。该算法的输入参数包括私钥sk和数据文件F, 返回认证的元数据T。

(3) GenProof(pk, F′, T, chal)→P。该算法由CSP运行, 生成完整性证明P。输入参数包括公钥pk、处理后的文件F′、挑战请求chal和认证元数据集合T, 返回证明P。

(4) CheckProof(pk, chal, P)→(1, 0)。该算法由验证者TPA运行, 对CSP返回的证明P进行判断。输入参数为公钥pk、挑战请求chal及证明P。返回验证结果1或0, 1表明数据完整, 0表示数据被破坏。

整个验证过程无需考虑数据的更新操作, 在DO初始化上传数据之后, 后续的完整性审计工作完全交给TPA完成, 大幅降低了DO的计算负担, 同时整个验证的通信量也得到大幅减少, 其对数据的审计是一次性生成元数据, 可以进行无数次的审计。此外, 由于使用的是HVTs, 因此BLS-PDP方案在拥有同态优势的同时, 生成元数据时占用的内存更少, 每个数据块只占用20 Byte, 从而减少了通信开销。

2)动态审计

对于需要进行动态更新的动态审计, 本文选用LBT-DPDP方案以高效地执行动态操作。文献[20]方案在动态审计时使用的是跳表, 但是LBT相比跳表更高效, 因此, 本文方案使用LBT-DPDP作为动态审计的方法。LBT支持大规模的数据插入操作, 其为动态更新最常使用的操作。动态审计的具体步骤如下:

(1) KeyGen(1^k)→{sk, pk}。该算法由DO运行, 输入安全参数1^k, 返回私钥sk和公钥pk。

(2) TagGen(sk, F)→{T}。该算法由DO运行并产生元数据, 将数据文件F和私钥sk作为输入并输出标签集T, T是数据块{m_i}上签名{τ_i}的集合。

(3) Update(F, Info, Ω, pk)→{F′, P}。该算法由CSP运行并应答TPA的更新请求。采用数据文件F, 更新信息Info, 以前的辅助信息Ω和公钥pk作为输入。输出的是数据文件F的新版本F′及其证明P。CSP将证明P发送给TPA。

(4) VerifyUpdate(P, pk)→{1, 0}。该算法由TPA运行并验证CSP是否正确更新了数据。输入包含来自CSP的证明P和公钥pk。如果证明有效则输出接受结果1, 反之输出拒绝结果0。

(5) Challenge(·)→{chal}。TPA运行该算法启动挑战并发送CSP的挑战信息chal。

(6) GenProof(F′, T, chal, pk)→{P}。该算法由CSP运行, 将数据文件F′、元数据T、挑战信息chal以及公钥pk作为输入, 输出证明信息P。

(7) VerifyProof(P, pk)→{1, 0}。TPA运行该算法来验证来自CSP的证明信息P。如果证明正确输出1, 反之输出0。

3 性能分析与实验评估

每一种检验云存储数据完整性的方案都有各自的优缺点, 有不同的适用场景, 没有哪一种方案能够满足所有的存储需求且性能最优。因此, 没有一个统一的标准来对每一种方案进行评价, 但是可以通过组合方案的方法发挥出各自方案的优点, 下文从通信开销和计算开销2个方面来分析BLS-PDP方案与LBT-DPDP方案在针对不同数据类型时的优势。

3.1 计算代价分析

计算开销主要来自于实体DO、TPA和CSP, 它们在不同阶段产生的计算开销决定了整个方案的验证效率。在初始化阶段, 主要是由DO对数据进行预处理产生的计算开销, 整个初始化阶段会因为采用不同的方案而有不同的计算复杂度。对于BLS-PDP方案而言, 不用构造树形结构而只需生成元数据即可, 因此, 计算开销大幅降低, 时间复杂度为O(1)。而LBT-DPDP方案则需要构建LBT, 整个过程的时间复杂度为O(log_kn)。因此, 对于DO而言, 在初始化阶段, 2种方案的计算复杂度不同, BLS-PDP方案在初始化阶段对数据的处理效率更高。

在动态更新阶段, LBT-DPDP方案进行修改操作时需要执行1次指数级计算操作, 进行插入操作时需要2次指数级计算, 进行删除操作时不需要计算, 而BLS-PDP方案没有动态更新操作。

在完整性审计阶段, 对数据的处理不同于初始化阶段的数据一次性处理和动态更新阶段的针对性处理, 因为这2个阶段的处理次数是有限制的, 而完整性审计阶段是一个周期性重复的过程, 只要数据存储在CSP, 就会不断地进行完整性审计, 因此, 完整性验证是整个方案中计算量最多的环节, 也决定了整个方案的验证效率。假设数据块的总数为n, 挑战的数据块数目为c, LBT-DPDP方案的审计过程需要的计算为2c次加法和2c次乘法, 此外每次审计都要遍历LBT, 因此, 总的时间复杂度为O(log_kn)。BLS-PDP的TPA审计过程只需要对随机抽取的c个数据块进行验证即可, 没有其他复杂的计算, 时间复杂度为O(c), 而c的值约为460, 数值不大, 因此, 整个时间复杂度可以表示为O(1)。

BLS的完整性审计计算速度远快于LBT, 大幅节约了整个系统的计算资源, 并且两者计算速度的差异会随着数据量的增大而增大, 满足线性关系。因此, 对于海量的云端数据而言, 本文混合方案能够节约计算资源, 提高整个云端数据的审计效率。

3.2 通信代价分析

通信开销主要在于信息的交互, 因为数据上传的通信开销只会在数据初始化阶段, 所以整个验证过程的通信代价都取决于挑战-应答阶段, 即TPA与CSP之间为进行完整性验证而相互传递信息的开销大小。LBT-DPDP方案在CSP产生证明信息时, 构建ADS需要大量辅助信息, 这使得通信代价大幅提高。而BLS-PDP方案因为不存在树形结构, 无需太多辅助信息来产生证明, 因此, 其通信代价远低于LBT-DPDP方案。

LBT-DPDP方案的完整性验证需要构建认证路径以及大量的辅助信息, 从被选取的数据块对应的叶子节点一直向根节点移动, 中间通过的路径的节点都为验证该数据块正确性的辅助信息, 时间复杂度为O(log_kn)。而BLS-PDP方案只需要传输c个数据块的信息就可以达到审计的目的, 并且因为使用HTVs, 可以将多个数据块的信息聚合为一个, 所以通信的时间复杂度为O(1)。BLS-PDP方案的通信开销远小于LBT-DPDP方案, 减轻了TPA与CSP的通信负担。

现有多种审计方案的性能比较结果如表 1和表 2所示, 其中, c为随机抽取的数据块数目, f为数据块损坏的比例, n为文件分块数, k为LBT的出度, a为动态文件百分比。可以看出, BLS-PDP方案除了不能进行动态更新, 在整个验证过程中效率明显高于LBT-DPDP方案, 节约了整个系统的计算资源, 减少了通信开销, 并且整个CSP存储的静态数据越多, BLS-PDP方案的性能优势越大, 而对于需要动态更新的动态数据, LBT-DPDP方案具有支持批操作以及审计过程中辅助信息更少的优点。由此可见, 2种方案的结合可使云数据的审计更高效。

3.3 实验评估

为验证本文混合验证方案的性能优势, 在Windows10环境中使用Java实现方案基本功能, PC机的配置为英特尔酷睿四核, CPU i5-4200M, 主频2.50 GHz, 内存4 GB。方案中使用的加解密算法、签名和哈希均从PBC库和OpenSSL库中调取。实验输入采用1 600个随机生成的数据文件, 总大小为1 GB, 结果取10次实验的平均值。

为验证本文混合方案的TPA验证效率优于单一动态验证方案, 分别实现BLS-PDP和LBT-DPDP验证方案, 并将三者进行对比, LBT-DPDP验证方案默认使用最大出度16。实验步骤如下:

1) 质询数据块数量为460, 混合验证方案的TPA验证时间与数据的类型有关, 设定不同的动态数据占比, 验证TPA时间与动态数据占比的关系。

2) 假定动态数据与静态数据各占50%, 质询数据块数量为460, 比较3种验证方案在不同数据块大小下TPA的验证时间。

3) 同样设置动态数据与静态数据各占50%, 数据块分块大小为4 kB, 比较3种方案总的审计时间, 验证本文方案的审计效率是否具有优势。

动态数据所占百分比对TPA验证时间的影响如图 3所示。可以看出, 全为静态数据与全为动态数据的验证时间分别为数据混合状态验证时间的下限与上限, 动态数据越多, 验证时间也越长, 验证时间与动态数据的占比接近呈线性关系。

3种方案的TPA验证时间比较如图 4所示, 从图 4可以看出, BLS-PDP方案时间最短, 其不涉及复杂的ADS生成与验证, LBT-DPDP方案时间最长, 而本文方案介于两者之间, 且与动态文件与静态文件各自所占比例有关, 静态文件越多, 本文方案的验证时间越短, 效率越高, 节省的系统资源越多。

文献[20]方案与本文方案的审计时间对比如图 5所示。可以看出, 与文献[20]方案相比, 因为LBT比跳表高效, 所以在相同的数据块大小情况下, 本文方案审计时间较少, 且随着审计数据块的增多, LBT审计节省的时间越多, 总体的审计效率更高。

4 结束语

本文提出一种云平台数据完整性混合验证方案。根据用户存储数据的类型选用不同的审计方案, 对静态类型文件与动态类型文件分别使用BLS-PDP方案和LBT-DPDP方案, 从而提高审计效率, 发挥不同审计方案的优势。性能分析与实验结果表明, 该方案能够减少完整性验证过程中的计算量与通信代价。下一步将研究具体的PDP与DPDP选择方法, 同时降低TPA与CSP的通信量。此外, 还将考虑解决方案的兼容性问题, 使2种方案能够实现代码复用和模块共用。