抗密钥泄露的支持密态数据去重的完整性审计方案

张襄松，李晨，刘振华

（1. 西安工业大学理学院，陕西 西安 710021；2. 西安电子科技大学数学与统计学院，陕西 西安 710071）

1 引言

云平台具有强大的计算能力和存储能力，个人或企业可以将各种复杂的任务外包给云平台进行处理[1]，而不再需要花费高昂的代价购置和维护软硬件。例如大数据云存储服务，用户将数据上传给云存储服务提供商（CSP, cloud service provider）存储管理，这大大减轻了用户的存储负担，方便用户随时随地访问云端数据[2]。但是，由于用户失去对云端数据的绝对控制权，不可避免地带来了一系列数据安全问题[3]，如数据完整性、重复性、密钥泄露等。

为了自身经济利益，CSP可能故意删除用户的一部分数据。即使 CSP能够诚实地存储用户的数据，也不可避免地存在因软硬件故障而导致的数据损坏。当上述问题发生时，CSP可能瞒报，声称数据仍完整正确地存储在云服务器上，因此，需要定期地对云端数据完整性进行审计检查。如果需要将数据下载到本地再进行验证，这显然是低效的，甚至在数据量较大时是不可行的。为此，Ateniese等[4]结合随机采样技术和随机化数字签名中的同态认证标签，提出了数据持有性证明（PDP, provable data possession）概念——在不进行数据取回的前提下,云服务器向用户证明云端存储数据的完整性。进而，Juels等[5]采用检查点和纠错码的方法，提出了数据可恢复性证明（PoR, proof of retrievability）概念，不仅可以进行完整性审计，而且还能实现损坏数据的恢复。

相同的数据文件可能被不同用户上传到云服务器进行存储，产生多个文件副本，这不仅占用了云存储服务商的存储空间，也浪费了用户的带宽资源，因此需要解决数据重复存储的问题。通过数据去重来消除冗余的数据，相同文件只保存一个副本，可以大大减少用户上传带宽及服务器存储空间。熊金波等[6]综述了数据去重的研究进展。

在云存储环境中同时实现数据的完整性验证和去重功能[7-10]是十分有意义的，但是机械地将去重功能和完整性验证组合起来不可避免地会导致上传者的身份混淆，以及由此产生的数据安全问题。这是因为后续用户上传一个服务器中已有的文件时，在生成的标签中含有用户的身份，这会导致标签与服务器中相应的文件之前的标签不一致，使云服务器存储了许多额外的数据，并且与完整性验证工作造成冲突。为此，Yuan等[11]提出了一种支持数据去重的公开审计方案，将用户端的计算和传输开销减小至常数级，且支持批量审计，但是该方案的数据去重仅限于文件级，不够灵活。随后，Li等[12]设计了支持数据审计和安全去重的SecCloud方案，利用MapReduce云代替第三方审计者（TPA, third party auditor）完成数据的完整性审计，但是将数据直接发送给MapReduce云破坏了用户身份的隐私性，且该方案不能降低用户的带宽消耗。为了解决带宽问题，Kiraz[13]提出了一种支持公开审计的安全客户端去重方案，该方案具有隐私保护性质，但是在上传数据过程中，用户完成所有权证明（PoW, proof of ownership）挑战的计算量较大，效率较低。此外，Kiraz所提方案中的密钥服务器可能会根据用户发送的消息恢复出数据的部分加密密钥。

