0 概述

随着互联网技术的迅速发展, 人们在日常工作和生活中产生及使用的数据量不断增大, 数据规模已由PB级发展到EB级甚至ZB级, 如何存储和处理大规模数据成为亟待解决的问题。云计算是通过互联网提供动态、易扩展和虚拟化资源的计算方式, 而云存储是云计算的应用模式, 其可远程高效存储数据, 能节省大量存储空间, 因此引起了人们的广泛关注, 并成为存储大数据的有效手段。

在云存储应用初期, 部分用户以明文形式上传数据, 由于云存储具有开放性和分布性, 数据脱离用户的物理控制存储在云端后, 一旦被外部攻击者截获或被恶意云服务提供者泄露, 将无法挽回损失。因此, 为保证所传数据的隐私性和安全性, 用户会将数据加密后再上传到云端。加密存储数据在一定程度上可以保证数据的隐私与安全, 但却给数据检索带来困难。

由于基于明文关键字的传统检索模型无法在密文下进行检索, 因此2000年SONG等人^[1]在对称密码体制的基础上提出可搜索加密的概念, 并设计出可在密文下进行检索的SWP方案。2004年BONEH等人^[2]首次提出公钥关键字搜索加密(Public Key Encryption with Keyword Search, PEKS), 并设计一种应用于邮件路由分发场景的方案, 将不同邮件分发到不同设备中, 公钥关键字搜索加密允许服务器根据接收到的陷门对不同关键字邮件选择分发路由, 且不会泄露邮件内容, 但是该方案在安全和效率方面存在不足。WATERS等人^[3]随后提出用来构造可搜索加密审计日志的新PEKS方法。GOLLE等人^[4]也提出基于连接关键词的可搜索加密方案, 可实现对多个关键词的搜索功能。2006年BYUN等人^[5]分析了文献[2]中PEKS方案, 指出该方案容易遭受关键字猜测攻击^[6-7], 此后研究者们提出大量抗关键字猜测攻击的PEKS方案^[8-10]。2016年XU等人^[11]提出合数阶双线性群下的PEKS方案, 该方案系统参数比其他方案更少, 且其安全性是基于静态假设下合数阶子群的不可区分性。文献[12]提出双服务器模型, 通过2个独立服务器分享秘密检索陷门执行搜索算法抵抗关键字猜测攻击。文献[13]通过加入发送者公私钥生成可搜索密文和陷门, 使服务器无法自行生成关键词陷门测试密文。文献[14]提出一种通过采用非确定算法生成关键字密文和陷门的方案, 可高效抵抗关键字猜测攻击。

然而PEKS框架本身存在一定不足, 即多数PEKS方案都需在服务器与接收者之间建立安全信道以传送陷门, 否则外部攻击者很容易截获关键字陷门进行搜索操作, 进而得到加密数据信息, 但是建立安全信道代价太高且很难实现。为解决该问题, 文献[15]提出无安全信道的公钥关键字搜索加密(Secure-Channel Free Public Key Encryption with Keyword Search, SCF-PEKS)方案, 由于关键字密文的生成需要云服务器公钥参与, 因此只有云服务器能够使用自身私钥检查关键字密文和陷门是否包含相同关键字。通过该方式, 用户可在无安全信道的情况下将关键字陷门发送到数据存储服务器。但是上述方案依赖于随机oracle模型, 而随机oracle模型不能真正反映方案在现实世界中的安全性。2009年FANG等人^[16]提出首个在标准模型下安全的SCF- PEKS方案, 但该方案检测算法太复杂, 不具备高效性。2011年EMURA等人^[17]利用匿名IBE、标签加密方案和一次性签名提出SCF-PEKS方案的通用设计方法。近期LI等人^[18]从静态假设出发提出在标准模型下安全高效的SCF-PEKS方案, 该方案主要基于判定性子群假设和DBDH假设, 与现有在标准模型下构造的相关方案相比, 具有更简洁的结构。

