0 概述

云存储技术能为数据提供巨大的存储空间, 且其使用较为便捷, 因此, 得到了研究人员的广泛关注。然而, 云数据通常以明文形式存储, 因此, 其安全性难以得到保证。近年来, 云数据泄露事件不断发生, 其中多数是由于黑客的非法入侵和云端服务器管理员的不当操作而导致。例如, 2011年Sony公司被黑客入侵导致上亿用户资料外泄。

为了更好地解决海量数据的安全存储与检索问题, 可搜索加密技术^[1]应运而生, 其目标是在不影响数据检索功能的前提下, 保护用户外包数据的安全性与查询隐私。可搜索加密技术的基本应用过程为:用户加密自己的数据并上传到远程服务器, 在需要检索文件时提交其关键词的陷门给服务器, 随后服务器使用陷门检索到密文并返回给用户, 整个过程中服务器将不会获取关于密文与其关键词的任何信息。

可搜索加密能够很好地保护用户外包数据的机密性, 同时使得加密数据的高效搜索成为可能, 即具有很好的扩展性。文献[2-3]提出对称可搜索加密方案并进行进一步完善。文献[4]提出基于公钥的可搜索加密协议, 其利用基于身份的加密设计了公钥可搜索加密方案。公钥可搜索加密方案允许多个用户利用公钥进行加密, 仅拥有相应私钥的用户才可以搜索加密的数据。文献[5-6]利用双线性对分别构造了基于连接关键词的可搜索加密方案BLL和RT, 2种方案的特点都是关键词陷门大小固定, 但是判断每个文档时都需要计算2次双线性对。文献[7]提出了在非结构文本上的基于连接关键词的可搜索加密方案FK, 其在搜索加密文档时无需指定关键词的位置。为了更接近实际中的搜索情况, 文献[8]利用词典和关键词间的编辑距离, 提出了一个基于模糊关键词的可搜索加密方案, 其在关键词拼写错误或格式不一致的情况下也能搜索出正确的密文。此外, 文献[9-10]提出了其他具有特殊功能的基于多关键词的可搜索加密方案, 扩展了多关键词可搜索加密的应用范围。

本文提出一种基于连接关键词的可搜索加密方案, 并通过Java编程语言实现该方案, 以验证其加密性能。

1 基础知识 1.1 双线性映射

设p为素数, 令G₁、G₂是p阶循环群, 若映射e:G₁×G₁→G₂满足以下性质, 则称e为一个双线性映射:

1) 双线性(bilinear):对于任意的P, Q∈G₁, a, b∈${\mathbb{Z}}$, e(aP, bQ)=e(P, Q)^ab。

2) 非退化性(non-degenerate):如果P是G₁的生成元, 则e(P, P)是G₂的生成元。

3) 可计算性(computable):对于任意的P, Q∈G₁, 存在多项式时间算法计算e(P, Q)。

1.2 方案的困难性假设

q-双线性Diffie-Hellman(q-BDH)问题即给定(P, xP, x²P, …, x^qP)∈(G₁^*)^q+1, 其中, x∈${\mathbb{Z}}_{p}$, P是p阶循环群G₁的生成元, 计算e(P, P)^1/x∈G₂^*。q-BDH假设^[11], 即对于任意的多项式时间算法A, 存在一个可忽略函数ε, 使得:

$ \Pr \left[ {A\left( {P, xP, {x^2}P, \cdots , {x^q}P} \right) = e{{\left( {P, P} \right)}^{1/x}}} \right] \ge \varepsilon $

2 基于连接关键词的可搜索加密方案 2.1 系统描述

本文系统包括以下3个实体:半可信服务器, 文件上传者和文件使用者。半可信即其会诚实执行协议, 但会观察所有交互的数据以便获得额外信息, 另外, 每个用户既可以是上传者, 也可以是使用者。如图 1所示, 考虑这样一种应用场景, 数据拥有者将自己特定类别的文件共享给特定用户群体。目前借助可信第三方的可加密方案较多, 但是这类方案对第三方的依赖性较强, 用户密钥的分发、用户权限的添加/撤销等全部交给可信第三方来处理, 不能实现用户的动态自主授权。另外, 这些用户隶属于不同机构, 因此, 不易在现实中找到被多方用户都信赖的第三方。本文方案无需可信第三方, 并且设置2个陷门, 搜索陷门T_Q^S用于查询文件是否存在, 解密陷门T_Q^D可以给需要文件的用户指定其可以使用不可信服务器发来的加密文件, 同时用自己的私钥和解密陷门T_Q^D进行文件解密。

2.2 算法定义