另外，由于用户安全意识薄弱或疏于管理的原因，在完整性审计过程中用户的私钥可能会丢失或遭到窃取。一旦恶意云得到了用户的私钥就能通过伪造认证标签来隐藏数据丢失，甚至为了节省存储空间删除用户不常访问的数据而不被察觉。在传统的完整性验证方案中，如果用户私钥遭到泄露，则需要用户下载其上传的所有数据，更换新的公私钥对后重新上传，显然这种方法效率极低，甚至是不可行的。因此，设计一种高效的抗密钥泄露的完整性审计方案也是十分必要的。Yu等[14]基于二叉树结构构造了一个密钥更新算法，该算法保证了密钥泄露之前的时间周期内认证标签的安全性，即事前泄露。但从密钥泄露之后到发现泄露之前，该方案无法保证之后认证标签的安全性，这是由于在实际情况中密钥泄露通常只能在用户发现认证标签不是自己生成的时候被察觉，因此 Yu所提方案的实用性较差。为了解决 Yu所提方案中的事前泄露问题，Yu等[15]又提出了强抗密钥泄露的云存储审计方案，使恶意的云不能通过已泄露时间周期的签名私钥获得其他时间周期用户的签名私钥，从而保护了除密钥泄露发生的时间周期外任意时间周期审计方案的安全性。

虽然现有数据完整性验证方案中已经实现了抗密钥泄露或数据去重功能，但目前尚没有同时支持这两项功能的数据完整性验证方案。如果只是单纯地再支持去重的审计方案中加入密钥更新，则可能会导致在不同时间周期由于用户私钥不同而无法成功去重。为解决这一问题，本文提出了一种具有密钥更新和密态数据去重的完整性验证方案。在本文方案中，采用收敛加密（convergent encryption）[12]方法保证文件的机密性；由第三方审计者协助用户进行密钥更新，能够保证用户在某一时间周期的私钥与其余时间周期的私钥相互独立，从而使得半可信的云服务器不能通过用户某一时间周期的私钥得到该用户其余时间周期私钥的任何信息。

2 预备知识

2.1 双线性映射

2.2 CDH困难问题假设

如果没有多项式时间的算法能以至少ε的优势解决CDH困难问题，那么就称CDH困难问题假设成立。

2.3 布隆过滤器

布隆过滤器（Bloom filter）[17]作为一种概率数据结构，能够近似表示集合中的元素并验证某元素是否属于该集合。由于存储空间和插入/查询请求时间均为常数，布隆过滤器较现有的其他支持以上功能的数据结构具有存储时间与空间更为高效的优势。与此同时，为了取得时空高效，布隆过滤器不可避免地牺牲了一定的准确率，即存在误判。具体来说，误判的定义是若某一元素不在集合中，在利用布隆过滤器验证时也会以一定的概率将该元素判定为属于集合；但是，若该元素是集合中的元素，则不会发生误判。

布隆过滤器由k个随机的散列函数h1(⋅),h2(⋅),和一个mbit的数组组成。初始化布隆过滤器时，需要将数组中的所有比特置为 0。若要向布隆过滤器中插入某一元素x，则需计算该元素在布隆过滤器的数组中的k个位置并将数组中相应比特置为 1。为了确定某元素是否在集合中，需要计算它的k个散列值然后验证数组中相应比特的值是否均为 1。在不考虑误判的情况下，该元素在集合中的充要条件是布隆过滤器数组中相应位置的值均为 1。此外，通过对布隆过滤器中误判的分析[18]，只要k选取适当的值，布隆过滤器的误判率可以很小。

2.4 系统描述

本文方案包含4个实体：云服务器、用户、第三方审计者（TPA）和密钥服务器（KS, key server），系统模型如图1所示。

图1 本文方案系统模型

在每个时间周期开始时，TPA通过向用户发送密钥更新消息来协助用户更新文件的签名私钥，从而达到抗泄露的目的。TPA在完整性审计时是诚实的，但在密钥更新时可能是不完全可信的。此外，在数据去重的过程中，用户需要配合云服务器验证是否需要将本地数据上传至云服务器，或是在云服务器的协助下进行 PoW 挑战而不需要上传数据本身。当用户需要对云服务器中存储的数据进行完整性审计时，首先需要将数据的认证标签发送给TPA验证其有效性，若能通过验证则TPA与云服务器执行挑战与响应协议。密钥服务器负责根据文件内容向用户分发私钥用于加密数据，用户需要从密钥服务器获取收敛密钥完成对文件进行加密。

