无第三方服务器的基于数据流行度的加密去重方案

哈冠雄，贾巧雯，陈杭，贾春福

0 引言

云存储技术[1]的快速发展使越来越多的用户选择将数据外包至云服务器（CS,cloud server）。随着数据量的不断增加，如何高效存储海量数据成为云服务提供商面临的一个关键问题。数据去重[2-3]是一种节省存储开销的有效方法，云服务器可基于去重技术识别用户间上传的重复数据内容，删除其中的冗余部分以节省存储开销。近年来，隐私泄露问题受到了越来越多的关注，数据的隐私保护变得愈发重要。传统加密算法可将数据转换为与随机比特串不可区分的密文形式，为其提供安全级别较高的语义安全。然而，传统加密算法与去重技术难以兼容。不同用户的加密密钥不同，跨用户上传的相同数据在加密后将变成完全随机的密文，这为重复数据的检测带来了困难。收敛加密（CE,convergent encryption）[4]使用数据哈希值作为加密密钥，首次实现了加密去重。但Bellare 等[5]指出CE 只能提供收敛安全性，其仅能为不可预测数据（明文空间无限，敌手无法遍历）提供语义安全。若使用CE 加密可预测数据，易受到离线字典攻击。

因此，在实现数据去重的同时提供语义安全是一个关键挑战。针对此问题，一些研究工作[6-9]基于数据流行度设计加密去重方案，旨在兼顾存储效率与数据安全。数据流行度指的是数据的所有者数量。具体而言，首先设定一个流行度阈值t，若外包数据的所有者数量超过t，则认为是流行数据，否则认为是不流行数据。对于流行歌曲、热门电影等流行数据，系统基于CE 为其提供安全级别较低的收敛安全性；对于研究报告、医疗记录等不流行数据，系统使用随机加密为其提供安全级别较高的语义安全。基于流行度对用户数据进行分类，可有效平衡存储效率与数据安全。Stanek 等[6]使用真实数据集分析了基于流行度的加密去重系统的存储效率，结果表明当流行数据的数量较多时，方案具有较高的存储效率。其他相关研究工作[7-9]也充分说明了基于流行度设计加密去重方案这一思路的可行性与实用性。

在基于流行度的加密去重中，如何安全准确地统计数据流行度是方案设计中面临的关键挑战。现有方案及其特点如表1 所示，一些经典的加密去重方案（如CE[4]、DupLESS[5]）将数据哈希值作为去重标签用于重复性检测，易使不流行数据受到离线字典攻击；一些现有方案[6-7]部署可信第三方协助统计数据流行度，这一方法的弊端主要有以下两点。1)系统中的所有用户都需要与第三方交互，影响了系统的可扩展性。当用户量较多、数据量较大时，第三方服务器的处理能力有限，易成为系统的效率瓶颈。2)第三方可得到系统中所有数据的流行信息，因此需要假设第三方是完全可信的，这一假设在真实场景中难以实现。并且，第三方易成为系统中的单点故障，一旦其被敌手攻破，所有不流行数据的语义安全都将被破坏。

表1 现有方案及其特点

文献[8-9]弱化了第三方的安全假设，通过引入半可信（即诚实但好奇）的第三方来统计数据流行度。Ha 等[8]通过部署一个半可信的第三方同态解密服务器统计数据流行度，其中的解密服务器同样易成为系统中的效率瓶颈。Gao 等[9]通过引入第三方密钥管理服务器实现了基于流行度的加密去重，该方案使用收敛密文的哈希值作为去重标签，易使不流行数据受到离线字典攻击。

由于引入第三方服务器会存在效率瓶颈和单点故障的问题，本文提出了一个无第三方服务器的基于数据流行度的加密去重方案。该方案基于Count-Min sketch（CM-sketch）算法[10]、sPAKE（symmetric password-authenticated key exchange）协议[11]以及Merkle Puzzles 协议[12]，在不需要部署任何第三方服务器的情况下实现了加密去重系统中的数据流行度精确检测，并可分别为流行数据和不流行数据提供收敛安全和语义安全。本文的主要贡献如下。

1)本文方案设计了两步检测的方法安全精确地统计数据流行度。首先，基于CM-sketch 算法在仅使用固定内存空间的前提下实现了数据流行度的初步检测，有效过滤了大量不流行数据。然后，通过用户与云服务器间执行Merkle Puzzles 协议进一步准确统计数据流行度。流行度检测过程仅由云服务器和用户两方完成，不需要任何第三方服务器。

2)通过在用户间执行sPAKE 协议，本文方案实现了不流行数据的去重检测和用户间的密钥传递，云服务器可同时对流行数据和不流行数据实现客户端加密去重，最大限度地节省了系统的通信开销和存储开销。

