随着大数据时代的到来, 作为基础设施的云存储服务变得愈加重要.在云服务持续高速度发展的背景下, 服务提供商不再局限于一味地堆积硬件, 而是逐步通过尽可能提高存储效率的方式, 达到“无形”增加存储空间并换取经济效益的目的.目前, 提高存储效率的技术主要包括数据压缩和重复数据删除.数据压缩技术虽然能够通过对整体数据重新编码, 实现存储空间的更少占用, 但由于压缩后的数据需要在解码后才可正常使用, 这无疑增加了系统的计算负担.重复数据删除技术的思想是通过摒除数据的重复存储, 进而减少存储冗余^{[1, 2]}.生而逢时, 在如火如荼发展的云计算和大数据应用场景中, 同一数据副本时常被不同用户重复存储, 造成巨量存储空间浪费, 重复数据删除技术恰成为解决该问题的最佳方法.经最新研究表明:重复数据删除技术可以在备份应用系统中减少高达90%的存储需求, 在标准文件系统中使存储需求降低约70%^[3].

良好的云存储系统应能够为用户提供安全的数据存储环境, 然而在实际应用中, 云服务提供商并非完全可信.例如, Facebook在2013年泄露了用户的联系信息^[4], iCloud在2014年泄露了用户的私密照片^[5].数据加密是解决此类风险的良好选择, 然而由于数据的加密密钥由用户在本地独立生成, 密钥的多样性导致相同数据副本被加密为不同密文, 使得云服务提供商无法识别数据是否重复, 造成大量存储冗余.如何对加密后的数据执行重复安全删除, 是云存储安全领域的研究热点之一.

起初, 研究者提出由云服务商提供唯一密钥并执行加密操作, 如此, 数据控制权依然驻留在云服务商中, 虽然能够抵抗外部敌手攻击, 但无法防止数据由服务商内部泄露.Douceur等研究者提出客户端收敛加密(convergent encryption, 简称CE)方法^[6].计算数据副本的哈希值并将其作为加密密钥, 此时输入同一数据副本即可得到相同数据密文^{[7, 8]}.收敛加密虽拥有较高的执行效率, 却未实现语义安全, 容易遭受离线暴力破解攻击^{[9, 10]}. Bellare等研究者提出信息锁加密方案(message-locked encryption, 简称MLE)^[11], 虽复杂化了密钥计算与加密方式, 但与CE相比, 其核心思想无变化, 因此同样无法实现语义安全^{[12, 13]}.Bellare等研究者提出了DupLESS^[14], 相同数据的不同属主与可信第三方运行茫然伪随机函数计算协议(oblivious pseudorandom function, 简称OPF), 用以输出相同加密密钥.Duan等研究者对DupLESS进行扩展与改进, 对可信第三方的任务进行分解, 将密钥生成过程的参与方扩展为多个用户^[15].文献[14, 15]中的方案无法抵抗云服务器在线穷举攻击.Puzio等研究者提出首个基于双层加密的重复加密数据删除方案ClouDedup^[7], 内层是高效的收敛加密, 外层加密与解密工作外包给可信第三方.除了安全性的提高, 双层加密带来的还有高额的计算开销与通信开销.与文献[14, 15]相似, ClouDedup无法防止云服务商与第三方的合谋攻击.Stanek等人提出:用户在上传数据之前需要确定数据的类型, 若数据属主数量低于预定义流行度阈值, 则该数据副本将被定义为非流行数据; 反之, 则将其标记为流行数据^[17].非流行数据采用双层加密.随着数据副本数量不断增加, 当等于阈值后, 云服务商便进行外层解密, 进而借助内层收敛加密的特性, 执行重复数据删除.同时, 为了抵抗敌手进行女巫攻击^{[16, 18]}, 引入身份服务器.与文献[7]中的方案类似, 多方服务器的引入带来高额的计算与通信开销.Puzio等研究者基于完美哈希函数(PHF)设计了数据流行度查询算法, 依赖第三方的协助, 查询数据副本流行度, 并根据查询结果执行相应的加密算法^[19].该方案无法解决非流行加密数据重复删除的问题^[3], 且与文献[14, 15, 17]类似, 可信第三方实体必须实时在线参与, 然而在实际应用中, 部署完全可信的第三方比较困难.Liu等研究者设计首个无可信第三方参与的加密数据重复删除方案, 使用口令认证密钥交换协议(password authenticated key exchange, 简称PAKE)传递密钥, 相同数据副本属主能够计算得到同一加密密钥^[9].方案的不足点在于, 参与方必须实时在线, 导致系统的可行性与实用性较低.

本文贡献:

本文在划分数据类型的基础上, 提出一种无需初始数据上传用户与可信第三方实时在线的加密数据重复删除方案.

1) 基于椭圆曲线构造流行度查询标签, 在语义安全的前提下, 使用该标签验证加密副本是否产生于同一明文, 并判断其流行度.借助密文策略属性加密, 保证查询标签生成协议的安全实现;

2) 设计安全的密钥共享协议, 确保同一数据副本的初始属主能够借助云服务商, 将加密密钥安全离线共享至后继属主, 实现非流行数据重复删除.构造新的流行数据加密算法, 增强流行数据的存储安全;