2.5 一般方案

参考现有的支持密钥更新的公开审计方案[15]和密文数据去重的公开审计方案[12,18-19]，支持密钥更新和密文数据去重的公开审计方案通常包含以下5个算法。

密钥生成（KeyGen）算法：利用密钥生成算法，产生用户ui的公私钥对系统公开参数pp、TPA的私钥skTPA、密钥服务器的收敛密钥种子ks及用于加密文件的加密密钥ck。

更新消息生成（UMGen）算法：在每一时间周期开始时，由 TPA输入系统公开参数pp、当前时间周期t和TPA的私钥skTPA，并输出更新消息tδ。

文件上传（FileUpload）算法：若用户ui需要上传索引为idF的文件F，首先需要将文件F分为n块，计算文件F的散列值H(F)并将其发送给云服务器，判断云服务器中是否已经存储了文件F，判断结果分2种。

情形1 若云服务器中没有存储文件F，则需要通知用户ui上传数据。用户ui收到通知后利用当前时间周期t、系统公开参数pp、用户自己的私钥ski和TPA发送的更新消息tδ来计算时间周期t的签名私钥skt，并利用密钥服务器生成的加密密钥对每个消息块mj加密得到相应的密文ctj。随后用户ui生成文件F的一组认证标签Φ，将文件F的n个消息块分别存储到布隆过滤器BFj中，并将文件F的所有密文集合索引值idj和布隆过滤器BFj一同发送给云服务器。

情形2 若云服务器中已经存储了文件F，则云服务器向用户ui发出验证消息K，用户ui收到之后生成一组证明值，这时云服务器就可以通过判断这些证明值是否在布隆过滤器BFj中来确认用户ui是否确实拥有文件F。

响应值生成（ResGen）算法：云服务器执行该算法。输入系统公开参数pp、时间周期t、挑战值chal、文件F的密文集合和文件F的一组认证标签Φ，输出响应值P。其中，云服务器输入的(t,chal)由TPA发布。

响应值验证（ResVerify）算法：TPA执行该算法。输入系统公开参数pp、时间周期t、挑战值chal和响应值P。若验证通过，返回“真”；否则，返回“假”。

2.6 安全模型

用户的隐私信息包含两部分：一部分是用于在时间周期t内生成消息认证标签的用户ui的签名私钥skt；另一部分是用于在时间周期t内生成签名私钥的用户ui的私钥ski。基于Yu等[15]的支持强抗密钥泄露的公开审计方案，本节定义了敌手A和挑战者C之间的安全性游戏。在游戏中，A强大到甚至可以询问用户ui在除一个时间周期之外的所有时间周期用户的私钥。具体安全模型如下。

1) 系统建立（setup）：首先令时间周期t=0，C执行KeyGen算法，生成系统公开参数pp、TPA的私钥skTPA和用户ui的私钥ski。C将pp发送给A，然后保留ski。

2) 询问（query）：C生成用户在时间周期t的签名私钥skt。

② 私钥询问：A选择是否询问时间周期t内用户ui的私钥，若是，C将用户在时间周期t的私钥和签名密钥skt发送给A；否则，发送⊥。

每个时间周期结束时，A可选择再次询问或进行挑战。

3) 挑战（challenge）：C选择一个A在私钥询问阶段中没有询问过的时间周期*t，并将挑战值发送给A，其中索引集合且集合中的元素均属于C向A请求时间周期*t下根据挑战值chal生成的响应值P。

4) 伪造（forgery）：A输出响应值P，若验证通过，则A赢得游戏。

在上述安全模型中，A在没有拥有挑战值chal中涉及的所有消息的情况下，若不能猜测出所有的消息的内容，则无法提供私钥没有泄露的时间周期的有效响应。在每个时间周期内A均可询问所有消息的认证标签。A还可询问除挑战阶段的时间周期外所有时间周期的用户私钥。A的目的是构造时间周期*t的有效响应值P。本文定义一个数据完整性审计方案的强抗密钥泄露，即存在一个提取器能够在A生成时间周期*t的有效响应值P时提取出挑战的消息。

