支持身份认证的数据持有性证明方案

2016-11-24李昊星李凤华宋承根阎亚龙

通信学报 2016年10期

李昊星，李凤华,2，宋承根，阎亚龙

(1. 西安电子科技大学综合业务网理论与关键技术国家重点实验室，陕西西安 710071；2. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093；3. 北京电子科技学院信息安全研究所，北京 100070)

支持身份认证的数据持有性证明方案

李昊星1，李凤华1,2，宋承根3，阎亚龙3

针对云应用场景中身份认证和数据持有性证明的双重需求，提出一种支持身份认证的数据持有性证明方案。基于数据标签签名和随机数复用，新方案通过3次交互即可实现用户对云持有数据的完整性验证、用户与云服务器之间的双向身份认证以及会话密钥协商与确认。与使用认证密钥协商和数据持有性证明的组合方案相比，新方案具有较少的运算量和交互轮次以及可证明的安全性。在随机预言机模型下，基于计算性Diffie-Hellman问题假设，给出方案的安全性证明。

认证；数据持有；云计算；可证明安全；随机预言机

1 引言

随着云计算的快速发展，基于云构建的各种应用逐渐融入了人们的工作和生活。云计算利用虚拟化技术实现了多租户共享云资源，提高了硬件资源的利用率，降低了用户的使用成本[1]。云计算为用户提供了高性能、高稳定性、低费用的服务，同时也带来了一些新的安全问题，如云环境中的身份认证、访问控制、数据搜索、数据完整性验证和数据安全删除等。近期接连发生的云计算相关安全事故使云安全问题成为产业界的热门话题和学术界的研究热点[2]。

基于云构建的存储系统中，敏感数据被加密保护后再上传到云服务器，在使用时被取回并解密。此过程中，应避免取回大量无效数据造成通信资源和下载时间的浪费。而基于云构建的复杂计算系统中，程序运算量大，单次运行周期长，应在程序执行前确认相关算法、策略或参数等关键内容的完整性，避免无效运行的情况发生。在诸如此类的云应用系统中，需要考虑外源数据的完整性问题。但云服务器并不完全可信，用户无法依赖云自身的安全防护手段保证数据的完整性，而且云服务器存在设备损坏、遭受自然灾害和黑客攻击的可能性。所以，用户需要自主地验证云数据的完整性。如果用户将云数据下载到本地以验证其完整性，在数据量较大的情况下是低效的。为此，研究者们提出了数据持有性证明（PDP, provable data possession）[3]和数据可恢复证明（POR, proofs of retrievability）[4]。PDP方案使用户即使删除了本地数据，仍然可在无需下载数据的条件下，利用数据标签验证云服务器是否持有完整的用户数据，且在此过程中不会泄露数据内容。PDP方案注重快速验证云端数据是否损坏，而 POR方案除此功能之外还能恢复已损坏数据，二者对应的应用需求不同。另外，在云计算环境中，用户身份认证是防止数据非法访问的前提条件，也是计费、日志记录和审计的基础[5]。即使云存储系统中的敏感数据已被加密保护，仍有必要对访问者进行身份认证，以便降低密钥泄露对敏感数据的安全威胁，也能有效减少攻击者发动侧信道攻击的可能性。通过上述分析可以看出，云应用场景中存在同时需要数据持有性证明和身份认证的情况。

针对云数据持有性证明问题，研究者首先提出了公开验证的 PDP方案[3,6～8]。在公开验证的 PDP方案中，任何人都可以向云提出数据持有性验证请求并得到正确的应答结果。但某些具有较高安全需求的用户将云服务器的数据持有情况视为隐私，不希望这些信息被公开获得。而攻击者可以利用公开验证的PDP方案评估攻击效果，进而找出针对云中敏感数据的有效攻击方法。所以，如何限定验证者身份成为 PDP方案需要解决的问题。为此，Shen和Zeng[9]提出了代理验证的PDP方案，该方案中数据拥有者为验证代理生成代理密钥，云服务器利用该代理密钥对数据拥有者生成的标签进行转换，使代理可以验证云中数据的完整性。Wang[10]给出了一个基于授权的PDP方案，该方案的基本思想是数据拥有者利用签名给验证者授权，拥有授权才能验证云服务器持有的数据是否完整。Ruan和Lei[11]提出了一种具有细粒度权限控制能力的代理验证方案，该方案中验证者可在不提供私钥的情况下向他人证明数据丢失。Xu等[12]提出了一种可保护验证者隐私的代理验证方案。

针对云环境中的身份认证，Nimmy和Sethumadhavan[13]提出了一种利用秘密共享实现的双向认证方案。该方案中，服务器将用户的凭证分为2份，一份存储在智能卡中，另一份存储在服务器中。Hao等[14]提出了一种基于时间有效期票据的云环境双向认证方案。该方案的优点是服务器向用户发出一定数量的数字票据，用户可以一次数据验证使用一张票据，所以它可以节省验证的时间。Huang等[15]提出了一种具有顽健性和隐私保护的云认证方案。Nagaraju和Parthiban[16]提出了可证明安全的多因子云认证方案。