2009年RHEE等人^[19]指出SCF-PEKS方案不能抵抗由外部攻击者发起的离线关键字猜测攻击, 并在文献[20]中引入陷门不可区分性的概念, 证明抵抗关键词猜测攻击的充分条件是陷门的不可区分性。本文对文献[11, 18]提出的基于合数阶双线性对的可搜索加密方案进行分析, 发现上述方案的关键字陷门生成算法无法满足搜索关键字陷门的不可区分性。针对该问题, 本文在文献[11, 18]方案的基础上, 提出一种改进的无安全信道公钥可搜索加密方案, 同时基于DBDH假设对其是否满足关键字陷门的不可区分性进行证明, 并研究了该方案的计算复杂度和空间存储复杂度。

1 基本知识 1.1 合数阶双线性群

文献[21]最早提出合数阶双线性群, 令$\mathcal{G} $表示双线性群生成算法, 以安全参数λ作为输入, 输出阶为合数N=p₁p₂p₃的群G和G_T, 其中p₁、p₂、p₃为3个互不相同的素数。

定义1 (合数阶双线性映射)  设G和G_T是2个阶为N=p₁p₂p₃的乘法循环群, g是G的生成元。双线性映射e:G×G→G_T满足以下性质:

1) 可计算性:映射e:G×G→G_T可以被有效计算。

2) 双线性:对于任意g, h∈G和a, b∈${{\mathbb{Z}}_{N}}$, 存在e(g^a, h^b)=e(g, h)^ab。

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

令G=G_p1G_p2G_p3, 其中G_p1、G_p2和G_p3分别是群G中阶为p₁、p₂和p₃的子群。假设g是群G的1个生成元, 则g^p₂p₃是子群G_p1的生成元。同理, g^p₁p₃是子群G_p2的生成元, g^p₁p₂是子群G_p3的生成元。因此, 存在α₁, α₂∈${{\mathbb{Z}}_{N}}$, 使得h₁=(g^p₁p₂)^α₁和h₂=(g^p₁p₂)^α₂, 此时存在如下关系式:

$ e\left(h_{1}, h_{2}\right)=e\left(g^{p_{2} p_{3} \alpha_{1}}, g^{p_{1} p_{3} \alpha_{2}}\right)=e\left(g^{\alpha_{1}}, g^{p_{3} \alpha_{2}}\right)^{p_{1} p_{2} p_{3}}=1 $

(1)

如果选取i≤j、h_i∈G_pi、h_j∈G_pj, 则e(h_i, h_j)是群G_T中的单位元, 这说明合数阶双线性群中各子群G_p1、G_p2和G_p3相互正交。

1.2 判定性子群假设

假设1 给定群生成器G(λ), 定义其分布如下:

$ \begin{align} & G=\left( N={{p}_{1}}{{p}_{2}}{{p}_{3}}, G, {{G}_{T}}, e \right)\overset{R}{\mathop{\leftarrow }}\, \mathcal{G}, {{g}_{1}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}, {{g}_{3}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{3}}}}, \\ & {{g}_{1, 2}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}{{G}_{{{p}_{2}}}}, D=\left( {{g}_{1}}, {{g}_{3}}, {{g}_{1, 2}} \right), {{T}_{0}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}, {{T}_{1}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}{{G}_{{{p}_{2}}}} \\ \end{align} $

(2)

其中, G_p1、G_p2和G_p3分别是群G中阶为p₁、p₂和p₃的子群, G_p1G_p2是阶为p₁p₂的子群, g₁、g₃和g_{1, 2}是从对应群中随机选取的群元素。对于公开元组D和任意概率多项式时间的敌手A, 能正确区分出T₀与T₁的优势Adv_{g, A}^SD1(λ):=Pr[A(D, T₀)=1]－Pr[A(D, T₁)=1]关于λ是可忽略的。

假设2 给定群生成器$\mathcal{G}$(λ), 定义其分布如下:

$ \begin{align} & G=\left( N={{p}_{1}}{{p}_{2}}{{p}_{3}}, G, {{G}_{T}}, e \right)\overset{R}{\mathop{\leftarrow }}\, \mathcal{G}, {{g}_{1}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}, {{g}_{3}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{3}}}}, \\ & {{g}_{1, 2}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}{{G}_{{{p}_{2}}}}, {{g}_{2, 3}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{2}}}}{{G}_{{{p}_{3}}}}, D=\left( {{g}_{1}}, {{g}_{3}}, {{g}_{1, 2}}, {{g}_{2, 3}} \right), \\ & {{T}_{0}}\overset{R}{\mathop{\leftarrow }}\, {{G}_{{{p}_{1}}}}{{G}_{{{p}_{3}}}}, T_{1}^{{}}\overset{R}{\mathop{\leftarrow }}\, G \\ \end{align} $