在实际情况下，许多用户对云服务器并不完全相信，为了保证用户数据的机密性，还需要在上传文件前对其进行加密处理。然而如果采用一般的加密方法，在去重过程中会导致不同用户利用不同密钥加密相同的文件，从而导致方案无法实现去重，因此需要对文件采用特殊的加密方法。文件的机密性要求阻止云服务器获取文件内容的攻击。特别地，要求方案能够抵抗字典攻击，也就是说，即使半可信的云服务器预先获得了包含所有可能文件及其密文的“字典”，仍旧无法恢复出目标文件。

在密钥生成算法中，TPA在每一时间周期均生成更新消息来帮助用户更新私钥。进一步要求 TPA不能根据自身私钥和生成的认证消息伪造任何认证标签，也就是认证标签的不可伪造性。

在文件上传算法过程中，考虑到有些恶意用户可能会通过伪造消息的证明值来试图利用 PoW 挑战获取合法用户上传的文件，因此，本文方案的安全性还需要达到PoW挑战中证明值的不可伪造性。如果恶意用户需要通过PoW挑战来获得文件F，假设该恶意用户已经拥有文件F的散列值和F的部分密文，那么恶意用户就可以伪造剩余部分的证明值从而达到通过 PoW 挑战的目的。本文方案不考虑恶意用户已经拥有绝大部分密文的情况，因为这种情况下恶意用户将不再需要伪造证明值。此外，本文方案利用收敛加密[7]的方法对文件F的n个消息块进行了加密，在确保文件加密密钥确定性的同时保证了文件的机密性，因此恶意用户即使已经获得了文件F的全部密文，也很难恢复出文件F对应的明文。

3 抗密钥泄露和支持去重的完整性审计方案

在实现抗密钥泄露时，本文方案中每一时间周期用户的签名私钥均为两部分的乘积，一部分是TPA根据自身私钥生成的更新消息，另一部分是由用户的私钥和当前时间周期计算而来的。任何时间周期的签名私钥都需要用户和TPA共同生成，这种方法能同时保证密钥更新的安全性和高效性，因此在没有TPA私钥的情况下，即使攻击者在某一时间周期入侵了用户，该攻击者也不能获得用户在其余时间周期的签名私钥。由于时间周期是认证标签的一部分，且无法分离出来，因此相同消息在不同时间周期的认证标签是不同的。在许多已有的云存储审计方案[2]中，利用数字签名SSig（secure signature）来保证文件索引idF的完整性。本文方案同样采用这种方式来保证文件索引idF和时间周期t的完整性，且签名SSig对应的公私钥对(ssk,spk)由用户生成。

定义3个抗碰撞散列函数H、H1和H2，其中，其中，m和len分别表示消息和证明值的长度是伪随机函数[18]，其中，κ是正整数。方案的具体构造如下。并计算gxi，得到用户ui的公私钥对

2) 更新消息生成：在时间周期t开始时，TPA利用私钥sk计算时间周期t的更新消息TPA并发送给用户。用户接收到更新消息tδ之后，利用验证消息的有效性。

3) 文件上传：若用户ui在时间周期t内上传文件F，首先需要将文件分为n个消息块其中，然后计算并上传给云服务器，云服务器收到hi之后判断hi是否已存在。

情况 1 若云服务器中没有找到相同的hi，则说明云服务器中没有存储过文件F，这时云服务器发送“No”给用户ui。用户ui收到后利用更新消息tδ计算并与密钥服务器一起执行如下步骤对文件F进行加密并生成认证标签Φ。

① 用户ui计算每个消息块的散列值mj并将所有计算结果发送给密钥服务器。

② 密钥服务器收到后对所有j=1,…,n，计算由密钥服务器保管。