基于连接关键词的可搜索加密方案由以下6个多项式时间算法组成:

KeyGen(1^k):为概率算法, 输入安全参数k, 生成一个公私钥对(A_pub, A_priv)。

Encrypt(A_pub, D):为用户执行的加密算法, 输入公钥A_pub和文件M, 输出密文C。

STrapdoor(A_priv, Q):输入私钥A_priv和查询Q, 输出搜索陷门T_Q^S。

DTrapdoor(A_priv, Q):输入私钥A_priv和查询Q, 输出解密陷门T_Q^D。

Test(A_pub, C, T_Q^S):输入公钥A_pub、密文C和搜索陷门T_Q^S, 如果{(W_I1=Ω₁)∧(W_I2=Ω₂)∧…∧(W_It=Ω_t)}, 输出Yes, 反之, 输出No。

Decrypt(A_pub, C, T_Q^D):输入公钥A_pub、密文C=Encrypt(A_pub, D)和解密陷门T_Q^D=DTrapdoor(A_priv, Q), 如果{(W_I1=Ω₁)∧(W_I2=Ω₂)∧…∧(W_It=Ω_t)}, 则输出加密文件及其对应的用公钥加密的解密密钥。

2.3 安全性模型

基于连接关键词的可搜索加密方案的安全性, 即在不提供陷门(T_Q^S或T_Q^D)时, 确保Encrypt(A_pub, D)不会泄露关于文件D=(M, H)的任何信息。本文目标是实现选择密文攻击的不可区分性, 即假设一个活跃的攻击者可以得到其选择的关键词和陷门, 在这种攻击下, 攻击者无法区分加密后的D₀=(M₀, H₀)和D₁=(M₁, H₁)。由此, 在攻击者将想要挑战的文件告知挑战者的前提下, 定义此模型下挑战者和攻击者之间的攻击游戏如下:

初始化  利用KeyGen(1^k)算法产生私钥A_priv并将其发送给攻击者。

阶段1  适应性询问阶段:

Search trapdoor query < Q_i>:挑战者运行算法STrapdoor生成与 < Q_i>的搜索陷门T_Qi^S并发送给攻击者。

Decrypt trapdoor query < Q_i>:挑战者运行算法DTrapdoor生成与 < Q_i>的解密陷门T_Qi^D并发送给攻击者。

Decryption query < Q_i, C_i>:挑战者运行算法DTrapdoor生成与 < Q_i>的解密陷门T_Qi^D, 再运行算法Decrypt, 使用T_Qi^D密文进行解密, 然后将文件内容或者⊥发送给攻击者。

挑战  攻击者向挑战者提交挑战文件D₀=(M₀, H₀)和D₁=(M₁, H₁)。其限制为:在阶段1中, D₀和D₁在搜索陷门询问阶段未被询问, 且Q_i与H₀和H₁的匹配情况在解密陷门询问阶段未被询问, 同时 < Q_i⊆H₀, C₀>和 < Q_i⊆H₁, C₁>在解密询问阶段未被询问。挑战者挑出一个随机数b∈{0, 1}, 并将其加密后的密文C=Encrypt(A_pub, D_b)发送给攻击者。

阶段2  攻击者重复阶段1的操作, 可以进行更多次询问, 但其限制为:T_Qi^S不能用来辨别D₀和D₁, 在多次询问过程中, Q_i$\underline{\not\subset }$H₀或H₁, C_i=C。

猜测  攻击者输出b′∈{0, 1}, 当b′=b时, 攻击者获胜。

本文定义攻击者A在攻击基于连接关键词的可搜索加密模型时的优势为:

