近年来，云存储被认为是互联网技术发展过程中最重要的转折点。许多组织、公司和个人使用公共云服务存储各种文件资料，以方便日常的业务运营^[1]，如购物支付、无处不在的网络灵活访问等。云存储是一种远程在线存储平台，它把数据存放在高度虚拟化的由第三方托管的云服务器上，为个人、组织和企业等提供可扩展的云存储资源，例如亚马逊海外云服务(AWS)、百度云、阿里云等^[2]。但云存储应用类型繁多，云服务器大多依托半可信第三方，有可能泄露用户的隐私。另外，出于商业利益的驱动，有些数据用户可能会借助云存储服务的公开性，通过攻击手段窃取他人云存储数据中的隐私^[3-5]，这严重阻碍了云存储技术的应用和发展。

为了保护云存储中用户的隐私数据，出现了许多云存储加密方案，将数据加密后上传到云中以保证数据的安全，但是在云上对加密文件搜索变得异常困难。为了解决此问题，文[6]提出了一种通用的可搜索加密(searchable encryption, SE)方案，授权用户可以根据参数生成密文，然而该方案在搜索时没有考虑语义，搜索结果不够准确。Kang等^[7]提出了一种基于合数阶双线性群的同义词可搜索加密(synonym searchable encryption, SSE)方案，以实现对同义词进行排序，但该方案搜索效率不高，还存在搜索结果不够准确的问题。文[8]针对基于属性加密(attribute-based encryption, ABE)策略加密每个文档标识时，存在云服务器无法确定用户是否有能力解密匹配数据的问题，提出了一种基于云端匹配技术的多读写器可搜索加密(multi-reader searchable encryption, SMSE)方案。文[9]提出了一种有效而安全的模糊逻辑云端数据搜索排序(effective securable fuzzy logic based ranking，ESFLBR)方案，以解决现有的可搜索加密方案不能很好地满足用户在云中存放大量文档时的数据搜索需求。但SMSE方案和ESFLBR方案都未考虑语义搜索，存在搜索效率不高、搜索结果不够精确等问题。为此，本文提出了一种基于语义的多用户高效搜索(efficient semantic-based multiuser search，ESBMS)方案，选用2个云存储服务器来处理数据用户的搜索，若其中1个云服务器判定数据用户提交的陷门搜索请求符合可搜索要求，则直接对搜索语义实施分析，不必数据拥有者一直在线，因而提高了数据用户的搜索精度和效率。本文首先给出了ESBMS方案的模型及工作过程，然后基于相关的基础技术，给出了ESBMS方案的设计及算法；最后对ESBMS方案的完备性进行推理证明，并对其安全性和时间复杂度进行分析，对比分析了其计算开销。

1 ESBMS方案模型

为了防止服务器集中检索时可推测密文语义信息的隐患，数据拥有者希望将数据密文与加密语义树分别存储在不同的服务器上。因此，ESBMS方案选用2个不同的云服务器CSP A和CSP B。其中：CSP A用于存储加密的数据文档，并返回数据用户相关的搜索结果；而CSP B用于存储语义树密文，并为请求搜索的数据用户产生陷门和进行陷门的匹配计算。如图 1所示，ESBMS方案由以下5个实体组成：

1) 数据用户(data user)：提交属性获得属性私钥，提交加密的查询数据。

2) 数据拥有者(data owner)：对自己拥有的数据文档进行加密，计算其可搜索索引，并上传至云服务器。

3) CSP A：存储数据拥有者所发送的消息，并返回密文给数据用户。

4) CSP B：存储语义树密文；在数据用户上传搜索请求时，利用生成的相应陷门判断是否满足搜索条件，只有满足条件时才将数据用户的搜索请求发送给云服务器CSP A。

5) 可信第三方(trusted third party, TTP)：负责使用属性加密语义树并为数据用户生成私钥。

2 基础技术 2.1 语义树

