边缘环境下基于无证书公钥密码的数据完整性审计方案

王子园，杜瑞忠

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

0 引言

外包数据的存储安全一直是云环境下的重要安全问题。为保证远程数据的安全与完整，Ateniese 等[1]首次提出了数据完整性审计（PDP,provable data possession）机制，将验证外包数据完整性的解决方案系统化、规范化，在此基础上许多行之有效的数据完整性审计方案被提出[2]。

随着万物互联的飞速发展和广泛应用[3]，以及边缘计算[4]的逐步成熟，越来越多的设备被接入边缘环境中，现有的云计算集中式处理环境逐渐向边缘与云计算协同处理的形势发展，用户侧产生了边缘节点这一新的实体。而边缘用户设备在计算能力和存储能力等方面的局限性使用户数据的计算和存储安全等问题[5]变得更加严重。受以上因素的影响，传统云环境下的安全性方案已经不适于新的边缘环境。

此外，数据完整性审计方案通常会将审计工作交由可信的第三方处理，然而实际应用环境下第三方并不完全可信，再加上边缘环境下数据存储的形式越来越多样化，实体间的信任模型越来越复杂。因此，如何有效利用边缘节点的存储与计算能力，设计一种面向边缘环境的低复杂度的数据完整性验证方案是本文研究的重点。

为了解决上述问题，本文在假定边缘节点半可信的情况下，致力于在降低用户计算开销的同时保障外包数据的完整性与安全性。本文的贡献总结如下。

1) 基于边缘环境资源受限的特性，将无证书公钥密码思想与在线/离线标签思想相结合，设计了一种适用于边缘环境的完整性审计方案。

2) 利用边缘节点的存储与计算能力，在保证隐私的情况下使不同的边缘节点分别执行审计者与存储者的职能。

3) 针对数据的不同存储状态进行分析，保证边缘环境下数据存储的正确性以及确定性删除。

4) 通过理论与实验分析，基于计算性Diffie-Hellman（CDH,computational Diffie-Hellman）问题假设，证明本文方案在随机预言模型下是安全的，且与其他低复杂度审计方案相比，本文方案效率更高。

1 相关工作

自Ateniese 等[1]首次提出数据完整性验证机制开始，之后的数据完整性验证方案基本遵循该审计结构。近年来，诸多数据完整性审计方案被提出[6-9]，且在安全性与计算开销上有了很好的提升。

PDP 方案通常需花费计算成本和存储成本来进行证书的管理，为设备带来较高的负担。为解决这一问题，有学者提出基于身份的数据完整性审计方案，其能够避免传统PDP 方案系统建立和管理密钥生成中心（KGC,key generation center）的困难。在这类审计方案中，用户的公钥由用户自身的身份信息产生，私钥由KGC 生成。Tian 等[10]提出的方案能够保证验证者在验证用户完整性的同时不会获取用户信息。Shen 等[11]使用清理程序来清理与文件敏感信息相对应的数据块，并将这些数据块的签名转换为已清理文件的有效签名。Li 等[12]提出了基于模糊身份的数据完整性审计方案，利用秘密共享技术，使用生物识别信息作为模糊身份。Wang 等[13]支持在多云环境下实现数据完整性审计，解决了分布式数据存储审计困难。Yu 等[14]支持审计单个服务器中存储的多个数据副本，同时支持部门级的动态操作。Wang 等[15]利用索引逻辑表为云存储构建基于身份的不可否认的动态可证明数据占有方案，有效防止恶意用户的攻击。

基于身份的加密体制使KGC 可以获取所有用户的私钥，若KGC 被攻破，则攻击者能够使用任意用户的数据标签，数据完整性验证就失去意义。针对这一问题，无证书公钥密码机制被提出。在无证书公钥密码学中，用户的私钥由两部分组成，一部分由KGC 产生，另一部分则由用户自己生成。因此KGC 无法得到用户的完整私钥，即增强了密钥托管的安全性。

He 等[16]提出了一个隐私保护的无证书数据完整性审计（PP-CLPDP,privacy-preserving certificateless PDP）方案，大大减少了用户上传数据时的计算开销。在其基础上，Ji 等[17]重新定义了安全性模型，提出了tHKWWC（twisted HKWWC）方案，该方案将CSP（cloud service provider）与KGC 实体分开，更接近真实的云环境。随后Gao 等[18]提出了无证书公共审计方案（CL-PAS,certificateless public auditing scheme），在标签生成阶段对数据块进行哈希处理，能够确保恶意云服务器无法伪造审计证据，并防止半可信的第三方审计直接获取用户数据信息，加强了隐私保护。