3)本文方案设计了密钥验证和密文验证的过程，并结合所有权证明（PoW,proof of ownership）[13]技术，可有效对抗所有权欺骗攻击[13-14]、文件伪造攻击[15]和字典攻击[15]等加密去重系统中的常见攻击，可分别为流行数据和不流行数据提供收敛安全性和语义安全性。

1 相关工作

近年来，国内外的多个研究团队均在加密去重领域进行了深入研究。Douceur 等[4]提出了CE，首次实现了加密去重。Bellare 等[15]将CE 形式化定义为消息锁加密（MLE,message-locked encryption)，并指出CE 无法为可预测数据实现语义安全。为此，Bellare 等提出了DupLESS[5]，其引入一个密钥服务器协助用户加密数据，有效防止了字典攻击。Halevi等[14]发现了客户端去重中的所有权欺骗问题。针对此问题，文献[13-14,16]提出了所有权证明方案。此外，文献[17-19]针对加密去重系统中的密钥更新与访问控制问题进行了研究。Li 等[20]提出了加密去重系统中的频率分析攻击，并给出了相应的防御方案[20-21]。文献[22-24]针对客户端去重中的侧信道攻击问题提出了防御方案。

在加密去重这一研究领域中，基于数据流行度设计加密去重方案[6-9]是一个重要的研究分支。Stanek 等[6]基于门限密码系统和双层加密实现了基于流行度的加密去重，当超过流行度阈值t个的用户上传某一密文后，云服务器可对外层的随机密文进行解密，保留内层的收敛密文，实现加密去重。Puzio 等[7]利用完美哈希实现了基于流行度的加密去重，用户可在与云服务器的交互中获取外包数据的流行信息。文献[6-7]需要引入可信第三方协助统计数据流行度，具有一定的局限性。为此，Ha 等[8]基于同态加密实现了数据流行度的安全统计，客户端上传外包数据的随机标签至云服务器，云服务器通过与同态解密服务器的交互进行流行度检测。Gao等[9]基于双层加密和密钥共享设计了基于流行度的加密去重方案，将第三方的安全假设降低为诚实但好奇的。然而，现有方案都需要引入第三方服务器，易出现效率瓶颈等问题，影响了方案在真实场景中的实用性。为此，本文提出了无第三方服务器的基于数据流行度的加密去重方案。

2 预备知识

2.1 CM-sketch

CM-sketch 可在误差较小的前提下利用有限的内存空间描述数据的频率特征，其内部的数据结构是一个w×d的二维数组，其中，参数ε δ、表示在 1−δ的概率下统计结果的总误差小于ε。CM-sketch 算法主要由以下3 个算法组成。

1)Setup(ε,δ)。输入参数,ε，δ初始化一个w×d的二维数组count，将所有元素值置0；随机选定d个两两独立的哈希函数h1(⋅),h2(⋅),…,hd(⋅)，其中hi(⋅)(i∈[1,d])的输出结果的长度为w。

2)Count(x,count)。输入元素x和数组count，计算哈希值h1(x),h2(x),…,hd(x)用于更新count，令count 中被哈希值映射到的位的计数值加1，即count[i][hi(x)]=count[i][hi(x)]+1，其中i∈[1,d]。

3)Freq(x,count)。输入元素x和数组count，输出x的频率信息。计算哈希值h1(x),h2(x),…,hd(x)，取{count[i][hi(x)]|i∈[1,d]}中的最小值作为元素x的频率信息输出。

2.2 sPAKE

sPAKE[11,25]是传统密钥协商的一个扩展。当运行协议的双方共享同一个口令时，可协商出相同的密钥；若双方口令不同，则各自得到一个随机密钥，双方均无法获得对方密钥的任何信息。

本文使用了目前已知最高效的sPAKE[11]，参与协议的双方仅需执行2 次幂运算，具有很高的执行效率，并且协议在随机预言机模型下是可证明安全的。具体的协议流程如图1 所示。本文方案使用数据哈希值取代了原协议中的口令。若参与sPAKE 协议的双方拥有相同的哈希值，可协商出相同的输出结果K1和K2，否则，双方得到完全随机的输出结果。

图1 sPAKE 协议流程

2.3 Merkle Puzzles

Merkle Puzzles 基于对称密码原语实现了安全的密钥协商。假设协商密钥的双方分别为Alice 和Bob，他们执行以下步骤协商密钥。