(3)

其中, G_p1G_p3是群G中阶为p₁p₃的子群, G_p2G_p3是阶为p₂p₃的子群。对于公开元组D和任意概率多项式时间的敌手A, 能正确区分出T₀与T₁的优势Adv_{g, A}^SD2(λ):=Pr[A(D, T₀)=1]－Pr[A(D, T₁)=1]关于λ是可忽略的。

1.3 DBDH假设

设G₁和G₂是阶为q的循环群, g是G₁的生成元, e:G₁×G₁→G₂是双线性映射。随机选取a, b, c, r∈G_p, DBDH假设指对任意概率多项式时间的敌手A区分e(g, g)^abc与e(g, g)^r的优势Adv^DBDH_{G1, A}(λ)=|Pr[A(g, g^a, g^b, g^c, e(g, g)^abc)=1]－Pr[A(g, g^a, g^b, g^c, e(g, g)^r)=1]|关于λ是可忽略的。

1.4 PEKS和SCF-PEKS

PEKS和SCF-PEKS方案都涉及发送者(数据拥有者)、接收者(用户)和云服务器三方参与者。发送者生成关键字的可搜索密文并将其连同密文数据发送给云服务器, 接收者生成关键字陷门, 云服务器根据关键字密文和陷门执行数据检索操作, 并将匹配的密文数据发送给接收者。

1.4.1 PEKS方案

定义2  公钥可搜索加密方案由以下4个算法组成:

1) Setup(λ)算法。输入安全参数λ, 算法生成全局参数gp, 用户公钥pk和私钥sk。

2) PEKS(gp, pk, ω)算法。由发送者执行, 输入全局参数gp、用户公钥pk和关键字ω, 输出关于关键字ω的可搜索密文C。

3) Trapdoor(gp, sk, ω)算法。由用户执行, 输入全局参数gp、用户私钥sk和关键字ω, 生成关键字陷门T_ω。

4) Test(gp, C, T_ω)算法。输入全局参数gp、可搜索密文C和关键字陷门T_ω, 服务器对关键字密文和陷门进行验证, 如果验证匹配则输出1, 否则输出0。

1.4.2 SCF-PEKS方案

SCF-PEKS方案与PEKS方案主要区别在于云服务器的公钥和私钥是否分别参与了可搜索密文生成算法和检测匹配算法。由于PEKS方案没有使用云服务器的公私钥对, 因此其传送关键字陷门时需要使用安全信道才能避免受到攻击。而因为SCF-PEKS方案中云服务器的公钥参与了可搜索关键字密文生成过程, 只有拥有对应私钥的云服务器才能进行检测匹配算法, 所以传送关键字陷门时不需安全信道参与。

定义3  无安全信道的公钥可搜索加密方案由以下4个算法组成:

1) Setup(λ)算法。输入安全参数λ, 生成全局参数gp, 并输出云服务器的公私钥对(pk_S, sk_S), 以及接收者的公私钥对(pk_R, sk_R)。

2) SCF-PEKS(gp, pk_S, pk_R, ω)算法。输入gp、接收者的公钥pk_R、云服务器的公钥pk_S以及关键字ω, 由发送者输出关键字ω的可搜索密文C。

3) Trapdoor(gp, sk_R, ω)算法。输入gp和接收者的私钥sk_R, 由接收者输出关键字ω的陷门T_ω。

4) Test(gp, sk_S, C, T_ω)算法。输入gp、关键字密文C和关键字陷门T_ω, 云服务器利用自身私钥对密文和陷门进行匹配验证, 如果匹配则输出1, 否则输出0。

1.5 陷门不可区分性

为避免关键字猜测攻击, 在设计方案时要保证关键字密文和陷门的不可区分性。本节只给出陷门不可区分性的安全性定义, 其他可参考文献[18]。根据文献[20]提出的陷门不可区分性概念及安全模型, 假设敌手A为外部攻击者(不是服务器和接收者), 关键字陷门的不可区分性通过多项式时间的挑战者B与敌手A之间交互游戏来描述, 具体过程如下:

1) Setup。给定安全参数λ, 挑战者B生成全局参数gp、云服务器和接收者的公私钥对(pk_S, sk_S)和(pk_R, sk_R), 并将gp、pk_R和pk_S发送给敌手A。

2) Queryphase1。敌手A可适应性的询问如下预言机O_T, 访问次数以多项式时间限定:

(1) 搜索陷门预言机O_T。输入接收者的私钥sk_R和选择的关键字ω∈KS_ω, O_T预言机返回关键字陷门T_ω←Trapdoor(gp, sk_R, ω)给敌手A。

(2) Challenge。一旦敌手A决定Queryphase1结束, A选择未询问过O_T预言机的关键字(ω₀, ω₁), 并将其发送给挑战者B。挑战者B随机选择b∈{0, 1}, 计算关键字ω_b对应的陷门T_ωb←Trapdoor(gp, sk_R, ω_b)并返回给敌手A。

3) Queryphase2。敌手A可以继续访问O_T预言机, 但要求不能就关键字(ω₀, ω₁)对预言机O_T进行询问。

4) Guess。敌手A猜测b′, 如果b′=b, 则敌手A获胜, 否则敌手A失败。

如果对任意概率多项式时间的敌手A成功区分游戏优势$\operatorname{Adv}_{\mathrm{A}}^{\mathrm{Game}}(\lambda)=\left|\operatorname{Pr}\left[b^{\prime}=b\right]-\frac{1}{2}\right|$关于λ是可忽略的, 则称陷门算法满足关键字的不可区分性。

2 可搜索加密方案分析

本节主要对文献[11, 18]分别提出的2个基于合数阶双线性对的公钥可搜索加密方案进行分析。上述方案对关键字陷门的设计均无法保证关键字陷门不可区分性, 存在安全问题。

2.1 文献[11]方案分析

文献[11]方案的安全性主要基于合数阶双线性群的子群不可区分性, 该方案具有IND-CKA安全性, 方案具体设计可参考文献[11], 下文对其中的Setup算法和Trapdoor算法进行阐述。

1) Setup算法。设G是阶为合数N=p₁p₂p₃的乘法循环群, 其中p₁、p₂、p₃互不相同的素数。记G的p₁阶子群为G_p1, 随机选取u, g, h∈G_p1和α∈${{\mathbb{Z}}_{N}}$, 计算e(g, g)^α。KS_ω=${{\mathbb{Z}}_{N}}$为关键字空间, 返回系统私钥sk=α, 公共参数gp={G, G_T, e, N, u, g, h, e(g, g)^α, KS_ω}。

2) Trapdoor算法。输入关键字ω和私钥sk, 用户随机选取r∈${{\mathbb{Z}}_{N}}$和R₃, R₃′∈G_p3, 计算关键字陷门T=[T₀, T₁]=[g^α(u^ωh)^rR₃′, g^rR₃]。

对文献[11]方案的安全性分析如下:

假设存在1个外部攻击者A, 给定2个关键字(ω₀, ω₁), 且A可获取包含目标关键字ω_b∈{ω₀, ω₁}的陷门T_ωb=[T₁, T₂]=[g^α(u^ω_bh)^rR₃′, g^rR₃], 外部攻击者A可通过以下攻击方式来区分该陷门中的关键字:

1) 外部攻击者A通过系统参数gp={G, G_T, e, N, u, g, h, e(g, g)^α}获取u、g、h的值。

2) A随机选择ω′∈{ω₀, ω₁}, 并计算得到:

$ \begin{aligned} M=\frac{e\left(T_{1}, g\right)}{e\left(T_{2}, u^{w^{\prime}} h\right)}=\frac{e\left(g^{\alpha}\left(u^{\omega_{b}} h\right)^{r} R_{3}^{\prime}, g\right)}{e\left( g^{r} R_{3}, u^{w^{\prime}} h\right)}=\\ \frac{e\left(g^{\alpha}, g\right) e\left(\left(u^{\omega_{b}} h\right)^{r}, g\right)}{e\left(g^{r}, u^{w^{\prime}} h\right)}=\frac{e(g, g)^{\alpha} e\left(u^{\omega_{b}} h, g\right)^{r}}{e\left(u^{w^{\prime}} h, g\right)^{r}} \end{aligned} $

