支持隐私保护和公平支付的数据完整性验证方案

富 瑶 李庆丹 张泽辉 高铁杠

(南开大学软件学院 天津 300350)

随着移动互联网、物联网、大数据时代的到来，数据量呈指数级增长趋势[1-3]，个人的存储能力已无法满足现有的存储需求.云存储是在云计算概念上延伸和发展出来的一个新的概念，通过集群应用、网络技术或分布式文件系统等功能，将网络中大量各种不同类型的存储设备通过应用软件集成起来协同工作，共同对外提供数据存储和业务访问[4-8].用户通过互联网访问存储在云中的文件，没有时间或位置的任何限制，采用按需付费的方式，支付一定的服务费便能享受到高质量的云服务.与传统本地存储相比，云存储无疑是一种更经济的选择.

然而，用户将数据外包至高效的云服务端后，便不再拥有对数据的实质控制权[9-11].如果云服务提供商是半诚实且好奇的实体，那么它可能会以某种经济利益的关系对用户数据进行恶意删除、篡改等行为.为防止用户存储在云中的数据遭受云存储服务器(cloud storage server, CSS)和其他用户窥探的风险，数据完整性验证的概念[12]被提出.最为直观的一种验证方法是数据拥有者(data owner, DO)从CSS中下载所有的数据，然后本地进行验证.但是，这不仅浪费大量网络传输资源和本地存储资源.同时，在完整性验证中，由于DO和CSS均无法保证能够提供公平、可信的结果，因此都不适合执行完整性验证工作.文献[13-33]在完整性验证中引入第三方验证者(third party auditor, TPA)，委托具有强大计算能力的TPA执行此验证任务，使得TPA能够从客观、独立的角度提供审计服务.如图1所示，基于TPA的验证模型主要由DO，CSS和TPA三个实体构成.

Fig. 1 Cloud storage data integrity verification model图1 云存储数据完整性验证模型

在验证模型中，具有存储需求的DO将本地资源数据存储到有强大存储和计算能力的服务器CSS中；当DO对云中的数据进行完整性验证时，委托具有丰富的审计经验和能力的TPA执行验证任务；TPA向CSS发起挑战请求，执行验证任务；CSS生成完整性证据返回给TPA；TPA通过复杂计算得出验证结果，将结果发送至DO；DO根据返回的验证结果判断云端数据是否被正确存储，完成数据完整性验证.

为支持动态更新验证，Ateniese等人[13]通过对数据持有性证明(provable data possession, PDP)机制进行简单的修改，使其支持了部分动态数据更新操作.为完全支持动态更新操作，Erway等人[14]提出基于跳表的PDP机制，利用认证跳表的动态数据结构，确保数据块在位置上的正确性，而数据块标签确保数据块内容的正确.但存在的问题是由于认证路径过于冗长，认证过程中需要大量的辅助信息，将导致系统产生较大的计算开销和通信开销.文献[15]提出了另一种支持动态操作的公开审计方案，通过构造Merkle散列树动态结构来确保数据块在位置上的正确性.相比跳表数据结构，Merkle散列树利用数据块而不是标签计算根节点散列值，因而具有更简单的数据结构.但是，在实际场景中，我们需要对TPA的可信性进行具体的探讨，也就是说TPA并不完全可信，有可能窃取用户数据隐私.为支持数据隐私保护，文献[20]基于同态密钥随机掩码技术，提出在审计阶段中引入2个参数隐藏服务器来生成证据内容，保证TPA不能够从返回的证据中获得任何有用信息，从而避免数据遭受隐私泄露的风险.Yang等人[23]提出的数据验证方案支持动态多用户多服务器和隐私保护，对来自多个服务器的多个用户进行动态数据验证，同时利用密码技术与双线性对的双线性性质的结合，提供数据隐私保护.文献[32]提出一种更为新颖高效的公开验证方案，在保证数据隐私的前提下，动态数据更新结构由一个双向索引信息表DLIT和一个记录位置的数组组成，双向信息表能够更快地定位某个数据块，位置数组可以维持块及其特定位置之间的关系.其中，双向信息索引表DLIT能够保证在对数据块进行插入和删除时不会导致信息表中其他记录的更改，因而相比其他方案将具有更低的系统开销.但文献[32]存在的问题是，在完整性验证过程中，DO向CSS发出完整性挑战请求后，CSS向TPA返回相应证明以表明正确存储了外包数据，然而TPA可能与CSP合谋攻击，因此有必要保证TPA验证结果的可信性.区块链因其去中心化、数据不可篡改的特性，在数据保护领域中有着天然的优势，因而给数据完整性验证提供了一种新的思路.文献[33-40]提出基于区块链的数据完整性验证方案，分布式的存储方式使得链上每一参与节点都保存整个数据库的副本，因此可有效避免集中化存储的单点故障问题，而且区块链自身的链式指针结构可确保其上数据无法被任意删改，这是对数据完整性的有效保证.文献[35]提出了一种ODPDP方案，将频繁的审计任务委托给外部，并同时提供日志审计，以抵制任何不诚实的参与者合谋串通.文献[36]提出了一种基于安全身份的聚合签名SIBAS方案，可信执行环境TEE作为验证者检查聚合签名的正确性，进行完整性验证，有效减少了数据信息泄露的可能性以及验证结果的不可信性.

