0 概述

在电子邮件系统中, 当数据发送者发给用户的邮件因用户的私人原因而无法及时处理时, 用户希望将该邮件共享给被委托者, 并由对方帮助其处理该邮件。一般情况下, 用户先下载某个邮件, 用其私钥解密该邮件并使用被委托者的公钥进行加密处理, 最后发送给被委托者, 该方式需要较大的计算代价和通信代价, 而代理重加密(Proxy Re-Encryption, PRE)技术可有效解决这一问题。

1998年, BLAZE等人^[1]提出PRE的概念, 主要内容是委托者通过一个半可信的代理者将密文授权给被委托者, 且在这个过程中, 代理者得不到消息的任何信息。文献[2]提出一个单向的PRE方案, 但是该方案只能达到选择明文安全的要求, 文献[3]提出第一个满足IND-CCA2的双向PRE方案。文献[4]在文献[5]的基础上, 改进了方案的安全模型, 并构造一个安全的IND-CCA2单向的PRE方案。文献[6]提出多跳PRE方案, 同年, 文献[7]提出电子病历中带关键字搜索的公钥加密方案。为解决复杂证书问题和密钥管理问题, 文献[8]提出新的基于证书条件的PRE方案。文献[9]构造管理云端数据访问授权确定性更新的PRE方案。为解决云端数据共享问题, 文献[10]提出标准模型下CPA安全的格上PRE方案。

随着电子邮件服务器上数据的增加, 为了实现密文搜索和数据共享2个功能, 文献[11]提出带关键字搜索的PRE的概念, 且构造在随机预言模型下可证明安全的PRES方案, 但文献[12]指出文献[11]存在使用了一次性强不可伪造签名来保证方案安全性的限制。文献[13]构造出有效且不使用一次性强不可伪造签名的PRE方案, 并证明该方案可使选择密文安全。为提高方案的效率, 文献[14]依据文献[11, 15]构造出只对部分文件的密文进行重加密的方案模型。为抵抗由不可信服务器执行的关键字猜测攻击, 文献[16]提出新的支持关键字搜索的加密方案, 文献[17]提出基于关键字搜索属性的PRE方案。

现有的支持关键字搜索的PRE方案存在一些问题需要解决, 如抵抗关键字猜测攻击和数据篡改等。在文献[18-19]中, 验证等式的信息都是公开信息或对方发送的信息, 易遭受篡改攻击。针对这一问题, 本文提出在加密电子邮件背景下支持关键字搜索的PRE方案。在该方案中, 服务器、邮箱网关与被委托者的验证方式均不同, 并且其采用更加高效的对称加密方式, 以提高搜索效率和解密效率。

1 基础知识 1.1 双线性对

令(G₁, +)和(G₂, ×)是阶为素数p、q的循环群, 双线性映射e:G₁×G₁→G₂满足以下性质:

1) 双线性:对任意的P, Q∈G₁, 存在a, b∈Z_q^*, 有e(aP, bQ)=e(P, Q)^ab成立。

2) 非退化性:存在P, Q∈G₁, 满足e(P, Q)≠1。

3) 可计算性:对于任意的P, Q∈G₁, 存在有效的算法计算e(P, Q)。

1.2 相关的困难问题

1) 判定Diffie-Hellman(Decisional Diffie-Hellman, DDH)问题。

给定一个四元组(g, g^a, g^b, g^c), 其中随机取a, b, c∈Z_p^*, g为群G₁的一个生成元, 判定g^c=g^ab是否成立。

2) 双线性判定Diffie-Hellman(Decisional Bilinear Diffie-Hellman, DBDH)问题。

给定一个五元组(g, g^a, g^b, g^c, r), 其中随机取a, b, c∈Z_p^*, 且r∈G₂, g为G₁群的一个生成元, 判定r=e(g, g)^abc是否成立。

3) 商判定Bilinear Diffie-Hellman(Quotient Decisional Bilinear Diffie-Hellman, QDBDH)问题。

给定一个四元组(g, g^a, g^b, r), 其中随机取a, b, c∈Z_p^*, 且r∈G₂, g为G₁群的一个生成元, 判定$r = e{\left( {g, g} \right)^{\frac{b}{a}}}$是否成立。

2 方案模型和安全模型 2.1 方案摸型

本节提出面向电子邮件高效支持关键字搜索的PRE方案。本方案实现了密文授权和密文搜索的功能, 具体如下:邮件发送者将已加密的邮件发送给用户i, 而用户i希望将该邮件授权给用户j处理, 便由加密邮箱服务器作为代理者对密文进行重加密, 将邮箱网关搜索重加密邮件密文, 并发送给用户j解密。该方案包括如下算法:

1) Setup(I):输入安全参数I^l, 输出系统参数Params。

2) KeyGen(Params):输入系统参数Params, 输出用户和加密邮箱服务器S的公私钥对。

