1.数据持有性证明概述

在云存储环境中，当数据由线下静态存储转向外包动态存储时，用户就失去了对其数据的直接控制。数据持有性证明的目的在于保障用户存储在云上的数据的完整性与安全性。传统数据完整性的检测方法，如MAC码和数字签名并不适合于云计算环境，这是因为用户不再物理上拥有数据，若将数据全部取回验证则不实际，因为海量的数据取回会消耗大量的通信带宽和本地的存储容量。现阶段研究主要集中在两个方面：一是数据持有性证明（Provable Data Possession，PDP），关注数据的完整性验证；二是数据可恢复性证明（Proof of Retrievability，POR），关注数据破坏后如何恢复出原始数据。实际上，数据可恢复性证明就是在数据持有性证明的基础上增加了纠错编码技术，从而实现数据恢复。

与传统的存储系统相比，云存储具有以下特性。

（1）云服务器无法完全被信任。数据的可控性是传统存储系统和云存储系统的主要区别之一，云存储系统中存储的数据是由云服务商控制管理的，而传统的存储系统则是由用户亲自管理的，这就造成了用户与服务提供者之间的信任危机，服务器无法完全被信任。云存储用户的数据除了面临云端硬件故障、自然灾害等不可控因素的影响以外，还会面临系统漏洞、恶意软件、管理失误和恶意内部攻击等。一些云服务商可能为了获取更多的利益，随意删除或篡改用户的数据，并欺骗用户说他们的数据仍然“安全”。这种情况下，传统的纠错码、访问控制技术等就无法很好地胜任用户数据完整性保护的职责。

（2）服务方式以合约为基础。在云存储活动中，云服务提供商与用户之间是事先约定的合约关系，为了保证服务双方都能够诚实守信地履行合约，单纯地靠道德约束或规章是远远不够的，因此需要一种介于双方之间的可信机制来保障。与传统存储不同的是，在云存储系统中，从用户的角度来说，其所顾虑的是自己所存储的数据文件遭到损坏以及被破坏以后如何向服务商索要赔偿；从云服务提供商的角度来看，其关注的是事故产生以后如何进行责任判定的问题。

（3）受限的客户端资源及带宽。常见的客户端设备主要有个人计算机、笔记本式计算机、平板电脑、智能手机等。通常来说，客户端设备的存储能力及计算能力是十分有限的，其与云服务器之间的带宽资源也是受限的，因而对于在云服务器上存储的数据在保证其完整性的同时，还需要考虑客户端的计算开销、存储开销以及与服务器之间的数据传输带宽开销。

数据持有性证明技术能够解决用户数据完整性验证的问题，云服务提供商向用户提供数据持有性的证据来证明用户数据被完好地保存。

数据持有性证明主要的要求如下。

（1）稳固性：保证数据存储验证方案能够准确地发现数据丢失、篡改以及云存储提供商不能以任何方式隐瞒、欺骗验证结果。

（2）机密性：保证验证者无法通过验证协议获得所验证数据、验证标签等信息。

（3）动态审计性：支持动态增加、删除、修改云存储中数据且能对其进行验证，并对动态操作简单审计，在发生存储争议时可作为有效证据。

（4）高效性：验证过程中所需的存储、计算、通信代价最小化。

云服务提供商通过向用户提供数据的多副本存储服务，进一步提高用户数据的可用性与可靠性，其通常的做法是将用户数据存储于不同地理位置的多个副本服务器中，以此增加数据的容错性和可恢复性。因此，一方面，数据拥有者通过对存储在服务器上的数据进行完整性验证，确保自己得到所支付费用的相应的存储服务；另一方面，用户在对数据进行完整性验证的过程中需要涉及每个副本服务器的验证过程，来确保每个副本都被完整地保存在副本服务器上，以便在某个节点的数据出现损坏时，通过其他副本对其进行恢复。

2.Ateniese等人的PDP方案

利用标签的同态特性进行数据持有性验证最初是由Ateniese等人提出的，在此之后的很多方案都是以此为基础，对其进行或多或少地改进。在标签计算的过程中利用标签的同态特性，将挑战验证过程中的多个标签值合成一个模幂值，降低网络带宽，同时能够较好地支持公开验证。下面将简要介绍Ateniese的经典PDP模型，其核心工作主要分为以下两个阶段。

初始化阶段：用户也就是文件F的所有者首先对要存储的文件进行分块，再对每个数据块计算标签：运行算法Key Gen（1k）→（pk，sk），产生整个数据持有性证明过程的公私钥。运行标签生成算法TagBlock（pk，sk，mi）→Tmi，1≤i≤n，为所有的数据块计算其相对应的标签值Tmi。接着，用户把文件F、公钥pk和标签集Σ=（Tm1，…，Tmi）外包存储在云服务器上。最后，用户将文件F和相对应的标签集Σ从本地刪除，自己只需保存密钥对（pk，sk）即可。