$ {{\rm{Adv}}_{\varepsilon , A}}\left( {{1^k}} \right) = \left| {Pr\left[ {b = b'} \right] - 1/2} \right| $

3 算法构造

基于文献[12]提出的SKBE方案, 本文提出了一个有效的基于连接关键词的可搜索加密方案。引入2个p阶素数群G₁、G₂, 双线性映射ê:G₁×G₁→G₂。设P₁、P₂是G₁的2个不同的生成元。如果给定一个密文和合适的搜索陷门, 测试者就可以生成ê(P₁, P₂)^r₀并输出Yes, 其中, r₀是${\mathbb{Z}}_p^*$中的随机数。如果加密文件的会话密钥蕴含在ê(P₁, P₂)^r₀中, 可通过将P₁更换为P₂来获得解密陷门。

对于基于连接关键词的可搜索加密方案, 需要一个安全对称密钥加密方案($\mathcal{G}$, ε, $\mathcal{D}$)、3个哈希函数(H₁:{0, 1}^*→_p^*, H₂:{0, 1}^*→${\mathbb{Z}}_p^*$, H₃:{0, 1}^*×κ→${\mathbb{Z}}_p^*$)和1个密钥加密函数(Enc:κ×P→${\mathbb{Z}}_p^*$)。其中, κ是($\mathcal{G}$, ε, $\mathcal{D}$)的密钥空间, P是分享目标的公钥, H₁和H₂不同。方案各阶段算法描述如下:

KeyGen(1^k):输入安全参数1^k, p阶群G₁、G₂的大小。该算法选择随机数s₁, s₂, …, s_m, s_m1, s_m2∈${\mathbb{Z}}_p^*$和群G₁的2个不同的生成元P₁、P₂, 输出A_pub=[P₁, P₂, Y₁=s₁P₁, Y₂=S₂P₁, …, Y_m=s_mP₁, Y_m+1=s_m1P₁, Y_m+2=s_m2P₁, g=ê(P₁, P₁), h=ê(P₁, P₂)]和A_priv=[s₁, s₂, …, s_m, s_m1, s_m2]。

Encrypt(A_pub, D):通过运行算法$\mathcal{G}$产生会话密钥sk∈κ。算法随机选择r₁, r₂, …, r_m∈${\mathbb{Z}}_p^*$生成B_i=r_iY_m+1, 1≤i≤m。设置r₀=H₃(M‖B₁‖B₂‖…‖B_m, sk), 其中, 每一个B_i被视为一个字符串, ‖是一个连接符。通过E=ε_sk(M)解密消息并计算以下值:A_i=r₀(Y_i+H₁(W_i)P₁)+r_iY_m+1, 1≤i≤m, K=r₀Y_m+2, S=H₂(g^r₀), R=H₂(h^r₀)⊕Enc(sk, P_B)。输出密文C=[E, A₁, A₂, …, A_m, B₁, B₂, …, B_m, K, S, R]。

STrapdoor(A_priv, Q):对于输入Q=(I₁, I₂…, I_t, Ω₁, Ω₂, …, Ω_t), 随机选择一个u∈_p^*, 使得搜索陷门T_Q^S=[T₁^S, T₂^S, T₃^S, I₁, I₂, …, I_t], 其中有:

$ T_1^S = \frac{{{P_1}}}{{{s_{{I_1}}} + {s_{{I_2}}} + \cdots + {s_{{I_t}}} + {H_1}\left( {{\mathit{\Omega }_1}} \right) + {H_1}\left( {{\mathit{\Omega }_2}} \right) + \cdots + {H_1}\left( {{\mathit{\Omega }_t}} \right) + {s_{m + 2}}u}} $

$ T_2^S = \frac{{T_1^S}}{{{s_{m + 1}}}} $

$ T_3^S = u $

DTrapdoor(A_priv, Q):对于输入Q=(I₁, I₂, …, I_t, Ω₁, Ω₂, …, Ω_t), 随机选择一个v∈${\mathbb{Z}}_p^*$, 使得解密陷门T_Q^D=[T₁^D, T₂^D, T₃^D, I₁, I₂, …, I_t], 其中有:

$ T_1^D = \frac{{{P_2}}}{{{s_{{I_1}}} + {s_{{I_2}}} + \cdots + {s_{{I_t}}} + {H_1}\left( {{\mathit{\Omega }_1}} \right) + {H_1}\left( {{\mathit{\Omega }_2}} \right) + \cdots + {H_1}\left( {{\mathit{\Omega }_t}} \right) + {s_{m + 2}}v}} $

$ T_2^D = \frac{{T_1^D}}{{{s_{m + 1}}}} $

$ T_3^D = v $

Test(A_pub, C, T_Q^S):检验式(1)。

$ {H_2}\left( {\frac{{\hat e\left( {{A_{{I_1}}} + {A_{{I_2}}} + \cdots + {A_{{I_t}}}, T_3^SK, T_1^S} \right)}}{{\hat e\left( {{B_{{I_1}}} + {B_{{I_2}}} + \cdots + {B_{{I_t}}}, T_2^S} \right)}}} \right) = S $

(1)

如果式(1)等式成立, 则输出Yes; 否则, 输出No。

Decrypt(A_pub, C, T_Q^D):

计算${{\tilde h}^{{r_0}}} = \frac{{\hat e\left( {{A_{{I_1}}} + {A_{{I_2}}} + \cdots + {A_{{I_t}}} + T_3^DK, T_1^D} \right)}}{{\hat e\left( {{B_{{I_1}}} + {B_{{I_2}}} + \cdots + {B_{{I_t}}}, T_2^D} \right)}}$, Enc(sk, P_B)=H₂(${{\tilde h}^{{r_0}}}$)⊕R, ${{\tilde r}_0}$=H₃(${\tilde M}$‖B₁‖B₂‖…‖B_m, sk), 检验式(2)。

$ {{\tilde h}^{{r_0}}} = {h^{{{\tilde r}_0}}} $

(2)

如果式(2)等式成立, 则输出E, Enc(sk, P_B); 否则, 输出⊥。

式(1)的数学证明如下:

如果W_Ii=Ω_i, 有:

$ \begin{array}{l} {H_2}\left( {\frac{{\hat e\left( {{A_{{I_1}}} + {A_{{I_2}}} + \cdots + {A_{{I_t}}} + T_3^SK, T_1^s} \right)}}{{\hat e\left( {{B_{{I_1}}} + {B_{{I_2}}} + \cdots + {B_{{I_t}}}, T_2^S} \right)}}} \right) = \\ \;\;\;\;\;{H_2}\left( {\frac{{\hat e\left( {{A_{{I_1}}} + {A_{{I_2}}} + \cdots + {A_{{I_t}}} + T_3^SK, T_1^S} \right)}}{{\hat e\left( {{r_{{I_1}}}{P_1} + {r_{{I_2}}}{P_1} + \cdots + {r_{{I_t}}}{P_1}, T_2^S} \right)}}} \right) = \\ \;\;\;\;\;{H_2}\left( {\hat e\left( {{r_0}\left( {{Y_{{I_1}}} + {H_1}\left( {{W_{{I_1}}}} \right){P_1}} \right) + \cdots + } \right.} \right.\\ \;\;\;\;\;\left. {\left. {{r_0}\left( {{Y_{{I_t}}} + {H_1}\left( {{W_{{I_t}}}} \right){P_1}} \right) + T_3^SK, T_1^S} \right)} \right) = \\ \;\;\;\;\;{H_2}\left( {\hat e\left( {{r_0}{P_1}, {P_1}} \right)} \right) = S \end{array} $

式(2)的数学证明如下, 有:

如果W_Ii=Ω_i, 有:

$ \begin{array}{l} {{\tilde h}^{{r_0}}} = \frac{{\hat e\left( {{A_{{I_1}}} + {A_{{I_2}}} + \cdots + {A_{{I_t}}} + T_3^DK, T_1^D} \right)}}{{\hat e\left( {{B_{{I_1}}} + {B_{{I_2}}} + \cdots + {B_{{I_t}}}, T_2^D} \right)}} = \\ \;\;\;\;\;\;\;\frac{{\hat e\left( {{A_{{I_1}}} + {A_{{I_2}}} + \cdots + {A_{{I_t}}} + T_3^DK, T_1^D} \right)}}{{\hat e\left( {{r_{{I_1}}}{P_1} + {r_{{I_2}}}{P_2} + \cdots + {r_{{I_t}}}{P_1}, T_2^D} \right)}} = \\ \;\;\;\;\;\;\;\hat e\left( {{r_0}\left( {{Y_{{I_1}}} + {H_1}\left( {{W_{{I_1}}}} \right){P_1}} \right) + \cdots + } \right.\\ \left. {\;\;\;\;\;\;\;{r_0}\left( {{Y_{{I_t}}} + {H_1}\left( {{W_{{I_t}}}} \right){P_1}} \right) + T_3^DK, T_1^D} \right) = \\ \;\;\;\;\;\;\;\hat e\left( {{r_0}{P_1}, {P_2}} \right) = {h^{{r_0}}} \end{array} $

$ \tilde sk = {H_2}\left( {{{\tilde h}^{{r_0}}}} \right) \oplus R = {H_2}\left( {{h^{{r_0}}}} \right) \oplus R = Enc\left( {sk, {P_B}} \right) $

$ \begin{array}{l} {{\tilde r}_0} = {H_3}\left( {\tilde M\left\| {{B_1}} \right\|{B_2}\left\| \cdots \right.\left\| {{B_m}} \right., sk} \right) = \\ \;\;\;\;\;\;{H_3}\left( {M\left\| {{B_1}} \right\|{B_2}\left\| \cdots \right.\left\| {{B_m}} \right., sk} \right) = {r_0} \end{array} $

因此, ${{\tilde h}^{{r_0}}}{\rm{ = }}{h^{{r_0}}}{\rm{ = }}{h^{{{\tilde r}_0}}}$。

4 安全性分析

本文通过建立一个随机预言机模型^[13]进行选择密文攻击, 采用规约化思想将安全性问题规约为求解q-BDH问题, 以证明本文方案具有选择密文攻击下的密文不可区分性(IND－CCA)。挑战者通过预言机得到的密文D₀和D₁不会泄露文件0和文件1是否包含相同关键词, 即敌手无法通过获得的陷门查询到含相同关键词的其他文件。

定理1  如果q-BDH问题在群G₁难解, 则本文可搜索加密方案具有选择密文攻击下的密文不可区分性(IND－CCA)。

证明  假设存在A以优势ε对本文方案进行攻击, A生成ST或DT至多q_T次, H₁用了至多q_H1次, H₃用了至多q_H3次, 本文构建一个敌手B, 他能在群G₁解决(q_T+1)-BDH问题的可能性$\varepsilon ' = \frac{\varepsilon }{{{\rm{e}}{{\left( {{q_{{H_1}}}} \right)}^m}{q_{{H_3}}}}}$, 其中, e是自然对数的底数, B攻击成功所需的时间与A近似相等。

在输入(P, xP, x²P, …, x^q_T+1P)后, 敌手B的目标是生成ê(P, P)^1/x∈G₂。模拟挑战者和攻击者A之间的交互过程如下:

初始化  敌手B随机选取δ₁, δ₂, …, δ_qT∈${\mathbb{Z}}_p^*$, 令$f(z) = \prod\limits_{j = 1}^{{q_T}} {\left( {z + {\delta _j}} \right)} $, 进行多项式展开, 记$f(z) = \prod\limits_{j = 1}^{{q_T}} {{c_i}{z^i}} $, 生成U=f(x)P=$\sum\limits_{i = 0}^{{q_T}} {{c_i}{x^i}P} $和V=xU=$\sum\limits_{i = 0}^{{q_T} + 1} {{c_{i - 1}}{z^i}P} $, $\frac{U}{{x + {\delta _i}}} = \frac{{f(x)}}{{x + {\delta _i}}}P = \sum\limits_{i = 0}^{{q_T}} {{d_i}} {z^i}P$, 1≤i≤q_T, 存储配对$\left( {{\delta _i}, \frac{U}{{x + {\delta _i}}}} \right)$。敌手B随机选取α₀, α₁, α₂, …, α_m+2, β₁, β₂, …, β_m∈${\mathbb{Z}}_p$并生成Y_i=α_iV-β_iU, 1≤i≤m, Y_m+1=α_m+1U, Y_m+2=α_m+2V, g=ê(U, U), h=ê(U, α₀U)。B给A公钥A_pub=[U, α₀U, Y₁, Y₂, …, Y_m, Y_m+1, Y_m+2, g, h], 对应的私钥A_priv=[s₁=α₁x-β₁, s₂=α₂x-β₂, …, s_m=α_mx-β_m, s_m1=α_m+1x, s_m2=α_m+2x], B无法知道其中的s₁, s₂, …, s_m和s_m+2。

H₁查询  敌手A向随机预言机H₁发出查询请求, 为了响应这个请求, B初始化一个空的三元组 < W_i, h_i, c_i>列表H₁, 当A向随机预言机H₁请求W_i∈{0, 1}^*时, B按以下规则做出回应:

1) 如果查询W_i出现在H₁表中, B回复H₁(W_i)=h_i。

2) 否则, B生成一个随机数c_i∈{1, 2, …, q_H1}, 概率Pr(c_i≤m)=$\frac{m}{{{q_{{H_1}}}}}$。

3) 如果c_i>m, B选择一个随机数h_i∈{0, 1}^{lb p}, 否则, h_i=β_ci。

