0 概述

2000年, SONG等人^[1]给出可搜索加密的概念, 即加密方建立关键字安全索引并与数据密文存储到云服务器平台, 用户可通过陷门查询包含关键字的密文数据, 实现对密文数据的直接操作, 但采用对称密钥加密数据, 需专门的安全信道传输对称密钥。文献[2]改进了SONG等人的工作, 采用解密方的公钥加密数据, 无需专门的安全信道传输密钥。文献[3]在云环境下提出了支持多服务器多关键字的可搜索加密方案, 多个服务器共同配合用户一次性提交的多个关键字搜索请求, 提高了密文检索的效率。文献[4]提出了支持搜索结果验证的公钥可搜索加密方案, 虽然该方案指出满足多用户请求的云存储环境, 但公钥密码体制中每一对公私钥是对应的, 公钥加密的数据仅由其对应的私钥才可解密, 无法真正实现多用户间的数据共享。

2005年, SAHAI等人^[5]给出了基于属性的加密方案，加密者用属性定义访问控制策略, 并在密文中嵌入该策略，只有属性满足访问控制策略的用户, 方可获得相应的数据, 开启了研究多用户数据共享的新研究领域。文献[6]结合属性加密技术与可搜索技术, 构造了基于属性的可搜索加密方案。文献[7-8]提出了可验证的属性基单关键字可搜索加密方案, 但都无法抵抗关键字猜测攻击。文献[9-10]提出了能够有效抵抗关键字猜测攻击的属性基可搜索方案, 但该方案未对检索结果进行验证。近年来, 新的支持可验证的多关键字搜索的属性基可搜索加密方案相继被提出^[11-12], 但均未考虑属性钥失效的非法用户越权访问的问题。文献[13]提出了支持属性撤销的可搜索加密方案, 但该方案计算开销过大。文献[14]提出了密文策略的属性撤销可搜索加密方案, 但该方案的搜索时间与属性个数线性正相关。文献[15]在文献[13]的基础上改进了文献[14]的不足, 但该方案需要完全可信的第三方验证搜索结果的正确性。

鉴于区块链技术具有防篡改、公开验证、去中心化等特点^[16]。文献[17]提出了基于区块链的单关键字可搜索加密方案。文献[18-19]基于区块链构造了可搜索加密方案, 但均不支持细粒度的用户访问。

本文提出一种混合存储属性基多关键字密文检索方案。通过将关键字索引与数据密文分别存储到区块链和云服务器上, 使数据检索空间缩小, 易于快速地在海量数据中查找所需数据，密钥加密后, 即可在公开信道传输。在此基础上，通过属性版本号撤销用户, 以防止属性变化身份失效的非法用户继续访问数据。

1 预备知识 1.1 符号说明

符号含义说明如表 1所示。

1.2 双线性映射

设G₁和G_T分别是两个阶为素数p的乘法循环群, 其中, g为G₁的一个生成元, 则双线性映射e:G₁×G₁→G_T满足以下3个性质:

1) 双线性:对于任意的a, b∈$\mathbb{Z}$_p^*, 有e(g^a, g^b)=e(g, g)^ab。

2) 非退化性:e(g, g)≠1。

3) 可计算性:对于群G₁中的任意两个元素g₁、g₂, 存在有效算法计算e(g₁, g₂)。

1.3 与门访问结构

在属性基密码体制中, 与门访问控制策略通常被定义为用户属性与访问控制结构之间的关联关系, 具体描述为:全局属性集合U={x₁, x₂, …, x_n}, 访问控制结构At={At=₁, At₂, …, At_n}, 当且仅当x_i=At_i, i∈[1, n]时, 称属性满足访问控制结构。

1.4 安全性理论假设

本文方案的安全性基于HDH问题、MDDH问题和CDH问题, 具体定义如下:

定义1(HDH问题)^[20]  设G是阶为素数p, 生成元为g的循环群, H:G→{0, 1}^l是一个哈希函数, 则G上的HDH问题指对于任意的a, b∈$\mathbb{Z}$_P^*, 给定参数H和(g, g^a, g^b, Z)∈(G)³×{0, 1}^l, 判断Z=H(g^ab)是困难的, 其中l为哈希函数H输出的二进制长度。