③ 用户ui加密每个消息块，计算(ksj,mj)，即得到文件F的密文其中，Enc(⋅)是一个对称加密算法，idF为文件F的标识符。

④ 用户ui用密钥服务器为其分配的私钥ck加密收敛密钥ksj，并存储在云服务器中。并由此计算每个消息块mj的认证标签为

⑤ 用户ui随机选择计算

其中，idj和idF分别为消息块mj和文件F的标识符。

⑥ 用户ui生成文件F的标签和认证标签集合

用户ui计算文件F中每个消息块相应的证明值和伪随机值然后将每个伪随机值Pj插入布隆过滤器BFF中，并将布隆过滤器BFF连同文件F的密文集合 ( idF,ct1,… ,c tn)、文件标签tagt和认证标签集合Φ一起上传给云服务器。云服务器计算H(F)，验证认证标签的正确性以及hi=H(F)是否成立。若验证通过，云服务器将用户ui上传的内容存储起来，并返回用户ui文件F密文的链接和标签tagt；否则，云服务器返回出错消息。

情况2 若云服务器中已经存储过文件F，则需要用户ui通过与云服务器的 PoW 挑战。首先，云服务器随机选择文件F中的s个密文消息块，并将这些消息块的索引集合K= {k1, … ,kl} (1 ≤l≤n)发送给用户ui。用户ui收到集合K后，计算集合中每个索引对应的证明值然后将返回给云服务器。对于所有云服务器选出的l个消息块，云服务器利用用户ui返回的计算其伪随机值并验证是否所有的Pkj均属于布隆过滤器BFF。若属于，则向用户ui发送文件F密文的链接和认证标签tagt；否则，返回出错消息。

4) 响应值生成：若用户ui需要验证已上传文件F的完整性，则首先将文件F的认证标签tagt发送给 TPA。TPA收到后利用spk验证文件认证标签tagt的有效性，若有效，则选择一个索引集合其中的每个元素均属于对于每个idj∈I，TPA随机选择vj，并生成挑战值发送给云服务器。云服务器在收到挑战值chal后，计算并将响应值P= (t,R,σ, μ)返回给TPA。

5) 响应值验证：TPA收到响应值P后，验证

是否成立，若成立，返回“真”；否则，返回“假”。

4 安全性分析

4.1 方案的一致性

对于一个随机的挑战值 c hal = {idj,vj}idj∈I和有效的证明值P= (t,R,σ, μ)，响应值验证算法总会返回“真”，因为有以下等式成立。

若用户ui需要取回存储在云服务器上的文件，那么在取回文件F的同时还需要下载事先已加密的收敛密钥ksj，并用私钥进行解密，从而得到相应的明文文件。

4.2 强抗密钥泄露

定理1 若1G上的CDH问题是困难的，则方案是强抗密钥泄露的。

证明 定义以下一系列安全性游戏，并分析敌手A在游戏中的行为差异。

游戏0 游戏0是第2.6节中定义的安全性游戏。

游戏1 游戏1基本与游戏0相同，不同之处在于，挑战者C维护一个所有经过他签名的认证标签列表。当A提交一个未通过C签名的有效标签时，C中止游戏。

分析 若A在游戏1中使C中止游戏，则容易利用A构造一个攻击攻破签名方案SSig。以下假设idF和t在交互过程中均由C生成。

游戏2 游戏2与游戏1基本相同。不同之处在于，C维护一个对A认证标签询问的响应值列表。若A取得游戏胜利，而响应值P中的R与C维护的列表中不同，则C中止游戏。

分析 若A能够使C在游戏2中中止游戏，则可以构造一个模拟算法S以不可忽略的概率解决CDH困难问题。S与游戏1中的C类似，但有以下不同：给予C一个CDH挑战通过A计算gab，然后选择签名公私钥对(ssk,spk)生成idF和t的签名。假设A进行了qk次私钥询问和qs次认证标签询问。