4) B将 < W_i, h_i, c_i>加入H₁表, 回复H₁(W_i)=h_i。

H₂查询  敌手A向随机预言机H₂发出查询请求, 为了响应这个请求, B需要初始化一个空的二元组 < g_i, γ_i>列表H₂, 当A向随机预言机H₂请求g_i∈{0, 1}^*时, B按以下规则做出回应:

1) 如果查询g_i出现在H₂表中, B回复H₂(g_i)=γ_i。

2) 否则, B随机生成一个γ_i∈{0, 1}^{lb p}, 并将 < g_i, γ_i>加入H₂表中, 回复H₂(g_i)=γ_i。

H₃查询  敌手A向随机预言机H₃发出查询请求。为了响应这个请求, B初始化一个空的多元组 < M_i‖B_{i, 1}‖B_{i, 2}‖…‖B_{i, m}, sk_i, r_oi, X_i, Y_i>列表H₃, 当A向随机预言机H₃发送请求M_i‖B_{i, 1}‖B_{i, 2}‖…‖B_{i, m}∈{0, 1}^*和sk_i∈κ时, B按以下规则做出回应:

1) 如果查询M_i‖B_{i, 1}‖B_{i, 2}‖…‖B_{i, m}和sk_i已经出现在H₂表中, B回复H₃(M_i‖B_{i, 1}‖B_{i, 2}‖…‖B_{i, m}, sk_i)=r_oi。