边缘环境下，也有一些数据完整性审计方案被提出。Wang 等[19]在可信的边缘计算环境下，为给资源有限的终端提供计算能力，将数据预处理任务卸载到边缘，降低了计算负荷，同时支持第三方验证平台进行数据完整性验证。Liu 等[20]提出了针对企业多媒体数据边缘环境下的数据完整性审计方案，采用同态验证码，交由完全可信的第三方进行数据审计，从而降低了用户计算开销。Li 等[21]允许应用程序供应商检查其应用的缓存数据的完整性，并能高效地定位损坏数据的位置。由于边缘计算设备位于网络边缘，缺少有效的审计措施，导致攻击者可能修改或删除用户在边缘节点上的数据来销毁某些证据。又因为边缘计算场景下参与的实体类型多、数量大，所以信任情况非常复杂。攻击者可能将恶意边缘节点伪装成合法边缘节点，使终端用户连接到恶意边缘节点，隐秘地收集用户数据[22]。为此，如何在真实环境中进行数据完整性审计是本文要解决的问题之一。

综上所述，传统的数据完整性方案并不完全适于边缘环境，因为边缘环境对计算及存储有很严格的资源限制，而已有的面向边缘环境的完整性审计方案计算复杂度依然偏高，所以本文提出了边缘环境下基于无证书公钥密码的完整性审计方案，在省去复杂的证书管理的同时，尽可能降低用户侧的计算开销，审计时预先对数据区块进行处理，不直接传输真实数据，从而保护用户的数据隐私不被泄露。

2 相关知识

2.1 双线性映射

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

1) 双线性：对于任意δ,ξ∈Zq和χ,γ∈GT，都有e(χδ,γξ) =e(χ,γ)δξ。

2) 非退化性：存在χ,γ∈GT，使e(χ,γ) ≠ 1GV。

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

2.2 困难型假设

1) CDH 问题。给定三元组(P,aP,bP)，对任意直接计算abp是困难的。

2) 离散对数困难性问题。给定P,Q∈G1，求满足Q=xP的整数x是困难的，其中

2.3 在线/离线签名

本文方案允许签名者在分离线阶段和在线阶段生成签名。在给出要签名的数据之前，执行离线阶段，当用户设备接通电源时，离线阶段可以作为后台计算持续执行。产生数据后，将执行在线阶段，通常在线阶段的执行时间很短，即使具有弱处理器的设备也可以有效执行。

3 方案设计

3.1 整体框架

本文方案采用边云混合的方式，分为用户、边缘以及云三层，涉及终端、边缘节点、密钥生成中心、云端四类实体，各实体分别负责不同的功能，具体介绍如下。系统模型如图1 所示。

图1 系统模型

1) 终端（End）。每个用户可以拥有一台或多台终端设备，其数量众多，性能参差不齐，自身的存储空间往往不能满足所产生的数据量，所以选择上传数据到边缘节点或云端，并将数据完整性验证工作外包。

2) 边缘节点（Edge）。接近用户侧的边缘节点负责一定范围内设备的数据交互，具有存储与计算功能。本文假定边缘节点是半可信的，拥有一定的用户数据管理权限，不会违背用户要求，但可能会对数据产生好奇。

为避免单一数据节点损坏或受到攻击而产生数据损坏的问题，本文规定不同边缘节点具有不同的职能。本文将进行存储数据的边缘节点命名为EdgeS，进行审计数据的边缘节点命名为EdgeA。

3) 密钥生成中心（KGC）。KGC 部署在边缘层，被所有用户信任，负责在初始化阶段使用主密钥为其他实体生成基于身份的部分私钥。

4) 云端（CS）。云端为边缘用户提供云存储服务。在本文中，云端不可信，且其需要接收边缘节点发来的数据完整性验证请求，以确认数据是否完整存储在服务器上。

3.2 具体方案

当终端接入网络后，由KGC 利用用户身份及设备身份生成部分私钥，交由终端生成完整私钥。传输数据时，用户在离线阶段预先处理计算量较大的运算，在线阶段只需进行轻量级运算即可上传数据至EdgeS，随后根据用户需求存储在本地或选择上传至云端。音视频等数据量较大的数据，经由边缘节点上传至云端；用户密码、智能家居配置信息等数据量小、隐私性强的数据，存储在边缘节点本地。审计阶段，用户委托EdgeA 代为审计，以减轻用户计算压力，最后得到审计结果。

系统包括6 个阶段，下面对每个阶段进行说明。具体符号说明如表1 所示。

表1 符号说明

3.2.1 初始化阶段

初始化阶段包括系统参数生成、部分密钥提取和完整密钥生成。