然而，现有完整性验证方案[33-41]，大多是在假设服务-支付公平的前提下进行的.但是，在实际的存储验证中，由于DO已经预先支付给CSS和TPA相应的服务费，如果CSS或TPA存在着欺骗行为，公平支付便无法得到保障.为解决TPA不可信问题和实现服务-支付公平，本文提出一种支持隐私保护和公平支付的数据完整性验证方案.

本文的主要贡献包括3个方面：

1) 引入一种新型数据认证结构——基于等级的Merkle散列树，实现数据位置的完整性验证，而且能够支持数据的可验证动态更新.

2) 为实现用户数据的隐私保护，设计了一种无交互式动态数据完整性证明机制NIDPDP，审计阶段中TPA无需向CSS发送挑战请求，即取消TPA和CSS进行挑战交互这一过程，避免数据隐私泄露.

3) 结合区块链的共识及不可篡改性，在NIDPDP验证机制上，提出支持隐私保护和公平支付的数据完整性验证模型.智能合约(smart contract, SC)通过对CSS与TPA的不诚实行为进行惩罚，实现验证方案的公平支付内容，保证模型的安全性、可靠性以及公平性.

1 研究动机

1.1 验证方案概述

云存储数据完整性验证是指CSS能够证明它正确存储用户的数据，用户数据被保存完整的一种机制.验证机制一般包括5个算法，分别是密钥产生、标签生成、挑战请求、证据生成、证据验证.支持动态验证的方案还包括执行更新、更新验证2个算法.

1) 密钥生成.DO运行概率性算法生成公钥和私钥，对外公布公钥信息.

2) 标签生成.DO对数据文件进行分块，计算每个数据块对应的标签作为认证的元数据.然后，将原始文件和所有数据块构成的标签集合上传至CSS.最后，删除本地文件及标签集合.

3) 挑战请求.TPA接受DO委托的验证任务，抽样对文件数据块进行验证.对需要验证的数据块产生随机挑战数，随机挑战数与块索引构成挑战集合，TPA向CSS发起挑战.

4) 证据生成.CSS接受TPA的挑战后，根据挑战集合，计算得到本次请求的完整性证据，返回给验证者.

5) 证据验证.TPA收到完整性证据后，通过计算对此证据进行验证，向DO返回验证结果.

6) 执行更新.CSS根据更新请求对存储的数据进行相应的更新，通过证据生成算法返回给验证者更新后的证据.

7) 更新验证.TPA接收更新后的证据，执行更新验证算法，向DO返回更新验证结果.

1.2 攻击模型

采用基于TPA的完整性验证方案时，有可能造成用户的数据隐私泄露.DO在将完整性验证任务委托给TPA后，如果TPA不诚实可信，那么它可能会重复地对相同位置上的数据块进行验证，即每次发送的挑战请求是相同的.通过这种方式，经过一定次数的挑战请求累积后，TPA便可得到一个方程组，然后通过高斯消去法获得文件信息内容，从而使得用户遭受隐私泄露的风险.具体攻击过程如下：

TPA重复对位置{s1,s2,…,sc}s1≤si≤sc的数据块进行完整性验证，经过c次挑战请求后，TPA可得到方程组：

(1)