3) 总结常见的敌手模型, 通过安全分析证明本方案可抵御敌手模型中的恶意攻击.

1 系统设计与敌手模型 1.1 系统模型

如图 1所示, 本系统共包含3类实体:密钥生成中心(KDC)、用户群(users)与云服务器(CSP).系统建立初期, KDC为用户生成密钥对集合, 并将随机值密文参数集合部署在云服务器, 然后转入离线状态.云服务器为用户提供数据的在线存储与共享服务, 且具有删除重复加密数据的功能.

1.2 设计目标

本方案需要满足以下性质.

1)   有效性

a)   云服务器能够识别重复的加密数据, 并判断数据类型(非流行数据或流行数据), 根据数据类型采取相应加密算法;

b)   数据初始上传者能够将加密密钥通过云服务器, 以离线的方式传递给后继上传者;

c)   云服务器能够执行加密数据重复删除.

2)   安全性

a)   使用椭圆曲线生成的查询标签识别数据冗余度与流行度, 识别过程不泄漏数据的任何明文信息;

b)   初始上传者将加密密钥以密文形式存储在云服务器, 但云服务器无法对其解密;

c)   客户端加密数据重复删除与云服务器端重复数据删除混合使用, 防止侧信道攻击.

3)   高效性

a)   保证流行度查询标签生成算法和密钥传递算法的高效性;

b)   针对不同流行度数据, 采用不同加密算法, 在确保安全性的前提下, 提高系统执行效率.

1.3 敌手模型

在数据安全需求方面, 用户假定云服务提供商是不可信的; 用户在系统效率方面的要求与云服务提供商的存储成本存在一定矛盾.因此, 本文不考虑用户与云服务器合谋攻击.由于在重复数据删除方案中, 侧信道攻击主要针对客户端重复数据删除(穷举并上传文件, 观察是否发生重复数据删除), 而本方案只对隐私度比较低的流行数据使用客户端重复数据删除, 因此侧信道攻击问题不是本文的研究重点.

本文的敌手有以下两类.

1) 云服务提供商

云服务提供商能够按照系统所设计的协议与用户执行所有的交互, 可以访问或复制用户存储在云服务器上的加密数据、查询标签等所有信息, 因此可以对查询标签与加密数据执行离线穷举攻击, 其攻击方式为:猜测穷举某数据内容的所有可能, 构造查询标签集合并与用户的查询标签进行比较, 验证猜测正确性, 最终获得数据内容.

2) 用户群中的恶意成员(恶意用户)

恶意用户拥有与合法用户完全相同的访问能力和权限, 掌握KDC分配的密钥对.其可能的攻击方式如下.

a)   劫持受害者与云服务器的通信信道, 假冒云服务器, 与受害者执行方案中的所有交互协议, 对受害者的查询标签执行离线穷举攻击, 即:穷举猜测某数据内容的所有可能, 构造查询标签集合并与用户的查询标签进行比较, 验证猜测正确性, 获得数据内容;

b)   执行在线穷举攻击, 穷举某数据内容的所有可能, 逐一构造查询标签并发送至云服务器, 根据云服务器的回复消息判断该数据是否已被存储在云服务器.

2 定义与预备知识 2.1 具有离线密钥传递的云加密数据安全重复删除方案

本方案共包含以下4种算法.

a)   SystemSet:系统初始设置算法.KDC为用户生成属性密钥对, 并为云服务器部署密文参数;

b)   PopularityCheck:流行度查询算法.由用户与云服务器共同完成.持有相同数据的用户, 可以在不泄露任何数据内容的情况下获得相同的查询标签, 进而查询数据流行度;

c)   UnPopularDedup:非流行加密数据重复删除算法.由用户与云服务器共同完成.云服务器存储首次上传的加密数据; 若云服务器检测到冗余数据被上传, 则将其删除, 并为当前用户创建数据的访问链接;

d)   PopularUpload:流行加密数据重复删除算法.由用户与云服务器共同完成.若拥有某数据的用户数量等于流行度阈值, 则用户上传收敛加密密文; 若大于流行度阈值, 则执行客户端重复数据删除, 即:用户无需实际上传加密数据, 云服务器会为其创建数据的访问链接.

2.2 有限域上的椭圆曲线

定义有限域GF(P), 其特征P≠2, 3, 参数a, b∈GF(P)满足4a³+27b²≠0.

定义满足等式y²=x³+ax+b的点(x, y)∈GF(P)×GF(P)与无穷远点O构成的集合为椭圆曲线E_{(a, b)}(GF(P))^[20-23].

在下面定义的加法运算下, 这些点可构成Abelian群:O是恒等元, 假设M, N为E_{(a, b)}(GF(P))上的两个点, 若M=O, 则-M=O, M+N=N+M=N; 设定M=(x₁, y₁), N=(x₂, y₂), 则-M=(-x₁, -y₁), 且M+N=O; 若M=-N, 则M+N=(x₃, y₃), 其中,