3) ReKeyGen(X_i, X_j):输入用户i的私钥X_i和用户j的私钥X_j, 加密邮箱服务器S生成重加密密钥RK_i→j。

4) Enc(Y_i, Y_S, w, m):输入用户i的公钥Y_i、加密邮箱服务器S的公钥Y_S、关键字w和明文m∈{0, 1}^*, 输出基于用户i公钥的密文CT_i。

5) ReEnc(CT_i, Y_i, X_S):输入基于用户i公钥的密文CT_i、用户i的公钥Y_i、加密邮箱服务器S的私钥X_S、重加密密钥RK_i→j, 加密邮箱服务器S输出基于用户j公钥的密文CT_j。

6) Trapdoor(X_j, Y_s, w, CT_j):输入用户j的私钥X_j、加密邮箱服务器S的公钥Y_S、基于用户j公钥的密文CT_j和关键字w, 用户j生成陷门T。

7) Test(CT_j, T):输入基于公钥的密文CT_j和关键字陷门T, 邮件网关通过算法Test(CT_j, T)验证陷门与密文是否匹配。若陷门与密文相匹配, 邮件网关发送基于用户j公钥的密文给用户j, 否则, 邮箱网关输出⊥。

8) Dec(CT_j):输入密文CT_j和私钥X_j, 用户j输出明文m。

2.2 安全模型

在标准模型下, 本文方案满足关键字密文隐私安全和陷门隐私安全^[20-22]。

2.2.1 关键字密文隐私安全

为满足关键字密文的不可区分性, 本文方案考虑敌手A_i(i=1, 2)和挑战者B之间的2个游戏。

游戏1    该游戏的目的是证明密文的不可区分性。在游戏中, 本文方案假设敌手A₁是恶意的邮箱服务器。

系统建立   挑战者B产生公共参数并将其给敌手A₁。

询问阶段1   敌手A₁进行如下询问:

1) 公钥预言询问O_Yi(i):挑战者B模拟算法KeyGen产生公私钥对(Y_i, X_i)并将公钥Y_i公开; 敌手A₁模拟算法KeyGen产生它的公私钥对(Y_j, X_j)并将公钥Y_j公开。

2) 重加密密钥询问阶段O_RK(X_i, X_j):挑战者B模拟ReKeyGen算法产生重加密密钥RK_i→j并输出给敌手A₁。

3) 重加密预言阶段O_Re(Y_i, Y_j, CT_i):挑战者B模拟重加密算法生成基于被委托者公钥的密文CT_j并将其发送给敌手A₁。

4) 陷门预言阶段O_T(w, X_j):敌手进行询问, 挑战者B则回应相对应的陷门。

5) 解密预言阶段O_Dec(Y_i, CT_j):挑战者B输出Dec(CT_j)给敌手A₁。

挑战   当询问阶段1完毕, 敌手A₁选择2个明文(m₀, m₁)发送给挑战者B。挑战者B随机选取δ∈{0, 1}, 并设置嵌入困难问题的挑战密文发送给敌手A₁。

询问阶段2  除了不能询问挑战密文及其衍生外, 其他询问同询问阶段1一致。