其中，μ(j)是第j次完整性验证过程中CSS返回的证据元素，1≤j≤c.

只要该方程组中的系数行列式不为0，则TPA便可通过求解线性方程组计算得到{ms1,ms2,…msc}的值，造成用户数据的隐私泄露.

1.3 支持隐私保护方案

为实现数据隐私保护的验证，文献[20-22]采用同态密钥随机掩码技术，该技术的核心思想是，在审计阶段引入2个参数隐藏服务器生成证据内容，保证TPA不能够从返回的证据中获得任何有用信息，从而避免数据隐私泄露.

然而，这种验证方式虽然能够实现隐私保护，但存在的问题是无法实现验证方案后续的服务-支付公平.如果CSS与TPA合谋攻击，即无论云端数据是否被正确存储，TPA都返回数据已保存完整的信息.由于在完整性验证过程中，DO已经预先支付给云服务提供商和验证者相应的费用，因此，验证方案的公平支付内容便没有得到保障.

2 支持隐私保护和公平支付的验证方案

为解决实际完整性验证中TPA不可信问题、实现服务-支付公平，本节提出一种支持隐私保护和公平支付的数据完整性验证模型.验证模型可分为3个阶段：初始化阶段、审计阶段和惩罚阶段.如图2所示，模型中包含的4个实体分别是：DO，CSS，TPA和SC.审计阶段中采用无交互式的验证模式NIDPDP保护数据隐私，在惩罚阶段通过智能合约对CSS和TPA的惩罚控制实现服务-支付的公平.

Fig. 2 Integrity verification model supporting privacy protection and fair payment图2 支持隐私保护和公平支付的完整性验证模型

2.1 基于等级的Merkle散列树

为确保数据块在云端存储位置上的完整性及动态更新的可验证性，我们引入一种新型的数据结构——基于等级的Merkle散列树(rank based Merkle-Hash tree, RBMT).相比于基于跳表的动态数据结构，RBMT不仅能够完全支持动态操作，包括对数据进行的更新、删除、插入等操作，而且能够避免由于辅助认证信息冗长而导致系统通信开销过大的问题.在RBMT中，节点W可以由3个元素构成，即W={r,s,h}.其中，r是节点的等级值，表示当前节点能够到达的叶子节点数量;s是存储节点的边信息，表示当前节点是父亲节点的左/右孩子节点；散列值h是叶子节点mi的直接散列，非叶子节点散列值h是它左右孩子节点的散列值与它的等级值级联后再进行散列的结果.任一节点W的散列值计算为

(2)

当验证者验证CSS是否正确存储数据块m3的位置时，利用辅助认证信息Ω3={W4,Wc,Wb}进行计算，如图3所示，验证过程有4个步骤：

1) 在节点d处，根据W3和W4计算节点d的散列值hd=H(h3‖h4‖rd)；

2) 在节点a处，根据Wc和Wd计算节点a的散列值ha=H(hc‖hd‖ra)；

Fig. 3 RBMT data location verification图3 RBMT数据位置验证

DO对存储在云中的数据进行更新时，包括对数据块修改、数据块删除、数据块插入操作.验证更新过程为：

3) 验证者重复上述RBMT数据位置验证过程，完成数据可验证动态更新.

2.2 无交互式动态数据完整性证明机制

为实现用户数据隐私保护，本文设计了一种无交互式动态数据完整性证明机制NIDPDP，如图4所示.在方案的审计阶段中采用无交互式的验证模式，TPA无需向CSS发送挑战请求，由此，TPA便无法在验证过程中通过重复地对一些相同位置的数据块发起挑战攻击而窃取用户数据隐私.审计阶段中CSS与TPA分别通过NIDPDP.ProofGen()，NIDPDP.Verify()过程独立地完成任务，减少实体间信息的交互，避免1.2节TPA发生不诚实的行为.同时，NIDPDP机制也与惩罚阶段中的SC相互配合，包括CSS向合约传递RBMT的根节点、辅助认证信息和NIDPDP.Verify()过程中TPA向合约验证结果的传递.

Fig. 4 Non-interactive dynamic provable data possession mechanism图4 无交互式动态数据持有性证明机制

审计阶段中采用NIDPDP机制运行过程为：