1)Alice 穷举密钥集合中的所有密钥{k1,k2,…,kn}，并生成n个密文{Ci=Enc(ki,0),Enc(ki,xi),，其中xi和si为随机值，Enc(⋅)为对称加密算法。Alice 将随机排序后发送给Bob。

2)Bob 随机选择一个密文Cj=(c1,c2,c3)，使用{k1,k2,…,kn}中的所有密钥尝试解密c1。当解密结果为0 时，Bob 确定对应的密钥为kj，然后使用kj解密c2和c3得到xj和sj，并将xj返回给Alice。

3)Alice 收到sj后密钥协商结束，双方得到的协商密钥为kj。

本文基于上述设计思路和Yu 等[26]对Merkle Puzzles 的使用方式，将Merkle Puzzles 应用于加密去重场景下的数据流行度统计中。

2.4 收敛加密

收敛加密[4]使用消息内容的哈希值作为密钥加密数据以实现密文去重，由以下3 个算法组成。

1)CE.KG(M)：输入消息M，输出收敛密钥kc。

2)CE.Enc(kc,M)：输入收敛密钥kc和消息M，输出收敛密文C。

3)CE.Dec(kc,C)：输入收敛密钥kc和收敛密文C，输出消息M。

3 系统模型与定义

3.1 系统架构

本文方案的系统架构如图2 所示，包括用户U和云服务器CS。CS 为U提供数据存储服务，基于数据的所有者数量将其划分为流行数据和不流行数据，可对U的外包数据进行去重以节省存储开销。U外包加密数据至CS 以节省本地存储开销，并且需要在上传数据后在CS 的协助下与其他上传数据的用户运行sPAKE 协议，以确定后续上传数据的流行情况。

图2 系统架构

3.2 威胁模型

本文主要考虑以下两类敌手。

1)内部敌手。内部敌手指系统中诚实但好奇的云服务器和合法用户，其会诚实地执行方案中设定的协议流程，同时也会试图窥探用户的数据信息。

2)外部敌手。外部敌手指系统中的恶意攻击者，其可在与云服务器交互的任何阶段发起攻击。具体来说，外部敌手可通过窃听信道得到用户上传的数据内容，发起字典攻击试图恢复数据信息，发起所有权欺骗攻击试图篡改数据流行度[9]或骗取数据所有权，发起密钥伪造攻击或文件伪造攻击试图破坏数据完整性。

3.3 安全目标

本文方案的安全目标如下。

1)数据机密性。任何敌手均无法恢复不流行数据的任何信息。对于流行数据，本文方案提供收敛安全性。

2)数据完整性。任何敌手不能篡改用户的外包数据，所有合法用户均可正确恢复其外包数据并验证数据完整性。

3.4 符号定义

本文使用的符号及其含义如表2 所示。

表2 符号及其含义

4 设计思路

基于流行度设计加密去重系统存在以下2个挑战。

1)如何安全准确地统计数据流行度。若使用数据哈希值（如SHA-256 值）进行流行度检测，不流行数据易受到离线字典攻击。若使用随机标签[9]进行流行度检测，在不引入第三方服务器的情况下难以判断数据流行度。

2)如何实现不流行数据的加密去重。由于需要为不流行数据提供语义安全，数据哈希值不可用于去重检测，并且用户需要使用随机密钥加密不流行数据。如何实现不流行数据的跨用户去重检测，并在不同用户间传递随机密钥以实现加密去重成为设计中的关键挑战。

4.1 流行度检测的设计思路

针对第一个挑战，本文设计了一个两步检测的方案来安全准确地统计数据流行度，如图3 所示。首先，使用外包数据的短哈希值进行流行度的初步检测，旨在过滤掉大量不流行数据。短哈希值[26-27]可通过截取哈希值的部分位数来实现（如截取SHA-256 值的前13 位）。由于短哈希值具有较高的冲突率，敌手无法基于短哈希值进行字典攻击。然而，当数据量较大时，统计大量短哈希值的所有者数量可能会给云服务器带来较大的内存开销。为此，本文在初步检测中使用了CM-sketch 算法，其特点是可以基于固定长度的内存空间进行流行度统计，有利于系统的可扩展性。即使数据量不断增加，用于统计流行度的内存空间仍可保持不变。

图3 方案流程

CM-sketch 的统计结果存在一定误差，与真实结果相比可能偏大。若CM-sketch 的统计值vm小于流行度阈值t，则数据一定不流行；若vm大于或等于t，需要进行后续检测。在后续检测中，云服务器与用户执行Merkle Puzzles 协议以检测外包数据的哈希值（如SHA-256 值）是否与现有流行数据的哈希值匹配。若用户可恢复出正确的pti[0]，则数据流行；否则，数据不流行。在后续检测中，云服务器可准确判断数据是否流行。

4.2 不流行数据加密去重的设计思路

