基于覆写验证的云数据确定性删除方案

杜瑞忠，石朋亮，何欣枫

（1. 河北大学网络空间安全与计算机学院，河北 保定 071002；2. 河北省高可信信息系统重点实验室，河北 保定 071002）

1 引言

作为新的服务模式，云计算[1]能够将数据存储和数据共享进行高效的结合，以便为用户提供更优质的服务。随着云计算技术的发展，越来越多的个人或者企业把数据上传到云端，一方面能节省本地硬件存储开销，另一方面可以随时随地享受云计算提供的服务。但 2018年泰累兹数据威胁报告[2]指出，2017年36%的受访者表示遭遇过数据泄露，并预测这一比例还将上升，数据泄露已成为影响云计算发展和应用的重要问题之一。其中数据的不安全性删除[3]是导致数据泄露的一个重要原因。

目前，用户大多是将数据加密后存储到云端，在数据删除命令发出后，通过删除加密密钥来保证数据的不可解密和恢复，以达到数据删除的目的。这样的删除机制存在很大的弊端，因为其只对数据进行逻辑删除，待删除的数据仍然存储在云端，一旦有非法分子获得云端的数据，就可能对所得数据进行暴力破解，从而导致敏感信息泄露。如果存在部分云服务提供商为了自身的利益，只对数据进行逻辑删除，那么用户在多租户模式下就面临着数据泄露危机。另外，云存储的模式和以往的存储模式有很大的区别。在云存储模式下，一方面数据拥有者将数据上传到云端存储，致使数据控制权被移交至云端。另一方面，现存的数据逻辑删除方式，一旦加密密钥被恢复，数据泄露几率增大。针对以上情况，在数据生命周期结束需要删除时，如何保证数据的确定性删除，使数据在云端永久性删除或者密钥删除后无法再次解密及恢复是现阶段云存储研究的一个重点和难点问题。

2 相关工作

目前，研究者对云端数据确定性删除已经做了很多有益的尝试。熊金波等[4]从密码学的角度对已有的确定性删除方法进行综合性分析对比，给出了目前存在的三大类确定性删除机制的优缺点。文献[5]利用（S,T）门限密钥共享方法将加密密钥分成n份，发送到网络节点上的分布式散列表（DHT，distributed hash table）进行存储，但是DHT社交网络容易遭受非法分子的跳跃攻击。为解决此问题，文献[6]将加密密钥的长度进行扩展后再使用密钥共享方案发送到DHT网络上，虽然能抵御跳跃攻击但是加重了密钥存储开销。为减少密钥存储开销，李超零等[7]采用两级加密方式，其中控制密钥由密钥生成树生成，基于树结构减少密钥的存储，之后通过秘密共享方法发到DHT网络中。文献[8]提出一种基于混沌序列比特流变化的云多媒体文件确定性删除方案，数据加密上传前进行数据比特流变换，数据删除时仅仅删除对应数据的比特流，达到安全删除的目的，减少了对加密密钥和可信第三方的依赖，但是只适用于视频和图片类的多媒体文件。薛亮等[9]提出一种基于属性加密和属性撤销的数据删除方案，通过撤销属性实现数据的访问控制，从而达到数据删除的目的。但是以上方案仅仅是对数据加密密钥进行安全性处理，原数据依然在云端，存在非法用户获得数据后暴力破解的可能，为此张坤等[10]将加密密文进行分片抽样，把抽样后的剩余密文上传到云端，抽样密文交由可信第三方保管，使存在云端的数据不完整，来抵制暴力攻击。但是如果使用密文抽样技术使云端存储的密文不完整，会给云端的数据更新和密文检索带来不便。而针对多样性用户，如何实现文件数据的细粒度控制操作也成为数据确定性删除要考虑的一个关键问题。文献[11]提出一种基于策略的删除机制，使得密文对应一条或者几条策略，用策略加密密文，用户只有满足访问策略才能访问密文，删除时撤销策略。基于这种思想，熊金波等[12]提出一种基于身份加密的安全自销毁方案，根据用户身份不同提供数据的细粒度访问，可是容易暴露用户身份信息。文献[13]提出基于属性加密的数据文件删除机制，用属性加密文件，用户只有满足访问控制属性才能访问文件，减少了用户身份信息的暴露。禹勇等[14]提出一种在互联网和雾计算框架下，基于细粒度访问控制的确定性删除方案，通过改变数据的访问控制，来达到数据删除的目的，但不适应云端大数据存储。以上文献都未对云端数据删除后进行验证。综合分析现有文献，发现存在以下挑战。