依照数据文档中搜索关键词的语义关系构建树状结构，由根节点、父节点、子节点和兄弟节点组成，其中语义关系主要有：近义词、整体与部分、主属性、上下位语义关系和属性值等。语义树中不相同的节点表示不相同的语义概念，语义概念拥有自己的属性，属性拥有自己的属性值。如图 2所示，根节点“Root”下有“医生”和“家具”等子语义概念，而“医生”语义概念下又有“临床”“中医”等子语义概念，“临床”下又有“重症”等子语义概念，“重症”下有“气管插管”和“心肺复苏”等属性值，“家具”语义概念下又有“书桌” “沙发”等子语义概念。语义树基于节点R和$\mathit{\mathbb{V}}$的语义相似度距离d(R,$\mathit{\mathbb{V}}$)表示语义对于搜索结果的影响^[10]。

2.2 双线性对函数

设p是乘法循环群G₀和G₁的阶，G₀的生成元为g，e: G₀×G₀→G₁是双线性对函数，则e满足以下3条性质：

1) 非退化性：存在r₀, r₁∈G₀，使e(r₀, r₁)≠1。

2) 双线性：随机选择r₀, r₁∈G₀，β, τ∈ Z _p，可以得到e(r₀^β, r₁^τ)=e(r₀, r₁)^βτ。

3) 可计算性：对所有的r₀, r₁∈G₀，存在有效的算法可计算出e(r₀, r₁)的值。

3 ESBMS方案

ESBMS方案研究了多用户MU_i(i=0, 1, 2, …, n；MU₀为数据拥有者)高效搜索加密方案，提出TTP采用多用户MU_i的搜索权限控制属性列表{L_MUi|i=0, 1, 2, …, n}={L_ij|i=0, 1, 2, …, n; j=1, 2, …, m}(如表 1所示)生成数据用户的属性私钥，数据用户利用其私钥解密密文。数据拥有者对各组数据文档生成相应的语义树，对其进行加密并上传到可信第三方，可信第三方再采用属性加密对其进行重加密。当数据用户的属性满足权限控制属性列表要求时，数据用户可搜索相应的数据文档并对语义树进行解密。

为了使ESBMS方案更好地适合多用户进行搜索，数据拥有者根据授权属性对文件集F={f₁, f₂, …, f_n}分组，分别生成语义树T={T₁, T₂, …, T_n}。ESBMS方案算法如下：

1) 生成公共参数(public-parameter，PP)和系统主密钥(master-key，MK)。

第1步   TTP随机选取2个阶为(n+1)(n+1)的可逆矩阵U和V。

$ \begin{array}{l} \mathit{\boldsymbol{U}}{\rm{ }} = \left[ {\begin{array}{*{20}{c}} {{u_{01}}}&{{u_{02}}}& \ldots &{{u_{0, {\rm{ }}n + 1}}}\\ {{u_{11}}}&{{u_{12}}}& \ldots &{{u_{1, {\rm{ }}n + 1}}}\\ \vdots & \vdots &{}& \vdots \\ {{u_{n1}}}&{{u_{n2}}}& \ldots &{{u_{n, {\rm{ }}n + 1}}} \end{array}} \right]{\rm{, }}\\ \mathit{\boldsymbol{v = }}\left[ {\begin{array}{*{20}{c}} {{v_{01}}}&{{v_{02}}}& \ldots &{{v_{0, {\rm{ }}n + 1}}}\\ {{v_{11}}}&{{v_{12}}}& \ldots &{{v_{1, {\rm{ }}n + 1}}}\\ \vdots & \vdots &{}& \vdots \\ {{v_{n1}}}&{{v_{n2}}}& \ldots &{{v_{n, {\rm{ }}n + 1}}} \end{array}} \right]. \end{array} $

第2步   TTP计算阶为(n+1)(n+1)的陷门生成参数E₁和E₂。