猜测  敌手返回猜测δ′, 如果δ′=δ, 则敌手猜测成功, 输出1, 否则, 输出0。游戏1中的优势定义为${\rm{Adv}}_{{A_1}}^{{\rm{Game1}}}\left( k \right) = \left| {\Pr \left[ {\delta = \delta '} \right] - \frac{1}{2}} \right|$。

游戏2  该游戏的目的是证明关键字的不可区分性。在游戏中, 本文方案假设敌手A₂是外部攻击者, 在游戏中, 挑战者B和敌手A₂进行如下交互:

系统建立  挑战者B产生公共参数并将其给敌手A₂。

询问阶段1  重复游戏1中的询问阶段1。

挑战  当询问阶段1结束, 敌手A₂选择2个关键字(w₁, w₂)、明文m和公钥Y^*一起发送给挑战者B。挑战者B随机选择δ∈{0, 1}, 并设置嵌入困难问题的挑战密文发送给敌手A₂。

询问阶段2  敌手A₂进行询问时, 除了不能询问挑战密文及其衍生外, 其他询问同询问阶段1一致。

猜测  敌手返回猜测δ′, 如果δ′=δ, 则挑战成功, 输出1, 否则, 输出0。游戏2中的优势定义为${\rm{Adv}}_{{A_2}}^{{\rm{Game2}}}\left( k \right) = \left| {\Pr \left[ {\delta = \delta '} \right] - \frac{1}{2}} \right|$。

2.2.2 陷门隐私安全

为了抵抗关键字猜测攻击, 文献[12]引入了陷门不可区分性。

游戏3   假设敌手A₃是外部攻击者, 在游戏中, 挑战者B和敌手A₃进行如下交互:

系统建立  挑战者B产生公共参数并公开。

询问阶段1   敌手A₃对关键字w进行陷门询问, 挑战者B回应陷门。

挑战阶段   敌手A₃选择2个关键字(w₁, w₂)、明文m和公钥Y^*一起发送给挑战者B。挑战者B随机选取δ∈{0, 1}, 并计算陷门发送给敌手A₃。

询问阶段2   除了不能询问挑战关键字及其衍生外, 其他询问同询问阶段1一致。

猜测   敌手返回猜测δ′, 如果δ′=δ, 则挑战成功, 输出1, 否则, 输出0。游戏3中的优势定义为${\rm{Adv}}_{{A_3}}^{{\rm{Game3}}}\left( k \right) = \left| {\Pr \left[ {\delta = \delta '} \right] - \frac{1}{2}} \right|$。

3 方案设计 3.1 方案构造

本文提出的方案包括8个部分, 具体设计如下:

1) Setup(I):输入安全参数I^l, 输出阶为素数p的循环加法群G₁和循环乘法群G₂, g为群G₁的生成元, g₂, u, v, d是群G₁上的随机元, 双线性映射对e:G₁×G₁→G₂。方案构造2个散列函数:H₁:G₁×{0, 1}^*×{0, 1}^L→Z_p^*, H₂:G₂→{0, 1}^L, L为对称密钥K的长度, 则系统参数Params={P, G₁, G₂, e, g, g₁, u, v, d, H₁, H₂, K)。

2) KeyGen(Params):输入系统参数Params, 用户i随机选择X_i∈ Z_p^*, 并计算Y_i=g^X_i, 则公私钥对为(X_i, Y_i)。加密邮箱服务器S随机选取X_S∈Z_p^*, 计算Y_S=g^X_S作为加密邮箱服务器S的公钥。

3) ReKeyGen(X_i, X_j):输入用户i的私钥X_i和用户j的私钥X_j, 生成重加密密钥$R{K_{i \to j}} = \frac{{{X_j}}}{{{X_i}}}\bmod p$。具体操作如下:

(1) 用户i选取r′∈ Z_p^*, 并发送r′·X_imod p给用户j, 同时发送r′给加密邮箱服务器S。

(2) 用户j计算$\frac{{{X_j}}}{{r'{X_i}}}$并发送给加密邮箱服务器S。

(3) 利用加密邮箱服务器S计算$R{K_{i \to j}} = r' \cdot \frac{{{X_j}}}{{r'{X_i}}} = \frac{{{X_j}}}{{{X_i}}}\bmod p$作为PRE密钥。

4) Enc(Y_i, Y_S, w, m):输入用户i的公钥Y_i、加密邮箱服务器S的公钥Y_S、关键字w和明文m∈{0, 1}^*, 用户i进行如下操作:

(1) 选取r∈ Z_p^*, 计算A=g^r, B=Y_i^r, 用对称加密算法计算C=Enc_K(m)。

(2) 计算D=e(Y_s, g^w₂)^r, E=H₂(e(g, g)^r)⊕K。

(3) 随机选取t∈ Z_p^*, 计算h=H₁(A, C, E), D₁=e(g, g₂^wh)^r, F=(u^hv^td)^r, G=g₂^rw。

(4) 输出基于用户i公钥的密文CT_i=(t, A, B, C, D, D₁, E, F, G)。

5) ReEnc(CT_i, Y_i, X_S):输入密文CT_i、用户i的公钥Y_i、加密邮件服务器S的私钥X_S和重加密密钥RK_i→j, 邮件服务器S计算h=H₁(A, C, E), 并验证式(1)是否成立:

$ {D^{\frac{1}{{{X_S}}}}}e\left( {A, {Y_i}\left( {{u^h}{v^t}d} \right)} \right) = e\left( {g, B \cdot F \cdot G} \right) $

(1)

若式(1)成立, 利用加密邮件服务器S计算B′=B^RK_i→j=Y_j^r, 输出基于用户j公钥的密文CT_j=(t, A, B′, C, D, D₁, E, F, G); 否则输出⊥。

6) Trapdoor(X_j, Y_s, w, CT_j):输入用户j的私钥X_j、加密邮件服务器S的公钥Y_S、基于用户j公钥的密文CT_j和关键字w, 用户j计算h=H₁(A, C, E), 从而得到陷门$T = {\left( {g_2^wh} \right)^{\frac{1}{{{X_j}}}}}$。

7) Test(CT_j, T):输入基于用户j公钥的密文CT_j=(t, A, B′, C, D, D₁, E, F, G)和关键字w的陷门T, 加密邮件网关验证式(2)是否成立:

$ e\left( {B', T} \right) = {D_1} $

(2)

若式(2)成立, 用加密邮件网关将基于用户j公钥的密文CT_j发送给用户j; 否则输出⊥。

8)Dec(CT_j):输入密文CT_j, 用户j计算h=H₁(A, C, E), 并验证式(3)是否成立:

$ e{\left( {B', g} \right)^{\frac{1}{{{X_j}}}}} = e\left( {g, A} \right) $

(3)

若式(3)成立, 用户j通过式(4)计算对称密钥K′, 则明文m=Dec_K′(C); 否则输出⊥。

$ K' = E \oplus {H_2}\left( {e{{\left( {B', g} \right)}^{^{\frac{1}{{{X_j}}}}}}} \right) $