2) 否则, B随机生成一个r_oi∈${\mathbb{Z}}_p^*$, 同时生成X_i=H₂(g^r_oi), Y_i=H₂(h^r_oi)⊕Enc(sk, P_C), 并将 < M_i‖B_{i, 1}‖B_{i, 2}‖…‖B_{i, m}, sk_i, r_oi, X_i, Y_i>加入H₃表中, 回复r_oi。H₁、H₂、H₃查询Hash算法说明如表 1所示。

挑战者与攻击者之间的攻击游戏如下:

阶段1  A提出查询q_i, 且q_i是以下查询中的一种:

1) ST查询:当A发起Q_i=(I_{i, 1}, I_{i, 2}, …, I_{i, ti}, Ω_{i, 1}, Ω_{i, 2}, …, Ω_i.ti)查询搜索陷门, B进行如下操作:

(1) B模拟H₁查询获得h_{i, j}, h_{i, j}=H₁(Ω_{i, j}), 找到 < Ω_{i, j}, h_{i, j}, c_{i, j}>对应表中的多元组, 如果∀j, c_{i, j}=I_{i, j}, 则B失败, 即不能找到含相同关键词的组。

(2) 否则, B定义J_i=s_{Ii, 1}+s_{Ii, 2}+…+s_{Ii, ti}+h_{i, 1}+…+h_{i, ti}=Γ_ix+Δ_i, 其中, Γ_i=α_{Ii, 1}+α_{Ii, 2}+…+α_{Ii, ti}, Δ_i=-(β_{Ii, 1}+β_{Ii, 2}+…+β_{Ii, ti})+(h_{i, 1}+h_{i, 2}+…+h_{i, ti})。