1) CSS与TPA同时运行伪随机函数φZ(τ)，从[1,n]中随机选择c个元素组成子集I={s1,s2,…,sc}.对于每一个元素si∈I，选择-个整数vi=h(τ‖i)，构成挑战信息Chal={i,vi}s1≤i≤sc.其中，τ是随时间变化的信息，不受CSS或者TPA的控制.

2) 证据生成NIDPDP.ProofGen()，CSS将公钥pk、文件F、认证元数据集合Φ和挑战信息Chal作为算法的输入，输出本次验证数据内容的完整性证明P.

3) 证据验证NIDPDP.Verify()，TPA将公钥pk和完整性证据P作为算法的输入，验证CSS返回的内容证据P是否正确.若验证成功返回result=1，失败返回result=0，并且将验证结果发送至SC.

4) 执行更新NIDPDP.ExUpdate()，算法由CSS运行，更新完整性证据，公钥pk、数据块集合F、认证元数据集合Φ和更新请求Update作为输入，返回给TPA更新后的证据PUpdate.

5) 更新验证NIDPDP.VerUpdate()，算法由TPA运行，公钥pk、更新请求Update、更新后的证据PUpdate作为输入，进行更新验证操作，将更新验证结果发送至SC.

2.3 安全性模型

在无交互式数据完整性验证方案中，安全性模型主要面向的对象是：CSS和不可信的TPA.

1) 对CSS的安全性验证

Fig. 5 Integrity verification process for privacy protection and fair payment图5 支持隐私保护和公平支付的完整性验证流程

2) 对TPA的安全性验证

② 对于每一个元素si∈I，选择-个整数vi=h(τ‖i)，构成挑战信息Chal={i,vi}s1≤i≤sc；

定义2.如果对TPA的安全性验证的5个过程正确，则称方案模型对TPA是可验证安全的.

2.4 支持隐私保护和公平支付的验证模型

本节在无交互式的验证机制NIDPDP基础上，结合区块链的共识及不可篡改性，提出支持隐私保护和公平支付的完整性验证模型.在保证方案公平支付的内容上，利用SC对CSS和TPA不诚实行为进行惩罚.也就是，若CSS没有正确存储DO的数据，则会向DO支付相应的罚款；若TPA没有正确验证CSS返回的证据，则也会向DO支付相应的罚款.本节提出的验证模型包括3个阶段：初始化阶段、审计阶段和惩罚阶段.如图5所示，各阶段分别对应的流程为：初始化阶段中DO执行①②③；审计阶段中CSS执行④⑤⑥,TPA执行⑦⑧；惩罚阶段中SC执行⑨⑩.

各阶段具体过程如下.

初始化阶段.

e:G1×G1→G2是一个双线性映射，G1和G2均是p阶的乘法循环群，g是G1的生成元；选取安全散列函数HK()；φZ(τ)是一个安全的伪随机函数.

1) DO首先在Zp中随机选择α，β并计算H1←gα，H2←gβ，然后产生一个随机签名密钥对(spk,ssk)←Sig，私钥为sk=(ssk,α,β,Z)，公钥为pk=(spk,g,H1,H2,φ).

2) DO首先对原始文件进行分块操作，F={m1,m2,…,mn}，同时，每个数据块mi分为s段，mi={mi1,mi2,…,mis}，因此，数据文件可分为n×s个部分.然后，选取预处理文件秘密值τ1,τ2,…,τs∈p，计算公共验证参数uj=gτj∈p，每个数据块mi均生成对应的标签：

(3)

审计阶段.

CSS与TPA均运行伪随机函数φZ(τ)，从[1,n]中随机选择c个元素组成子集I={s1,s2,…,sc}，对于每一个元素si∈I，选择-个整数vi=h(τ‖i)，构成挑战信息，其中，τ是随时间变化的信息，不受CSS或者TPA的控制.

Fig. 6 Smart contract图6 智能合约

(4)

(5)

2) TPA在收到CSS发送的内容证据后，运行NIDPDP.Verify()，即验证式(6)是否成立：

(6)

将验证结果result=1或result=0发送至SC.

惩罚阶段.