询问（query）：将H和H2看作 2个由C控制和存储的随机预言机，C需要对A发出的询问做出回答。

1)H预言机询问：C存储一个初始为空的H列表。当A向C发送时间周期t来询问H预言机时，C查找H列表，检查是否有包含输入的时间周期t的元素(t,c,λ,h)。若有，则向A发送h；否则，C掷一枚硬币c∈ { 0 ,1}，满足结果为 0的概率为结果为1的概率为若投掷结果为0，C随机选择并计算gλ，然后将加入H列表；否则，C随机选择，然后将(t, 1 ,λ,h=Yλ)加入H列表，最后，C向A发送h。

2)H2预言机询问：C存储一个初始为空的H2列表。当A向C发送进行询问时，C查找H2列表，检查是否有包含该输入的元素若有，则向A发送h2；否则，C随机选择添加到H2列表，最后，C向A发送h2。

3) 私钥询问：当A在时间周期t内进行私钥询问时，C从H列表中取出不失一般性，假设A向H预言机询问过时间周期t。若c=1，则C中止（用E1表示）；否则，C计算其中最后，C返回(ski, skt)。

挑战（challenge）：C选择一个A没有进行过私钥询问的时间周期*t，然后向A发送一个挑战值和时间周期*t，其中I是消息块索引的一个子集。此外，C还要求A提供时间周期*t文件在挑战值下的响应值P。

分析C在上述模拟算法中不中止的概率为

其中，pk和ps分别为A私钥询问和认证标签询问的数量。

如果A通过了挑战，但响应值P中的R与C从H2列表中找到的R不相同，那么C能够以不可忽略的概率解决CDH困难问题。

游戏3 游戏3与游戏2类似，不同之处在于C存储一个生成的A认证标签询问的返回结果列表。C检查列表中的元素，若任何元素中有A虽通过挑战但A的认证标签则C中止。