${x_3} = {\mu ^2} - {x_1} - {x_2}, {y_3} = \mu ({x_1} - {x_3}) - {y_1}, \;\mu = \left\{ {\begin{array}{*{20}{l}} {\frac{{3x_1^2 + a}}{{2{y_1}}}, {\rm{ }}M = N} \\ {\frac{{{y_2} - {y_1}}}{{{x_2} - {x_1}}}, {\rm{ }}M \ne N} \end{array}} \right..$

2.3 密文策略属性加密

安全的基于密文策略属性加密(CP-ABE)方案通常包含以下算法^[24-26].

a)   Setup(λ)→〈PK, MS〉:系统初始化.输入安全参数λ, 输出密钥对〈PK, MS〉;

b)   Encrypt(PK, F, S)→C_S:加密算法.输入公钥PK, 消息F, 访问结构S, 输出密文C_S;

c)   $KeyGen(MS, PK, A{T_i}) \to SKA{T_i}$:私钥生成算法.输入主密钥MS, 公钥PK, 用户的属性集合AT_i, 输出用户私钥SK_ATi;

d)   Decrypt(PK, SK, C_S)→F:解密算法.输入公钥PK, 用户私钥SK, 密文C_S, 其中, 访问策略隐含在C_S中.当且仅当AT_i∈S, 才能解密得到消息F^{[27, 28]}.

3 具有离线密钥传递的云加密数据安全重复删除方案 3.1 方案概述

系统建立初始, KDC通过SystemSet算法为每个注册用户生成属性加密算法的公私钥对, 并将密文参数集合部署到云服务器.在PopularityCheck算法中, 用户发送数据短哈希值至云服务器, 以获取生成查询标签所需要的参数值, 并使用椭圆曲线计算流行度查询标签, 用以查询数据的流行度.在此之后, 云服务器将查询结果回传至用户, 并与用户执行UnPopularDedup或PopularUpload, 其中, UnPopularDedup表示非流行加密数据重复删除算法, PopularUpload表示流行加密数据重复删除算法.

3.2 SystemSet

1)   KDC执行以下算法生成密钥对〈PK, MS〉.

a)   生成公共元素{q, G₁, G₂, g, e}, 其中, G₁与G₂表示两个乘法循环群, q与g分别表示G₁的阶与某一生成元, e:G₁×G₁→G₂表示双线性映射;

b)   选择哈希函数H:{0, 1}^*→{0, 1}^m, 并随机选择$T \in Z_q^{2 \times m}$, 其中, $T = \left( {_{{t_{1, 1}}\;...\;{t_{1, m}}}^{{t_{0, 1}}\;...\;{t_{0, m}}}} \right), \;m \in N$;

c)   选取y∈Z_q, g₁∈G₁, 计算Y=(g, g₁)^y与g^T, 其中, ${g^T} = \left( {_{{g^{{t_{1, 1}}}}\;...\;{g^{{t_{1, m}}}}}^{{g^{{t_{0, 1}}}}\;...\;{g^{{t_{0, m}}}}}} \right)$;

d)   定义公钥PK={q, G₁, G₂, g, e, g₁, Y, g^T, H}, 主秘密MS={y, T}.

2)   用户群${\{ {U_i}\} _{i \in [1, Nu{m_U}]}}$通过以下算法1获取各自私钥, 其中, Num_U表示用户数量.

算法1.  私钥生成算法.

Input:KDC主秘密MS, 用户${\{ {U_i}\} _{i \in [1, Nu{m_U}]}}$的属性集合$S = {\{ A{T_i}\} _{i \in [1, Nu{m_U}]}}$;

Output:${\{ {U_i}\} _{i \in [1, Nu{m_U}]}}$的私钥集合${\{ S{K_{A{T_i}}}\} _{i \in [1, Nu{m_U}]}}$.

1:  For i=1 to Num_U do

2:    用户U_i发送属性集合AT_i至KDC;

3:    KDC计算h=H(at₁||at₂||…||at_n), at_j∈AT_i;     //H表示密码哈希函数, j∈[1, n], n表示U_i的属性个数;

4:    KDC随机选择z∈Z_q, 生成解密密钥$S{K_{A{T_i}}} = \{ S{K_{i1}}, \;S{K_{i2}}\} = \left\{ {g_1^y{{\left( {\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}, i}}}}} } \right)}^z}, {g^z}} \right\}$;

5:  Return $\left\{S K_{A T_{i}}\right\}_{i \in\left[1, N u m_{U}\right]}$;

3)   KDC通过以下方式得到密文参数集合, 并将其部署在云服务器.

a)   生成随机数向量集合:${\{ {N_r} = \langle {\lambda _r}, {\mu _r}\rangle \;\} _{r \in [1, Nu{m_U}]}}$与${\{ {R_r} = \langle {\theta _r}, {\omega _r}\rangle \} _{r \in [1, Nu{m_U}]}}$;

b)   计算${\{ {N_r} - {R_r}\; \} _{r \in [1, Nu{m_U}]}}$;

c)   通过算法2加密${(\{ {N_r} - {R_r}\;\} , \{ {R_r}\} )_{r \in [1, Nu{m_U}]}}$, 得到${\left( \begin{gathered} \{ {X_{r1}} = Encrypt(PK, S, {N_r} - {R_r})\} \\ \{ {X_{r2}} = Encrypt(PK, S, {R_r})\} \\ \end{gathered} \right)_{r \in [1, Nu{m_U}]}}$,