云服务器若检测到外包数据是流行数据，可基于CE 实现加密去重；若检测到外包数据是不流行数据，如图3 所示，可基于sPAKE 协议进行去重检测，并在用户间传递随机密钥，以实现不流行数据的加密去重。假设用户U的外包文件为F，云服务器索引短哈希值sh(F)对应的不流行数据的用户列表为（云服务器的存储结构如图4 所示），要求U与使用数据哈希值运行sPAKE 协议。协议结束后，云服务器可通过协议的输出结果进行去重检测，判断本次数据上传为首次上传或后续上传。若数据为首次上传，用户执行首次上传的流程；若数据为后续上传，执行密钥传递的数据过程在用户间安全地传递随机密钥，实现不流行数据的加密去重。

图4 云服务器的存储结构

5 方案详细设计

本文方案流程主要分为系统初始化、流行度检测、不流行数据上传、流行数据上传和数据下载。

5.1 系统初始化

用户生成各自的RSA 公私钥对(pk,sk)。为防止在线字典攻击，用户为每个外包文件设置一个参与sPAKE 协议的数量上限NP[27]。若用户在某一时间段Δ 内收到了对某一个文件超过NP次的sPAKE请求，则拒绝执行协议。云服务器CS 设定系统的安全参数λ和流行度阈值t。若数据的所有者数量num≥t，则认为是流行数据；否则，认为是不流行数据。此外，云服务器设定CM-sketch 的参数。CM-sketch 由一个二维数组组成，包含r行、w列，共r×w个计数器。云服务器发布用于CM-sketch的r个独立的短哈希函数，每个短哈希函数均可将数据对应到CM-sketch 的r行中的一个计数器j(1≤j≤w)上。

5.2 流行度检测

流行度检测的流程如算法1 所示，具体可分为基于CM-sketch 的初步检测和基于Merkle Puzzles的后续检测，详细流程如下。

1)基于CM-sketch 的初步检测。假设外包文件为F，用户U计算短哈希值sh(F)和并将其发送至云服务器CS。CS 将中的每个值映射到CM-sketch 的r行中的计数器上，并将相应计算器的值加1。统计流行度时，云服务器使用r个计数值中的最小值vm作为sh(F)当前的流行度统计值。CM-sketch 的统计值与真实结果相比可能偏大。因此，若vm

2)基于Merkle Puzzles 的后续检测。云服务器CS在流行数据列表中检索sh(F)（云服务器的存储结构如图4 所示）。若无法检索到sh(F)，则F是不流行数据；否则，CS检索sh(F)对应的流行数据列表中的所有辅助信息[26]（其生成细节见5.3.4 节），其中表示文件哈希值。CS发送至用户U。U基于文件F的哈希值HF解密，得到随机值集合，计算哈希值并返回CS。CS检查是否存在。若存在，说明F为流行数据；否则，F为不流行数据。至此，流行度检测结束，CS可精确统计文件F的流行度。

算法1流行度检测

5.3 不流行数据上传

不流行数据上传的流程包括去重检测、数据首次上传、数据后续上传和流行度转换。

5.3.1 去重检测

去重检测的流程如算法2 所示。若检测到文件F不流行，云服务器CS索引sh(F)对应的所有不流行数据的用户列表，在每个列表中选择一个当前在线的用户组成检查者列表，要求U与中的用户运行sPAKE 协议。在sPAKE 协议中，U输入文件F的哈希值HF，每个Ui输入各自的文件哈希值，协议中的通信数据均由CS转发，用户间不需要直接通信。协议结束后，每个Ui得到sPAKE 协议的输出值Ki，U得到输出值列表，U和将输出值发送至CS。CS 收到U发送的发送的后，检查是否存在=Kj。若存在，说明U的外包文件F与Uj此前上传的文件相同，U执行数据后续上传的流程；否则，U执行数据首次上传的流程。

算法2去重检测

5.3.2 数据首次上传

用户U生成收敛密钥kc=CE.KG(F)，对F进行收敛加密得到收敛密文CF=CE.Enc(kc,F)，计算哈希值HCE=H(CF)；生成随机密钥kr←{0,1}λ和随机值s←{0,1}λ，对F进行随机加密得到Cr=Enc(kr,F)；计算所有权证明值pF=H(s,F)；上传Cr至CS，本地存储(HF,kr,kc,pF,s,HCE)。

5.3.3 数据后续上传