分析 假设使C中止的文件为 {1,F→m时间周期为t，文件的认证标签集合为A 的响应值为挑战值为A诚实情况下生成的预期响应值因此，有效的响应值可由式(1)验证。

根据C中止可以推断出σ′≠σ，且σ′能够通过如下等式的验证

设 Δ μ = μ ′- μ ，显然有 Δμ≠0，否则与假设矛盾。构造如下模拟算法S解决CDH困难问题。

向S输入(g,ga′,v)，最终输出va′。S代替游戏2中的C，但有以下不同：在系统建立阶段，S选择计算并生成实际情况下所有时间周期的私钥。H2可看作一个由S控制并存储的随机预言机，当A向H2预言机发送时，S验证H2列表中是否已经存在相应的元素若有，S返回h2给A；否则，S随机选择将添加到H2列表，并向A返回h2。

当A询问消息块mj在时间周期t的认证标签时，S随机选择计算R= (ga)ς和与已有值碰撞的概率是可忽略的。S计算认证标签

即

由此解决了CDH困难问题

若A赢得游戏2和游戏3的概率有不可忽略的差别，则S能够解决CDH困难问题，所以在任何能够通过验证的响应值中σ必须是正确的。

游戏4 游戏4与游戏3除以下区别外基本相同：C存储并检查进行认证标签询问时给A的返回值。若存在A赢得游戏但A的聚合消息μ′≠则C中止游戏。

因此，若A在赢得游戏3和游戏4的概率之间存在一个不可忽略的差别，就可以构造一个模拟算法S解决离散对数问题。

根据本文分析，这些游戏之间仅存在可忽略的差别，且解决CDH问题的困难程度蕴含着解决离散对数问题的困难程度。若1G上的CDH问题是困难的，且签名算法SSig是不可伪造的，则C除了A上传正确的响应值P的情况外将无法验证通过。

4.3 机密性

由于方案中引入了密钥服务器来帮助用户生成文件的收敛密钥，因此若不利用密钥服务器存储的收敛密钥种子，半可信的云服务器就不能以不可忽略的概率生成任何文件有效的收敛密钥。由于文件的散列值可以看作一个有效的消息认证码，因此云服务器在没有密钥服务器的帮助下就无法实施暴力攻击。此外，所有消息块在上传给云服务器前均已加密，且收敛密钥由密钥服务器生成，并由上传文件的用户公钥加密后存至云服务器的，也可以认为收敛密钥是由文件本身和密钥服务器的收敛密钥种子共同产生的，这就意味着收敛密钥并不仅仅源于文件本身。

假设半可信的云服务器不能与密钥服务器共谋，那么即使文件是可预测的，半可信的云服务器也不能利用暴力攻击推测出文件的内容，由此说明本文方案能够抵抗字典攻击。

4.4 可检测性

假设云服务器存储一个n块的文件，其中的k块均被损坏，在挑战阶段TPA的挑战值中包含s块，则损坏的块被发现的必要条件是当且仅当被挑战的块中至少一个是损坏的块。利用一个独立的随机变量X表示挑战阶段选择的块中损坏的块数量，用PX表示在挑战阶段选择的块中至少有一个被损坏块的概率。因此，有。也就是说，损坏的块被检测出的概率至少是说明损坏的块越多，TPA选出进行挑战的块越多，损坏的块被检测出的概率越大。

4.5 认证标签的不可伪造性

从文件上传算法中可以看出，时间周期t内计算任何认证标签均需要私钥 skt，而用户私钥的生成过程中私钥是由用户ui的私钥ski和TPA的私钥这两部分私钥构成的，具体来说，就是由于方案中的TPA只拥有skTPA且仅需要计算更新消息tδ，因此TPA不知道用户ui的私钥ski也就不能计算出skt。因此TPA不能通过自己的私钥skTPA和更新消息tδ伪造任何消息块的认证标签。

4.6 证明值的不可伪造性

在文件上传算法中，若某一用户需要向云服务器上传文件，在上传消息之前需要先发送文件的散列值来验证云服务器中是否已经存储该文件，若没有存储，则需要用户上传文件F、文件标签tagt、认证标签集合Φ和消息的布隆过滤器BFF；若云服务器中已经存储过，则用户不再需要上传文件本身，而改为执行 PoW 挑战，目的在于避免恶意用户通过拥有文件的散列值而不是整个文件来恶意获取合法用户的数据。简单地说，本文方案利用布隆过滤器匹配消息的证明值来实现PoW挑战。

PoW 挑战要求用户生成云服务器随机选取的k个消息块的证明值，云服务器收到证明值后用伪随机函数处理并用相应的布隆过滤器验证是否属于选定的消息。假设恶意用户需要获得消息mj，若恶意用户拥有mj的一些消息块，在进行PoW挑战时恶意用户需要生成所有云服务器选择的k个消息块的证明值。在Blasco等[18]的方案中已经得出，如果恶意用户仅仅拥有少数消息块，布隆过滤器的参数选取得当，且k足够大，那么恶意用户成功伪造消息证明值，从而通过PoW挑战的概率是可忽略的。

不能否认的是，若用户拥有绝大多数的消息块，则会以很大概率通过 PoW 挑战。在这种情况下，由于用户几乎已经拥有该消息，也就可以将这个用户看作一个合法的拥有者了。

5 性能分析与实验结果

本节从方案实现的功能和效率这2个方面进行分析。由于目前没有能同时支持抗密钥泄露和密文数据去重的完整性审计方案，本文方案在功能上更有优势。在方案的效率方面将从计算效率和通信效率两部分进行评价。为便于表示，用exp、mul、hash和pair分别表示指数运算、乘法运算、散列运算和对运算。

在文件上传阶段，若云服务器中没有存储需要上传的文件，则用户需要计算签名私钥skt、文件标签tagt、认证标签集合Φ和布隆过滤器BFF，计算开销为(n+ 1 )hash + 2 exp + 3 mul+ s ig + p rf ，其中，sig和prf分别为数字签名和伪随机函数；反之，若云服务器中已经存储过该文件，则用户需要生成PoW挑战的证明值，相应的计算开销为(l+ 1 )hash 。在挑战阶段，TPA仅随机选择一些消息块的索引生成挑战值，因此计算开销很小。然而在响应阶段，云服务器生成响应值时的计算开销为se xp + (s- 1 )mul +smul，其中s表示挑战值中选取消息块的个数。最后，在验证阶段，TPA判断响应值是否有效，计算开销为(s+ 2 )exp + (s+2)mul+ 3 pair。表1分析了方案的总体计算开销。

表1 支持密钥更新和密文数据去重的公开审计方案的计算开销

本文方案的通信开销主要包括文件上传、挑战阶段和响应阶段这3个部分。在文件上传的过程中，用户需要将发送给云服务器，这部分的通信开销为分别表示文件的大小和Zp或G1上一个元素的大小。挑战阶段挑战值TPA挑出的s个(idj,vj)组成，因此通信开销为其中，为索引的长度。相应阶段响应值的通信开销为

实验通过对方案的计算开销和通信开销进行比较，利用PBC库给出Windows 7环境下的效率分析结果，实验配置为 Intel Core I3-2120 CPU@3.30 GHz，4 GB RAM。假设1G和Zp上的元素大小均为160 bit，消息块的大小为2 KB，集合I中的元素大小为20 bit，以下实验结果为50次实验的平均值。

图2显示了方案中用户、云服务器和TPA在云服务器中有副本和无副本这2种情况下的计算开销随文件块数和挑战块数取值的变化趋势。仿真实验选定文件的分块数量为 400，选取挑战块数分别为50、100、150、200和 250。图2(a)表明当云服务器中无副本时，TPA和云服务器的计算开销随着审计过程中挑战块数量的增加呈线性增长，而用户的计算开销只与文件分块的个数n有关，故用户的计算开销呈直线，且大于TPA和云服务器的计算开销。图 2(b)表明当云服务器中有副本时，云服务器承担了密文数据去重的大多数计算开销，随着审计过程中TPA挑战块数量的增加而呈线性增长，而用户和TPA的计算开销只与文件分块的个数n有关，故呈直线，且用户的计算开销小于TPA的计算开销。因此，在云服务器中无副本时，用户的计算开销较大；而有副本时，云服务器的计算开销较大。

图2 用户、云服务器和TPA计算开销的变化趋势比较

图3显示了方案中用户、云服务器和TPA三方在云服务器中有副本和无副本这2种情况下的通信开销随文件块数和挑战块数取值的变化趋势。在图3(a)中，选取文件分块数量分别为250、300、350、400和450，结果表明，在云服务器中无副本时，用户的通信开销随着文件分块数量增加而线性增加，而TPA和云服务器的通信开销较小。在图3(b)中，选定文件的分块数量n为400，选取挑战块数分别为50、100、150、200和250，仿真结果表明，在云服务器中有副本时，TPA的通信开销随着审计过程中挑战的文件块数量的增加线性增长，而用户和云服务器的通信开销较小。因此，当云服务器中无副本时，用户的通信开销较大；而云服务器中有副本时，通信开销主要在审计过程中由TPA承担。

图3 用户、云服务器和TPA通信开销的变化趋势比较

6 结束语

本文提出了同时支持密钥更新和密文数据去重的公开审计方案。新方案首次在支持数据去重的完整性审计方案中解决密钥泄露问题，且方案不仅考虑密钥泄露之前的安全性，还考虑到密钥泄露之后的用户数据机密性保护问题，使用户在某一时间周期内的私钥不会影响到其他时间周期，且敌手即使通过了PoW挑战也很难恢复出明文数据。安全性分析表明，新方案达到了强抗密钥泄露、机密性、可检测性以及认证标签和证明值的不可伪造性。下一步需要提高效率和进行全面形式化安全性证明。