虽然数据持有性证明方案和云认证协议分别解决了云环境中数据持有性证明及用户身份认证问题，但在一个方案中既完成用户认证又实现数据持有性证明，可提供更好的安全性、运算效率和环境适应能力。所以，研究支持身份认证功能的数据持有证明具有理论和应用价值。2015年，Hahn等[17]首次提出了基于数据块持有证明的认证方案。但该方案仅实现了认证，不支持密钥协商，且用户需要存储由云服务器生成的、完整的Merkle树，要求用户具有较大的存储空间。

为此，本文提出一种支持身份认证的数据持有性证明方案，简称A-PDP方案。本方案利用预生成的数据标签和数据持有性证明过程的中间数据实现用户与云服务器之间的身份认证与密钥协商，且不泄露数据内容和用户身份。本文贡献如下：提出一个方案，用于既要验证云持有数据完整性，又要验证用户身份的应用场景，仅当用户拥有授权且云持有完整数据的条件下，才能完成相互认证和会话密钥协商；方案具有密钥确认功能，且交互轮次比组合方案减少一半；方案的用户端运算量小、存储内容少；在随机预言机模型下证明了方案的安全性。

2 A-PDP模型

本节首先给出A-PDP方案定义，然后描述方案的安全目标和相应的攻击模型。

2.1 方案定义

A-PDP方案架构如图1所示，方案中存在3种实体：云服务器S、数据拥有者H和用户U。

图1A-PDP方案架构

数据拥有者H首先对将要上传到云服务器S的数据进行分组，为每组数据生成标签，然后将数据分组和标签存储到云服务器S中。用户U在访问及验证数据拥有者H上传到云中的数据前，首先要通过安全信道获得数据拥有者H的授权。用户U得到授权之后，可以生成数据持有性验证的挑战并发送给云服务器S。云服务器S收到挑战后，利用数据分组和对应的标签，生成数据持有凭证并返回给用户U。用户U根据持有凭证判断云服务器S是否持有完整的数据，然后生成授权凭证并发送给云服务器S。云服务器S根据授权凭证判断用户拥有的授权是否有效。最后，双方根据需要协商出会话密钥。上述过程可简述为：用户U判断云服务器S中数据拥有者H的数据是否完整；而云服务器S判断用户U是否拥有授权。只有当云服务器S持有完整的数据且用户U拥有授权的情况下，二者才能协商出相同的会话密钥。在A-PDP方案中，假设云服务器S是半可信的，会诚实地执行方案，不会主动泄露私钥和秘密数据。

一个A-PDP方案包括7个多项式时间算法：Setup、TagGen、Authorize、Challenge、GenProof、CheckProof和CheckAuthority，算法具体定义如下。

Setup(1k)：系统输入一个安全参数 k，为数据拥有者H和云服务器S生成公私钥对。其中，数据拥有者H的公私钥对为(pkH,skH)，云服务器S的公私钥对为(pkS,skS)。

TagGen(pkH,skH,m)→Tagm：数据拥有者 H根据自身的公私钥对(pkH,skH)，为数据分组m生成标签Tagm，然后将数据分组m和Tagm一起发送给云服务器S。

Authorize(skH,IDU)→cert：数据拥有者H根据自身的私钥skH和用户U的身份标识IDU，生成授权cert并安全递送给用户。

Challenge(pkS,cert, Tagm)→Chal：用户 U根据云服务器 S的公钥pkS、授权cert和数据标签Tagm，生成挑战Chal并发送给云服务器S。

GenProof(pkH,skS, Tagm,m, Chal)→Vm：云服务器S根据数据拥有者H的公钥pkH、自身的私钥skS、数据标签Tagm、数据分组m以及用户U生成的挑战Chal，生成持有数据m的凭证Vm并发送给用户U。

CheckProof(pkH,pkS,cert, Chal, Vm)→{success,failure,VU}：用户U根据数据拥有者H的公钥pkH、云服务器S的公钥pkS、授权数据cert、挑战Chal和云服务器S生成的凭证Vm，判断云服务器S是否持有完整的数据分组m，然后生成拥有授权cert的凭证VU，将凭证VU发送给云服务器S。

CheckAuthority(pkH,skS, VU)→{succes s,failure}：云服务器 S根据收到的授权凭证VU，验证用户 U是否具有数据拥有者H的授权。

最后，云服务器S和用户U可利用上述步骤的过程数据协商出相同的会话密钥。

2.2 安全模型

A-PDP方案具有数据持有性证明和认证密钥协商功能，应同时满足二者的安全目标。A-PDP方案的安全目标为：1) 在无数据m的情况下，云服务器不能正确地给出持有数据m的凭证；2) 无授权用户无法判断出云服务器中挑战对应数据的完整性；3)无授权用户或者其他授权用户无法正确地猜测出某授权用户与云服务器之间协商的会话密钥。其中，目标1)和目标2)分别为数据持有性证明的可验证性和授权验证性，目标3)为认证密钥协商安全性。