定义2(MDDH问题)^[21]  设G₁和G_T是阶为素数p的乘法循环群, g是群的G₁生成元。对于任意的a, b, c∈$\mathbb{Z}$_P^*, 给定(g, g^a, e(g, g)^b, e(g, g)^ab, e(g, g)^c)∈(G₁)²×(G_T)³, 判断e(g, g)^ab=e(g, g)^c是困难的。

定义3(CDH问题)^[22]  设G是阶为素数p的乘法循环群, g是群的G生成元。对于任意的a, b, c∈$\mathbb{Z}$_P^*, 给定(g, g^a, g^b, g^c)∈(G)⁴, 计算g^abc∈G是困难的。

2 基本方案

本文方案包含的实体主要有以下5个部分:

1) 数据属主:用对称密钥加密文档, 并上传到云服务器, 提取关键字生成索引, 并上传到区块链。

2) 云服务器:只存储文档密文。

3) 授权机构:生成系统公共参数和主密钥。

4) 区块链:存储关键字索引信息, 生成下载数据令牌。

5) 数据用户:生成陷门值, 解密相应文件。其中, 云服务器是诚实但好奇的; 区块链是完全可信的存储设备, 方案中仅用于存储关键字索引。

具体的系统模型如图 1所示。

3 具体方案

本文具体方案如下:

1) Setup(λ)→(GP, msk):授权机构执行, 输入安全参数λ。输出双线性映射参数(G, G, e, p, g), 其中, 素数p为乘法循环群G和G_T的阶, g为群G的生成元, e:G₁×G₁→G_T是双线性映射。定义哈希函数H₀:{0, 1}^λ→$\mathbb{Z}$_P^*, H₁:{0, 1}^λ→$\mathbb{Z}$_P^*, H₂:G→{0, 1}^λ, H₃:{0, 1}^2λ→$\mathbb{Z}$_P^*, H₄:G_T→{0, 1}^λ, H₅:{0, 1}^λ→{0, 1}^λ, H₆:{0, 1}^*→G。对于身份为IDu_i, 1≤i≤m的用户, 其属性集Atts=(a₁, a₂, …, a_n)中的每一个1≤a_i≤n, 随机选取β∈$\mathbb{Z}$_P^*, 计算T_i=g^βH₀(a_i)。随机选取φ∈$\mathbb{Z}$_P^*, 计算φ=e(g, g)^φ。保密系统主密钥msk= < β, φ, t_i, …, t_n>。公开系统公共参数GP= < G, G_T, e, p, g, g^β, φ, T₁, …, T_n, H₀, H₁, H₂, H₃, H₄, H₅>。

2) KeyGen(msk, Atts, IDu)→(sk, rk):授权机构执行, 输入系统主密钥msk、用户属性集Atts及用户身份集IDu。对每一个属性a_i∈Atts, 随机选取r_i∈$\mathbb{Z}$_P^*, 令$r=\sum\limits_{i=1}^{n}{{{r}_{i}}}$, 计算K=g^φ-r, L_i=g^{r_i/βH₀(a_i)}。对身份为IDu_i的用户, 随机选取v∈$\mathbb{Z}$_P^*, 计算F_IDui=g^vH₁(IDu_i), F′=g^v, F″_i=L_i⊕H₁(g^vH₁(IDu_i))。将属性密钥sk= < K, {L_i}, F′, F″_i>发送给用户; 将用户身份信息rk= < F′, {F_IDi}>广播到区块链。

3) Enc(GP, D, IDd)→CT:数据属主执行, 输入文档集D=(d₁, d₂, …, d_N)、文档标识符集IDd=(IDd₁, IDd₂, …, IDd_N)、系统公共参数GP。首先, 对每一个文档d_i, i∈[1, N]用对称加密算法Enc(·)和对称密钥k加密, 即C_i=Enc_k(d_i)⊕H₅(IDd_i)。其次, 随机选取μ∈{0, 1}^λ, 计算π=H₂(μ‖k), $\tilde C$₁=g^π, $\tilde C$₂=μ⊕H₃(φ^π), $\tilde C$₃=k⊕H₄(μ), $\bar C = {\left( {\prod\limits_{i = 1}^n {{T_i}} } \right)^\pi }$。最后, 输出授权密文集CT=(At, {C_i}, $\tilde C$₁, $\tilde C$₂, $\tilde C$₃, C), 并将其存储到云服务上。