系统参数生成。KGC 执行以下操作，输入安全参数k，生成大素数q、乘法循环群G1和G2、生成元P∈G1和双线性对选择随机数作为KGC的主密钥并保密，设置Ppub=zP为系统公钥。定义 2 个安全的 Hash 函数随后KGC 公开其系统参数{q,G1,G2,e,P,Ppub,H1,H2}。

部分密钥提取。当用户设备IDu要注册到KGC时，计算该设备部分私钥的步骤如下。

1) IDu选择随机数作为IDu的秘密值，计算Xu=xu P。

2) 用户设备将发送(IDu,Xu)给KGC，KGC 计算Qu=H1(IDu,Xu)和Du=zQu，其中z是KGC的主密钥。

3) 输出Di为部分私钥，并发送部分私钥给用户。

完整密钥生成。当终端收到KGC 返回的部分私钥后，执行以下步骤完成密钥的生成。

每台用户设备在接入网络后需执行初始化阶段生成密钥，考虑到密钥有泄露风险，在怀疑密钥泄露或一定周期后，应再次执行初始化阶段产生新的密钥。

3.2.2 标签生成阶段

当数据发生变化需要更新时，标签集合φ与文件签名TagF也会对应更新，随后重新上传。

3.2.3 数据传输阶段

外包数据存在3 种状态，即只保存在云端、只保存在边缘节点以及既保存在云端又保存在边缘节点，状态分别用θ=(0,1)、(1,0)和(1,1)来表示，且状态的选择权交由用户。

对式(1)进行证明，即

若验证失败，则返回失败结果，拒绝存储，以防恶意用户伪造数据欺骗存储数据者；若验证成功，则说明设备上传数据正确。然后依据用户选择θ对数据进行操作，数据上传流程如图2 所示。

图2 数据上传流程

存储数据时，建议将敏感、短期、数据量较小的数据存储于边缘节点，而长期、数据量较大的数据上传至云端。

当数据不存储于某些节点，或达到一定存储期限需要进行删除时，设备通过随机生成脏数据f替换原有节点中的文件F，以确保原有数据正确删除。

3.2.4 挑战阶段

数据上传后，当用户需要对数据完整性进行审计时，向EdgeA 发起验证请求，EdgeA 收到请求后，根据状态对相应存储位置发起挑战。首先存储数据处的节点利用数据F与节点私钥生成签名并将其发送给EdgeA 进行验证。若EdgeS 未存储数据，则生成脏数据f的文件标签验证过程均同式(1)。若验证不成立，则说明审计数据错误，需终止程序，向用户返回结果；若验证成立，则说明存储数据正确，且不存储于错误的存储节点，继续挑战。数据审计流程如图3 所示。

图3 数据审计流程

1) EdgeA 从全集Ω={1,2,…,n}中随机选择i个不同元素，并为每一个i∈I生成随机值vi。

由于存储状态θ不同，挑战发送位置也不同，当θ=(0,1)时，数据只保存在云端，EdgeA 只需向CS 发送挑战；当θ=(1,0)时，EdgeA 只需向EdgeS发送挑战；当θ=(1,1)时，EdgeA 需向EdgeS和CS都发送挑战，以验证2 个副本的数据完整性。

3.2.5 证据生成阶段

先对证据信息进行哈希处理后再发送Proof={δ,μ}给EdgeA，以免证据信息在传输过程中被恶意窃取，从而推导出用户的数据信息。

3.2.6 证据验证阶段

EdgeA 收到存储位置发来的证据信息后，执行下面步骤验证数据完整性。

4 安全性分析

4.1 攻击模型分析

基于无证书公钥密码机制，本文提出了三类敌手攻击：Type-Ⅰ类型敌手A1，一般用户攻击，不能获取KGC 主密钥但能替换任意用户私钥；Type-Ⅱ类型敌手A2，恶意KGC 攻击，可以获取KGC主密钥但不能替换用户私钥；Type-Ⅲ类型敌手A3，恶意EdgeS/CS 攻击，EdgeS/CS 可能会破坏数据并对审计者伪造证明。

Type-Ⅰ敌手。基于CDH 问题困难性假设，在随机预言模型下，若本文方案对敌手A1是不可伪造的，则本文方案是安全的。

Proof。对于这类攻击，A1可以随意替换用户公钥(XU,YU)，故挑战者C 设YU=Q2=bP。在部分私钥提取中，对两次H1询问设aP,j=1,2，其中sj是C 选择的随机数。因为CS在接收数据时已经收到所有的数据签名，所以不再进行标签生成询问。在证据生成阶段，挑战者C 利用哈希重放向H2询问同一个挑战，从而生成2 个不同的证据 (δ1,μ1)和(δ2,μ2)，那么式(5)和式（6）成立