以下对上述安全目标对应的攻击者进行说明。目标1)的攻击者是云服务器，云服务器希望在篡改或删除用户数据的情况下，仍然可以向用户证明存储在服务器上的数据是完整的，该情况是所有PDP方案都需要解决的问题。目标2)的攻击者是没有授权的用户，称为“外部攻击者”，该攻击者希望得到云服务器数据持有的相关信息，如某份数据是否存储在云服务器中。目标3)的攻击者有2类，一类是外部攻击者，另一类是有授权的恶意用户，称为“内部攻击者”。目标3)的2类攻击者都希望获得其他授权用户与云服务器之间的会话密钥，而内部攻击者拥有外部攻击者的全部能力并且拥有合法的授权数据。为便于说明，本文将外部攻击者作为目标2)的攻击者，将内部攻击者作为目标3)的攻击者。

根据安全目标和相应的攻击者，构造3种攻击模型。其中，C表示挑战者，A表示攻击者。

可验证性攻击模型：在该模型中，攻击者是云服务器，拥有云服务器的私钥以及若干询问。攻击模型如下。

Setup：C运行Setup(1k)为云服务器S和数据拥有者 H生成公私钥对，得到(pkS,skS)和(pkH,skH)，公开公钥并将云服务器私钥skS发送给A。C运行Authorize(skH,IDU)，得到授权cert。C运行标签产生算法TagGen(pkH,skH,mi)，计算出若干数据分组mi的标签Tagmi，将数据和标签发送给A。

TagQuery：A可以选择任意数据块mi，将mi发送给C。C运行标签产生算法TagGen(pkH,skH,mi)，生成标签Tagmi并返回给A。

HashQuery：A可以将任意数据发送给C，C将对应的散列结果返回给A。

Challenge：C选择一个A没有的数据m′，生成相应的挑战信息Chalm′以及m′的标签Tagm′，将Chalm′和Tagm′发送给A 。

Forge：A根据Chalm′ 生成挑战应答 Ansm′（此时A 不知道mi′），将Ansm′发送给C。

Check：C运行CheckProof(pkH,pkS,cert,Chalm′,Ansm′)，若运行结果为success，则表明A正确地生成了对于m′挑战应答，破坏了方案的可验证性。

定义 1如果任何多项式时间的攻击者按照上述模型攻破某 A-PDP方案可验证性的概率是可忽略的，则该A-PDP方案具有可验证性。

授权验证性攻击模型：在该模型中，A是外部攻击者，不能获得云服务器的私钥和用户的授权数据。攻击模型如下。

Setup：C运行Setup(1k)为云服务器S和数据拥有者 H生成公私钥对，得到(pkS,skS)和(pkH,skH)。C运行Authorize(skH,IDU)，得到授权certU。C运行标签产生算法TagGen(pkH,skH,mi)，计算出若干数据分组mi的标签Tagmi，将数据分组和标签发送给A。

TagQuery：A可以选择任意数据分组mi，然后发送mi给C。C运行标签产生算法TagGen(pkH,skH,mi)，计算出数据分组mi的标签Tagmi，然后将得出的标签发送给A。

HashQuery：A可以将任意数据发送给C，C将对应的散列结果返回给A。

SendQuery：A冒充当前用户，发送任意消息给C。C根据协议运行，对消息进行处理后将对应的应答返回给A。

Challenge：C选择一个A没有询问过的数据分组mj，发送数据分组mj的标签Tagmj给A。需要A判断标签Tagmj对应的数据分组是否存储在云服务器S中。

Judge：如果A可以正确地计算出CheckProof(pkH,pkS,cert, Tagmj,Chal, Vmj)的结果，则说明A破坏了方案的授权验证性。

定义 2如果任何多项式时间的攻击者按照上述模型攻破某 A-PDP方案授权验证性的概率是可忽略的，则该A-PDP方案具有授权验证性。

认证密钥协商安全性攻击模型，在该模型中，A是内部攻击者。攻击模型如下。

Setup：C运行Setup(1k)为云服务器S和数据拥有者 H生成公私钥对，得到(pkS,skS)和(pkH,skH)。C运行Authorize(skH,IDU′)为所有合法用户生成授权，A可得到除当前用户 U之外任何其他用户U′的授权certU′。C运行标签产生算法TagGen(pkH,skH,mi)，计算出若干数据分组mi的标签Tagmi，将数据分组和标签发送给A。

TagQuery：A可以选择任意数据分组mi，然后发送mi给C。C运行标签产生算法TagGen(pkH,skH,mi)，计算出数据分组mi的标签Tagmi，然后将得出的标签发送给A。

HashQuery：A可以将任意数据发送给C，C将对应的散列结果返回给A。

SendQuery：A冒充当前用户，发送任意消息给C。C根据协议运行，对消息进行处理后将对应的应答返回给A。

TestQuery：A选择一个之前没有进行过任何询问的会话作为测试会话，对该会话进行Test询问。C随机选择一个比特b。若 b=1，则C发送正确的会话密钥给A；反之，b=0，C选择一个随机数作为会话密钥返回给A。