(4)

3.2 正确性证明

本文方案满足正确性。在重加密过程中, 邮件服务器验证式(1)是为了证明密文CT_i在传输过程中并没有被篡改。在搜索过程中, 加密邮件网关通过验证式(2)来实现关键字与密文之间的匹配。在解密过程中, 用户j通过式(3)验证重加密密文是否被篡改, 通过式(4)解密密文。验证过程如下:

$ \begin{array}{l} 1){D^{\frac{1}{{{X_S}}}}}e\left( {A, {Y_i}\left( {{u^h}{v^t}d} \right)} \right) = e{\left( {{Y_S}, g_2^w} \right)^{r\frac{1}{{{X_S}}}}}e\left( {{g^r}, {Y_i}\left( {{u^h}{v^t}d} \right)} \right) = e{\left( {g, g_2^w} \right)^r}e\left( {{g^r}, {Y_i}\left( {{u^h}{v^t}d} \right)} \right) = \\e\left( {{g^r}, g_2^w{Y_i}\left( {{u^h}{v^t}d} \right)} \right) = e\left( {g, g_2^{wr}{g^{{X_i}r}}{{\left( {{u^h}{v^b}d} \right)}^r}} \right) = e\left( {g, B \cdot F \cdot G} \right) 2)e\left( {B', T} \right) = \left( {Y_j^r, {{\left( {g_2^wh} \right)}^{\frac{1}{{{X_j}}}}}} \right) =\\ e\left( {{g^{{X_i}r}}, {{\left( {g_2^wh} \right)}^{\frac{1}{{{X_j}}}}}} \right){\rm{ = }} e\left( {{g^r}, g_2^wh} \right) = e{\left( {g, g_2^wh} \right)^r} = {D_1} 3)e{\left( {B', g} \right)^{\frac{1}{{{X_j}}}}} = e{\left( {{g^{{X_i}r}}, g} \right)^{\frac{1}{{{X_j}}}}} = \\e\left( {g, A} \right) 4)K' = E \oplus {H_2}\left( {e{{\left( {B', g} \right)}^{\frac{1}{{{X_j}}}}}} \right) = {H_2}\left( {e{{\left( {g, g} \right)}^r}} \right) \oplus K \oplus {H_2}\left( {e{{\left( {{g^{r{X_j}}}, g} \right)}^{\frac{1}{{{X_j}}}}}} \right) = K \end{array} $

因此本文方案是正确的。

4 安全性证明 4.1 关键字密文隐私安全

定理1    假设解决QDBDH和DBDH问题困难, 本文方案在标准模型下可证明IND-CCA和IND-CKA是安全的。

引理1    假设解决QDBDH问题困难, 本文方案在标准模型下可证明IND-CCA是安全的。

证明   假设存在恶意的邮箱服务器A₁能以优势ε攻破本文方案(q_RK, q_RE, q_T, q_Dec, ε), 则挑战者B便能以不可忽略的优势解决QDBDH问题。设H₁、H₂、H₃是免碰撞的哈希函数, 且K是对称加密密码。则有$\varepsilon \ge \frac{\varepsilon }{{e\left( {1 + {q_{RK}}} \right)}} - \frac{{{q_{RE}} + {q_{{\rm{Dec}}}}}}{p} - {\rm{Adv}}_{H.{A_1}}^{{\rm{TCR}}} - {\rm{Adv}}_K^{{\rm{PRF}}}$。

假设给挑战者B一个QDBDH实例(g, M=g^a, N=g^b, Q)∈(G₁)³×G₂, 其中a, b∈Z_p^*, 挑战者B的目的是确定$Q = e{\left( {g, g} \right)^{\frac{b}{a}}}$是否成立。游戏过程如下:

系统建立   挑战者B选取随机数a₀, a₁, a₂, a₃, b₁, b₂, b₃, 计算系统参数g₂=M^a₀, h=M^b, u=g^a₁N^b₁, v=g^a₂N^b₂, d=g^a₃N^b₃。

询问阶段1    敌手A₁进行如下询问:

1) 公钥预言询问O_Yi(i):挑战者B随机选取X_i∈Z_p^*, 并抛掷一个硬币, 若正面朝上, 则c_i=1, 公钥Y_i=g^X_i; 否则c_i=0, 公钥Y_i=g^aX_i=M^X_i。挑战者B将三元组(Y_i, X_i, c_i)加入至列表L^list中并将公钥Y_i公开。敌手A₁产生它的公私钥对(Y_j, X_j)并将公钥Y_j公开。