$ \begin{array}{l} \mathit{\boldsymbol{E}}_1{\rm{ }} = \left[ {\begin{array}{*{20}{c}} {{u_{01}}}&{{u_{02}}}& \ldots &{{u_{0, {\rm{ }}n + 1}}}\\ {{u_{11}}}&{{u_{12}}}& \ldots &{{u_{1, {\rm{ }}n + 1}}}\\ \vdots & \vdots &{}& \vdots \\ {{u_{n1}}}&{{u_{n2}}}& \ldots &{{u_{n, {\rm{ }}n + 1}}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{L_{01}}}&{{L_{02}}}& \ldots &{{L_{0m}}}\\ {{L_{11}}}&{{L_{12}}}& \ldots &{{L_{1m}}}\\ \vdots & \vdots &{}& \vdots \\ {{L_{n1}}}&{{L_{n2}}}& \ldots &{{L_{nm}}} \end{array}} \right]{\rm{, }}\\ \mathit{\boldsymbol{E}}_2 = \left[ {\begin{array}{*{20}{c}} {{v_{01}}}&{{v_{02}}}& \ldots &{{v_{0, {\rm{ }}n + 1}}}\\ {{v_{11}}}&{{v_{12}}}& \ldots &{{v_{1, {\rm{ }}n + 1}}}\\ \vdots & \vdots &{}& \vdots \\ {{v_{n1}}}&{{v_{n2}}}& \ldots &{{v_{n, {\rm{ }}n + 1}}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{L_{01}}}&{{L_{02}}}& \ldots &{{L_{0m}}}\\ {{L_{11}}}&{{L_{12}}}& \ldots &{{L_{1m}}}\\ \vdots & \vdots &{}& \vdots \\ {{L_{n1}}}&{{L_{n2}}}& \ldots &{{L_{nm}}} \end{array}} \right]. \end{array} $

第3步   TTP生成系统主密钥及系统公共参数。

设g是乘法循环群G₀的生成元，TTP随机选取数φ, η, a₀, a₁, a₂, …, a_n∈Z_p，计算t=e(g, g)^η, N_i=g^a_i(i=0, 1, 2, …, n)。令PP={(g, t, N_i)|i=0, 1, 2, …, n}，MK={(η, a_i)|i=0, 1, 2, …, n}。

2) TTP根据数据用户MU_i(i=0, 1, 2, …, n) 的属性L_MUi={L_ij|j=1, 2, …, m}生成属性私钥K_MUi={k_ij|j=1, 2, …, m}。

第1步   TTP选取一个随机数r∈ Z_p，计算

$ {r_{ij}} = \frac{{r{L_{ij}}}}{{\sum\limits_{j = 1}^m {{L_{ij}}} }}. $

(1)

其中：i=1, 2, …, n; j=1, 2, …, m。

第2步   TTP计算${k_{ij}} = N_i^{{r_{ij}}}$(i=1, 2, …, n; j=1, 2, …, m)。数据用户MU_i的属性密钥为K_MUi={k_ij|j=1, 2, …, m}。

第3步   TTP计算：

$ b = {g^{\eta {\rm{ - }}\varphi }}, {d_i} = {g^{\varphi a_i^{{\rm{ - }}1}}}. $

(2)

其中i=1, 2, …, n。TTP将生成的密钥K_MUi以及b、d_i发送给数据用户。

3) TTP加密语义树T得到G_T。

利用步骤2)中第1步生成的随机数r以及公共参数中的t，TTP加密语义树：

$ \rho = {g^r}, C = T{t^r} = \left\{ {{T_1}{t^r}, {T_2}{t^r}, \cdots , {T_n}{t^r}} \right\}. $

(3)

则C_T=(ρ, C)。

4) 索引生成。