数据后续上传的流程如算法3 所示。方案实现了不流行数据的客户端加密去重，若数据为后续上传，则不需要用户U上传完整的数据内容，仅需进行所有权证明和密钥验证的过程，可有效节省系统的通信开销。在后续上传中，CS发送U的公钥pkU至检查者列表中的Uj。Uj计算Ck=kr⊕pF和Cs=并将其返回至CS，二者用于密钥传递和所有权证明。CS将(Ck,Cs)转发至U。U使用私钥skU解密Cs得到；使用s和F计算所有权证明值pF=H(s,F)，恢复随机密钥k r=Ck⊕pF；计算收敛密钥kc=CE.KG(F)和哈希值HCE=H(CF)；本地存储(HF,kr,kc,pF,s,HCE)。

算法3数据后续上传

为防止密钥传递时出现伪造情况，方案设计了密钥验证过程。U使用kr计算随机密文=Enc(kr,F)，计算哈希值HC=并发送至CS。CS检索本地存储的随机密文Cr，验证HC是否与H(Cr)相等。若不相等，说明存在密钥伪造攻击，CS不进行数据去重以防止数据完整性被破坏；若相等，将U加入用户列表当中，并将文件的所有者数量num 加1。若此时num 小于t，上传过程结束；若num 等于t，表明此次数据上传后F变为流行数据，CS需与U进行流行度转换。

5.3.4 流行度转换

在流行度转换中，用户U发送收敛密文CF至CS，CS进行如下的密文验证过程。CS 计算哈希值H(CF)发送至Uj，Uj检查H(CF)与本地存储的HCE是否相等。若不相等，可能存在文件伪造攻击，CS 不进行数据去重以防止数据完整性被破坏；若相等，说明U与Uj计算的收敛密文一致，云服务器存储CF，并删除此前存储的随机密文Cr以节省存储开销。最后，U生成随机值rM←{0,1}λ，计算辅助信息pt=(H(HF,rM),Enc(HF,rM))并发送至CS，用于后续其他用户的流行度检测。

5.4 流行数据上传

若外包文件F是流行数据，方案可实现客户端去重，用户U只需与云服务器CS 进行如下的所有权证明[9]。CS生成随机种子u发送至U。U计算收敛密文CF，根据u生成随机索引序列，计算所有权证明值pF=H(H(CF[u1]),H(CF[u2]),…,并返回至CS。CS 基于本地存储的收敛密文CF与判断pF是否正确。若正确，CS将U加入所有者列表中，U存储收敛密钥kc；否则，所有权证明失败。

5.5 数据下载

用户U向CS发出文件F的下载请求。CS根据F的流行情况返回收敛密文CF或随机密文Cr。U使用kc或kr解密CF或Cr以恢复F，并通过验证H(F)与HF是否相等来检测数据完整性是否被破坏。

6 安全性分析

本节分析了方案的正确性以及在内部敌手和外部敌手攻击下的安全性并做出如下安全假设。1)方案中使用的对称加密和RSA 加密具有语义安全性；2)方案中使用的哈希函数（短哈希函数除外）满足抗碰撞性，且可看作随机预言机；3)方案中的sPAKE 协议是安全的，若参与协议的双方输入不同，则无法获取对方输入的任何信息；若双方输入相同，则可得到相同的协议输出结果。

6.1 正确性分析

本节分析方案在不流行数据首次上传、后续上传以及流行数据上传3 种情况下的解密正确性。

在不流行数据的首次上传中，用户U本地安全存储了收敛密钥kc和随机密钥kr。基于传统对称加密算法和CE 的解密正确性，下载数据时U可使用kc或kr恢复正确的数据内容。在不流行数据的后续上传中，U收到CS发送的Ck和Cs。基于RSA 解密的正确性，拥有正确私钥的U可恢复随机值s。若拥有完整的数据内容，U可计算出收敛密钥kc和所有权证明值pF=H(s,F)，并恢复出随机密钥kr。因此，U可通过方案中的密钥传递过程得到正确的随机密钥kr和收敛密钥kc，在数据下载时可使用kc或kr恢复正确的数据内容。流行数据上传时，U本地存储了收敛密钥kc，下载数据时可使用kc恢复正确的数据内容。

6.2 内部敌手的安全性分析

本节分析方案在内部敌手攻击下的安全性。根据3.2 节描述的威胁模型，内部敌手是诚实但好奇的云服务器或用户。基于sPAKE 协议[11]的安全性，参与协议的诚实用户不会获取其他用户的任何数据信息。因此，本节中的内部敌手AI指诚实但好奇的云服务器。本节分别从流行度检测的安全性、流行数据的收敛安全性和不流行数据的语义安全性三方面进行安全性分析。

6.2.1 流行度检测的安全性

在流行度检测中，AI可得到短哈希值sh(F)、和哈希值集合。由于短哈希值具有高碰撞率，AI无法将短哈希值与用户文件一一对应，因此无法通过离线字典攻击恢复数据信息。由于随机值对AI保密，且哈希函数可看作随机预言机，与等长的随机比特串具有不可区分性，AI无法获得数据信息。