2) 重加密密钥询问阶段O_RK(X_i, X_j):从列表L^list中调用三元组(Y_i, X_i, c_i), 并查询X_i和X_j是否存在三元组中, 若不存在, 则调用公钥预言询问O_Yi(i), 否则进行如下操作:

(1) 若c_i=c_j=1, 则用户i的私钥为X_i, 用户j的私钥为X_j, 挑战者B模拟算法ReKeyGen(X_i, X_j)产生代理重加密密钥$R{K_{i \to j}} = \frac{{{X_j}}}{{{X_i}}}$。

(2) 若c_i=c_j=0, 则用户i的私钥为aX_i, 用户j的私钥为aX_j, 挑战者B模拟算法ReKeyGen(X_i, X_j)产生PRE密钥$R{K_{i \to j}} = \frac{{a{X_j}}}{{a{X_i}}} = \frac{{{X_j}}}{{{X_i}}}$。

(3) 否则, 挑战者B输出⊥。

3) 陷门预言阶段O_T(w, X_j):挑战者B从列表L^list中调用三元组(Y_i, X_i, c_i)并查询X_j是否存在三元组中, 若不存在, 则调用公钥预言询问O_Yi(i), 否则进行如下操作:

(1) 若c_j=1, 则用户j的私钥为X_j, 挑战者B设陷门为$T = {g^{\frac{{a{a_0}w}}{{{X_j}}}}}{g^{\frac{b}{{{X_j}}}}} = {\left( {g_2^wh} \right)^{\frac{1}{{{X_j}}}}}$。

(2) 若c_j=0, 则用户j的私钥为aX_j, 挑战者B设陷门为$T = {g^{\frac{{{a_0}w}}{{{X_j}}}}}{g^{\frac{b}{{{X_j}}}}} = {\left( {g_2^wh} \right)^{\frac{1}{{a{X_j}}}}}$。

4) 重加密预言阶段O_RE(Y_i, Y_j, CT_i):若式(1)验证失败, 则挑战者B输出⊥; 否则挑战者B从列表L^list中恢复三元组(Y_i, X_i, c_i)并执行如下操作:

(1) 若c_i和c_j均为1或均为0, 则挑战者B调用重加密密钥询问O_RK(X_i, X_j), 生成重加密密钥RK_i→j, 然后将ReEnc(CT_i, RK_i→j)返回给敌手A₁。

(2) 若c_i=0∧c_j=1, 则意味着用户i的私钥为X_i和用户j的私钥为aX_j, 挑战者B通过$A = {g^r} = {M^{\frac{r}{a}}}$和F=(u^hv^td)^r=(g^{a₁h+a₂t+a₃}M^{b₁h+b₃t+b₃})计算:

$ {g^r} = {\left[ {\frac{F}{{{M^{a\left( {{b_1}h + {b_3}t + {b_3}} \right)}}}}} \right]^{\frac{1}{{{a_1}h + {a_2}t + {a_3}}}}} $

(5)

则通过式(5)得到B′=(g^r)^X_j=Y_j^r, 并将CT_j=(t, A, B′, C, D, D₁, E, F, G)发送给敌手A₁, 等式a₁h+a₂t+a₃=omod p 至少以$\frac{1}{p}$的概率成立。

(3) 若c_i=1∧c_j=0, 则意味着用户i的私钥为aX_i和用户j的私钥为X_j, 挑战者B计算B′=g^aX_jr=(M^r)^X_j=A^aX_j。

5) 解密预言阶段O_Dec(Y_i, CT_j):挑战者B从列表L^list中恢复三元组(Y_i, X_i, c_i)并执行如下操作:

(1) 若c_j=0, 则用户j的私钥为aX_j, 挑战者B验证式(3), 若式(3)验证失败, 则挑战者B输出⊥; 否则挑战者B计算对称密码$\begin{array}{l} K = E \oplus {H_2}\left( {e{{\left( {B', g} \right)}^{\frac{1}{{a{X_j}}}}}} \right) = E \oplus {H_2}\left( {e{{\left( {g, g} \right)}^r}} \right) \end{array}$, 然后计算得到m=Dec_K′(C)。

(2) 若c_j=1, 则用户j的私钥为X_j, 挑战者B将输出Dec(CT_j)给敌手。

挑战阶段  当询问阶段1完毕, 敌手A₁选择2个明文(m₀, m₁)、公钥Y^*一起发送给挑战者B。挑战者B从列表L^list中恢复三元组(Y_i, X_i, c_i), 若c^*=1, 挑战者B输出⊥, 否则挑战者B随机选取δ∈{0, 1}, 并设置$\begin{array}{l} {A^ * } = {N^{\frac{1}{a}}}, {B^*} = {N^{\frac{{{X_j}*}}{a}}}, {C^*} = \\ {\rm{En}}{{\rm{c}}_{K*}}\left( {{m_\delta }} \right), {D^*} = e\left( {{Y_s}, {N^{{a_0}w}}} \right), {h^*} = {H_1}\left( {{A^ * }, {C^*}, {E^*}} \right), \\ {t^*} = - \frac{{{a_1}{h^*} + {a_3}}}{{{a_2}}}, {F^*} = {N^{{b_1}h^* + {b_2}t^* + {b_3}}}, {G^*} = {N^{{a_0}w}} \end{array}$。挑战者B输出挑战密文CT_i^*=(t, A^*, B^*, C^*, D^*, D₁^*, E^*, F^*, G^*)给敌手A₁。

如果$Q = e{\left( {g, g} \right)^{\frac{b}{a}}}$, CT_i^*是基于公钥Y^*下的挑战密文, 设${r^*} = \frac{b}{a}$, 则有$\begin{array}{l} {A^*} = {N^{\frac{1}{a}}} = {\left( g \right)^{\frac{b}{a}}} = {g^{{r^*}}}, {B^*} = {N^{\frac{{{X_j}*}}{a}}} = {g^{\frac{{b{X_j}*}}{a}}} = {\left( {{g^{{X_j}*}}} \right)^{r*}}, {C^*} = {\rm{En}}{{\rm{c}}_{K^*}}\left( {{m_\delta }} \right), {D^*} = e\left( {{Y_s}, {N^{{a_0}w}}} \right) =\\ e{\left( {{Y_s}, {g^{a{a_0}w}}} \right)^{\frac{b}{a}}} = e{\left( {{Y_s}, g_2^w} \right)^{r^*}}, {D_1}^* = e\left( {g, {N^{{a_0}w}}{N^b}} \right) = e{\left( {g, {M^{{a_0}w}}{M^b}} \right)^{r*}} = e{\left( {g, g_2^wh} \right)^{r^*}}, {E^*} =\\ {H_2}\left( {e\left( {g, {N^{\frac{1}{a}}}} \right)} \right) \oplus {K^*} = {H_2}e{\left( {g, g} \right)^{r^*}} \oplus {K^*}, {F^*} = {N^{{b_1}h^* + {b_2}t^* + {b_3}}} = \left( {{g^{{a_1}h^* + {a_3} + {a_2}t^*}}} \right. {\left. {{M^{{b_1}h^* + {b_2}t^* + {b_3}}}} \right)^{r^*}}, {G^*}\\ = {N^{{a_0}w}} = {\left( {{A^{{a_0}w}}} \right)^{r^*}} = {\left( {g_2^w} \right)^{r*}} 。\end{array}$

询问阶段2   敌手A₁进行询问, 除了挑战密文及其衍生不能询问外, 其他与询问阶段1一致。

猜测  最后敌手返回猜测δ′, 如果δ′=δ, 则挑战成功, 输出1;否则输出0。

引理2   假设解决DBDH问题困难。本文方案在标准模型下可证明IND-CKA是安全的。

证明   假设敌手A₂是外部攻击者, 其以优势ξ攻破本文方案(q_RK, q_RE, q_T, q_Dec, ξ), 则本文方案能够构造挑战者B以一个不可忽略的优势解决DBDH问题。若H₁, H₂, H₃是免碰撞的哈希函数, 且K是对称加密密码, 则有$\begin{array}{l} \xi \ge \frac{\varepsilon }{{e\left( {1 + {q_{RK}}} \right)}} - \frac{{{q_{RK}} + {q_{{\rm{Dec}}}}}}{p} - {\rm{Adv}}_{H.{A_1}}^{{\rm{TCR}}} - {\rm{Adv}}_K^{{\rm{PRE}}} \end{array}$。

假设给挑战者B一个DBDH实例(g, M=g^a, N=g^b, O=g^c, γ)∈(G₁)³×G₂, 其中a, b, c∈Z_p^*, 挑战者B的目的是确定γ=e(g, g)^abc是否成立。游戏过程如下:

系统建立  挑战者B随机选取数a₀, a₁, a₂, a₃, b₁, b₂, b₃, 计算系统参数g₂=M^a₀, h=M^b, u=g^a₁N^b₁, v=g^a₂N^b₂, d=g^a₃N^b₃。

询问阶段1  敌手A₂进行如下询问:

1) 公钥预言询问O_Yi(i):挑战者B随机选取X_i∈Z_p^*, 并计算公钥Y_i=g^X_i。

2) 重加密密钥询问阶段O_RK(X_i, X_j):挑战者B生成代理重加密密钥$R{K_{i \to j}} = \frac{{{X_j}}}{{{X_i}}}$。

3) 陷门预言阶段O_T(w, X_j):挑战者B生成陷门$T = {\left( {g_2^wh} \right)^{\frac{1}{{{X_j}}}}}$。

4) 重加密预言阶段O_RE(Y_i, Y_j, CT_i):若式(1)验证失败, 则挑战者B输出⊥; 否则挑战者B调用重加密密钥询问O_RK(X_i, X_j), 生成重加密密钥$R{K_{i \to j}} = \frac{{{X_j}}}{{{X_i}}}$, 并将ReEnc(CT_i, RK_i→j)返回给敌手A₂。

5) 解密预言阶段O_Dec(Y_i, CT_j):挑战者B输出Dec(CT_j)给敌手A₂。

挑战阶段  当询问阶段1完毕, 敌手A₂选择2个关键字(w₀, w₁)、明文m和公钥Y^*一起发送给挑战者B。挑战者B随机选取δ∈{0, 1}, 并设置r^*=c为DBDH困难问题里的成分, 计算A^*=O, B^*= O^X_j*, C^*=Enc_K^*(m), D^*=e(Y_s, O^a₀aw), E^*=H₂(e(g, O))⊕K^*h^*=H₁(A^*, C^*, E^*), F^*=O^{a₁h*+a₂t*+a₃}, G^*=O^a₀aw, D₁^*= ${\gamma ^{\left( {\frac{{{a_0}w}}{b} + 1} \right)}}$。挑战者B将挑战密文CT_i^*=(t, A^*, B^*, C^*, D^*, D₁^*, E^*, F^*, G^*)返回给敌手A₂。若γ=e(g, g)^abc, CT_i^*是基于公钥Y^*下的挑战密文, 则有A^*=O=g^c=g^r*, B^*=O^X_j*=g^cX_j*=Y^r_j*, $\begin{array}{l} {D_1}^* = {\gamma ^{\left( {\frac{{{a_0}w}}{b} + 1} \right)}} = e{\left( {g, {g^{{a_0}aw}}{g^{ab}}} \right)^{r*}} = e{\left( {g, g_2^wh} \right)^{r*}} \end{array}$。

询问阶段2  敌手A₂进行询问, 除了挑战密文及其衍生不能询问外, 其他同询问阶段1一致。

猜测  敌手返回猜测δ′, 若δ′=δ, 则挑战成功, 输出1;否则输出0。

4.2 陷门隐私安全

定理2  假设解决DDH问题困难。本文方案可证明在陷门上是安全的。

证明  假设存在外部攻击者A₃能以优势ζ攻破本文方案(q_RK, q_RE, q_Dec, ζ), 则存在挑战者B能以优势ζ解决HDH问题。假设H₁、H₂、H₃是免碰撞的哈希函数, 且K是对称加密密码, 敌手询问陷门的次数为q_T次, 其中$\xi \ge \frac{{\varepsilon '}}{{e\left( {1 + {q_{RK}}} \right)}} - \frac{{{q_{RE}} + {q_{{\rm{Dec}}}}}}{p} - {\rm{Adv}}_{H.{A_1}}^{{\rm{TCR}}} - {\rm{Adv}}_K^{{\rm{PRF}}}$成立。

假设给挑战者B一个HDH实例(g, M=g^a, N=g^b, λ)∈G₁, 其中a, b∈Z_p^*, 挑战者B的目的是确定λ=g^ab是否成立。游戏过程如下:

系统建立  挑战者B选取随机数a₀、a₁、a₂、a₃、b₁、b₂、b₃、并计算系统参数g₂=M^a₀, h=M^b。

询问阶段1   敌手A₃进行如下询问:

1) 公钥预言询问O_Yi(i):挑战者B随机选择X_i∈Z_p^*。并抛掷一个硬币, 若正面朝上, 则c_i=1, 公钥Y_i=g^X_i; 否则c_i=0, 公钥Y_i=g^aX_i=N^X_i。挑战者B将三元组(Y_i, X_i, c_i)加入到列表L^list中, 将私钥X_i返回给敌手A₁, 公开公钥Y_i。

2) 陷门预言阶段O_T(w, X_j):挑战者B从列表L^list中调用三元组(Y_i, X_i, c_i)并查询X_j是否存在三元组中, 若不存在, 则调用公钥预言询问O_Yi(i), 否则进行如下操作:

1) 若c_j=1, 则用户j的私钥为X_j, 挑战者B设陷门为$T = {g^{\frac{{{a_0}abw}}{{{X_j}}}}}{g^{\frac{b}{{{X_j}}}}} = {\left( {g_2^wh} \right)^{\frac{1}{{{X_j}}}}}$。