1） 云存储环境下无法对数据文件进行有效的细粒度操作，致使数据泄露。

2） 没有实现即时删除，基于DHT社交网络的删除机制，只能依赖网络的更新周期，不能适用云存储环境下的即时删除要求。

3） 删除云存储中的数据时，大多数是采用删除密钥这样的逻辑删除方式，致使密钥删除后文件依旧存在泄露的可能。

4） 没有对云数据删除操作进行验证。

针对以上情况，提出一种基于密文重加密和数据覆写验证结合的云数据确定性删除方案（WV-CPABE，overwrite and verify ciphertext-policy attributed based encryption），可以有效实现数据访问以及删除细粒度控制和数据删除验证。本方案的主要工作如下。

1） 采用基于密文策略属性基加密机制（CPABE，ciphertext-policy attribute-based encryption）加密数据，当数据拥有者想删除外包数据时，通过重新加密密文改变密文对应的属性访问控制策略来实现数据细粒度操作和确定性删除。

2） 设计了一种基于脏数据覆写的可搜索路径散列二叉树（DSMHT，dirty data and search merkle hash tree），对云存储的数据覆写后进行验证。根据辅助的可信删除证据，判断是否对数据文件真正进行了覆写操作。

3） 对提出的云数据确定性删除方案进行了详细的敌手模拟安全性证明，表明本方案可以满足要求的数据细粒度操作和确定性删除目标。

3 预备知识

3.1 属性基加密

属性基加密[15]（ABE，attribute-based encryption）是由Sahai和Watens在2005年的欧密会上提出的模糊身份加密。目前常用的2种方案是：基于密钥策略属性基加密（KP-ABE，key-policy attributebased encryption）和基于密文策略属性基加密（CP-ABE，ciphertext-policy attribute-based encryption）。这 2种加密机制都用到属性访问控制策略（AC，access control）。

假设初始化的系统属性个数为n，则得系统属性集合为 Ω={att1,att2,… ,attn}，Ai={vi,1,vi,2,…,vi,ni},其中ni=|Ai|，Ai表示第i个属性atti的取值。用户属性集合 Au= {Au1,Au2,⋅⋅⋅,A um},其中m∈ [1,n]。Aui表示用户属性集合 Au中属性的取值。AC =[AC1,AC2,…，A Ck]，k∈ [1,n]，为定义的一个密文的访问控制策略。访问控制策略是借助树结构，采用与门、或门和门限控制方法对属性进行管理。数据拥有者首先将访问控制策略AC转换为一棵访问控制树，其中非叶子节点表示属性控制判断条件，叶子节点表示属性值。图1所示的是访问控制策略AC=[hebie, cs, man, pro, is]转化为树形式的一种表达。

3.2 双线性映射

设p是素数，GT是阶为p的乘法循环群，Gv是阶为p的乘法循环群，通常称映射e:GT×GT→GV为一个双线性对，e满足以下的3个性质。

1） 双线性：对于任意δ,ξ∈Zp和χ,γ∈GT，都有e（χδ,γξ）= e（χ,γ）δξ。

2） 非退化性：存在χ,γ∈GT，使e（χ,γ） ≠ 1Gv。

3） 可计算性：对任意的χ∈GT,γ∈Gv，存在有效的算法计算e（χ,γ）的值。

图1 访问控制策略AC

4 方案体设计

4.1 符号意义

符号及其含义如表1所示。

表1 符号及其含义

4.2 系统模型

本文提出的云数据确定性删除方案（WVCP-ABE）共包括四部分，分别是数据拥有者（DO，data owner）、可信授权机构（TA，trusted authority）、云服务提供商（CSP，cloud server provider）和用户（user）。整体结构如图2所示，具体各部分的功能如下。

图2 系统整体结构