Judge：如果A可以以不可忽略的优势猜测出TestQuery中b的值，即猜中TestQuery的输出是随机数还是真实的会话密钥，则说明攻击者破坏了方案的认证密钥协商安全性。

定义 3如果任何多项式时间的攻击者按照上述模型攻破某 A-PDP方案认证密钥协商安全性的概率是可忽略的，则该A-PDP方案具有认证密钥协商安全性。

3 方案构造

本节给出A-PDP方案具体构造。A-PDP方案利用指数运算的同态性，可同时对多个数据分组进行批量验证，即可实现数据分组的随机线性组合(random linear combination)验证。

A-PDP方案具体构造如图2所示。

图2A-PDP方案构造

Setup(1k)：系统选择2个安全的大素数p和q。设N=pq为RSA算法中的模，QRN是模N的二次剩余所组成的群，g是QRN的生成元。系统选择散列函数H(·)∶(0,1)*→(0,1)k、一对安全的对称加解密算法和密钥派生函数KDF( i, len)。其中，k为安全参数，K是对称密钥，i是派生因子，len是派生密钥的长度。N、g、H(·)、EK(·)、DK(·)和KDF(·,·)是系统公开参数。系统为数据拥有者H和云服务器S生成公私钥对，将公钥公开，将私钥安全递送给相应实体。其中，数据拥有者 H的公私钥对为；云服务器S的公私钥对为。系统选择大素数 d、e，满足de≡1mod(p−1)(q−1)，将(d,e)作为数据拥有者 H的标签签名公私钥对。

TagGen(pkH,d,pkS,mi(1≤i≤n))：数据拥有者H将数据m（可以是加密生成的数据）分成n组，每个分组标记为mi(1≤i≤n)。数据拥有者H为每个分组m生成标签i，然后将数据分组和标签一同发给云服务器S。其中，wmi是每个分组对应的特征值，云服务器S利用特征值查找数据分组，特征值不泄露数据内容，可包含文件名、按照一定规则定义的序号、关键词等。

Authorize(skH,IDU)：用户U首先通过安全信道发送自己的身份标识IDU给数据拥有者H。数据拥有者 H随机选择r∈并计算RU=gr和。其中，。数据拥有者H通过安全信道将授权发送给用户U。用户 U在收到授权 cert后，验证等式是否成立。若等式成立则说明授权有效；否则说明授权无效。

Challenge(pkS,cert, wmi(1≤i≤n))：用户U在收到数据拥有者H的授权(RU,sU)后，任何时候都可以对云服务器S上数据拥有者H的数据进行持有性验证。假设用户U要验证数据m，数据分组mi对应的标签为Tagmi，数据分组的特征值为wmi，其中，1≤i≤n。用户 U 随机选择并计算ga、K=(gsS)a和加密密钥H( K||ga||gsS)，选取n个随机数a1, a2,…,an∈ZN*，将挑战消息Chal={ga,C}发送给云服务器S。其中，

GenProof(pkH,skS, Tagm,m, Chal)：云服务器S在收到挑战消息Chal={ga,C}后，执行以下操作。首先，根据自己的私钥sS计算K′=(ga)sS以及解密密钥H( K′||ga||gsS)，并利用D(·)解密 C，得到ID,R,ga,a, w,a, w,…,a, w。然后，根据得UU1m12m2nmn到的数据特征值查找出所有对应的数据分组和标签。如果所有数据分组都被找到，则随机选取b∈Z*计算：N和否则，随机生成T1、T2和M。最后，根据T2和M计算，将{T, T, V}作为121挑战响应发送给用户U。

CheckAuthority()：云服务器 S收到V2后，验证等式是否成立。若等式不成立，退出当前会话；否则，说明用户U拥有授权并计算出了相同的会话密钥。最后，计算skey=KDF( IDU||IDS||M, klen)。

4 正确性分析

本方案中，数据拥有者对所有数据分组的标签进行了签名，使包括云服务器在内的其他实体无法伪造标签，用户在验证消息前无需存储或获取相应的标签。云服务器将标签聚合后生成T1并发送给用户，用户无需得到每个数据分组实际的标签数据，仅需验证标签的聚合结果，并从中获得关于数据分组的信息。本方案的关键点是用户U计算出的M′与云服务器S计算出的M是否相等。下面将数据分组标签代入到方案中，给出方案的正确性分析。

所以，当云服务器拥有挑战对应的所有数据分组的情况下，若云服务器按照方案设计应答用户挑战请求，则用户和云服务器可以计算出相同的M值。否则，将导致验证失败。

5 安全性分析

根据2.2节中的攻击模型，在随机预言机模型中证明本方案的安全性。

定理1若CDH假设在QRN中成立，则A-PDP方案在随机预言模型下具有可验证性。

证明根据可验证性攻击模型，C在随机预言模型下为A模拟A-PDP方案，并回答A提出的所有数据分组mi的标签询问以及所有数据的散列询问。若A可以在多项式时间内以不可忽略的概率攻破A-PDP方案的可验证性，则挑战者C可以利用A破解QRN上CDH问题。具体证明过程如下。