(3) B选取第i对$\left( {{\delta _i}, \frac{U}{{x + {\delta _i}}}} \right)$, 取u_i=$\left( {\frac{{{\Delta _i}}}{{{\delta _i}}} - {\mathit{\Gamma }_i}} \right)$α_m+2, ${v_i} = \frac{{{\Delta _i}}}{{{\delta _i}}}$, 满足$\frac{1}{{x + {\delta _i}}}U = \frac{{{v_i}}}{{{\mathit{\Gamma }_i}x + {\Delta _i} + {\alpha _{m + 2}}x{u_i}}}U$, B生成${F_i} = \frac{U}{{\left( {x + {\delta _i}} \right){v_i}}}$, F_i与1/(s_{i, 1}+s_{i, 2}+…+s_{i, ti}+h_{i, 1}+h_{i, 2}+…+h_{i, ti}+s_m2u_i)·U相等, 因此, (F_i, F_i/α_m+1, u_i)是对应Q_i查询到的正确的搜索陷门, B回复[F_i, F_i/α_m+1, u_i, I_{i, 1}, I_{i, 2}, …, I_{i, ti}]给A。

2) DT查询:当A发起Q_i=(I_{i, 1}, I_{i, 2}, …, I_{i, ti}, Ω_{i, 1}, Ω_{i, 2}, …, Ω_i.ti)查询解密陷门, B进行如下操作:

(1) B模拟H₁查询获得h_{i, j}, h_{i, j}=H₁(Ω_{i, j}), 找到 < Ω_{i, j}, h_{i, j}, c_{i, j}>对应表中的多元组, 如果∀j, c_{i, j}=I_{i, j}, 则B失败, 即不能找到含相同关键词的组。

(2) 否则, B定义J_i=S_{Ii, 1}+S_{Ii, 2}+…+S_{Ii, ti}+h_{i, 1}+h_{i, 2}+…+h_{i, ti}=Γ_ix+Δ_i, 其中, Γ_i=α_{Ii, 1}+α_{Ii, 2}+…+α_{Ii, ti}, Δ_i=-(β_{Ii, 1}+β_{Ii, 2}+…+β_{Ii, ti})+(h_{i, 1}+h_{i, 2}+…+h_{i, ti})。