数据拥有者（DO）：创建数据文件，上传云端前对数据文件进行加密处理。数据拥有者虽然上传了数据到云端，但是怀疑云服务提供商是否按照约定对数据进行处理，担心数据有泄露的危险。

可信授权机构（TA）：产生密钥中心，负责给用户分发私钥，根据用户属性分发不同的用户私钥，而只有满足数据文件访问控制策略的用户才能下载文件解密出明文。

云服务提供商（CSP）：自身拥有强大的计算能力和存储资源，对租户提供长时间的存储服务。但是本身是诚实且好奇的，在商业利益和自己名声的驱使下，会有泄露租户信息的不法行为。

用户（user）：数据文件的使用者，通过自身拥有的属性在可信授权机构获取私钥，然后在云端下载数据，如果满足数据的访问控制策略，就能成功解密文件。

4.3 系统结构流程

云数据确定性删除方案（WV-CP-ABE）总共包括以下几个步骤：系统初始化setup、用户私钥产生KeyGen、数据加密encrypt、数据解密dncrypt、删除信息生成DelRequest、删除密钥生成ReKeyGen、访问控制策略重加密 ReEncrypt和数据覆写验证Verify，流程如图3所示，具体如下。

步骤1系统初始化setup（1k）：TA执行初始化算法，依据相应的参数K，产生一对密钥，即公共密钥PK和主要密钥MSK。

步骤 2用户私钥产生 KeyGen（PK,MSK,Au）：TA对PK、MSK以及用户属性集合Au进行计算，生成用户私钥SKu；并给数据拥有者生成私钥ssk，该私钥用于密文签名。

步骤3数据加密encrypt（PK, AC,M）：数据拥有者将明文M、公钥PK和访问控制策略AC作为参数，生成密文C；并对密文访问控制策略进行签名。

图3 方案整体流程

步骤4数据解密decrypt（SKu,C）：用户首先需要通过数据文件的访问控制策略 AC，如果通过，则利用获得的私钥SKu将密文C解密出明文M。

步骤 5删除信息生成 DelRequest（AC）：数据拥有者输入要删除数据的访问控制策略 AC，输出删除信息 DR，分别发送给授权机构和云服务提供商，云服务商返回删除数据的签名，数据拥有者对其返回的签名进行验证。

步骤6删除密钥生成ReKeyGen（DR,MSK）：可信授权机构输入删除信息DR和系统主密钥MSK生成新加密密钥newk。

步骤7访问控制策略重加密ReEncrypt （newk，C）：云服务提供商输入newk、密文C输出重新加密的密文NC。

步骤 8数据覆写验证 verify（NC,H（R））：数据拥有者构建基于脏数据块覆写的可搜索路径散列二叉树对云数据进行覆写操作，并验证覆写结果的正确性。

4.4 安全模型

假设存在敌手A、挑战者和模拟器S，为本方案构建以下敌手攻击游戏，具体如下。

1） 敌手A尝试构建访问控制策略AC。

2） 挑战者运行setup初始化算法，输出PK给敌手。

3） 敌手为得到用户属性集合AU，向模拟器 S请求多个私钥。

4） 敌手A给挑战者发送2条等长的数据明文M0和M1，挑战者随机选择其中一条φ= {0,1}，挑战者选择访问控制策略加密AC加密数据，将加密明文Cφ发送给敌手。

5） 敌手多次尝试 3）。

6） 敌手根据得到的信息对φ进行猜测得到φ′，如果敌手A猜测的φ′=φ，则敌手在游戏中获胜；反之，敌手 A失败。在敌手攻击游戏中，敌手 A的优势为

5 方案详细设计

本节给出云数据确定性删除方案（WVCP-ABE）中数据加密解密阶段和数据删除阶段的具体流程设计方案。数据加密解密阶段包括系统初始化、用户私钥产生、数据加密和数据解密4个步骤。数据确定性删除阶段包括删除信息生成、删除密钥产生、访问控制策略重加密和数据覆写验证4个步骤。

5.1 加密解密阶段

1） 系统初始化 setup（1K）

这是在可信授权机构 TA运行的一个随机算法。首先可信授权机构TA选择2个阶为p的乘法循环群GT，GV，满足e:GT×GT→GV，其中g为GT的生成元，TA随机选择y∈Zp，计算