Setup：C运行Setup(1k)算法为云服务器S生成公私钥对，为数据拥有者H生成公私钥对和标签签名公私钥对。其中，云服务器 S的公私钥对，数据拥有者 H的公私钥对，标签签名公私钥对为(d,e)。根据A-PDP方案生成用户授权(RU,rU)。这里将数据拥有者H的公钥pkH、云服务器S的公钥pkS和私钥skS发送给A。

TagQuery：A可以选择若干分组mi(1≤i≤n)，并发送mi给C，C按照如下方式回答A的标签询问。

若已对数据mi(1≤i≤n)进行过TagGen询问，则C从标签列表里找到对应的Tagmi，将Tagmi发送给A；若没有对数据mi进行过TagGen询问，则C运行标签产生算法，计算出数据mi的标签Tag=(H( w) gmi)d，然后将Tag 发送给A，同时miimi存储(mi,Tagmi)到标签列表中。

HashQuery：A可以对随机预言机进行询问，从而得到某个消息的散列值。C按照如下方式回答攻击者对消息X的散列询问。

若消息X已经被进行过散列询问，则C从散列列表里找到对应的散列值hx，将hx发送给A；若消息X没有被进行过散列询问，则C随机选取一个数值hx，将hx作为消息 X的散列值发送给A，同时存储hx=H( X )到标签列表中。

Challenge：C任选一个验证实例，在该实例中任选一个随机数gx作为协议中的ga，随机选取，并计算K=(gx)sS以及。然后C再任选一个随机数gy，满足y是中一个数据分组，标签为，特征值为wy。C计算其中，有一个mi即为选定的y，其对应的随机数为ay。C将挑战信息Chal=(gx,C)发送给A。这里的挑战模拟是合理的，因为A要在不知道数据y的情况下，成功地证明他拥有y。

Forge：A利用私钥sS，解密 C得到。A的目的是产生包含数据分组y的挑战Chal的应答信息Vy。若A可以成功地生成挑战信息Chal=(gx,C)的应答信息Vy，使CheckProof(pkH,pkS,cert,Chal, Vy)的结果为success，则C可以A破解CDH问题。因为，若A要使CheckProof成功，即要得出Vy使其满足。也就是说，A要得出这样的Vy，必然进行了的散列询问。其中，，b为A选择的随机数。因此，C可以查找散列列表获得。由于C知道s、s、US所有ai以及除了消息y以外的所有mi，所以C可以获得，也就获得了。由于，所以C可以获得gxy，也就破解了QRN上 CDH问题。由于QRN上CDH假设在多项式时间内是成立的，所以定理1得证。

定理 2若 CDH假设在QRN中成立，则A-PDP方案在随机预言模型下可以提供用户的授权验证性。

证明定理2说明的是外部攻击者没有授权，不能对任何数据分组进行持有性验证。该外部攻击者即没有授权数据，也不知道云服务器和数据拥有者的密钥。授权验证性的目标是：外部攻击者知道数据分组mi及其标签的情况下，仍然不能验证mi是否存储在云服务器当中。具体证明如下。

Setup(1k)：C运行Setup(1k)算法产生数据拥有者H的公私钥对为pk=gsH、sk=gsH以及用于

H H标签签名的公私钥对(d,e)。在产生云服务器S的公钥时，C选择一个随机数gy作为其公钥。C按照如下方式为用户U发放授权。C选择r∈并计算RU=gr，然后C随机选择gx，令gx=h=H( ID||R)。C可

U UU以这样做的原因是C控制着所有散列函数的返回值，最后C计算 sU=r+hUsH并将(RU,sU)发送给用户U。外部攻击者可以获得的是数据拥有者和云服务器的公钥、用户U相关信息(IDU,RU)、数据分组mi及相应标签。

HashQuery、TagQuery：A可以进行标签询问以及散列询问，C对这些询问的应答方式与可验证性证明相同。

SendQ uery：A根据标签，生成针对若干数据分组mi(1≤i≤n)的挑战信息Chal=(gz,C )并发送给C。C收到挑战信息后，运行GenProof(pkH,skS,Tagmi,mi,Chal )算法。这里需要注意的是，由于C不知道云服务器公钥gy中的y，因此，无法直接计算出K=(ga)y以及H( K||ga||gy)，但是C可以查看随机预言机 H。若在散列列表中，则意味着已经有实体对散列函数进行了H( K||ga||gy)询问，那么C可以得到h=H( K|| ga||gy)。若不在散列列表中，则C选取一个随机数h作为该散列询问的返回值，同时，将该消息对存储在散列列表中。所以，虽然C不知道 y，但可以利用随机预言机为A正确的模拟本文方案。当C得到h=H( K||ga||gy)后，解密C得到数据分组mi的特征值。若所有数据分组mi(1≤i≤n)都存在，C选择一个随机数b∈Z*并计算p以及。虽然C不知道y，但知道r、a 、b 、s、gy以及所有的a和m，所以仍然可Hii以计算出M，生成多个数据分组mi(1≤i≤n)的凭证V1，并将发送给用户U。若有一个分组mi不存在，则C随机生成(T1, T2, V1)作为挑战相应返回给A。