如果A1能够攻破，说明式(9)有解，与假设矛盾。

Type-Ⅱ敌手。基于CDH 问题困难性假设，在随机预言模型下，若本文方案对敌手A2是不可伪造的，则该方案是安全的。

Proof。对于恶意KGC 攻击，A2可以随意替换用户主密钥，故设置系统公钥为Ppub=Q1=aP，其中a为系统主密钥。C 猜测Qu'=bP，用户秘密值为si，计算在证据生成阶段，挑战者C 利用哈希重放向H2询问同一个挑战，从而生成2 个不同的证据 (δ1,μ1)和(δ2,μ2)，那么式(10)和式(11)成立

如果A2能够攻破，说明式(14)有解，与假设矛盾。

Type-Ⅲ敌手。基于CDH 问题困难性假设，在随机预言模型下，若本文方案对敌手A3是不可伪造的，则本文方案是安全的。

Proof。对于这类攻击，敌手A3根据挑战者C发起的挑战信息，返回伪造的证明

整理式(15)和式(16)，可得μ*=μ，与假设矛盾。综上所述，本文方案能够抵抗三类敌手攻击，因此本文方案是安全的。

4.2 安全特性

本文方案满足以下几个性质。

1) 公开可验证。通过证据生成和证据验证阶段，审计者EdgeA 可以使用公共参数来验证数据的完整性，而不需要终端提供秘密值。

2) 存储正确性。只有当数据正确时，产生的证明才能通过三类敌手游戏模型。

3) 隐私保护性。验证边缘节点EdgeA 无法从挑战证明中获取数据信息。审计过程中，EdgeA 接收到 CS 或 EdgeS 发送的证明，(IDu,IDEdge,IDCS,TagF,Tagf)部分不包含具体的数据信息，下面对μ进行分析。EdgeA 能够忠实地完成用户审计任务，但会对数据产生好奇，CS 或 EdgeS 发送给EdgeA，EdgeA 可以通过多次挑战求解线性方程组，从而获取H2(mi)。根据哈希函数的不可逆性质，EdgeA 无法推导出数据块mi的值，从而有效对数据进行了隐私保护。

5 实验与分析

5.1 实验环境配置

本文方案共涉及4 种类型的实体，在本文的实验中，4 种实体由4 种具有不同功能和配置的机器模拟。具体来说，云端采用阿里云服务器ECS 部署，拥有2 GHz 处理器、2 GB 内存，边缘节点采用阿里云边缘节点服务ENS 部署，拥有2 GHz 处理器、1 GB 内存，终端与KGC 部署在本地计算机上，采用Intel i7-8086K 4 GHz 处理器、16 GB 内存。以上均基于Ubuntu14.04 版本系统搭建，openssl1.0.1 版本。

在实验中，本文使用C++和Python 进行代码编写，GMP 库和PBC 库实现密码操作。采用类型A的配对曲线，参数类型A 提供在所有默认设置中具有最快速度的对称配对参数，哈希函数为SHA1（160 bit）。所得实验结果均为多次计算后的平均值。

5.2 效率分析

在边缘环境中，对于资源有限的边缘设备用户来说，计算复杂度越小越好。如何在有限的资源限制下合理分配资源、缩短数据传输时的计算时间、提高计算效率是本文亟须解决的问题。本节将本文方案与另外5 种审计方案进行对比，并将审计算法放在相同的实验条件下，因此具有一定的可比性。

表2给出了数据上传时的时间复杂度分析。在用户层，CLPDP 与tHKWWC 方案需n次哈希运算（H）与2n次点乘运算（Mul），CL-PAS 方案需2n次哈希运算与2n次点乘运算，以上3 种方案属于轻量级审计方案。边缘环境下，文献[19]方案将用户侧计算任务全部卸载到边缘，因此用户侧有较低时延，边缘侧进行了n次哈希运算、n次点乘运算以及2n次指数运算（Exp）；文献[20]方案将边缘侧视为半可信，因此计算均在本地进行，时间复杂度同样为n次哈希运算、n次点乘运算以及2n次指数运算；本文方案由于将部分计算移至离线阶段，在线阶段只需进行n次哈希运算与n次点乘运算即可，时间复杂度最低，显著提高了数据上传时的计算效率。

表2 数据上传时的时间复杂度分析

表3为初始化阶段生成操作用时。每台用户设备在接入网络后需执行初始化阶段生成密钥，考虑到密钥有泄露风险，在怀疑密钥泄露或一定周期后，应再次执行初始化阶段产生新的密钥，但每次执行的时间开销与标签生成的时间开销相比可以忽略不计。