2） 用户私钥产生 KeyGen（PK,MSK,Au）

首先随机选择计算用户私钥的公共基r∈Zp，计算用户私钥基D0

对于每个属性aj，都有rj∈Zp，然后基于用户属性计算属性值Dj

最后产生的用户私钥为 SKu= （D0,Dj） 。同时可信授权机构TA为数据拥有者DO产生用于访问控制策略签名的公私钥对（spk，ssk），随机选择一个α∈ Zp，计算v，如式（5）所示。

3） 数据加密 encrypt（PK,AC,M）

数据拥有者输入明文M、公钥PK和数据访问控制策略AC，输出密文C。数据拥有者首先随机选择s∈Zp，计算密文C1、C2和C3如式（6）～式（8）所示。

最后得到的密文为C=（AC,C1,C2,C3）,然后数据拥有者用签名的私钥对访问控制策略进行签名，计算标签，如式（9）所示。

其中，fname是数据文件的唯一名字标识，最后上传{fname,C,σ}到云端。

4） 数据解密 encrypt（SKu，C）

解密过程如下。

其中，Au为用户的属性集合，对于每一个属性aj∈Au，都随机选择一个随机数Si∈Zp，且满足

其中，i为访问控制属性AC中属性的序号。

5.2 数据确定性删除阶段

1） 删除信息生成 DelRequest（AC）

当数据拥有者想删除外包的数据时，首先生成数据的删除信息 DR =（fname,AC），其中fname是要删除数据的唯一名字标识。然后将 DR分别发送给可信授权机构和云服务提供商。之后云服务提供商返回 {fname,σ}给数据拥有者，数据拥有者再认证

如果成立，则证明C3确实是要删除密文中的属性访问控制策略。

2） 删除密钥生成ReKeyGen（DR，MSK）

可信授权机构收到数据拥有者发送的删除信息DR，根据主密钥MSK，随机选择计算ck

然后将 newk =（fname,AC,ck） 返回给数据拥有者，数据拥有者收到newk后，立即将newk信息发送给云服务提供商。

3） 访问控制策略重加密ReEncrypt（newk,C）

云服务提供商接收到newk信息后，选择密文C，然后计算

然后替换原来密文的C3部分，组成新的密文

4） 覆写验证 verfiy（NC,H（R））

数据拥有者首先构造基于脏数据覆写的可搜索路径散列二叉树，根据要删除数据块的多少生成最小二叉树，从数字1开始，层次遍历二叉树给节点赋值。然后准备一个和外包数据一样大小的二进制随机脏数据块，从二叉树根节点到每个叶子节点都有一条最短路径，将路径经过的节点序号记录下来再转换为二进制，和脏数据文件数据逐位进行异或运算，得到的新的数据就是此叶子节点对应的要删除的数据块需要覆写的数据，然后叶子节点存储这个脏数据块的散列值，作为验证的根据。按照上述操作遍历完所有的叶子节点。按照新生成的数据对云端存储的数据进行数据覆写，写操作完成后让云服务提供商返回覆写完数据的散列值，和本地存储的进行验证，如果一致，说明覆写删除步骤完成。

数据覆写算法如下。

步骤1输入DeldatanumDirtyData

步骤 2DSMHT＜—GetTree（Deldatanum）

步骤 3Levelsearch（DSMHT）

步骤4foriton

步骤 5Road＜—search（i）

步骤 6Broad＜—Binary（Road）

步骤7forjtom:

步骤8DC＜—DirtyData^Broad

步骤 9H（R）＜—getHash（H（R）L||H（R）r）

步骤 10overwrite（DC）

步骤11end

下面以一个删除8个数据块的例子详细说明数据覆写的过程，生成的二叉树如图4所示。

要删除的数据a1，它到根节点的最短路径如图中的曲线所示，其中经过的节点序号为 8421，将8421转换为二进制得到10000011100101，然后与准备的脏数据进行异或运算得到新的数据文件，即是a1数据文件需要覆写的脏数据。然后依照此步骤完成其余7个数据文件的覆写操作，最后通过递归算法得出DSMHT根节点的散列值。等到云端要删除数据覆写结束后，让云端返回覆写完数据的散列值，再与本地的散列值进行判断，以此判定覆写删除过程是否正确完成。