(4)

3) 若ω_b=ω′, 则M=e(g, g)^α, 由于e(g, g)^α已知, 外部攻击者A可不通过验证测试算法就能区分并获取陷门中的关键字, 因此该方案不满足陷门的不可区分性。

2.2 文献[18]方案分析

文献[18]提出在标准模型下利用合数阶双线性对的SCF-PEKS方案, 该方案具有安全性和高效性, 且主要基于判定性子群假设和DBDH假设, 方案具体设计可参考文献[18], 以下对其中的Setup算法、SCF-PEKS算法和Trapdoor算法进行阐述。

1) Setup(λ)算法。输入安全参数λ, 选取1个抗碰撞的单向哈希函数H:{0, 1}^*→${{\mathbb{Z}}_{N}}$, 系统全局参数gp=(N, G, G_T, e, H, KS_ω), 关键字空间KS_ω=${{\mathbb{Z}}_{N}}$。服务器随机选取x∈$\mathbb{Z}_{N}^{*}$和h∈G_p1, 计算得到X=g₁^x、Y=e(X, h)。输出服务器公钥pk_S=(g₁, h, Y)、私钥sk_S=x; 而接收者随机选取y∈${{\mathbb{Z}}_{N}}$、u∈G_p1、g₃∈G_p3, 接收者的公私钥分别为pk_R=(g₁, g₁^y, e(g₁, u))、sk_R=(y, u, g₃)。

2) SCF-PEKS(gp, pk_S, pk_R, ω)算法。发送者随机选取r, s∈${{\mathbb{Z}}_{N}}$, 计算U=g₁^s、t=H(e(X, h)^s)、V=g₁^(y+ω)r/t以及W=e(g₁, u)^r, 输出关键字密文C=(V, U, W)。

3)Trapdoor(gp, sk_R, ω)算法。接收者确认关键字后, 随机选取R₃∈G_p3, 计算T_ω=u^1/(y+ω)R₃, 返回T_ω。

对文献[18]方案的安全性分析如下:

由于该方案在无安全信道的环境下传送关键字陷门, 因此陷门很容易被攻击者获取, 且攻击者只需按如下攻击方式进行计算, 便可轻易区分并获取陷门中的关键字, 具体攻击过程为:

1) 给定2个关键字(ω₀, ω₁), 假设存在1个外部攻击者A, 将包含目标关键字ω_b∈{ω₀, ω₁}的陷门T_ωb=u^1/(y+ω_b)R₃发送给A。

2) 将服务器和接收者的公钥pk_S=(g₁, h, Y)和pk_R=(g₁, g₁^y, e(g₁, u))发送给A。

3) A随机选择ω′∈{ω₀, ω₁}, 并计算得到:

$ \begin{array}{c} M=e\left(T_{\omega_{b}}, g_{1}^{y} \cdot g_{1}^{w^{\prime}}\right)=e\left(u^{1 /\left(y+\omega_{b}\right)} R_{3}, g_{1}^{y} \cdot g_{1} \omega^{\prime}\right)= \\ e\left(u^{1 /\left(y+\omega_{b}\right)}, g_{1}^{y+\omega^{\prime}}\right)=e\left(u, g_{1}\right)^{\frac{y+\omega^{\prime}}{y+\omega_{b}}} \end{array} $

(5)

4) 若ω_b=ω′, 则M=e(u, g₁), 由于e(u, g₁)在pk_R中已知, 攻击者A可区分陷门中的关键字, 因此该方案不满足陷门的不可区分性。

3 SCF-PEKS改进方案

针对文献[11]和文献[18]方案存在的安全问题, 本文提出一种改进的基于合数阶双线性对的无安全信道可搜索公钥加密方案, 该方案可保证关键字陷门的不可区分性, 且能抵抗外部关键字猜测攻击。

3.1 本文方案设计