4) Index(GP, IDd, W)→(In_W):数据属主执行。随机选取s∈$\mathbb{Z}$_P^*, 计算δ=g^s。若文档d_i, i∈[1, N]包含关键字(w₁, w₂, …, w_m), 则令δ_j=g^βsH₅(w_j), j∈[1, m]; 否则令δ_j=1。计算I_i=H₅(IDd_i), 令I=(I_i, …, I_N), 计算R=H₆($\tilde C$₁‖$\tilde C$₂‖$\tilde C$₃‖C₁‖, …, ‖C_N‖ C)^π, 将索引信息In_W=(δ, δ_j, I, R)广播到区块链上。

5) Trapdoor(W ′, sk)→Tk:用户执行, 输入属性钥sk及搜索关键字集W′。随机选择z∈$\mathbb{Z}$_P^*, 计算${\rm{t}}{{\rm{k}}_1} = \prod\limits_{i = 1}^\tau {{g^{az{H_5}\left( {{{w'}_i}} \right)}}} $, tk₂=g^z, K′=K^z, L′_i=L_i^z, F′_IDui=F_IDui^z, 输出搜索陷门Tk=(tk₁, tk₂, K′, L′_i, F′_IDi)。

6) Search(In_W, Tk)→I:区块链上的搜索者执行, 输入搜索陷门Tk和索引In_W。首先, 搜索者通过式(1)检验陷门中用户身份与索引中用户身份是否相同; 然后, 通过式(2)检验陷门中关键字与索引中关键字是否相同; 若式(1)和式(2)同时成立, 则将I=(I₁, I₂, …, I_N)返回给用户; 否则输出⊥。

$ e\left( {{F_{{\rm{ID}}{u_i}}}, {\rm{t}}{{\rm{k}}_2}} \right){\rm{ = }}e\left( {{{F'}_{{\rm{ID}}{u_i}}}, g} \right) $

(1)

$ e\left( {\prod\limits_{i = 1}^\tau {{g^{\beta z{H_5}\left( {{{w'}_i}} \right)}}} , {g^s}} \right) = e\left( {\prod\limits_{i = 1}^\tau {{g^{\beta s{H_5}\left( {{w_j}} \right)}}} , {g^z}} \right) $

(2)

7) Dow(GP, I)→CT:云服务执行。输入公共参数GP、索引I。云服务器计算式Enc_k(d_i)=C_i⊕H₅(IDd_i)，并将所得结果Enc_k(d_i)返回给用户。

8) Verify(R, CT):用户输入CT和R, 计算式(3)验证搜索结果的正确性, 若等式成立转入步骤(9);否则, 输出⊥。

$ e\left( {{{\tilde C}_1}, {H_6}\left( {{{\tilde C}_1}\left\| {{{\tilde C}_2}} \right\|{{\tilde C}_3}\left\| {{C_i}} \right\|\bar C} \right)} \right) = e\left( {g, R} \right) $

(3)

9) Dec(CT)→(D):用户执行, 输入搜索密文Enc_k(d_i), 用户属性钥sk。首先, 身份为IDu_i用户通过计算H₁(F′^H₁(IDu_i)), 恢复出L_i=F″⊕H₁(F′^H₁(IDu_i))。若用户的属性满足访问结构, 则可通过式(4)计算得到E, 进而通过式(5)和式(6)计算得到对称密钥k, 解密出原始密文; 否则终止算法。

$ E = e\left( {{{\tilde C}_1}, K'} \right) \cdot e\left( {\prod\limits_{i = 1}^n {{L_i}, \bar C} } \right) = e{\left( {g, g} \right)^{\pi \varphi }} $

(4)

$ \mu = {\tilde C_1} \oplus {H_2}\left( E \right) $

(5)

$ k = {\tilde C_2} \oplus {H_3}\left( \mu \right) $

(6)

10) Rev(V):授权机构检测到用户属性改变时, 会更新用户版本号信息(i, v′, F′_IDui), 并向全网广播。用旧版本号信息(i, v, F_IDui)生成的私钥, 无法计算有效的私钥组件F″=b⊕H₁(g^vH₁(IDu_i)), 从而实现用户撤销。

4 安全性分析 4.1 抗用户合谋攻击

在用户的私钥中同时嵌入用户属性和用户版本号。因版本号的不同, 即使拥有相同属性集合的用户, 他们的私钥也不会相同。用户间私钥合谋生成搜索陷门, 该陷门也无法通过区块链上搜索者的验证, 用户间合谋也得不到额外信息, 本文方案满足抗用户间的合谋攻击。

4.2 私钥传输

定理1  若HDH问题是困难的, 则本文方案私钥的传输无需安全信道。

证明  根据HDH问题的定义:已知g^v和g^H₁(IDu_i), 在v和H₁(IDu_i)未知的前提下, 判断H₁(g^vH₁(IDu_i))是否为群G中的元素是困难的。进而, 求解私钥组件L_i=sk₂⊕H₁(g^vH₁(IDu_i))是困难的, 因此私钥的传输无需安全信道。

4.3 对称密钥安全性

文档上传云服务器前, 先用传统的对称算法加密, 再用属性加密算法加密对称密钥。本文方案基于MDDH问题确保对称密钥的安全性。

定理2  若MDDH问题是困难的, 则本文方案在随机预言模型下对称密钥是安全的。

证明  挑战者B输入MDDH问题的实例(g, g^π, e(g, g)^φ, Z)和群参数(g, p, e, G, G_T), 目标是计算Z=e(g, g)^πφ挑战者B和敌手A进行如下游戏模拟:

初始化:A提交挑战访问结构A^*=Λ_i∈IW^*A_i给挑战者B, 运行系统建立算法, 将公共参数GP= < e, p, g, g^β, φ, T₁, T₂, …, T_n, H₀, H₁, H₂, H₃, G, G_T>返回给A。

1) H₀询问:B维护一个初始为空的列表L₀= < a_i, h₀>。A向B请求属性a_i的哈希H₀值。B查询L₀表。若a_i∈L₀, B将相应的h_i=H₀(a_i)返回给A; 否则, B随机选取c_i∈$\mathbb{Z}$_P^*, 计算h₀=c_i, 并将(a_i, c_i)该属性添加到L₀。

2) H₁询问:B维护一个初始为空的列表L₁= < IDu_i, h₁>。A向B请求身份IDu_i的哈希H₁值。B查询L₁表。若IDu_i∈L₁, B将相应的h_i=H₀(IDu_i)返回给A; 否则, B随机选取c_i∈$\mathbb{Z}$_P^*, 令h₁=c_i, 并将(IDu_i, c_i)添加到L₁中, 然后发送h₁给敌手A。

3) H₂询问:B维护一个初始为空的列表L₂= < R₂, h₂>。A向B询问R₂∈{0, 1}^2λ的H₂值, B首先查找R₂是否在表L₂中, 若是, 则将相应的h₂值返回给A; 否则随机选取d₂∈$\mathbb{Z}$_P^*, 令h₂=d₂, 并添加到表L₂中, 然后发送h₂给A。

4) H₃询问:B维护一个初始为空的列表L₃= < R₃, h₃>。A向B询问R₃∈G_T的H₃值, B首先查找R₃是否在表L₃中。若是, 则将相应的h₃值返回给A; 否则随机选取d₃∈{0, 1}^λ, 令h₃=d₃, 并添加到表L₃中, 然后发送h₃给A。

5) H₄询问:B维护一个初始为空的列表L₄= < R₄, h₄>。A向B询问R₄∈{0, 1}^λ的H₄值, B首先查找R₄是否在表L₄中。若是, 则将对应的h₄值返回A; 否则随机选取d₄∈{0, 1}^λ, 令h₄=d₄, 并添加到列表L₄中, 然后返回h₄给A。

询问阶段1:

1) 密钥询问:敌手A提交一个不满足挑战访问结构At^*的属性集Atts给挑战者B, 对每一个属性a_i∈Atts, B随机选取r′_i∈$\mathbb{Z}$_P^*, 令$, 计算K^*=g^φ-r′, L^*_i=g^{r′_i/βH₀(a_i)}。对挑战身份IDu^*, 随机选取v′∈$\mathbb{Z}$_P^*, 计算F_IDui=g^{v′H₁(IDu*)}, F′=g^v′, F″_i=L_i⊕H₁(g^{v′H₀(IDu*)}, 将私钥sk^*= < K^*, {L_i^*}, {F_IDui}, F′, F″_i>发送给A。

2) 解密询问:敌手A做访问结构At^*下的解密询问, B应答如下:

(1) 若A的属性Atts满足访问结构At^*, B以⊥应答; 否则, 转到步骤(2)。

(2) B从列表L₂、L₃和L₄中, 分别选取 < R₂, h₂>、< R₃, h₃>及 < R₄, h₄>, 且同时满足R₂=μ‖k, $\tilde{C}$₂=μ⊕h₃, R₃=φ^h₂, $\tilde{C}$₃=k⊕h₄和R₄=μ。若不满足, 则输出⊥; 否则输出π。

3) 挑战:A提交对称密钥k给B, B计算$\tilde{C}$₂=μ⊕H₃(Z), $\tilde{C}$₃=k_b⊕H₄(μ), $\bar{C}={{\left( \prod\limits_{i=1}^{n}{{{T}_{i}}} \right)}^{\pi }}$, $\tilde{C}$₁=g^π, 其中, b∈{0, 1}, μ∈{0, 1}^λ。

询问阶段2:敌手A可以重复进行阶段1的询问。

猜测:A输出关于b的猜测b′∈{0, 1}, 若b=b′, 则B能判断出e(g, g)^πφ=Z; 否则e(g, g)^πφ≠Z。

证毕。

4.4 陷门的不可区分性

定理3  若CDH假设成立, 则本文方案满足陷门的不可区分性。

证明  假设存在一个多项式时间敌手A能够以不可忽略的优势ε_A攻破本文方案, 则挑战者B可以利用A以不可忽略的优势ε_B解决CDH问题。

初始化:A向B提交要挑战的访问策略A^*=Λ_i∈IW^*A_i, 其中I_W^*表示属性下标, 即属性索引值。

建立阶段:挑战者B运行系统建立算法, 输出公共参数GP。挑战者B通过抛掷硬币游戏选择ξ∈{0, 1}, 如果ξ=1, 则T=g^abc; 否则, T为群G中的一个随机值。

询问阶段1:

敌手A选择任意属性集Atts^*和身份IDu^*, 进行密钥和陷门询问:

1) 密钥询问:B对于不满足挑战访问结构At^*的属性a_i∈Atts, 随机选取r_i∈$\mathbb{Z}$_P^*, 令$r=\sum\limits_{i=1}^{n}{{{r}_{i}}}$, 计算K=g^φ-r, L_i=g^{r_i/βH₀(a_i)}。对于挑战身份IDu^*, 随机选取v′∈$\mathbb{Z}$_P^*, 计算F_IDui=g^v′H₁(IDu^*), F′=g^v′, F″_i=L_i⊕H₁(g^v′H₀(IDu^*), 将私钥sk^*= < K, {L_i}, {F_IDui}, F′, F″_i>发送给A。

2) 陷门查询:当A询问关键字ω_i, 1≤i≤m的陷门时, B随机选择z′∈$\mathbb{Z}$_P^*, 计算tk₁=$\prod\limits_{i=1}^{\tau }{{{g}^{a{z}'{{H}_{5}}\left( {{\omega }_{i}} \right)}}}$, tk₂=g^z′, K′=K^z′, L′_i=L_i^z′, F′_IDi=F_IDi^z′, 并将陷门T_ωi= < tk₁, tk₂, K′, L′_i, F_IDui>发送给敌手A。

3) 挑战阶段:敌手A向挑战者B提交长度相同的关键词(ω₀, ω₁), 挑战者B随机选择s′∈$\mathbb{Z}$_p, 计算δ=g^s′, δ_b=g^{βs′H₅(w_b)}, b∈[0, 1], I_{i, 0}=IDd_{i, 0}⊕b, I_{i, 1}=IDd_{i, 1}⊕b, 将关键字密文In_W= < δ, δ_b, I₁, I₂>发送给敌手A。

询问阶段2:敌手A可以重复进行阶段1的询问。

猜测:敌手A输出ξ对ξ′∈{0, 1}的猜测。当ξ=ξ′时, 挑战者B输出1, 表示T=g^abc; 否则输出0, 表示T是G中的随机值, 挑战者解决困难问题的概率计算如下:

1) 当输出为1时, 表明敌手A得到关键字 < ω₀, ω₁>的有效密文。此时, 敌手A的优势为:ε_A=Pr[ξ′=ξ|T=g^abc]=ε+1/2。

2) 当输出为0时, 表明T是群G中的一个随机值。此时, 敌手A的优势为:ε_A=Pr[ξ′=ξ|T∈G_T]=1/2。

根据步骤1)和步骤2)得出挑战者B的优势为:

$ {{\varepsilon }_{B}}=\frac{1}{2}\Pr \left[ {\xi }'=\xi |T={{g}^{abc}} \right]+\frac{1}{2}\Pr \left[ {\xi }'=\xi |T\in G \right]-\frac{1}{2}=\frac{\varepsilon }{2} $

因此, 挑战者B能够以不可忽略的优势ε/2解决CDH问题。

5 性能分析

为更全面地阐述本文方案的性能, 从功能特性、计算开销以及实验仿真等方面对比分析本文方案与具有代表性的支持属性撤销可搜索加密^[13-15]方案的优劣势。

5.1 功能特征对比

从表 2可以看出, 相比于文献[13-15]方案, 本文方案在支持用户撤销的基础上, 加密了用户属性私钥, 可使其在公开信道传输; 同时, 将索引和密文分开存储, 易于提高检索效率。另外, 相比于文献[13]方案, 本文方案支持多个关键字同时检索, 易于快速检索所需数据。其中, √为支持, ×为不支持。

5.2 计算开销对比

通过理论数值分析, 对比本文方案与文献[13-15]方案。假设关键字个数对计算开销的影响相同, 仅考虑耗时长的指数运算和对数运算, 忽略哈希运算和异或运算, 对比结果如表 3所示。其中:|U|代表全局属性个数; |S|代表用户属性个数; |R|代表满足搜索要求的密文文件数; E代表群G上的指数运算; E_T代表群G_T上的指数运算; P代表对数运算。

从表 3中系统建立、密钥生成、加密、陷门生成、搜索等开销可以看出, 本文方案和文献[15]方案均优于文献[13-14]方案; 另外, 本文方案的解密计算开销远远低于文献[14]方案, 为恒定值。与文献[15]方案相比, 本文方案系统建立开销与用户个数线性相关, 但本文方案的密钥生成、加密及陷门生成开销低于文献[15]方案, 搜索开销高于文献[15]方案, 但也为恒定值。

5.3 实验仿真

实验环境为:Intel^Ⓡ Core^TM i5-2400 @ 3.10 GHz的处理器、4 GB的内存、Windows10 x64的操作系统, 调用jpbc-2.0.0库。设定关键字空间大小为1 000, 用户属性个数取10、20、30、40、50、60。数值模拟对比本文方案与文献[13-15]的加密和搜索阶段的时间开销。实验结果如图 2、图 3所示。

从图 2可以看出, 文献[13-15]方案的加密时间开销, 随着属性个数的增加线性增长，而本文方案加密阶段采用耗时少的哈希函数运算、异或运算, 并对用户属性进行聚合, 使得加密时间恒定, 与属性个数无关。从图 3可以看出, 文献[13-14]方案的搜索时间与属性个数正相关, 而本文方案和文献[15]方案的搜索时间恒定, 与理论分析结果保持一致。

6 结束语

云服务器在属性基可搜索加密方案中执行关键字搜索、用户撤销等操作时, 存在搜索效率低、用户隐私泄露等问题。本文通过引入区块链技术, 将属性可搜索加密中的索引与密文文档分开存储, 同时对密钥进行加密, 使其在公开信道传输。此外, 在密钥中同时嵌入用户版本号和用户属性, 及时撤销由属性变化引起用户身份失效的非法用户, 防止隐私泄露。效率分析结果表明, 该方案搜索时间与属性个数无关。下一步将在区块链环境下, 通过隐藏访问策略实现属性基可验证的多关键字密文搜索。