6 安全性分析

针对4.3节定义的安全模型，本节模拟游戏来证明本文提出的解决方案是安全的。

图4 二叉树

判定的双线性 Diffie-Hellman问题（简称DBDH）：假设输入（P,aP,bP,cP,abcP）和（P,aP,bP,cP,μP），其中，a、b、c、μP均为随机的，如果（P,aP,bP,cP,abcP）和aP、bP、cP、μP在多项式时间内可区分出来，则输出true。

定理 1 如果敌手在安全模型下可以攻破本方案，则至少存在一个概率多项式时间算法内敌手以不可忽略的优势解决DBDH（Diffe-Hellmen）问题。

证明假设存在一个敌手A以优势ε在多项式时间内攻破本方案，下面证明如下的DBDH问题游戏可以以优势完成。

假设e:G0×G0→GV是一个双线性映射，首先DBDH问题挑战者设以下情况。

敌手模拟游戏的具体过程如下。

1） 敌手A尝试创建访问控制策略AC。

2）模 拟 器 S初始 化 公共参数Y=e（A,B）=e（g,g）ab，发送给敌手A。

3） 敌手A为了满足用户属性集合Au，向模拟器S请求多个私钥。模拟器S接收到信息后，对于每一个属性aj∈Au，随机选择rj∈Zp计算用户私钥然后返回给敌手A。

4） 敌手为了能猜测出加密使用的密钥，提交2个长度一样的内容不同的明文M0、M1给模拟器S，模拟器S随机选取r={0,1}，然后用访问控制策略 AC加密明文 Mr，返回密文C给敌手 A。其中密文C包括C=MYsφ=1。当φ=0时，由假设Z=e（g,g）abc，其中αl（l∈ {1,2,…,N}）可以 使ab= ∑αl,c=s， 这 样 就 可 以 得 到Z=e（g,可知道密文C是关于 Mr的一个有效密文。当φ=1时，r′≠r，因为z为随机数，所以密文C不包括明文Mr的任何有用信息。

5） 敌手A重复上述攻击。