本文方案由4个算法组成, 其中Setup(λ)算法、SCF-PEKS(gp, pk_S, pk_R, ω)算法与文献[18]方案中算法一致, 另外改进的2个算法具体如下:

1) Trapdoor(gp, sk_R, ω)算法。接收者随机选取z∈G_N和R₃∈G_p3, 并计算T₁=g₁^z与T₂=u^n/(y+ω)R₃, 接收者n=H(e(X, h)^z)发送关键字陷门T_ω=(T₁, T₂)给云服务器。

2) Test(gp, T_ω, C, sk_S, ω)算法。服务器先使用自身私钥计算t=H(e(U, h)^x)和n=H(e(T₁, h)^x), 再检验e(V^t, T₂)=Wⁿ是否成立。若等式成立, 则输出1, 否则输出0。

对本文方案的正确性证明如下:

$ t=H\left(e(U, h)^{x}\right)=H\left(e\left(g_{1}^{s}, h\right)^{x}\right)=H\left(e(X, h)^{s}\right) $

(6)

$ n=H\left(e\left(T_{1}, h\right)^{x}\right)=H\left(e\left(g_{1}^{z}, h\right)^{x}\right)=H\left(e(X, h)^{z}\right) $

(7)

$ \begin{aligned} e\left(V^{t}, T_{2}\right)=& e\left(\left(g_{1}^{(y+w) r / t}\right)^{t}, u^{n /(y+w)} R_{3}\right)=\\ & e\left(g_{1}^{(y+w) r}, u^{n /(y+w)} R_{3}\right)=e\left(g_{1}, u\right)^{r n}=W^{n} \end{aligned} $

(8)

由式(6)~式(7)可知, 服务器通过自身私钥可计算出正确的t和n, 将其代入式(8)计算得知, 陷门和可搜索密文能够正确匹配, 从而证明了本文方案具有正确性。

本文方案主要在生成陷门的Trapdoor算法基础上进行重新设计。根据上述分析, 改进方案在生成陷门时增加1个n次幂, 其中n=H(e(X, h)^z), z为随机值。从而保证陷门即使在被攻击者获取的情况下, 也无法通过计算区分出关键字, 且必须计算出n值才能进行验证操作, 虽然增加了计算量, 但是可保证关键字陷门的不可区分性。采用对文献[18]方案相同的攻击方式对本文方案进行攻击, 可以得到:

$ \begin{array}{c} M=e\left(u^{n /\left(y+\omega_{b}\right)} R_{3}, g_{1}^{y} \cdot g_{1}^{\omega^{\prime}}\right)= \\ e\left(u^{n /\left(y+\omega_{b}\right)}, g_{1}^{y+\omega^{\prime}}\right)=e\left(u, g_{1}\right)^{\frac{n\left(y+\omega^{\prime}\right)}{y+\omega_{b}}} \end{array} $

(9)

若ω′=ω_b, 则M=e(u, g₁)ⁿ, 此时对于外部攻击者而言, 虽然e(u, g₁)已知, 但n值需要通过云服务器或接收者的私钥计算得到, 攻击者无法通过M值判断ω′是否等于ω_b, 不能对陷门中的关键字进行区分, 因此, 本文方案能抵抗外部关键字猜测攻击。

3.2 安全性证明

本文主要证明改进方案关键字陷门的不可区分性, 而由于可搜索密文的不可区分性等其他安全性基于判定性子群假设和DBDH假设, 因此本文安全性证明过程与文献[18]中的安全性证明过程基本一致, 具体可参考文献[18]。

定理1 如果DBDH假设是困难的, 那么对于任意概率多项式时间算法的敌手A, 能区分关键字陷门的概率优势可忽略。

证明 假设存在多项式时间算法的外部敌手A攻击本文方案, 构造1个DBDH游戏的挑战者B。模拟过程为:挑战者设置阶为p₁的群G′、G′_T以及双线性映射e:G′×G′→G′_T, 其中G′、G′_T分别为合数阶群G、G_T的素数阶子群。输出参数(g₁, g₁^a, g₁^b, g₁^c, T)给B, 而挑战者B的目标为区分T等于e(g₁, g₁)^abc还是等于G_T中的随机元素。

敌手A和挑战者B进行游戏如下:

1) Setup。输入安全参数λ, 选取1个抗碰撞的单向哈希函数H:{0, 1}^*→${{\mathbb{Z}}_{N}}$, 双线性映射参数为(N, G, G_T, e), 令关键字空间KS_ω=${{\mathbb{Z}}_{N}}$, 得到全局参数gp=(N, G, G_T, e, H, KS_ω)。设X=g₁^a、h=g₁^b、Y=e(X, h), 可得服务器公钥为pk_S=(g₁, h, X, Y), 随机选取y∈${{\mathbb{Z}}_{N}}$、u∈G_p1、g₃∈G_p3, 输出接收者公钥pk_R=g₁, g₁^y, e(g₁, u), 将pk_S和pk_R发送给敌手A。

2) Queryphase1。敌手A向预言机O_T询问关键字ω_i的陷门。预言机O_T输入接收者的私钥sk_R和关键字ω_i后, 随机选择z∈${{\mathbb{Z}}_{N}}$和R₃∈G_p3, 计算T₁=g₁^z、n=H(e(X, h)^z)、T₂=u^n/(y+ω_i)R₃, 将关键字陷门T_ωi=(T₁, T₂)返回敌手A。

3) Challenge。在多次询问预言机O_T之后, 敌手A随机选择2个未询问过预言机O_T的关键字(ω₀, ω₁)发送给挑战者B, 挑战者B随机选取b∈{0, 1}, 设挑战关键字ω^*=ω_b, 随机选取R₃∈G_p3、n=H(T)、T₁=g₁^c、T₂=u^n/y+ω*R₃, 将关键字陷门T_ω^*=(T₁, T₂)发送给A。

4) Guess。敌手A输出猜测b′。在验证过程中, 当b′=b时, n=H(e(T₁, h)^a)=H(e(g₁, g₁)^abc), T=e(g₁, g₁)^abc, 则T_ω^*为合法输出, 返回1;当b′≠b时, T≠e(g₁, g₁)^abc, 则T是G_T中随机元素, 返回0。

如果敌手A能区分陷门中的关键字, 那么挑战者B便可攻破DBDH假设。因此, 本文方案的关键字陷门具有不可区分性, 可抵抗外部攻击者的关键字猜测攻击。

3.3 性能比较

将文献[11, 18, 20, 22]中的可搜索加密方案与本文方案的陷门和密文的尺寸、各算法的计算复杂度以及是否具有陷门的不可区分性等信息进行对比, 令|G|、|G_T|、|${{\mathbb{Z}}_{p}}$|分别为G、G_T、${{\mathbb{Z}}_{p}}$中的元素大小, P为双线性对运算, E为模幂运算, H为哈希函数运算, 结果如表 1所示。可以看出, 本文方案与文献[11, 18]中同为基于合数阶双线性群的方案及文献[20]中具有陷门不可区分性方案差别较小, 具有良好的陷门和密文尺寸。虽然本文方案验证测试算法的计算复杂度稍高, 但文献[11, 18]方案无法保证关键字陷门的不可区分性, 文献[20]方案不是在标准模型下构造, 因此本文方案在现实环境中比文献[11, 18, 20, 22]方案更加安全。而文献[22]提出的陷门不可区分性方案虽然安全性与本文方案接近, 但是其在密文尺寸和各算法的计算复杂度上均不如本文方案, 效率较低。综上所述, 本文方案在相同的计算复杂度、良好的陷门和密文尺寸情况下, 比其他可搜索加密方案具有更好的安全性。

4 结束语

本文对传统基于合数阶双线性对的可搜索公钥加密方案进行研究, 指出其中陷门算法不具有关键字不可区分的安全属性, 并提出一种改进的基于合数阶双线性对的可搜索加密方案。该方案在陷门、密文尺寸及计算复杂度与原方案接近的情况下, 可保证关键字陷门的不可区分性, 从而抵抗外部关键字猜测攻击。关键字猜测攻击较多由外部攻击者发起, 如果由内部攻击者(恶意服务器)发起猜测攻击, 则更容易造成数据泄露。后续将在本文对外部关键字猜测攻击研究的基础上, 继续对合数阶双线性对进行改进, 以抵抗内部关键字猜测攻击并提高计算效率。