6.2.2 流行数据的收敛安全性

对于流行文件F，AI可得到其收敛密文CF、密文哈希值HCE、所有权证明值pF和辅助信息pt。基于收敛安全性[5]的定义，AI通过(CF,HCE)恢复不可预测的流行数据的概率是可忽略的；pF为CF抽样后的哈希值，同样不泄露不可预测数据的任何信息；pt[0]和pt[1]分别为随机值rM的哈希值和对称密文，由于哈希函数可看作随机预言机且对称加密具有语义安全性，因此pt 与等长的随机比特串具有不可区分性，不泄露数据信息。

6.2.3 不流行数据的语义安全性

本节通过定义安全游戏的方式形式化分析不流行数据的语义安全性。安全游戏将方案的安全性规约到对称加密、RSA 加密和密码本加密的安全性上。本节定义安全游戏G0模拟真实场景下的方案，其中敌手A 模拟诚实但好奇的云服务器，挑战者C模拟诚实执行协议的用户。本节将安全游戏中的哈希函数看作随机预言机，挑战者C 计算哈希值时需询问随机预言机。对于每次询问，预言机将返回一个均匀随机的输出。对于重复出现的询问，预言机将返回相同的结果。安全游戏G0的具体描述如下。

1)初始化阶段。挑战者生成随机密钥kr、随机种子s和RSA 公私钥对(pku,sku)。

2)挑战阶段。敌手A 输出2 个等长的挑战明文(M0,M1)。C 随机选择b∈R{0,1}，计算PF=H(s,Mb)，返回Cr=Enc(kr,Mb)、Cs=和Ck=kr⊕pF至A。

3)猜测阶段。A 输出b'，如果b=b'，则A 赢得G0。将A 在G0中具有的概率优势定义为Adv(A)=。

定义1若对于任意的概率多项式时间（PPT,probabilistic polynomial time）敌手A，存在一个可忽略的值ε，满足Adv(A)≤ε，则认为本文方案中诚实但好奇的云服务器无法破坏不流行数据的语义安全性。

定理1若方案中使用的对称加密和RSA 加密是语义安全的，则在随机预言机模型下本文方案中的云服务器无法破坏不流行数据的语义安全性。

这里通过定义多个不可区分的安全博弈游戏来证明定理1。

6.3 外部敌手的安全性分析

外部敌手AE可通过截获通信数据并发起字典攻击破坏数据机密性；通过篡改数据内容破坏数据完整性；发起密钥和文件伪造攻击破坏数据完整性；使用部分数据内容进行所有权欺骗攻击试图获取数据所有权或篡改数据流行度，本节针对上述攻击进行安全性分析。

1)字典攻击。不流行数据均为随机加密后的密文，基于对称加密的语义安全性，AE无法进行离线字典攻击。对于不可预测的流行数据，基于CE 提供的收敛安全性，AE无法运行离线字典攻击。由于用户为每个文件设置了进行sPAKE 协议次数的上限NP，AE无法通过频繁运行sPAKE 协议进行在线字典攻击。

2)数据篡改攻击。AE可在用户下载数据时截获通信数据并进行篡改。用户下载数据后可通过验证H(F)与HF是否相等来检测数据完整性是否被损坏。若检测到完整性损坏，用户可重新下载数据，并删除已被篡改的数据。

3)密钥伪造攻击。在不流行数据上传过程中，若AE为sPAKE 协议中的检查者，则使用伪造的密钥进行密钥传递发起密钥伪造攻击，试图破坏其他用户的数据完整性。在密钥验证过程中，数据上传者发送密文哈希值HC至云服务器。基于哈希函数的抗碰撞性，云服务器可通过比对哈希值识别出密钥伪造攻击，并中止数据去重。

4)文件伪造攻击。在流行度转换过程中，AE可通过上传正确的文件哈希值HF和伪造的收敛密文发起文件伪造攻击，试图破坏数据完整性。在密文验证的过程中，云服务器计算哈希值H(CF)并发送至检查者Uj，Uj验证H(CF)是否与本地存储的HCE相等，并将比较结果返回给云服务器。基于哈希函数的抗碰撞性，云服务器可在密文验证过程中检测出文件伪造攻击，通过中止数据去重防止数据完整性被破坏。

5)所有权欺骗攻击。在流行数据上传的过程中，AE需要与云服务器进行所有权证明，基于文献[9]中的安全分析，仅拥有部分数据内容的AE通过所有权证明的概率是可忽略的。在不流行数据上传的过程中，AE需要拥有完整的数据内容才能计算出H(F,s)以恢复密钥kr。基于哈希函数的雪崩效应，仅拥有部分数据内容的AE无法恢复kr，从而无法进行所有权欺骗攻击。