其中, Encrypt(·)表示公钥加密算法.

算法2.  属性加密算法.

Input:随机数向量集合({N_r-R_r}, {R_r})_i∈_{[1, Num]}, 公钥PK, 访问结构S;

Output:随机值密文集合({X_r1=Encrypt(PK, S, N_r-R_r)}, {X_r2=Encrypt(PK, S, R_r)})_i∈_{[1, Num]}.

1:  For r = 1 to Num_U do

2:  计算h=H(s₁||s₂||…||s_n), s_i∈S;

3:  随机选择ε∈Z_q, $\partial$∈Z_q, 计算$\left(\begin{array}{l} {C_{r1, 1}} = ({N_r} - {R_r}) \cdot {Y^\varepsilon }, {C_{r1, 2}} = {g^\varepsilon }, {C_{r1, 3}} = {\left({\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}}}, i}}} } \right)^\varepsilon }\\ {C_{r2, 1}} = {R_r} \cdot {Y^\partial }, {C_{r2, 2}} = {g^\partial }, {C_{r2, 3}} = {\left({\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}}}, i}}} } \right)^\partial } \end{array} \right)$;

            //其中, h_i表示h的第i比特, h_i∈{0, 1};

4:  Return ({X_r1=(S, C_{r1, 1}, C_{r1, 2}, C_{r1, 3}), X_r2=(S, C_{r2, 1}, C_{r2, 2}, C_{r2, 3}))_i∈_{[1, Num]};

3.3 PopularityCheck 3.3.1 获取生成查询标签所需随机数

U_i选取短哈希函数SH, 计算数据F_i的短哈希值sh_i=SH(F_i), 并发送sh_i至云服务器(短哈希函数具有较高的碰撞率, 相同数据的短哈希值必定相同, 不同数据的短哈希值可能相同).

1) 若云服务器中存在与sh_i相同的短哈希值$s{h'_i} = SH({F'_i})$, 则U_i可能为数据${F'_i}({F_i})$的后继上传者, 其中, ${F'_i}$表示${U'_i}$上传的数据, 执行以下操作.

a)   云服务器将与${F'_i}$关联的信息发送至U_i.该信息包含${\eta '_i}$与$\left( \begin{gathered} {{X'}_{i1}} = Encrypt(PK, AT, {{N'}_i} - {{R'}_i}) \\ {{X'}_{i2}} = Encrypt(PK, AT, {{R'}_i}) \\ \end{gathered} \right)$, 其中, ${\eta '_i}$表示云服务器为${U'_i}$选定的随机数; ${X'_{i1}} \in \{ {X_{r1}}\} , {X'_{i2}} \in \{ {X_{r2}}\} $表示云服务器为${U'_i}$选取的密文参数(如前文所述, 密文参数集合来自KDC, 云服务器无法获得明文信息);

b)   U_i设定${\eta _i} = {\eta '_i}$, 通过以下方法解密${X'_{i1}}$与${X'_{i2}}$, 其中, Decrypt(·)表示公钥加密中的解密算法:

$\begin{gathered} \langle {{\lambda '}_i} - {{\theta '}_i}, {{\mu '}_i} - {{\omega '}_i}\rangle = Decrypt(PK, S{K_i}, {{X'}_{i1}}) = \frac{{{{C'}_{i1}} \cdot e({{C'}_{i1, 3}}, S{K_{i2}})}}{{e({{C'}_{i1, 2}}, S{K_{i1}})}}, \\ \langle {{\theta '}_i}, {{\omega '}_i}\rangle = Decrypt(PK, S{K_i}, {{X'}_{i2}}) = \frac{{{{C'}_{r2, 3}} \cdot e({{C'}_{r2, 3}}, S{K_{i2}})}}{{e({{C'}_{r2, 3}}, S{K_{i1}})}}; \\ \end{gathered} $

c)   U_i计算$\langle {\lambda '_i} - {\theta '_i}, {\mu '_i} - {\omega '_i}\rangle + \langle {\theta '_i}, {\omega '_i}\rangle $得到随机数向量$\langle {\lambda '_i}, {\mu '_i}\rangle , $并设定$\langle {\lambda _i}, {\mu _i}\rangle = \langle {\lambda '_i}, {\mu '_i}\rangle $.

注意:若存在N_max个短哈希值与sh_i相同, 则以上操作执行N_max次, 即, 设定${\{ \langle {\eta _{i, j}}, \;{\lambda _{i, j}}, {\mu _{i, j}}\rangle \} _{j \in [1, {N_{\max }}]}}$为生成流行度查询标签所需参数.

2) 若云服务器无法查找出相同的短哈希值, 则U_i是数据F_i的初始上传者.

a)   云服务器从密文参数集合{X_r1}, {X_r2}(r∈[1, n])中随机选择X_a1∈{X_r1}与X_b2∈{X_r2}(a≠b), 另外生成随机数η_i, 一起发送至U_i, 并将X_a1, X_b2与U_i关联;

b)   U_i解密X_a1与X_b2得到:

$\begin{gathered} \langle {\lambda _a} - {\theta _a}, {\mu _a} - {\omega _a}\rangle = Decrypt(PK, S{K_i}, {X_{a1}})\; = \frac{{{C_{a1, 1}} \cdot e({C_{a1, 3}}, S{K_{i2}})}}{{e({C_{a1, 2}}, S{K_{i1}})}}, \\ \langle {\theta _b}, {\omega _b}\rangle = Decrypt(PK, S{K_i}, {X_{b2}}) = \frac{{{C_{b2, 1}} \cdot e({C_{b2, 3}}, S{K_{i2}})}}{{e({C_{b2, 2}}, S{K_{i1}})}}; \\ \end{gathered} $

c)   U_i计算〈λ_a-θ_a, μ_a-ω_a〉+〈θ_b, ω_b〉得到随机数向量〈λ_i, μ_i〉=〈λ_a-θ_a+θ_b, μ_a-ω_a+ω_b〉, 设定$\left\langle\eta_{i, j}, \lambda_{i, j}, \mu_{i, j}\right\rangle_{j=0}$为生成流行度查询标签所需参数, 由于云服务器未找到相同的短哈希值, 因此将j设定为固定值0.

3.3.2 流行度查询

U_i使用随机数向量集合${\{ \langle {\eta _{i, j}}, \;{\lambda _{i, j}}, \;{\mu _{i, j}}\rangle \} _{j \in [0, {N_{\max }}]}}$(第3.3.1节中, 两种情况下j的取值分别为j∈[1, N_max]与j=0, 将二者合并得到j∈[0, N_max])与云服务器执行算法3, 以查询数据的流行度.

算法3.  流行度查询算法.

Input:U_i持有的随机值${\{ \langle {\eta _{i, j}}, \;{\lambda _{i, j}}, \;{\mu _{i, j}}\rangle \} _{j \in [0, {N_{\max }}]}}$;

Output:流行数据, 非流行数据.

1:  For j=0 to N_max do

2:    U_i计算$\left(x_{i, j}, y_{i, j}\right)=\eta_{i, j} \cdot A+\lambda_{i, j} \cdot A+\mu_{i, j} \cdot B$;     //A与B代表椭圆曲线上两个点;

3:    U_i计算盲化因子l_{i, j}=x_{i, j} mod n, 并计算密文C_{i, j}=H(F_i+l_{i, j});

4:  U_i计算${\bar C_{i, j}} = {C_{i, j}} - {\mu _{i, j}}$, 并将其发送至云服务器;

5:  For j=0 to N_max do

6:  云服务器计算${\sigma _{i, j}} = {\eta _{i, j}} - S{K_{CSP}} \cdot {\bar C_{i, j}}$;       //SK_CSP表示云服务器私钥;

7:    If云服务器中存有与σ_{i, j}相同的值

8:          计算$\sigma_{i, j}^{\prime}\left(\sigma_{i, j}\right)$的数量, 并将其记作${Count}_{\sigma_{i, j}}$;

9:          设定${Num}_{\sigma_{i, j}}={Count}_{\sigma_{i, j}}$;

10:  Else

11:          设定$Nu{m_{{\sigma _{i, j}}}} = 0$;

12: If $Nu{m_{{\sigma _{i, j}}}} < T$    //其中, T表示系统设定流行度阈值;

13: Return非流行数据;     //云服务器与U_i执行非流行加密数据重复删除算法UpopularDedup.

14: Else

15:    Return流行数据;     //云服务器与U_i执行流行加密数据重复删除算法PopularDedup.

3.3.3 UnpopularDedup

1)   假设云服务器中存在${\sigma _{i, j}} = \;{\sigma '_{i, j}}$, 即${F_i} = {F'_i}$, 则U_i是F_i的后继上传者(假设${U'_i}$为${F'_i}$的初始上传者).

a)   云服务器将${L'_i} = E({k'_{i, j}}, K{F'_i} - H({F'_i}))$发送至U_i, 其中, E(·)为对称加密算法, ${k'_{i, j}} = {y'_{i, j}}\bmod n$表示${U'_i}$为保护数据${F'_i}$的加密密钥${K'_{{F_i}}}$而选取的密钥, ${y'_{i, j}}$由${U'_i}$在执行PopularityCheck时计算得出;

b)   由PopularityCheck协议可知${k_{i, j}} = {k'_{i, j}} \leftarrow {y_{i, j}} = {y'_{i, j}} \leftarrow {\sigma _{i, j}} = {\sigma '_{i, j}}$.U_i使用k_{i, j}解密${L'_i}$得${K'_{{F_i}}} - H({F'_i})$.由于$H({F_i}) = H({F'_i}) \leftarrow {\sigma _{i, j}} = {\sigma '_{i, j}}$, 因此${K_{{F_i}}} = {K'_{{F_i}}} - H({F'_i}) + H({F_i})$;

c)   U_i使用${K_{{F_i}}}$对F_i加密得到$E({K_{{F_i}}}, {F_i}\;)$.由于${K_{{F_i}}} = {K'_{{F_i}}}$且${F_i} = {F'_i}$, 因此$E({K_{{F_i}}}, {F_i}) = E({K'_{{F_i}}}, {F'_i})$.故云服务器删除$E({K_{{F_i}}}, {F_i})$.

2)   若云服务器中不存在任何查询标签与σ_{i, j}相同, 则执行以下协议.