挑战阶段：进行数据持有性验证时，挑战的数据块的个数和位置都是可以任意选择的，被挑战的数据块以及其对应的标签集合由服务器来计算，将其作为持有性证据返回给客户端，再由客户端验证其正确性，即客户端随机生成一个包含被挑战数据块的数目及位置的挑战值chal，并将其提交给云服务器，对其发起挑战，服务器收到来自客户端的挑战后，运行证据生成算法GenProof（pk，F，chal，Σ）→V，再将计算得到的结果也就是持有性证明值V发送给客户端。最后，用户执行证据验证算法Check Proof（sk，pk，chal，V）来验证V是否正确。

当然，用户在将其文件或数据外包到云服务器之前可以对其进行加密，也就是说，用户的文件可以是以密文形式存储的。

PDP中主要用到的核心技术包括同态标签的计算和抽样验证方法。其中，代数的同态特性是指两个结构（例如环、群、域或向量空间）之间保持某种关系不变的映射，也就是存在这样的函数θ：X→Y，满足θ（x·y）=θ（x）◦θ（y）。其中，·是在X上的运算，◦是在Y上的运算。而对于每个数据块m来说，其同态标签则是指存在这样的Tm：它由数据块m计算得到，且可以根据其所具备的同态特性将多个标签值计算组成一个简单值。假定所给的两个数据块分别为mi和mj，其所相对应的标签值为Tmi和Tmj，那么由标签的同态性得出mi+mj所对应的标签值为Tmi·Tmi。因此，用户在外包数据前只需事先对每个数据块计算其同态标签值，验证数据持有性时，用户可以一次性随机地挑战多个数据块，服务器就可以根据用户所挑战的数据块位置及序号，找出相应的数据块并将多个数据块的标签值合成一个简单值返回给客户端，从而达到节约带宽的目的。而抽样验证的目的在于客户端在无须验证所有数据块的前提下，仍然保持很高的数据持有性检测概率，同时也减少了服务器与客户端的计算量。图10.6与图10.7分别为PDP的两个主要的阶段，工作流程如下。

图10.6　数据分块、标签计算和存储

图10.7　验证数据持有性

（1）初始化阶段客户端调用：Key Gen（1k）→{sk，pk}

输入：1k

计算：公钥pk=（N，g），私钥sk=（e，d，v），其中N=pq，p和q是两个大素数，g是Ζn的一个生成元。p=2p′+1，q=2q′+1，ed≡1 mod p′q′。

输出：公私钥对{pk，sk}。

（2）标签生成阶段客户端调用：TagBlock（pk，sk，i，mi）→Ti，mi

输入：公钥pk=（N，g），私钥sk=（d，v），数据块mi。

计算：wi=v‖i，Ti，mi=（h（wi）·gmi）d mod N，其中h（·）为哈希函数。

输出：Ti，mi。

（3）证据生成阶段服务器调用：GenProof（pk，F，chal，Σ）→V

输入：公钥pk=（N，g），文件F={m1，m2，…，mn}，标签集Σ=（T1，m1，…，Tn，mn），挑战值chal=（c，k1，k2，gs），其中c是要挑战的文件块数，k1、k2是随机选择的两个密钥，gs=gs，s是一个伪随机数。

输出：ν=（T，ρ）。(www.daowen.com)

（4）证据验证阶段客户端调用：Check Proof（pk，sk，chal，V）→（Success，Failure）

输入：公钥pk=（N，g），私钥sk=（d，v），chal=（c，k1，k2，gs），（T，ρ）=ν

计算：τ=Te，对于任意的1≤j≤c，

（最后，得到τ=ga1mi1+…+acmic mod N）

输出：若H（τs mod N）=ρ，输出Success，否则输出Failure。

Ateniese方案的安全性是基于大整数因子分解难题的。只要被验证方（云服务器）能够通过计算提供正确的数据持有性证明，就可以证明被挑战的数据块均完整地保存在服务器端，也即PDP方案的安全性得以保证。

PDP方案的开销方面，假设用户外包文件为4 GB，包含1 000 000个4 KB的数据块，则其计算得到的每个标签大小为128 B。对用户来说，只需要存储很少量的密钥信息，大约3 KB，占用的空间非常小；对于CSP来说，除了存储用户的文件以外，只需要额外存储文件对应的标签集即可，总的文件膨胀率小于3.2%，因此PDP方案存储开销是很小的。挑战验证阶段在客户端与服务器之间也只需要很小、常量级别的通信开销（每次挑战与应答只需要少于1 KB）。在计算开销方面，预处理阶段客户端为每个数据块计算同态标签的复杂度为O（n），此模幂运算的计算量较大。在持有性验证的过程中，客户端随机生成一个挑战值，服务器端接收到挑战后，生成相应的证据，再由客户端验证。计算包括模乘运算、模加运算以及哈希运算，总的计算开销都不大。