Challenge：C随机生成一个数据分组mi，生成相应的标签Tag=(H( w) gmi)d、特征值w、随miimi机数值ai，将发送给A。

Judge：A要判断云服务器S是否持有某数据分组mi。A首先冒充用户者U向C发起挑战。A选择gz，并计算以及的值，然后将挑战信息Chal=(gz,C)发送给C。C收到该消息后，执行SendQ uery的方式生成(T1, T2, V1)并返回给A。A根据(T1, T2, V1)判断数据分组mi是否存储在云服务器S中。若A输出的结果与用户 U运行算法CheckProof(pkH,pkS,cert,wmi,Chal,V )得到的结果相同，则说明A成功计算出了V1，即获得了。那么C可以查看散列列表找到对应的散列询问，从而得到。在QR上CDH假设N下，A不可能正确地计算出V1。因为将 M变形后可得。A知道ai、z和mi，则可以计算出。但是A却无法计算出中的。若A能计算出，由于C知道 r、s、a和m，根据Hii，C可以得到gxy，计算出了CDH( gx,gy)，即破解了QR上 CDH问题。由N于QRN上CDH假设在多项式时间内是成立的，所以定理2得证。

定理 3若 CDH假设在QRN中成立，A-PDP方案在随机预言模型下可以提供认证密钥协商安全性。

证明根据2.2节中给出的认证密钥协商安全性攻击模型，只需证明内部攻击者A不能获得其他授权用户与云服务器之间的会话密钥即可，证明过程与授权验证性证明类似，这里只给出简要的分析。授权验证性的攻击者是没有合法授权的外部攻击者，而认证密钥协商安全性的攻击者可以拥有除了目标用户U以外所有授权用户的授权信息，但他仍然不能获得U和云服务器S之间的会话密钥。根据会话密钥公式A可以获得IDU、IDS以及klen，但不能获得M。参考授权验证性的证明过程，若A能正确获取M，则C可以利用攻击者破解QRN上CDH问题。所以，A拥有certU'不能对获得目标用户U的会话密钥产生任何优势。定理3得证。

6 性能分析

6.1 理论分析

本方案在同一个会话中既实现了数据持有性证明又实现了用户身份认证与密钥协商。为进行效率比较，除Hahn等方案[17]外，分别挑选2组经典、高效的AKA方案和PDP方案。其中，AKA方案选择Cremers和Feltz提出的SIG (NAXOS)方案[18]和Krawczyk提出的HMQV方案[19]，而PDP方案选择Ateniese等提出的 S-PDP方案[3]和 Wang提出的PPDP方案[10]。对各方案的运算量、存储消耗以及通信消耗等方面进行了分析，分析结果如表1所示。表 1中，P表示预处理，U表示用户或验证者，S表示服务器端。表1内容中，n表示数据分组的数量，p表示一次双线性对运算，e表示一次指数运算，h表示散列运算，E表示对称加解密运算，sig表示签名运算，ver表示签名验证运算，f表示伪随机函数运算。

表1方案性能对比

运算量方面。Hahn等方案[17]利用数据持有证明完成认证，不支持密钥协商。若不考虑本文方案，同时完成数据持有性证明和认证密钥协商需要PDP方案和 AKA协议组合。本文以效率较高的HMQV方案和S-PDP方案组合为例。该组合方案的运算量将是HMQV方案和S-PDP方案运算量的叠加。组合方案的用户端运算量为 2e+2h+(n+3)e+(n+1)h+(2n+3)f=(n+5)e+(n+3)h+(2n+3)f，Hahn 等方案[17]用户端运算量为(n+1)e+ (3n+2)h+(n+2)f，而本文方案的用户端运算量仅为 5e+1E+(n+1)f+3h。本文方案用户端中运算较大的指数运算e的数量不随数据分组数量n变化。这意味着验证的数据分组数量越大，本文方案用户端的性能优势越明显。其原因在于，本文方案的标签生成算法和方案设计降低了用户验证云服务器数据持有凭证的运算量，而认证过程复用了数据持有性证明运算的中间结果，使方案在无需额外运算量和交互步骤的情况下，实现了功能目标。

存储消耗方面。本文方案与组合方案相比，用户端和服务器端的存储消耗相同。本文方案中，用户端仅存储授权信息，而服务器端存储数据分组及标签。需要说明的是，本文方案中数据拥有者对所有标签进行了签名，使其他实体或攻击者无法伪造标签，用户不需要获得每个数据分组的标签，仅需验证标签聚合结果是否正确。而Hahn等方案[17]中，用户需要存储完整的Merkle树，不适合数据分组数量较大的情况。