6） 敌手 A 根据收到的信息猜测r′的值。如果r′≠r，则模拟器S输出φ′=1，敌手无法获取任何关于r的信息，则有当然也有如果r′=r，则模拟器 S输出φ′= 0，敌手获取Mr的密文，之前定义过敌手的优势为ε，则有得Pr[φ′=φ|最后得到的整体优势为

为进一步说明本文所提出的WV-CP-ABE方案的安全可靠性。本文从加密方式、删除机制、细粒度安全访问和删除验证4个方面将WV-CP-ABE方案与现有的云数据确定性删除方案 Vanish[16]、ISS[17]、ESITE[18]和 SelfDOC[19]进行对比分析，详细结果如表2所示。结果表明本方案一方面在云数据删除时采用重加密访问控制策略和数据覆写双重保证，另一方面在云数据删除后增加验证过程，防止不可信云服务提供商伪造删除信息，具有较高的安全性。

7 实验仿真

本文采用腾讯云服务器和本地电脑搭建实验所需的环境。腾讯云服务器为专业型服务器，CPU为四核、内存为 8 GB，充当方案中的云服务提供商。本地 3台电脑件配置为戴尔OptiPlex 3020 Mini Tower台式机，处理器为Inter Core（TM） i5-4590@3.30 GHz四核，内存为 8 GB，主硬盘为影驰 CX0128ML106-P（128 GB固态硬盘），分别充当方案中的数据拥有者、授权机构和用户。部署的Linux系统为Centos6.7，Hadoop版本为 hadoop-2.6.0，采用 C语言并基于 PBC（pairing- based cryptography library）函数库进行编程开发。

实验主要是测试所提WV-CP-ABE方案在文件加解密、云端数据重加、二叉树生成以及数据覆写验证等过程的时间消耗情况。

图 5测试不同文件大小方案加密时间的消耗。首先，在访问控制策略固定为15个属性的情况下，为更好构建现实的云存储环境，选用的文件大小分别为 1 MB、2 MB、4 MB、8 MB、16 MB、32 MB、64 MB、128 MB和256 MB测试数据文件的加密时间。图6是在相同条件下测试用户解密数据的时间消耗。从图5和图6中可以发现与文献[9]、文献[21]相比，加解密消耗时间随着数据文件的增多逐渐增多，但是数据文件增大到 256 MB时本方案的加解密时间明显少于对比方案。主要原因是本方案和文献[21]采用 CA-ABE加密，密文仅和一个访问控制策略有关，而文献[9]采用KP-ABE加密，密文和属性相关，随着文件的增多，将属性关联到文件中时间消耗增大，导致对应的加解密时间增多。

图5 不同文件大小加密时间消耗

表2 不同方案对比

图6 不同文件大小解密时间消耗

图7测试数据大小固定，随着访问控制策略中属性个数变化，数据加解密时间消耗。根据云存储中个人数据使用的调查报告[20]发现，云数据中文档类型占比最大，其次为照片类型。基于此情况本实验选用1 MB大小的数据作为测试数据，分析已存在的加密方案同时结合本文的设计目标，属性个数大多数在5～15个之间变化，而当属性个数为15个时已能满足方案安全要求。为此本实验数据大小固定为1 MB情况下，访问控制策略AC中属性个数从5个增加到15个。从图中可以看出随着访问控制策略里属性增多，数据加密和解密的时间大致呈现线性上升关系，而且相同属性个数情况下，数据加密消耗时间小于数据解密时间消耗。

图7 不同属性个数加解密时间消耗

图8测试的是不同属性个数情况下云端对密文中访问属性控制结构重加密的时间消耗。数据删除阶段的重加密密钥在可信授权结构生成时，TA只需要在Zp寻找一个随机数，所以计算时间消耗很小，而主要的时间消耗在云端访问控制策略重加密。当固定文件大小为1 MB，访问控制策略中属性个数从5个增加到15个，从图中可以看出来，随着属性个数增多，时间消耗基本维持在95 ms左右。

图8 不同属性个数情况下重加密时间消耗

图9测试的是生成不同高度DSMHT树的时间消耗。由于数据分块的大小不同，导致数据块个数不同，致使DSMHT的高度也不同，为不失一般性，每个准备的脏数据块大小为4 KB，生成树的高度从14增加到21，当树高度为21时，基本可以满足数据覆写验证要求。从图中可以看出随着树高度的增加，时间消耗不再呈现线性关系。当高度为21时，时间消耗大约为5.30 s，在可接受的范围。

图9 不同高度DSMHT生成时间消耗

图10测试的是文件大小从1 MB到64 MB，采用全零覆写、随机覆写和本方案覆写时的时间消耗，从图中可以看出随着文件的增大，覆写时间消耗大致呈比例增大，且本方案的时间消耗虽然比全零覆写方式多，但是却和随机覆写方式的时间消耗基本一致。分析其原因，全零覆写模式直接对文件数据进行覆写，所以相同文件大小，时间消耗最少；随机覆写模式需要产生随机数，本方案覆写模式需要读取生成好的脏数据，因此比全零覆写模式消耗时间多，而这2种模式的时间消耗大致相同。

图10 不同覆写方法时间消耗

表3测试的是对文件大小从1 MB到64 MB进行覆写验证的时间消耗。从表中可以看出随着文件大小的增加，时间消耗逐渐增多。64 MB的文件覆写的时间大约为2.70 s，覆写验证时间为9.45 s，均在允许接受的范围。

表3 不同大小数据覆写及覆写验证时间消耗

8 结束语

采用删除验证思想，提出一种基于密文重加密与覆写验证技术结合的数据确定性删除方案。当数据删除时，首先采用重加密云端密文的访问控制策略，使数据文件不能解密；其次构建基于脏数据块覆写的可搜索路径散列二叉树对云端密文进行覆写验证处理，保证删除过程准确地完成；最终通过敌手模拟游戏证明方案满足细粒度操作和确定性删除目标。

下一步研究目标是对上传到云端的数据进行安全等级分类，对不同安全等级的数据文件采用不同的数据确定性删除方法，以便达到资源合理的动态分配。