Ateniese等人PDP方案的实验表明，硬盘I/O操作的时间占了数据持有性验证时间的大部分，也就是说PDP的预处理部分有一定的计算开销，而数据持有性验证部分的计算量则很小。其存储开销、计算开销与通信开销都是比较理想的，但此方案不支持数据的动态操作，如数据文件的增、删、改等。

为了验证用户在云端数据的完整性，用户也可以通过独立的第三方审计者进行验证。主要步骤如下。

（1）用户对其要上传到云端的数据文件进行预处理。用户使用自己的私钥对数据块进行运算，得到这些数据块的认证标签，并将所有数据块及其对应的认证标签上传到云端。

（2）为了验证用户在云端数据的完整性，用户向第三方审计者（Third-Party Auditor，TPA）发出审计请求。TPA随机生成一些质询消息，将这些质询消息发送给云端。质询消息中包括审计者选取了哪些消息块进行审计的信息。

（3）当云端收到审计者的质询消息后，根据质询消息和所存储的消息块生成用来证明数据块正确存储的证据，并将其发送给审计者。

（4）当审计者收到云端的证据后，验证云端是否正确存储了用户数据，审计者将审计结果通知用户。

3.多副本持有性证明

多副本下的云存储模型中，用户把数据外包给CSP进行存储，CSP向用户承诺可以对这些数据文件进行多副本存储，即将原始数据文件复制s份，交给s台不同的服务器同时进行存储，提高数据存储的容灾能力和可恢复能力，从而增加数据的可用性与可靠性。

Curtmola等人在2008年提出了一个多副本持有性证明MR-PDP，此方案主要由3个阶段构成，即初始化阶段、副本处理阶段和挑战阶段，包括5个算法，即Key Gen、ReplicaGen、TagBlock、GenProof、Check Proof。KeyGen是密钥生成算法，由客户端在初始化阶段运行，ReplicaGen算法用于在客户端生成文件副本，TagBlock用于在客户端为文件块生成验证标签，GenProof由服务器端运行用于证据生成，CheckProof由客户端运行用于证明数据持有性。

初始化阶段：客户端运行KeyGen来初始化此方案，使用ReplicaGen为文件F生成t个副本，再调用TagBlock为副本文件生成验证标签。客户端将副本文件和标签存储到服务器端，自身保留很少量的信息用于接下来的证据挑战。最后，客户端将原文件、副本文件以及标签都从本地删除。

副本处理阶段：这个阶段允许客户端执行副本的维护，客户端可以调用ReplicaGen动态地创建新的副本。

挑战阶段：客户端可以进行对单个文件副本的挑战或者全体副本的挑战。对于单一副本来说，客户端选择要挑战的服务器Su，然后验证Su在挑战的过程中是否正确地持有其相应的副本Fu，对全体副本的挑战包含了t个单一副本的挑战，是可以并行执行的：对于1≤u≤t来说，客户端挑战服务器Su来证明副本Fu的持有性，且对于挑战次数是没有限制的。

多副本持有性证明MR-PDP的主要步骤如下。

(1)KeyGen

客户端计算：公钥pk=（N，g），私钥sk=（e，d，v，z，K），其中N=pq，p和q是两个大素数，g是Ζn的一个生成元。p=2p′+1，q=2q′+1，ed≡1 mod p′q′，v、z、K为k bit的随机数。

(2)ReplicaGen

首先用密钥K对文件F={f1，f2，…，fn}加密得到的文件F′={b1，b2，…，bn}，其中bi=EK（fi），1≤i≤n，表示密文数据块。

生成每个服务器上的副本文件：存储在Su上的副本可以表示为Fu=（mu，1，mu，2，…，mu，n），1≤u≤t，每个数据块按如下计算得到：mu，i=bi+ru，i，1≤i≤n，其中ru，i是一个随机大整数，ru，i=Ψz（u‖i），Ψ（·）是一个伪随机函数，这样每个副本服务器上的每个子数据块都能拥有独立的随机数。

(3)TagBlock

客户端为每个加密后的数据块生成标签集Σ={T1，T2，…Tn}，其中Ti=（hi·gbi）d mod N，1≤i≤n，hi=h（v‖i），h（·）是一个哈希函数。

可以看到，标签Ti是数据块bi的一个函数，这样就能够使服务器Su从副本Fu中证明其持有相应数据块mu，i，同时每个标签Ti都与一个序号i绑定，这样就能够避免服务器用其他的标签来证明客户端挑战标签的持有性（实施替换攻击）。最后，客户端将所有的副本Fu以及标签集合Σ={T1，T2，…，Tn}发送给相应的副本服务器Su，并从本地删除源文件、副本和标签集，每个副本服务器所存的标签集相同。

(4)GenProof

为了验证副本Fu=（mu，1，mu，2，…，mu，n）的持有性，客户端要求服务器Su证明Fu中随机个数据块子集，chal包括c（挑战的块数）、k（伪随机置换函数π（·）的密钥）和gs=gs mod N，s∈Ζ*n。

(5)CheckProof