对于每个文件，数据拥有者产生1个n维向量索引υ，并扩展υ为n+1维向量，其中υ的第n+1维为步骤2)中第1步生成的随机数r，表示为$\mathit{\boldsymbol{\vec \upsilon }} = \left( {\mathit{\boldsymbol{\upsilon }}, r} \right)$。最后，数据拥有者计算$\mathit{\mathbb{V}} = \left\{ {\mathit{\boldsymbol{E}}_1^{\rm{T}} \cdot \mathit{\boldsymbol{\vec v}},\mathit{\boldsymbol{E}}_2^{\rm{T}} \cdot \mathit{\boldsymbol{\vec v}}} \right\}$和e($\mathit{\mathbb{V}}$)，并发送e($\mathit{\mathbb{V}}$)给CSP A和CSP B。

5) 陷门生成。

数据用户发送搜索请求R，CSP B对于每一个搜索请求R生成1个向量$\mathit{\boldsymbol{R}} = \left\{ {\mathit{\boldsymbol{E}}_1^{ - 1}R, \mathit{\boldsymbol{E}}_2^{ - 1}R} \right\}$，并建立两个向量：${\mathit{\boldsymbol{R}}_1} = ({\sigma _1}, {\sigma _2}, \ldots , {\sigma _{j - 1}}, \zeta - h, {\sigma _{j + 1}}, \ldots , {\sigma _n})$, ${\mathit{\boldsymbol{R}}_2} = ({\sigma _1}, {\rm{ }}{\sigma _2}, {\rm{ }} \ldots , {\rm{ }}{\sigma _{j - 1}}, {\rm{ }}\zeta + h, {\rm{ }}{\sigma _{j + 1}}, {\rm{ }} \ldots , {\rm{ }}{\sigma _n})$。其中：R [j]=ζ, h，即$\mathit{\boldsymbol{R}} = \left\{ {\mathit{\boldsymbol{E}}_1^{{\rm{ - }}1}R, \mathit{\boldsymbol{E}}_2^{{\rm{ - }}1}R} \right\}$中$\mathit{\boldsymbol{E}}_1^{ - 1}R$和$\mathit{\boldsymbol{E}}_2^{ - 1}R$的第j维分别为ζ和h。σ_i (i=1, 2, …, j-1, j+1, …, n)是随机正整数。

6) 搜索。

CSP B利用以下公式可以先验证每对e(R₁)与e(R₂)是否满足限制条件:

$ \begin{gathered} {\text{comp}}(e({\mathit{\boldsymbol{R}}_1}), e({\mathit{\boldsymbol{R}}_2}), e\left( \mathit{\mathbb{V}} \right)) = \hfill \\ \left\{ {\begin{array}{*{20}{c}} {0, }&当&{d\left( {{\mathit{\boldsymbol{R}}_1}, \mathit{\mathbb{V}}} \right) = d\left( {{\mathit{\boldsymbol{R}}_2}, \mathit{\mathbb{V}}} \right);} \\ {1, }&当&{d\left( {{\mathit{\boldsymbol{R}}_1}, \mathit{\mathbb{V}}} \right) < d\left( {{\mathit{\boldsymbol{R}}_2}, \mathit{\mathbb{V}}} \right);} \\ {{\text{ - }}1, }&当&{d\left( {{\mathit{\boldsymbol{R}}_1}, \mathit{\mathbb{V}}} \right) > d\left( {{\mathit{\boldsymbol{R}}_2}, \mathit{\mathbb{V}}} \right).} \end{array}} \right. \hfill \\ \end{gathered} $

其中：d(R₁, $\mathit{\mathbb{V}}$)和d(R₂, $\mathit{\mathbb{V}}$)分别为R₁和R₂与$\mathit{\mathbb{V}}$的语义相似度距离。

如果comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$))≥0，则CSP A返回数据用户C_T。