通信消耗方面。本文方案效率不如其他方案，原因是用户需要传输为每个数据分组选取的随机数和用于查找数据分组的特征值，而其他对比PDP方案均指定了数据分组集合，没有数据分组查找过程，不符合实际应用情况。若本文方案利用伪随机函数选择待验证的数据分组并生成所需的随机数，通信损耗可以降至O(1)，但用户必须存储所有数据标签，以防止云服务器利用无关数据生成持有证明。本文方案以通信损耗换取存储空间和计算性能，并减少了系统参数中的伪随机函数，降低了系统复杂度，使本文方案具有较强的用户端设备适应性，适应运算能力和存储能力相对较弱的移动设备或云终端。

交互次数方面。本文方案用户和服务器之间的有3次交互，而2个经典AKA方案仅需2次交互。但这2个AKA方案中均未提供会话密钥确认功能，也就是说不能确定对方是否能正确的计算出会话密钥。通常情况下，若实现会话密钥确认，AKA方案至少需要额外增加2次交互，一次交互用于用户确认服务器的会话密钥，另一次交互用于服务器确认用户的会话密钥。所以，若组合方案增加会话密钥确认功能，则共需6次交互，而本文方案需要3次交互，次数减少一半，其原因是方案利用数据持有性证明的确认步骤既作为对云服务器的认证，又作为会话密钥的确认，这是普通AKA方案无法实现的。Hahn等方案[17]交互次数与本文方案相同，但该方案不支持密钥协商且认证的发起者是云服务器。在云环境中，用户在线情况变化较快，不应由云服务器发起认证请求，至少应先由用户发送含身份信息的消息给云服务器。所以，Hahn等方案[17]合理的交互数应为4次。

6.2 实验仿真

下面先对实验环境和实验过程中选择的算法及参数进行说明，然后给出实验结果。

基于 MIRACL库[20]实现了本文方案和组合方案，并通过测试程序得到了2种方案在不同数据分组数量情况下方案各步骤的运行时间。实验环境由宿主机和测试平台2个部分组成，二者通过网络连接。宿主机是一台普通 PC，用于交叉编译方案程序和测试程序，运行64位Linux系统，发行版本为Ubuntu 12.04.5。测试平台是一块嵌入式开发板，用于运行方案程序和测试程序。测试平台的主处理器为飞思卡尔公司的i.mx6系列四核Cortex-A9 ARM处理器，主频为1.2 GHz，拥有512 MB DDR2内存，运行32位Linux 3.1系统，测试平台的运算性能如表2所示。

表2测试平台运算性能

本文方案和组合方案选用相同的算法和安全参数，具体如下。安全参数k为1024 bit，选用1024位RSA算法，选用1024位DH算法（160位幂），选用SHA1作为摘要算法，选用AES作为对称加解密算法，选用MIRACL库自带的随机数生成算法。RSA算法的安全大素数p和q均为512 bit，N为1024 bit，d为1024 bit，e为常数65537。模N二次剩余群QRN的生成元g为1024 bit。

本文方案的性能实验结果如图3所示。其中，预处理是指数据有拥有者生成数据分组的标签。从图3可以看出，随着数据分组数量的增加，用户端运算时间的变化很小，服务器端运算时间有所增加，而预处理运算时间显著增加。实验环境中，当分组数量为10万时，用户端完成全部运算的时间为4023 ms。图4给出了本文方案和组合方案用户端的运算时间对比。得到图4实验结果的原因是RSA运算和DH运算中的指数运算的时间消耗较大，相应步骤处理一个数据分组需要的指数运算越多则运算时间变化越明显。而根据表2统计的运算量，本文方案用户端所需的指运算数量固定不变，而预处理和服务器端所需的RSA和DH运算量均与数据分组数量成比例。

图3A-PDP方案性能

根据实验结果推算，测试平台的预处理性能仅为 76.6 kbit/s，处理普通大小的文件也需要较长时间。但预处理过程是数据拥有者独立执行的，与云服务器和用户无关。在方案实际部署时，数据拥有者可以把预处理交给高性能的可信第三方完成。因此，预处理性能对方案部署不会产生较大影响。另外，云服务器的运算性能通常也远高于嵌入式测试平台，方案部署时服务器端运算消耗的时间会大幅减少。影响方案整体性能的关键是用户端的运算量，而本文方案有效降低了用户端运算量，且在数据分组数量增加时，用户端运算量增加较小。

图4用户端运算时间对比

7 结束语

云应用中，通过一次会话同时实现认证密钥协商和数据持有性证明的密码方案具有研究意义和实用价值。本文提出了一种支持身份认证的数据持有性证明方案，给出了方案定义和具体构造，并在随机预言机模型中证明了方案的安全性。根据性能分析结果，本文方案用户端运算量低、交互步骤少，满足云应用对方案功能、性能和安全性等方面的多重需求。下一步将研究密文搜索与数据持有性证明方案融合的可行性。

[1]BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009,25(6):599 -616.

[2]WU J, SHEN Q, WANG T, et al. Recent advances in cloud security[J].Journal of Computers, 2014, 5(10):2156-2163.

[3]ATENIESE G, BURNS R, CURTMOLA R, et al. Provable data possession at untrusted stores[C]//Proceedings of the 14th ACM Conference on Computer and Communications Security. ACM, 2007: 598-609.