2) 若c_j=0, 则用户j的私钥为aX_j, 挑战者B设陷门为$T = {g^{\frac{{{a_0}bw}}{{{X_j}}}}}{g^{\frac{b}{{{X_j}}}}} = {\left( {g_2^wh} \right)^{\frac{1}{{a{X_j}}}}}$。

挑战阶段  敌手A₃选择2个关键字(w₀, w₁), 并发送给挑战者B。挑战者B从列表L^list中恢复三元组(Y_i, X_i, c_i), 若c^*=1, 则挑战者B输出⊥; 若c^*=0, 则挑战者B随机选择δ∈{0, 1}, 并生成挑战陷门${T^*} = {\lambda ^{\frac{{{a_0}w\delta }}{{{X_j}*}}}}$, 其中λ是DDH困难问题中的成分。若$\lambda = {g^{ab}}, {T^*} = {\lambda ^{\frac{{{a_0}w\delta + 1}}{{{X_j}*}}}} = {g^{\frac{{{a_0}abw\delta + ab}}{{{X_j}*}}}} = {M^{\frac{{{a_0}bw\delta + b}}{{{X_j}*}}}} = {\left( {g_2^{{w_\delta }}h} \right)^{\frac{1}{{{X_j}*}}}}$均成立, 则T^*是公钥Y_j下的一个有效陷门。