a)   云服务器随机选择用户U_z的${L_z} = E{({k_z}, {K_{{F_z}}} - H({F_z}))_{z \in [1, Nu{m_U}]}}$, 并将其发送至U_i, 其中, F_z(U_z上传的数据)与F_i的短哈希值相同, 但长哈希值不同, 即$s h_{z}=s h_{i} \wedge H\left(F_{z}\right) \neq H\left(F_{i}\right)$;

b)   由PopularityCheck可知y_{z, j}=y_{i, j}←sh_z=sh_i.因此, U_i使用k_{i, j}=y_{i, j} mod n对L_z解密得到${K_{{F_z}}} - H({F_z})$;

c)   U_i使用${K_{{F_i}}} = {K_{{F_z}}} - H({F_z}) + H({F_i})$(由于H(F_z)≠H(F_i), 因此${K_{{F_i}}} = {K_{{F_z}}} - H({F_z}) + H({F_i}) \ne {K_{{F_z}}}$)对F_i加密得到密文$E({K_{{F_i}}}, {F_i})$;

d)   U_i将$E({K_{{F_i}}}, {F_i})$存储在云服务器.

3.3.4 PopularDedup

1)   若$Nu{m_{{\sigma _{i, j}}}} = T$, 则F_i正由非流行数据向流行数据转换.

a)   U_i计算数据F_i的哈希值H(F_i);

b)   U_i设定F_i的加密密钥为${K_{{F_i}}} = H({F_i}) + {y_{i, j}}\bmod n$;

c)   U_i使用${K_{{F_i}}}$加密数据F_i得到$E({K_{{F_i}}}, {F_i})$, 并将其上传至云服务器.

2)   若$Nu{m_{{\sigma _{i, j}}}} > T, $表示F_i已是流行数据.由于$E({K_{{F_i}}}, {F_i})$已被存储在云服务器, 用户不再执行上传操作, 即

采用效率更高的客户端加密数据重复删除(client-side deduplication).

4 安全分析与证明

结合前文所述的敌手模型, 本节从以下4个方面分析方案的安全性.

4.1 密文参数与查询标签安全性

1) 密文参数安全.

定理1.  若则属性加密方案中的解密算法(Decrypt)无法正常执行, 其中, AT_CSP表示云服务器属性集合, ⊭表示云服务器属性集合无法满足用户属性集合.

证明:由SystemSet可知:

●  密文:${X_{r1}} = (S, \; {C_{r1}} = ({N_r} - {R_r}) \cdot {Y^\varepsilon }, {C_{r2}} = {g^\varepsilon }, {C_{r3}} = {\left({\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}, i}}}}} } \right)^\varepsilon }$;

●  解密密钥:$S{K_{A{T_i}}} = \{ S{K_{i1}}, S{K_{i2}}\} = \left\{ {g_1^y{{\left( {\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}, i}}}}} } \right)}^z}, {g^z}} \right\}$.

由PopularityCheck可知$Decrypt(PK, S{K_i}, {X_{j1}}) = \frac{{{C_{j1}} \cdot e({C_{j3}}, S{K_{i2}})}}{{e({C_{j2}}, S{K_{i1}})}} = \frac{{{C_{j1}} \cdot e(Cj3, {g^z})}}{{e\left( {{C_{j2}}, g_1^y{{\left( {\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}, i}}}}} } \right)}^z}} \right)}}$.

若AT_CSP⊭S, 则${h_{CSP}} = H(a{t_{CS{P_1}}}||a{t_{CS{P_2}}}||...||a{t_{CS{P_n}}}) \ne H({s_1}||{s_2}||...||{s_n}) = h$, 即$g_1^y{\left( {\prod\limits_{i \in [1, m]} {{g^{{t_{{h_{CS{P_i}}}, i}}}}} } \right)^z} \ne g_1^y{\left( {\prod\limits_{i \in [1, m]} {{g^{{t_{{h_i}, i}}}}} } \right)^z}$, 因此, 云服务器无法解密X_r1.

同理, 云服务器无法解密X_r2.

2) 流行度查询标签安全.

云服务器虽持有σ_{i, j}与参数密文X_j1, X_j2, 然而, 由定理1可知, 云服务器无法解密X_j1, X_j2, 故只能通过以下方式穷举查询标签, 以猜测加密数据的明文信息.

a)   穷举数据集合{F_r}_r∈_{[1, n]};

b)   穷举随机参数值集合{x_t}_{t∈[1, n]};

c)   穷举随机参数值集合{μ_z}_{z∈[1, n]};

d)   计算标签集合{σ_CSP=η_i-SK_CSP·(H(F_r+x_t mod n)-μ_z)};

e)   将得到的结果与${\sigma '_i}$逐一比较, 其中, ${\sigma '_i} = {\eta _i} - S{K_{CSP}} \cdot (H({F_i} + {x_i} \bmod n) - {\mu _i})$, 观察是否存在相等值;

f)   若存在相等值, 则表明F_r=F_i.

然而, 由以上可知, 云服务器攻击的时间复杂度为O(n³).由于n可视为无限大值, 因此在实际应用中, 实现第e)步是极为困难的.