区块链智能合约CompareContract(图6(a)所示)将验证CSS和TPA是否发生了不诚实的行为，以实现验证方案的公平支付.若CSS没有正确存储DO的数据，则CompareContract会调用合约TCSS(图6(b)所示)，CSS向DO支付相应的罚款；同理，若TPA没有正确验证CSS返回的证据，则Compare Contract会调用合约TTPA(图6(c)所示)，TPA向DO支付相应的罚款.具体惩罚过程为：

1) 在审计阶段，CSS在将生成的证据发送给TPA的同时，调用在区块链中已创建完成的智能合约CompareContract，发送已构建完成的RBMT根节点Wroot及辅助认证信息Ωi(1≤i≤c).同时，TPA在计算出CSS返回证据的验证结果后，也会将验证结果result发送至区块链智能合约CompareContract.

3 性能分析

3.1 正确性分析

定理1.如果CSS诚实地存储用户数据，返回相应的证据，那么该内容证据就可以通过TPA的校验，使式(6)成立.

证明.

证毕.

3.2 安全性分析

定理2.如果本方案的标签生成算法是不可伪造的，CDH困难问题和DL困难问题在随机预言机模型下是不可解的，那么不存在任何多项式时间算法，能够以不可忽略的概率破坏模型的安全性.

证明.

Game1. 定义为对CSS的可验证安全数据完整性证明游戏.

(7)

(8)

得到

(9)

(10)

得到

(11)

(12)

综上所述，如果本方案的标签生成算法是不可伪造的，那么不存在任何多项式时间算法，能够以不可忽略的概率赢得Game1,2,3游戏，破坏模型的安全性.

证毕.

3.3 隐私性分析

定理3.在本文提出的支持隐私保护和公平支付的数据完整性验证方案中，给定CSS返回的内容证据信息θ={σ,μ}，若好奇且不诚实的TPA试图从已掌握信息中获得DO的数据信息F={m1,m2,…,mn}，从计算上是不可行的.

此外，在惩罚阶段中智能合约CompareContract的约束下，由于TPA无法判断CSS返回给Compare Contract位置证据的正确性，智能合约Compare Contract一旦判断出CSS返回给其位置证据是错误的，而TPA返回给其正确的验证结果，那么将会调用合约TTPA对TPA进行惩罚.因此，TPA与CSS在完整性验证中将各自独立执行任务，不可能合谋攻击.

综上所述，在本文提出的完整性验证方案中，好奇且不诚实的TPA无法获取用户的数据信息，有效保证了用户的隐私安全.

证毕.

4 实验与结果

本节将从计算开销、通信开销2个方面来评价整个方案的性能.

4.1 计算开销

计算开销主要来自于方案的3个实体，包括DO，TPA，CSS，它们在不同的阶段产生的计算开销决定了整个方案的验证效率.在初始化阶段，主要是DO对文件数据块生成标签产生的开销.在审计阶段，计算开销主要是由CSS生成证据和TPA验证证据所产生.为评估方案模型的性能，我们首先分析不同数据块大小对所提方案计算成本影响.实验环境配置为Windows10系统，Intel Corei5处理器，2.20 GHz CPU，4 GB RAM.方案使用Java语言实现基本功能，加解密算法从JPBC库调取，取10次实验结果的平均值.审计阶段采用抽样策略，以4.6%的概率从文件数据块总数中选取挑战块数目.在文件数据块大小分别为30 KB，60 KB，90 KB，120 KB，150 KB，180 KB，210 KB，240 KB，270 KB，300 KB情况下，对64 MB，128 MB，256 MB，512 MB，1 024 MB的随机文件，分别测试数据块大小对各实体在不同验证阶段产生计算开销的影响.

从图7可以看出，随着数据块的增大，DO生成认证元数据标签的时间逐渐减小，并且在240 KB以后，标签生成时间基本稳定在某一数值.这是因为，随着数据块的增大，文件数据块数量减少，标签数量也随之减少，但当数据块大小达到一定数值，生成的标签数量相差不大，与此同时，数据块包含的数据段个数也增加，单个标签的计算时间变长，因此，在数据块大小增加到一定程度，标签生成时间会稳定在某一数值.如图8所示，随着数据块的增大，CSS生成完整性证据的时间也逐渐增加.这是因为，由于数据块增大，数据块段数s增加，CSS生成的完整性证据中包含的元素个数μj也增加，因此，证据计算越复杂，所用时间越多.如图9所示，随着数据块的增大，TPA验证证据的时间逐渐减小.这是由于随着数据块的增大，挑战块数目c减小，而TPA验证完整性证据的计算开销为(c+2)M+(s+c+1)E+2P，因此，TPA验证时间将减小.