[4]BOWERS K D, JUELS A, OPREA A. Proofs of retrievability: theory and implementation[C]// ACM Cloud Computing Security Workshop,CCSW 2009. Chicago, Il, USA, 2009:43-54.

[5]CHOUDHURY A J, KUMAR P, SAIN M, et al. A strong user authentication framework for cloud computing[C]// IEEE Asia-Pacific Services Computing Conference. Jeju, Korea, 2011: 110-115.

[6]LIU C, CHEN J, YANG L T, et al. Authorized public auditing of dynamic big data storage on cloud with efficient verifiable fine-grained updates[J]. IEEE Transactions on Parallel amp; Distributed Systems,2014, 25(9):2234-2244.

[7]GRITTI C, SUSILO W, PLANTARD T. Efficient dynamic provable data possession with public verifiability and data privacy[M]// Information Security and Privacy. Springer International Publishing,2015:395-412.

[8]WANG B, LI B, LI H. Panda: public auditing for shared data with efficient user revocation in the cloud[J]. IEEE Transactions on Services Computing, 2015 (1): 92-106.

[9]SHEN S T, ZENG W G. Delegable provable data possession for remote data in the clouds[M]// Information and Communications Security. Springer Berlin Heidelberg, 2011:93-111.

[10]WANG H. Proxy provable data possession in public clouds[J]. IEEE Transactions on Services Computing, 2013, 6(4):551-559.

[11]RUAN H M, LEI C L. Fine-grained audit privilege control for integrity audit on cloud storage[C]// 2014 Ninth Asia Joint Conference on Information Security (ASIA JCIS). IEEE, 2014: 156-163.

[12]XU J, CHEN W, JI S, et al. A novel preserving client privacy and designate verifier auditing scheme for cloud storage[J]. International Journal of Security and Its Applications, 2015, 9(1): 295-304.

[13]NIMMY K, SETHUMADHAVAN M. Novel mutual authentication protocol for cloud computing using secret sharing and steganography[C]//Applications of Digital Information and Web Technologies.IEEE, 2014:101-106.

[14]HAO Z, ZHONG S, YU N, et al. A time-bound ticket-based mutual authentication scheme for cloud computing[J]. International Journal of Computers Communications amp; Control, 2011, VI(2):227-235.

[15]HUANG J J, JUANG W S, FAN C I, et al. Robust and privacy protection authentication in cloud computing[J]. International Journal of Innovative Computing, Information and Control, 2013, 9(11): 4247-4261.

[16]NAGARAJU S, PARTHIBAN L. SecAuthn: provably secure multifactor authentication for the cloud computing systems[J]. Indian Journal of Science and Technology, 2016, 9(9).

[17]HAHN C, KWON H, KIM D, et al. Enhanced authentication for outsourced educational contents through provable block possession[J].Multimedia Tools amp; Applications, 2015,23:1-20.

[18]CREMERS C, FELTZ M. Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal[J]. Designs, Codes and Cryptography, 2015, 74(1): 183-218.

[19]KRAWCZYK H. HMQV: a high-performance secure Diffie-Hellman protocol[C]//Advances in Cryptology–CRYPTO 2005. Springer Berlin Heidelberg, 2005: 546-566.

[20]SCOTT M. MIRACL - multiprecision integer and rational arithmetic C/C++ library (1988-2007)[EB/OL]. http://www3.cs.stonybrook.edu/～algorith/implement/shamus/distrib/ miracl3.zip.

Provable data possession scheme with authentication

LI Hao-xing1, LI Feng-hua1,2, SONG Cheng-gen3, YAN Ya-long3
(1. State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China;2. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;3. Information Security Institute, Beijing Electronic Science and Technology Institute, Beijing 100070, China)

To satisfy the requirements of identity authentication and data possession proven in the cloud application scenarios, a provable data possession scheme with authentication was proposed. Based on data tag signature and randomness reusing, the proposed scheme could accomplish several issues with three interactions, including the possession proof of cloud data, the mutual authentication between user and cloud computing server, the session key agreement and confirmation. Compared to the simple combination of authentication key agreement and provable data possession schemes, the proposed scheme has less computation and interactions, and better provable securities. In the random oracle model, the security proof of the proposed scheme is given under the computational Diffie-Hellman assumption.

authentication, data possession, cloud computing, provable security, random oracle

s:The National Natural Science Foundation of China General Project(No.61170251), The National High Technology Research and Development Program of China (863 Program)( No.2015AA016007),The National Natural Science Foundation of China-Guangdong Provincial People’s Government of the Joint Natural Science Fund Projects (No.U1401251)

TP393

10.11959/j.issn.1000-436x.2016203

2016-06-20；

2016-08-03

李凤华，lfh@iie.ac.cn

国家自然科学面上基金资助项目（No.61170251）；国家高技术研究发展计划（“863”计划）基金资助项目（No.2015AA016007）；国家自然科学基金—广东联合基金资助项目（No.U1401251）