4.2 防止假冒云服务器的行为

以下为恶意用户U_D假冒云服务器与受害者U_i运行PopularityCheck算法的过程.

a)   U_i向云服务器发出执行PopularityCheck请求;

b)   U_D截获请求消息, 发送η_DG, X_D1, X_D2至t(a);

c)   U_i计算, 并将${C'_D}$发送至U_D;

d)   U_D将查询标签σ_D=η_D-d_D·C''发送至U_i;

e)   由于U_D持有η_DG, X_D1, X_D2, 因此可以对C_D采取离线穷举攻击, 即执行以下操作:

① 穷举数据{F_r}_{r∈[1, n]};

② 计算密文集合{C_r}={H(F_r+l_D)};

③ 与C_i逐一对比.若C_r=C_i, 则F_r=F_i.

解决方法:用户在与云服务器通信之前, 需要借助公钥基础设施(PKI)获取并验证云服务器身份, 借助PK_CSP协商会话密钥对通信内容加密.U_D便无法仿冒云服务器身份获取有用信息.

4.3 防止用户进行在线穷举攻击

定理3.  恶意用户U_D无法对云服务器中的非流行数据F_i执行在线穷举攻击.

证明:不失一般性, U_D的攻击方式为:

a)   U_D穷举数据{F_r}_{r∈[1, n]};

b)   U_D将穷举结果逐一与云服务器运行PopularityCheck和UnpopularDedup;

c)   云服务器根据是否存在等式${\sigma '_{i, j}} = {\sigma '_r}$回复U_D相应信息;

d)   U_D根据响应, 判断攻击是否成功.

由UnpopularDedup可知:

●  情况a:当F_r=F_i时, 云服务器将${L'_i} = E({k'_{i, j}}, {K'_{{F_i}}} - H({F'_i}))$回复给U_D;

●  情况b:若F_r为首次上传数据, 云服务器随机选择用户U_z的${L_z} = E{({k_z}, {K_{{F_z}}} - H({F_z}))_{z \in [1, Nu{m_U}]}}$发送至U_D.

由于两种情况下, U_D获得的伪随机数${K'_{{F_i}}} - H({F'_i})$和${K_{{F_z}}} - H({F_z})$的计算方式相同, U_D无法区分情况a与情况b, 故无法对存储在云服务器的非流行数据进行在线穷举攻击.

4.4 标签唯一性与正确性证明

1) 唯一性证明

由安全哈希算法H的抗碰撞性得到引理1.

引理1.  对于安全的哈希算法H, 若${F'_i} = {F_i}$, 则$H({F'_i}) = H({F_i})$的概率是可忽略的.我们采用ε表示可忽略值:

$Prob[H({F'_i}) \ne H({F_i})|{F'_i} = {F_i}] < \varepsilon .$

定理3.  若${F'_i} = {F_i}$, 则${\sigma '_{i, j}} \ne {\sigma _{i, j}}$的概率是可忽略的:$Prob[{\sigma '_{i, j}} \ne {\sigma _{i, j}}|{F'_i} = {F_i}] < \varepsilon .$

证明:

根据PopularityCheck可知:若$s{h'_i} = s{h_i}$, 则${\eta '_i}G = {\eta _i}G \wedge {X'_{i1}} = {X_{i1}} \wedge {X'_{i2}} = {X_{i2}}$, 故${l'_{i, j}} = {l_{i, j}} \leftarrow ({x'_{i, j}}, {y'_{i, j}}) = ({x_{i, j}}, {y_{i, j}})$.

由引理1可得:

$Prob[H({F'_i} + {l'_{i, j}}) \ne H({F_i} + {l_{i, j}})|{F'_i} = {F_i} \wedge {l'_{i, j}} = {l_{i, j}}] < \varepsilon $ .

因此, ${\bar C'_i} = {\bar C_i} \leftarrow {C'_i} = {C_i}$, 故${\sigma '_{i, j}} = {\sigma _{i, j}}$.换言之, 持有相同数据的不同用户, 生成流行度查询标签${\sigma _{i, j}}({\sigma '_{i, j}})$是唯一的.

2) 正确性证明