Fig. 7 Influence of block size on DO tag generation time图7 数据块大小对DO生成标签时间影响

Fig. 8 Influence of block size on CSS proof generation time图8 数据块大小对CSS生成证据时间影响

Fig. 9 Influence of block size on TPA proof verification time图9 数据块大小对TPA验证证据时间影响

综上，为使所提方案性能最优，我们选择在数据块为240 KB这种理想情况下，计算不同大小数据文件验证过程的系统开销.

文献[32]采用基于TPA的验证机制，方案主要包括2个阶段：初始化阶段和审计阶段，其具有的动态数据结构双向信息索引表DLIT，能够保证在对数据块进行插入和删除时不会导致信息表中其他记录的更改，因而相比于其他方案具有更低的系统开销.为证明本文所提方案性能的优越性，将与文献[32]进行计算开销和通信开销方面的对比.同时，文献[32]支持全局与抽样验证，抽样验证同样以4.6%这一固定概率对数据块进行挑战验证.本文方案与文献[32]理论上的计算开销对比如表1所示，其中，n表示文件数据块总数，c表示挑战块数目，s表示数据块包含段的个数，M表示乘法操作，E表示指数操作，P表示双线性映射.可以看出，文献[32]的标签生成开销、证据生成开销虽然要比本方案小，但是在TPA验证证据过程中，文献[32]产生的计算开销为cM+E+(c+1)P，而本文所提方案的计算开销是(c+2)M+(s+c+1)E+2P，由于双线性操作所用时间将远大于乘法操作和指数操作，并且TPA验证证据是周期性进行的，因此，本文所提方案双线性操作次数远小于文献[32]，计算开销更小．实验过程中，采用64 MB，128 MB，256 MB，512 MB，1 024 MB的随机文件，对比文献[32]与本文方案的计算开销，其中，挑战块数目占文件数据块总数的4.6%，实验结果如图10所示.

Table 1 Computational Cost Comparison表1 计算开销对比

Fig. 10 Comparison of the computational cost for two schemes 图10 2种方案的计算开销对比

4.2 通信开销

通信过程的开销主要在于信息的交互，在云存储完整性验证模型中主要取决于审计阶段中CSS,TPA,SC间的信息交互.具体来说，本方案中通信开销包括审计阶段CSS向TPA发送内容完整性证据及向SC发送位置完整性证据过程，TPA向SC发送内容验证结果过程，如表2所示，通信开销分别为O(logn/c)，O(1).相比文献[32]，本方案在整个验证过程中没有TPA向CSS发送挑战请求这一过程，因此，方案的通信开销将大大减少.文献[32]与本文方案通信开销实验对比结果如图11所示.

Table 2 Communication Cost Comparison表2 通信开销对比

Fig. 11 Comparison of the communication cost for two schemes图11 2种方案的通信开销对比

5 总 结

本文提出一种支持隐私保护和公平支付的数据完整性验证方案，能够解决数据完整性验证过程中隐私泄露和公平支付问题.为实现用户数据隐私保护，本文设计了一种无交互式动态数据完整性证明机制NIDPDP，审计阶段中TPA无需向CSS发送挑战请求，即取消TPA和CSS进行挑战交互这一过程，避免用户数据隐私的泄露.为实现服务-支付公平，SC首先通过辅助认证信息计算得到RBMT根节点，与CSS发送的根节点进行对比，确保数据块在位置上的完整性.其次，区块链智能合约Compare Contract通过调用合约TCSS和TTPA对CSS与TPA不诚实行为进行惩罚，使各实体均诚实地按照协议规则执行.理论分析与实验结果表明，本文方案与其他方案相比，在计算开销和通信开销方面都有进一步的降低，在保障数据隐私的同时，能够实现服务-支付的公平.

作者贡献声明：富瑶提出创新点，负责模型设计、理论分析、实验数据分析和论文撰写；李庆丹参与模型设计、论文框架讨论和论文修改；张泽辉参与模型设计，优化论文结构，修改论文；高铁杠提出研究方向，分析创新点，指导理论分析与实验设计，审核论文.