证明：根据文[11]，存在常数k > 0，使得comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$))=[e(R₁)-e(R₂)]e($\mathit{\mathbb{V}}$)=0.5k[d²(R₂, $\mathit{\mathbb{V}}$)-d²(R₁, $\mathit{\mathbb{V}}$)]。因此，当d(R₁, $\mathit{\mathbb{V}}$)=d(R₂, $\mathit{\mathbb{V}}$)时，comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$))=0。当d(R₁, $\mathit{\mathbb{V}}$) < d(R₂, $\mathit{\mathbb{V}}$)时，comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$)) > 0。因此，定义comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$))=1合理。当d(R₁, $\mathit{\mathbb{V}}$) > d(R₂, $\mathit{\mathbb{V}}$)时，comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$)) < 0, comp(e(R₁), e(R₂), e($\mathit{\mathbb{V}}$))=-1合理。

7) 解密。

数据用户MU_i(i=0, 1, 2, …, n)利用私钥K_MUi和C_T=(ρ, C)解密得到原文。

第1步   计算$\frac{C}{{e\left( {\rho , b} \right)}} = {T_1}$。

第2步   计算$\prod\limits_{j = 1}^m e ({k_{ij}}, {d_i}) = D$。

第3步   数据用户通过$\frac{{{T_1}}}{D} = T$计算获得原文。

4 安全性与效率 4.1 完备性

证明：由$\sum\limits_{j = 1}^m {{r_{ij}}} = \sum\limits_{j = 1}^m {\left( {\frac{{r{L_{ij}}}}{{\sum\limits_{j = 1}^m {{L_{ij}}} }}} \right)} = \frac{{r\sum\limits_{j = 1}^m {\left( {{L_{ij}}} \right)} }}{{\sum\limits_{j = 1}^m {{L_{ij}}} }} = r$

得到

$ \begin{array}{c} D = \prod\limits_{j = 1}^m e ({k_{ij}}, {d_i}) = \prod\limits_{j = 1}^m e (N_i^{{r_{ij}}}, {g^{\varphi a_i^{ - 1}}}) = \\ \prod\limits_{j = 1}^m {e\left( {{g^{{a_i}{r_{ij}}}}, {g^{\varphi a_i^{ - 1}}}} \right) = \prod\limits_{j = 1}^m e {{\left( {g, {\rm{ }}g} \right)}^{{a_i}{r_{ij}}}}^{\varphi a_i^{ - 1}} = } \\ \prod\limits_{j = 1}^m e {\left( {g, g} \right)^{{r_{ij\varphi }}}} = e{\left( {g, {\rm{ }}g} \right)^{\varphi \sum\limits_{j = 1}^m {{r_{ij}}} }} = e{\left( {g, {\rm{ }}g} \right)^{\varphi\ r}}. \end{array} $

于是，

$ \begin{array}{c} \frac{{{T_1}}}{D} = \frac{C}{{e\left( {\rho , b} \right)D}} = \frac{C}{{e\left( {\rho , b} \right)e{{\left( {g, g} \right)}^{\varphi\ r}}}} = \\ \frac{C}{{e\left( {{g^r}, {g^{\eta - \varphi }}} \right)e{{\left( {g, g} \right)}^{\varphi\ r}}}} = \frac{C}{{e{{\left( {g, g} \right)}^{r(\eta - \varphi )}}e{{\left( {g, g} \right)}^{\varphi\ r}}}} = \\ \frac{C}{{e{{\left( {g, g} \right)}^{r\left( {\eta - \varphi } \right) + \varphi\ r}}}} = \frac{C}{{e{{\left( {g, g} \right)}^{\eta\ r}}}} = \frac{{T{t^r}}}{{e{{\left( {g, g} \right)}^{\eta\ r}}}} = \\ \frac{{T{{\left( {e{{\left( {g, g} \right)}^\eta }} \right)}^r}}}{{e{{\left( {g, g} \right)}^{\eta\ r}}}} = \frac{{Te{{\left( {g, g} \right)}^{\eta\ r}}}}{{e{{\left( {g, g} \right)}^{\eta\ r}}}} = T. \end{array} $