综上，外部敌手无法通过上述攻击方式破坏数据完整性和机密性。

6.4 与现有方案的安全性对比

表3 将本文方案与现有基于流行度的加密去重方案的安全性进行了对比。与文献[6-7]相比，本文方案引入了所有权证明和完整性验证，可有效对抗所有权欺骗攻击并可提供数据完整性。与文献[8]相比，本文在不流行数据上传的过程中设计了密钥传递过程，可实现不流行数据的加密去重以节省存储空间（表3 中的数据去重指同时实现流行数据和不流行数据的去重）。与文献[9]相比，本文使用短哈希值进行流行度检测，可为不流行数据提供语义安全。另外，本文方案最关键的特性是在不需要部署任何第三方服务器的情况下，实现了数据流行度的安全统计以及不流行数据的加密去重，这使本文方案不存在性能瓶颈和单点故障等缺陷。

表3 安全性对比

7 性能分析

本节分别从算法复杂度和实验评估两方面分析方案的性能。

7.1 算法复杂度

表4 分析了不流行数据首次/后续上传和流行度转换3 种不同情况下的客户端计算开销，鉴于流行数据上传的过程较为简单，且本文方案与现有方案[6,8-9]的开销几乎相同，因此这里不做分析。为方便表述，方案中哈希值、加密密钥和随机值的大小统一用λ表示，lF和lλ分别表示外包数据大小和随机值s的RSA 密文大小；SE、H、TE、HE、SS、PoW、sPAKE、SK、PT 分别表示对称加密、哈希函数、门限加密[6]、同态加密[8]、秘密共享[9]、所有权证明[8,13]、sPAKE[11]、RSA 解密和生成辅助信息pt 的计算开销。由表4 可以看出，现有方案在不同情况下的计算开销类似，而本文方案在3 种不同情况下的计算开销则略有不同。由于实现了不流行数据的客户端去重，本文方案中流行度转换和不流行数据后续上传的计算开销略高于不流行数据首次上传。

表4 客户端计算开销

另外，与现有方案[6,8-9]相比，本文方案数据上传的计算开销差距不大，都主要集中在对外包数据的哈希和对称加密上；本文方案增加的计算开销主要在于sPAKE 协议的执行和密文/密钥的验证过程。由7.2.1 节的实验结果可知，sPAKE 协议对方案的性能影响不大。在不流行数据后续上传中，由于引入了密钥验证的过程，本文方案与现有方案[6,8-9]相比增加了一次数据哈希的操作，这增加了一定的计算开销。本文方案引入的计算开销主要用于消除系统对第三方服务器的依赖，提高方案在真实场景中的应用价值。

7.2 实验评估

本节通过仿真实验对本文方案进行了性能评估。实验使用戴尔Inspiron 5680 台式计算机模拟实现了方案中的云服务器和用户，其配备有3.20 GHz Intel(R)Core(TM)i7-8700 六核处理器和8 GB 运行内存，运行操作系统为64 bit Ubuntu 20.04.1。对于加密去重系统来说，存储效率和加密上传的时间开销是2 个关键的性能指标。本文方案同时实现了流行数据和不流行数据的去重，达到了最佳的去重效率。因此，本节主要针对方案中数据上传的时间开销进行分析。本节中的所有实验结果均为50 次以上实验结果的平均值。实验中短哈希值位数为13，哈希函数使用SHA-256 算法，对称加密使用AES，密钥长度为256 位。

7.2.1 Merkle Puzzles 和sPAKE 的性能分析

本文方案的数据上传过程中，Merkle Puzzles和sPAKE 的时间开销会随着系统中的数据量和用户量而变化。本节首先测试了不同文件数量下Merkle Puzzles 的时间开销，如图5 所示。从图5可以看出即使文件数量为1 024 个，Merkle Puzzles的时间开销也仅为210 μs 左右。由于Merkle Puzzles仅需对长度较短的随机值进行对称加解密和哈希操作，这部分的时间开销极小，在数据加密上传的整体时间开销中占比极低，几乎可忽略不计。

图5 不同文件数量下Merkle Puzzles 的时间开销