用户${U'_i}$已将数据${F'_i}$的流行度查询标签${\sigma '_{i, j}}$存储在云服务器.

当U_i与云服务器执行PopularityCheck时, 云服务器生成数据F_i的流行度查询标签σ_{i, j}, 并且判断${\sigma '_{i, j}} = {\sigma _{i, j}}$是否成立.

定理4.  若${\sigma '_{i, j}} = {\sigma _{i, j}}$, 则${F'_i} \ne {F_i}$的概率是可忽略的:

$Prob[{F'_i} \ne {F_i}|{\sigma '_{i, j}} = {\sigma _{i, j}}] < \varepsilon .$

证明:不失一般性, 由PopularityCheck可知σ_{i, j}=k_i-SK_CSP·(H(F_i+x_{t, j} mod n)-μ_{i, j}).

a)   若${\sigma '_{i, j}} = {\sigma _{i, j}}$, 则${\eta '_{i, j}} - S{K_{CSP}} \cdot (H({F'_i} + {x'_{i, j}} \bmod n) - {\mu '_{i, j}}) = {\eta _{i, j}} - S{K_{CSP}} \cdot (H({F_i} + {x_{i, j}} \bmod n) - {\mu _{i, j}})$;

b)   由于$s{h'_i} = s{h_i}$, 故${\eta '_{i, j}} = {\eta _{i, j}} \wedge {x'_{i, j}} = {x_{i, j}} \wedge {\mu '_{i, j}} = {\mu _{i, j}}$, 因此, $H({F'_i}) = H({F_i})$;

c)   根据引理1可得:若${\sigma '_{i, j}} = {\sigma _{i, j}}$, 则${F'_i} = {F_i}$.

证毕.

5 实验分析

实验采用C++语言, 借助OPENSSL^[29], GMP^[30], PBC^[31]和CP-ABE^[32]函数库实现了系统软件.以阿里云作为云服务提供商, 租用虚拟机配置为4Core CPU, 8GB内存, 1Mbps带宽, 1T存储空间.椭圆曲线基域大小设定为512bit, 域中元素大小为160bit.随机选取了2 500个文件存储在云服务器中.随机设定拥有每个文件的用户数量.设置流行度阈值为T=8, 非流行数据与流行数据的比例大致为3:4.

通过以下3组实验, 证明方案的高效性.

a)   上传大小为80MB的文件F_A, 计算本方案各阶段的时间开销;

b)   上传大小为10MB的文件F_B, 分别测试本方案与PerfectDedup方案^[19]的总时间开销;

c)   上传大小相同的文件, 比较本方案、文献[17]中的方案、文献[19]中的方案各自所需的存储开销.

实验中的每步操作重复执行20次, 取平均值作为实验结果.

1) 系统每阶段的时间开销.

将文件设定为以下3种情况:非流行数据($Coun{t_{{F_A}}} < T$)、流行度转换数据($Coun{t_{{F_A}}} = T$)与流行数据($Coun{t_{{F_A}}} > T$).分别测量3种情况下文件分块、查询标签生成、流行度查询、加密与上传各自所需要的时间开销.实验结果如图 2所示, 发生在用户端的文件分块、查询标签生成、加密所需要的时间开销较小.上传与流行度查询操作在云服务器端执行, 所需要的时间开销远远超过用户端.当$Coun{t_{{F_A}}} > T$时, 用户不再需要文件的加密与上传操作, 大幅减少了计算开销, 节省了网络带宽.

如何高效且安全地识别冗余数据, 是加密数据重复删除方案的基础.本文对较为优异的现有相关方案的生成查询标签算法进行了效率测试, 并与本方案比较.实验结果如图 3所示, 本方案在生成查询标签方面, 明显优于其他方案.

为达到语义安全, 本方案需要将初始上传属主的加密密钥安全共享至后继上传属主, 这会使数据加密算法产生部分额外通信与计算开销.然而, 由于密钥传递方式的设计较为高效, 因此它对加密算法的性能影响较小.本方案与CE^[6]的比较结果在表 1中给出, 其中, t(a)表示本方案在执行加密算法时产生的时间开销, t(b)表示执行收敛加密时产生的时间开销, t(b)-t(a)表示执行两种加密算法时产生时间开销的差值, $\frac{{t(b) - t(a)}}{{t(a)}}$表示以上差值为系统带来影响的大小.实验结果表明:二者加密算法所需的时间开销相差甚小; 且随着数据不断增大, 差值渐成为可忽略值.

2) 较少的总时间开销.

本方案与PerfectDedup方案^[19]所需要的总时间开销对比如图 4所示.与PerfectDedup相比, 由于本方案不需要进行第三方服务器的数据更新, 流行度查询阶段需要的时间开销较小, 因此在总时间开销方面, 本方案具有较明显的优势.

3) 占用更少的存储空间.

通过上传大小为500MB文件, 测试本方案、文献[17]中的方案、文献[19]中的方案各自占用云服务器中的存储空间情况, 实验结果如图 5所示.由于本方案支持非流行数据重复删除, 因此能够节省更多的存储空间.文件越大, 优势越明显.

4) 方案特点比较.

由上述实验可知, 摆脱实时在线第三方的依赖与划分数据流行度, 是减少方案计算开销与通信开销的有效方法.表 2分析了本方案与其他代表性方案是否具备上述两种方法的特点.

6 总结与展望

本文提出一种无需初始数据上传用户和可信第三方实时在线参与的加密数据重复删除方法.基于椭圆曲线构造流行度查询标签, 在语义安全的前提下, 使用该标签识别数据冗余度与流行度.借助密文策略属性加密, 保证查询标签生成协议与密钥共享协议的安全实现, 同一数据副本的初始上传用户能够借助云服务商, 将加密密钥安全离线共享至后继上传用户, 实现非流行数据重复删除.改进后的收敛加密算法, 能够使用户自行计算安全加密密钥, 不仅保证了流行数据的存储安全, 同时提高了云服务商消除流行重复加密数据的效率.本文最后进行了详细的安全性分析与效率评估, 并与其他现有方案对比, 证明本方案在满足语义安全的同时, 进一步提高了加密数据重复删除系统的执行效率.

在本文基础上设计具有动态更新数据所有权的安全加密数据重复删除方案, 是下一步的研究方向.