(3) B选取第i对$\left( {{\delta _i}, \frac{U}{{x + {\delta _i}}}} \right)$, 取u_i=$\left( {\frac{{{\Delta _i}}}{{{\delta _i}}} - {\mathit{\Gamma }_i}} \right)$α_m+2, ${v_i} = \frac{{{\Delta _i}}}{{{\delta _i}}}$, 满足$\frac{1}{{x + {\delta _i}}}U = \frac{{{v_i}}}{{{\mathit{\Gamma }_i}x + {\Delta _i} + {\alpha _{m + 2}}x{u_i}}}U$, B生成${G_i} = \frac{{{\alpha _0}U}}{{\left( {x + {\delta _i}} \right){v_i}}}$, G_i与α₀/(s_{i, 1}+s_{i, 2}+…+s_{i, ti}+h_{i, 1}+h_{i, 2}+…+h_{i, ti}+s_m2u_i)·U相等, 因此, $\left( {{G_i}, \frac{{{G_i}}}{{{\alpha _{m + 1}}}}, {u_i}} \right)$是对应Q_i查询到的正确的解密陷门T_Qi^D, B回复[G_i, ${\frac{{{G_i}}}{{{\alpha _{m + 1}}}}}$, u_i, I_{i, 1}, I_{i, 2}, …, I_{i, ti}]给A。

挑战者A输出2个文件D₀=(M₀, H₀)和D₁=(M₁, H₁), 并发送给B。B进行如下操作:

1) B执行上述算法, 通过回复H₁查询来获得h_{i, j}, h_{i, j}=H₁(W_{i, j}), i∈{0, 1}, 1≤j≤m。将 < W_{i, j}, h_{i, j}, c_{i, j}>添加在H₁表中。若∀j, c_{i, j}=j对i=0或1成立, 则B成功。

2) B取i=0或1, 使得∀j, c_{i, j}=j。

3) B随机生成ρ, r₁, r₂, …, r_m∈${\mathbb{Z}}_p^*$, sk∈κ生成E=ε_sk(M_i), ${A_j} = \frac{\rho }{x}$(β_jU+(α_jx-β_j)U)+r_jU=ρα_jU+r_jU, 1≤j≤m, K=ρα_m+2U, B随机选择S, R∈{0, 1}^{lb p}, 将C=[E, A₁, A₂, …, A_m, B₁, B₂, …, B_m, K, S, R]回复给A。

阶段2  B重复阶段1的操作获得它所输入关键词的陷门, 其中有一个限制为:C未被询问过, 即未对D₀和D₁进行过陷门查询和解密查询。

最终, A会给出判断结果, 表明B给出的挑战C是否为D₀或D₁的密文。

猜测  B在H₃表的r_oi中选择随机r, 生成h^r和(h^r)^1/α₀ρ。B输出ê(P, P)^1/x, B成功获得ST或DT陷门的可能性为:${\varepsilon _1} = \prod\limits_{i = 1}^{{q_T}} {\left( {1 - \frac{1}{{{{\left( {{q_{{H_1}}}} \right)}^{{t_i}}}}}} \right)} \ge \prod\limits_{i = 1}^{{q_T}} {\left( {1 - \frac{1}{{{{\left( {{q_T}} \right)}^{{t_i}}}}}} \right)} \ge $$\prod\limits_{i = 1}^{{q_T}} {\left( {1 - \frac{1}{{{q_T}}}} \right)} = \frac{1}{e}$, B在模拟准备阶段成功的可能性为:ε₂≥1/(q_H2)^m, B输出正确的可能性可以规约为B解决优势为ε′>ε×$\frac{1}{e} \times {\left( {\frac{1}{{{q_{{H_1}}}}}} \right)^m} \times \frac{1}{{{q_{{H_3}}}}} = \frac{\varepsilon }{{e{{\left( {{q_{{H_1}}}} \right)}^m}{q_{{H_3}}}}}$的(q_T+1)-BDH问题的可能性。

5 应用方案

根据算法过程, 本文实现了服务器与客户端一对多的交互型可搜索加密云存储系统^[14], 将可搜索加密方案划分到服务器和客户端2个部分, 通过交互实现文件的存取和共享^[15]。

5.1 控制台算法的分析与实现

为进行算法效率测试, 需实现一个控制台算法, 从而避免在真实场景下网络与文件的读写影响算法的实际运行时间。本文借助Java的JPBC库来实现控制台算法^[16], 工具函数的说明如下:

1) 字符串处理函数:算法在具体描述中, 关键词以比特串形式存在, 因此, 需要将关键词编码成比特串。本文编码方案先取出字符串中每个字符的Ascii码, 将其转化为8位比特串, 将每个字符串的比特串拼接得到字符串的比特串标识, 上述过程可逆。

2) 哈希函数选择:算法中需要H₁、H₂、H₃ 3个哈希函数, 程序选择MD5消息摘要算法作为H₁、H₃, SHA1数字签名算法作为H₂。H₃的输入由比特串和对称加密密钥的比特串拼接构成。