表3 初始化阶段生成操作用时

生成标签步骤分为离线标签生成与在线标签生成2 个阶段，为保证用户设备能够以最低的开销进行计算，本文首先对上传文件块大小进行了评估。以本文方案与CLPDP、tHKWWC、CL-PAS 作为评估方案，对其在文件数据总量分别为200 MB、400 MB、600 MB、800 MB和1 000 MB的在线标签生成实验进行了模拟，对比了文件块大小对标签生成时间的影响，结果如图4 所示。

从图4 可以看出，随着文件块大小的增长，标签生成时间呈指数形式递减。

图4 文件块大小对标签生成时间的影响

考虑到文件传输以及安全性，文件块越大，给数据传输带来的困难就越大，完整性验证就越不能达到预期效果，因此并不能无限制增大传输文件块的大小，分析实验结果后，以文件块大小等于4 096 bit为基准进行后续的对比实验。

由于标签生成阶段计算开销在总计算开销中占比较大，执行步骤较多，下面将对标签生成阶段总执行时间和数据上传时用户执行时间分别进行说明。

标签生成阶段总执行时间对比如图5 所示。从图5 中可以看出，随着文件块数量的增加，生成在线标签的时间呈线性增长，其中 CLPDP 与tHKWWC 方案需n次哈希运算与2n次点乘运算；CL-PAS 方案与本文方案需2n次哈希运算与2n次点乘运算，用时相对较高，这是因为CL-PAS 方案与本文方案对数据进行了哈希处理，以防审计者从中获取数据信息；文献[19]方案与文献[20]方案均进行了n次哈希运算、n次点乘运算以及2 次指数运算，虽然计算位置不同，但时间开销最高。

图5 标签生成阶段总执行时间对比

数据上传时用户执行时间如图6 所示。从图6中可以看出，随着文件块数量的增加，生成离线标签的时间呈线性增长。本文方案效率最高，其中文献[19]方案是在上传数据后再进行的数据预处理，因此时间开销最低。

图6 数据上传时用户执行时间

随着文件数据总量的增加，标签生成的计算时间呈线性增长。另外，在相同大小的文件数据总量下，文件块数量越多，文件块大小越小，需要计算的标签数相应增加，因此计算时间相应增长。虽然文件数据总量以及计算时间相对较大，但是只需要进行单次计算即可生成标签，并且可以在挑战验证过程中重复使用，因此实验结果可以接受。

在挑战和验证阶段，EdgeA 在接收到用户的审计请求后，向CS 或EdgeS 发起挑战，CS 或EdgeS生成证明并将之返回给EdgeA，然后EdgeA 根据持有的公钥对证明进行验证。

根据Ateniese 等[1]提出的方案，假设模拟的数据块数量为100 000，如果云服务器污染了1%，验证者可以挑战460 个区块使检测服务器错误的概率达到99%。当验证的区块越小时，验证所花费的时间就越短，同时验证检测率也会下降，当验证区块数为300 时，检测率在95%以上。接下来，给出挑战阶段取样300 与460 个区块时各审计方案的时间对比。

对于不同的文件数据总量，在固定了文件块大小的情况下，挑战与验证时间不变，说明证据生成与证明验证的计算时间与文件数据总量无关。用户选择的存储状态不同，审计的目标与大小也不同，当数据在EdgeS 与CS 中均进行存储时，证据生成与证明验证时间也会成倍增长，为表示统一，实验阶段均以θ=(0,1)状态进行比较。

证据生成阶段时间如表4 所示。证明验证阶段时间如表5 所示。各方案生成证据时间相差不大，均进行了双线性对运算。与整体时间开销相比，证据生成、证明验证用时占比并不大，因此实验结果是可以接受的。

表4 证据生成阶段时间

表5 证明验证阶段时间

5.3 存储开销

本文方案的额外存储开销集中在EdgeS 与CS，主要是上传文件时伴随的文件块标签集合，而用户自身上传数据后只需保留文件哈希值。

6 结束语

本文提出的边缘环境下基于无证书公钥密码学的在线/离线数据完整性审计方案具备保证用户安全、复杂度低的特点。基于无公钥密码学思想，在离线阶段进行部分签名的生成操作，使用户设备上传数据时的效率有了显著提升。针对数据不同存储状态，本文方案能够合理审计数据的正确性和完整性。在随机预言模型下，基于CDH 问题证明了本文方案的安全性。模拟分析审计方案中各阶段的主要运算开销，结果表明本文方案在边缘环境下的用户设备上传数据时间开销最低。