因此，ESBMS方案是完备的。

4.2 抗共谋攻击

假设n+1个用户MU_i(i=0, 1, 2, …, n)利用其属性密钥K_MUi={k_ij|j=1, 2, …, m}进行共谋攻击，根据第3节步骤2)的第2步，攻击者首先要解离散对数方程${k_{ij}} = N_i^{{r_{ij}}}$(i=1, 2, …, n; j=1, 2, …, m)，由于计算离散对数的困难性，他们不可能解出r_ij。假设攻击者以很低的概率进行若干次重复后猜测出r_ij，根据式(1)，他们可以共谋构建由n+1个方程n+2个未知数r，L_0j, L_1j, …, L_nj组成的方程组：

$ \left\{ {\begin{array}{*{20}{c}} {{r_{0j}} = \frac{{r{L_{0j}}}}{{\sum\limits_{j = 1}^m {{L_{0j}}} }}, }\\ {{r_{1j}} = \frac{{r{L_{1j}}}}{{\sum\limits_{j = 1}^m {{L_{1j}}} }}, }\\ \vdots \\ {{r_{nj}} = \frac{{r{L_{nj}}}}{{\sum\limits_{j = 1}^m {{L_{1nj}}} }}} \end{array}} \right. $

(4)

由于式(4)为不定方程组，有无穷多个解，因此攻击者无法根据n+1个数据从式(4)中解出未知数r，故他们无法从式(3) C=Tt^r={T₁t^r, T₂t^r, …, T_nt^r}中共谋计算出语义树T。

4.3 语义隐私性

根据式(3)，TTP利用随机数r和公共参数t加密语义树T，由于t^r=(e(g, g)^η)^r=e(g, g)^{η r}，攻击者利用e(g, g)^{η r}的计算结果获得随机数r是很困难的，因而攻击者从C=Tt^r={T₁t^r, T₂t^r, …, T_nt^r}中获得语义树T是不可能的。

4.4 时间复杂度分析

如果用f表示文件个数、v表示生成向量的个数，从表 2可以看出，文[11]、文[12]和ESBMS方案的索引生成的时间复杂度依次为O(vf²)、O(v(f+2)²)和O(v(f-3)²)。因为O(v(f-3)²) < O(vf²) < O(v(f+2)²)，所以ESBMS方案的索引生成的计算开销最少。

从表 2也可以看出，文[11]、文[12]和ESBMS方案的陷门生成的时间复杂度依次为O(f²)、O((f+2)²)和O((f-2)²)。同样，因为O((f-2)²) <O(f²)<O((f+2)²)，所以ESBMS方案的陷门生成的计算开销也最少。

通过以上对比分析可以发现，ESBMS方案具有高效性，这主要是因为ESBMS方案选用了2个云存储服务器CSP A和CSP B，利用云服务器比客户端更强大的存储及计算资源，将语义树存储于云端，并调用云服务器进行大量的陷门计算，克服了客户端存储及计算资源不足的瓶颈。

从图 3可以看出：随文件数的增加，ESBMS方案与文[11]和[12]的索引生成时间皆呈指数增长，而ESBMS方案的索引生成时间要少于文[11]和[12]，表现出较高的效率。

图 4对ESBMS方案、文[11]和[12]的陷门生成时间进行了对比。各方案的陷门生成时间随文件数的增加呈幂函数方式增长，而ESBMS方案的陷门生成时间要少于文[11]和[12]，同样表现出较高的效率。

5 结束语

本文针对加密云存储搜索提出ESBMS方案。该方案采用语义树，基于多用户权限控制可搜索属性列表，支持离线多用户加密搜索。该方案把大量计算迁移到云中，使用户不需要花费大量的计算资源，同时不需要数据拥有者一直在线，就可以进行访问与搜索，提高了搜索效率和数据拥有者的数据隐私安全。本文所提方案的索引生成和陷门生成的效率优于已有研究中的其他2个方案。