参数设置:有限域的阶数为512比特位, 群的阶数为128比特位。

控制台算法运行结果如图 2所示。其中, H2=S说明STrapdoor匹配成功, origin_sk=get_sk表明DTrapdoor匹配成功并解密出正确密钥。

5.2 服务器-客户端的分析与实现

将可搜索加密方案分离到服务器与客户端2个部分^[17], 服务器交互界面如图 3所示, 客户端工具界面如图 4所示。

方案步骤说明如下:

1) 文件的加密方式:采用AES128加密算法进行加密。

2) 代数结构与元素的存储方式:不同于控制台程序, 服务端和客户端不再共享变量, 因此, 所有的群元素、群结构需要编码成某种形式并传送给服务器, 本文将群元素编码成byte数组进行传输, 将群结构以Java配置文件.properties形式存取。

3) 本地索引:算法本身能够实现连接查询, 但是需要用户自行记忆关键词在文件中的位置, 这对用户不够友好, 因此, 通过生成本地关键词索引, 实现用户本地的预查询, 这样可以避免记忆关键词位置, 同时也可以实现否定查询。

4) 密钥封装:由于用户无需记忆AES128的密钥, 因此为了简化程序过程, 通过群元素生成AES128密钥, 这样避免了将密钥编码成椭圆曲线上的点的繁琐步骤, 同时对安全性没有任何影响。

5) 密钥存储:自存自取的文件密钥均存储在本地, 本地工具默认对不同文件使用不同的密钥, 保证某个用户分享文件后, 分享对象不会获得解密该用户所有文件的能力。

6) 一对多分享设计:在本文算法步骤中, 同时分享文件给多个用户是不冲突的, 通过输入其他用户的公钥集合, 程序针对每个公钥生成一个私钥, 从而方便一对多的分享过程, 且相比于单一分享模式, 一对多分享需要的额外存储空间可以忽略不计。

7) 文件存取等步骤的简化:用户查询到的文件和公钥一般是多个, 本文方案能够对多个文件同时进行解密而非逐个解密, 对公钥集合进行统一上传而无需逐个上传。

5.3 效率分析

本节分析方案的效率, 用m、P、E、H和n分别代表关键词个数、一次双线性运算的复杂度、一次指数运算的复杂度、哈希运算和其他运算, p代表Z_p的阶数。本文方案与其他方案进行效率比较^[18], 结果如表 2所示。算法运行环境是Linux deepin15.5, Intel(R)Core(TM)i7-7700HQ, 8 GB内存, 语言为Java 8。

由于文件及其索引均以密文形式存储在云端, 因此文件与文件之间、索引与索引之间都具有不可区分性, 无法进行排序, 这使得在陷门匹配的过程中, 陷门需要通过顺序查找与所有文件索引一一匹配, 算法复杂度为O(n), 其中, 每一步都包含了2次双线性配对。在效率分析时, 本文不再考虑文件加密、密钥生成、密钥解密、文件解密过程中所消耗的时间, 原因是它们的时间相比于陷门匹配可忽略不计。

针对不同的关键词个数, 分别比较本文方案和基于PEKS的连接关键词方案(简称PEKS方案)在密文生成、陷门生成和单个文件匹配上的时间, 结果如图 5~图 7所示。在图 7中, worst是最长匹配时间, 即全部关键词匹配成功的时间, best是最短匹配时间, 即在第一个关键词就匹配失败的时间, average是平均匹配时间。可以看出, 本文方案与对比方案在密文生成上的效率相当, 而在陷门生成和文件匹配时, 由于对比方案以及多数方案^{[4, 19]}中采用决策树来实现连接关键词搜索, 需要生成多个陷门并进行多次匹配, 因此所需时间随着关键词个数的增多而显著提高, 而本文方案仅需单陷门单次匹配, 因此, 其陷门生成和匹配时间复杂度与关键词无关, 由结果可见, 本文方案在保证密文生成效率的同时, 大幅提高了连接关键词的搜索效率。

6 结束语

本文提出一种基于连接关键词的可搜索加密方案, 安全性证明结果显示, 破译该方案的难度高于求解BDH问题。考虑到记忆关键词位置时存在一定难度, 本文制作一个索引作为单关键词文件并加密上传, 用户可通过解密获得关键词位置信息, 方便其进行文件查询。此外, 该方案在不泄露私钥的前提下可以完成与他人的文件共享。但是, 本文方案中多个关键词使用单个陷门, 下一步将针对方案中可能存在的哈希碰撞问题进行研究并提出解决方案。