询问阶段2  敌手A₃进行询问, 除了不能询问挑战关键字及其衍生外, 其他同询问阶段1一致。

猜测   敌手A₃返回猜测δ′, 若δ′=δ, 则挑战成功, 输出1;否则输出0。

5 效率分析

通过理论和数值实验对dPRES^[18]方案和本文方案进行分析。首先从理论上对计算开销进行分析, dPRES方案和本文方案效率比较结果见表 1, 其中T_p、T_F、T_h、T_e、T_eo分别为双线性运算、伪随机函数族运算、哈希运算、指数运算和异或运算的计算代价。

由表 1可知, 在搜索阶段, 本文方案比dPRES方案少一个指数运算和两个哈希运算。此外, 在解密阶段, 本文方案比dPRES方案少一个双线性对运算。因此, 与dPRES方案相比, 本文方案在计算效率上有较大的提高。

为了更直观地显示结果, 本节从数值分析上对方案的计算成本进行了模拟。在Linux系统上使用PBC库, 基于C语言编程实现dPRES方案和本方案。数值环境配置参数如表 2所示。

本文方案和dPRES方案均能实现密文授权和搜索功能。在数值实验中, 加密和解密阶段两方案均加密相同数量的关键字, 随着关键字数量的变化, 统计在不同数量关键字下的加密时间, 结果如图 1所示。

由图 1可知, 在加密阶段, 本文方案的时间开销较dPRES方案高。搜索阶段是统计搜索不同数量关键字的时间开销, 如图 2所示。

由图 2可知, 在搜索阶段, 当关键字数量为10个时, 本文方案的时间开销为42 ms, 而dPRES方案的时间开销为164.4 ms; 当关键字数量为30个时, 本文方案的时间开销为122.4 ms, 而dPRES方案的时间开销为456.2 ms; 当关键字数量为50个时, 本文方案的时间开销为198.9 ms, 而dPRES方案的时间开销为762.2 ms。随着关键字数量的增加, dPRES方案的时间开销增长速率比本文方案大, 说明本文方案的搜索效率优于dPRES方案。

统计在不同数量关键字下的解密开销时间, 如图 3所示。

由图 3可以看出, 在解密阶段, 随着关键字数量的增大, 本文方案的时间开销几乎保持不变; 当关键字数量为10个时, dPRES方案的时间开销为85.7 ms; 当关键字数量为30个时, dPRES方案的时间开销为236.5 ms; 当关键字数量为50个时, dPRES方案的时间开销为390.8 ms, 说明dPRES方案的时间开销与关键字数量之间呈线性增长。因此, 本文方案的解密效率优于dPRES方案。

由图 1~图 3可知, 虽然在加密阶段, 本文方案的时间开销较dPRES方案高, 但是在搜索阶段, 本文方案时间开销远远小于dPRES方案, 且在解密阶段, 本文方案时间开销也低于dPRES方案。因此, 本文方案在解密算法和搜索算法的计算代价上有明显优势, 减少了电子邮箱服务器和用户之间的通信代价, 提高了系统的性能。

6 结束语

为解决密文授权和密文搜索问题, 本文提出一种面向电子邮件支持高效关键字搜索的PRE方案。该方案在搜索过程中只用了一个双线性对, 因此搜索效率较高。同时, 本文方案在标准模型下关键字隐私、密文隐私和陷门隐私是安全的, 还可以抵抗篡改攻击和关键字猜测攻击。分析结果表明, 相对dPRES方案, 本文方案在搜索效率上有较大的提升。目前, 支持关键字搜索的PRE方案还有一些问题需要解决, 如进一步减少时间开销, 提高方案的计算效率和通信效率等, 这将是下一步的研究方向。