此外，本节测试了执行不同次数sPAKE 的时间开销，如图6 所示。从图6 可以看出，相比于Merkle Puzzles，sPAKE 的时间开销明显更大。当用户执行160 次sPAKE 协议时，时间开销约为4.2 s。虽然本文使用了目前已知最高效的sPAKE 协议[11]，但sPAKE 协议的参与方仍需执行2 次幂运算。当sPAKE 协议的执行次数较多时，仍会产生一定的时间开销。但是，本文方案为防止敌手的在线字典攻击，需要对执行sPAKE 协议的次数进行限制。因此，系统中执行sPAKE 协议的时间开销的上限是固定的。当系统设定参与sPAKE 协议的数量上限为80时，执行sPAKE 协议的时间开销的上限约为2.1 s。总体而言，由于次数限制，执行sPAKE 协议的时间开销在整体数据加密上传的过程中占比不大，这一点可以通过7.2.2 节中的实验分析看出。

图6 执行不同次数sPAKE 协议的时间开销

7.2.2 数据加密上传的时间开销

本文方案中的数据加密上传可分为4 种情况：不流行数据首次上传，不流行数据后续上传、流行度转换和流行数据上传。7.2.2 节和7.2.3 节的实验中均分别将Merkle Puzzles 使用的文件数量和执行sPAKE 协议的次数设定为20 个和5 次。

首先，本节使用不同大小的测试文件对这4 种情况下的数据加密上传的时间开销进行了评估，如图7 所示。从图7 可以看出，当数据变得流行后，数据加密上传的时间开销明显降低。当测试文件的大小为1 024 MB 时，流行数据上传的时间开销仅为不流行数据首次上传的42.6%。流行度转换的时间开销较高，原因在于流行度转换过程中需要生成随机密文以进行密钥验证和密文验证，并且需要加密上传收敛密文至云服务器。但是在数据上传过程中，系统大概率仅需进行一次流行度转换过程。因此，这一过程的时间开销对大多数用户的影响较小。

图7 不同文件大小对数据加密上传的时间开销的影响

本节还统计了数据加密上传的时间开销中的各部分占比情况，如图8 所示，其中，P、UP_F、UP_S 和Conv 分别表示流行数据上传、不流行数据首次上传、不流行数据后续上传和流行度转换4 种情况。由图8 可知，对于流行数据上传而言，收敛加密占比极高，约占81%。在其他3 种情况中，数据加密（收敛加密+随机加密）的时间开销分别占总开销的66%、50%和49%。在不流行数据后续上传和流行度转换过程中，用户需要在密钥验证过程中计算随机密文的哈希值，这部分的时间开销占比较高，约占总开销的20%。方案中引入的所有权证明和sPAKE 协议的时间开销相对于其他部分占比较低，在不流行数据后续上传和流行度转换的过程中占比均约为9%。

图8 数据加密上传的时间开销中各部分的占比情况

本节还评估了执行不同次数sPAKE 协议对数据加密上传的时间开销的影响，如图9 所示。从图9可以看出，不同次数sPAKE 协议的执行对不流行数据后续上传的时间开销的影响有限。当测试文件的大小为1 024 MB，执行5 次sPAKE 协议时，不流行数据后续上传的时间开销约为执行160 次sPAKE协议时的时间开销的90%，二者差距不大。

图9 执行不同次数sPAKE 协议对数据加密上传的时间开销的影响

7.2.3 与现有方案的性能对比

本节对比分析了本文方案与文献[6,8]方案的不流行数据加密上传的时间开销，如图10 所示。由于本文方案未部署第三方服务器，引入了sPAKE、Merkle Puzzles 以及密钥/密文验证等过程，因此与现有方案相比增加了一些计算开销。本文方案的不流行数据上传分为首次上传和后续上传，文献[6,8]方案中不流行数据上传不区分首次上传和后续上传。本文方案的首次上传过程并未引入过多的计算开销，但后续上传过程中需要进行密钥传递和密钥验证的过程，与现有方案相比增加了一定的计算开销。当测试文件大小为1 024 MB 时，与现有方案相比，本文方案的不流行数据首次上传和后续上传分别增加了约1%和13%的时间开销。

图10 不同方案的不流行数据加密上传的时间开销

8 结束语

本文提出了一个无第三方服务器的基于数据流行度的加密去重方案，在不需要部署任何第三方服务器的情况下实现了数据流行度的精确统计，并为不流行数据提供了语义安全和加密去重。首先，基于CM-sketch 算法实现了数据流行度的初步统计；然后，基于Merkle Puzzles 协议实现了数据流行度的精确统计；最后，通过用户间执行sPAKE 协议实现了不流行数据的客户端加密去重。本文还考虑了加密去重场景下常见的字典攻击、文件伪造攻击和所有权欺骗攻击等，在所提方案中设计了密钥验证和密文验证的过程，并结合了速率限制和所有权证明等过程为用户数据提供了全面的安全保障。如何进一步提高方案的数据加密上传的性能是接下来需要研究的重要课题。