1.   引言

云计算^[1]能够提供广泛的计算、分析、存储、部署和支持应用程序等服务，帮助用户降低成本。考虑到云数据的敏感性^[2]，引入密码系统来加密私有数据。可搜索加密^[3]既可以保护用户的隐私，又支持搜索加密数据，在云数据存储中有广泛应用。

2004年，Boneh等人^[4]提出了第1个公钥可搜索加密方案。该方案既支持密文检索，又能实现用户数据共享。传统公钥可搜索加密中，证书颁发机构是公钥基础设施系统的核心部分，负责发布和管理用户的证书，这样带来了证书管理问题。基于身份的公钥可搜索加密方案^[5]可以解决传统公钥可搜索加密的证书管理问题，但是又引入了密钥托管问题。2014年，Peng等人^[6]提出了无证书可搜索加密方案。该方案既解决了证书管理问题，又解决了密钥托管问题。2017年，Ma等人^[7,8]提出了分别应用于工业互联网和医疗健康网络的无证书可搜索加密方案。但是，以上方案^[6-8]只能对使用了相同公钥加密的数据进行操作。云环境中用户可能会使用不同的公钥对数据进行加密，但是，服务器不能直接对不同公钥加密的数据进行比较，因此公钥可搜索加密技术^[9,10]存在一定的局限性。

2010年，Yang等人^[11]提出了公钥加密等值测试(Public Key Encryption with Equality Test, PKEET)，该技术可以判断不同公钥加密的密文是否是同一明文所产生。也就是说，若${{C}}$和${{C'}}$是用两个不同公钥加密的密文，其中${{C}} = {\rm{Encrypt}}\left( {{{M}},{\rm{PK}}} \right)$和${{C'}} = {\rm{Encrypt}}\left( {{{M'}},{\rm{PK'}}} \right)$，该算法通过比较${{C = C'}}$是否成立来判断${{M = M'}}$是否成立。但是，Yang方案不提供授权机制，任何用户都可以进行等值测试，暴露了数据所有者的隐私。2011年，Tang^[12]在PKEET中引入授权机制，提出了一个支持细粒度授权的公钥加密等值测试方案。随后，Tang^[13,14]又提出了仅指定用户可以进行密文等值测试和抵抗离线消息恢复攻击的密文等值测试方案。2015年，Ma等人^[15]提出了支持灵活授权的公钥加密等值测试方案。2016年，Ma^[16]提出了身份等值测试方案，该方案简化了证书管理问题并支持用户级授权。2018年，Qu等人^[17]提出了无证书密文等值测试加密方案，该方案可以解决传统PKEET方案^[18]和身份PKEET方案^[19]中的证书管理和密钥托管问题。但是，当前已有的PKEET方案不提供关键字检索功能。如果云服务器存储的密文中根本没有用户需要的信息，而用户只有执行密文等值测试后才能得知，这无形中消耗了大量的网络带宽。

针对上述问题，本文提出了支持关键字搜索的无证书密文等值测试加密(CertificateLess Equality test EncrypTion with keyword Search, CLEETS)方案。方案中用户首先根据关键字生成一个陷门，利用该陷门判断云服务器的密文中是否包含关键字对应的密文信息。如果包含则进行等值测试；否则不进行等值测试，这样，将提高用户的检索效率。在随机预言模型下证明方案满足适应性选择关键词不可区分性。同时将方案与已有的PKEET方案进行功能和效率对比。对比结果表明，虽然本文方案的计算代价略高，但是它在密文等值测试中增加了关键字检索功能，使得方案的适用性更强。

2.   CLEETS方案安全模型

2.1   CLEETS方案系统模型

支持关键字搜索的无证书密文等值测试加密(CLEETS)方案包括云服务器、公钥服务器、密钥生成中心(KGC)、数据拥有者和用户5类实体。系统模型如图1所示。

图 1  系统模型图

下载: 全尺寸图片 幻灯片

(1) 云服务器：存储密文，并且通过接收者的陷门和授权执行密文搜索与等值测试。

(2) 公钥服务器：存储所有用户的公钥。

(3) 密钥生成中心(KGC)：生成部分私钥。

(4) 数据拥有者：生成、上传密文到云服务器。

(5) 用户：提出搜索和等值测试请求，生成搜索陷门和等值测试陷门。

2.2   CLEETS方案形式化定义

CLEETS方案包括以下算法：

(1) 系统设置：KGC安全参数K，生成系统公共参数PP和主密钥$\hat {{g}}$。

(2) 生成部分私钥：KGC输入参数PP、主密钥$\hat {{g}}$和用户的身份，生成用户的部分私钥${D_i}$。

(3) 生成秘密值法：用户输入参数PP，生成用户的秘密值${{{X}}_{{i}}}$。

(4) 生成私钥：用户输入参数PP、部分私密钥${D_i}$和秘密值${{{X}}_{{i}}}$，生成用户的(完整)私钥${\rm{S}}{{\rm{K}}_i}$。

(5) 生成公钥：用户运行，输入参数PP和秘密值${{{X}}_{{i}}}$，生成用户的公钥${\rm{P}}{{\rm{K}}_{{i}}}$。

(6) 加密：数据拥有者输入参数PP、关键字${w_i}$、接收者的公钥${\rm{P}}{{\rm{K}}_{{i}}}$和身份${\rm{I}}{{\rm{D}}_{{i}}}$，输出密文$C$。

(7) 生成搜索陷门：接收者输入参数PP、关键字${w_i}^\prime$和接收者的私钥${\rm{S}}{{\rm{K}}_{\rm{R}}}$，输出搜索陷门${{{T_{\rm{W}}}}}$。

(8) 生成测试陷门：接收者运行，输入参数PP和接收者的私钥${\rm{S}}{{\rm{K}}_{\rm{R}}}$，输出测试陷门${\rm{t}}{{\rm{d}}_{{i}}}$。

(9) Test₁搜索测试算法：服务器输入参数PP、服务器私钥${\rm{S}}{{\rm{K}}_{\rm{R}}}$和搜索陷门${T_{\rm{W}}}$。如果${w_i} = {w_i}^\prime$，输出“1”并执行Test₂算法；否则输出“0”，终止操作。

(10) Test₂等价测试算法：服务器运行，设${C_{\rm{A}}}$和${\rm{t}}{{\rm{d}}_{\rm{A}}}$为接收者${\rm{A}}$的密文和测试陷门，${C_{\rm{B}}}$和${\rm{t}}{{\rm{d}}_{\rm{B}}}$为接收者${\rm{B}}$的密文和测试陷门。输入参数PP和两个密文/测试陷门对$\left( {{C_{\rm{A}}},{{\rm{td}}_{\rm{A}}}} \right)$和$\left( {{C_{\rm{B}}},{{\rm{td}}_{\rm{B}}}} \right)$。如果二者为同一消息的密文，则输出“1”；否则输出“0”。

2.3   CLEETS方案安全模型

与文献[8,17]一样，本文定义敌手${{\rm{A}}_{\rm{I}}}$和${{\rm{A}}_{{\rm{II}}}}$。其中，敌手${{\rm{A}}_{\rm{I}}}$模仿恶意用户，用户的公钥可以被任意替换，但是无法获得用户的部分私钥。敌手${{\rm{A}}_{{\rm{II}}}}$模仿恶意${\rm{KGC}}$，它不能得到用户的公钥，但是知道主密钥及部分私钥。CLEETS方案的安全性由挑战者${\rm{C}}$与敌手${{\rm{A}}_{\rm{I}}}$及${{\rm{A}}_{{\rm{II}}}}$之间的游戏来完成。

游戏1：挑战者${\rm{C}}$和${{\rm{A}}_{\rm{I}}}$之间的游戏过程如下：

(1) 系统建立阶段：${\rm{C}}$输入安全参数${{K}}$，输出主密钥$s$和参数${\rm{PP}}$。${\rm{C}}$返回${\rm{PP}}$给${{\rm{A}}_{\rm{I}}}$，保存$s$；

(2) 询问阶段：${{\rm{A}}_{\rm{I}}}$进行${\rm{Hash}}$、生成部分私钥、生成私钥、生成公钥、公钥替换、生成搜索陷门、生成测试陷门等询问，${\rm{C}}$将返回相应值给${{\rm{A}}_{\rm{I}}}$；

(3) 挑战阶段：${{\rm{A}}_{\rm{I}}}$输出两个挑战关键字${w_0}$和${w_1}$, ${w_0} \ne {w_1}$且未被${{\rm{A}}_{\rm{I}}}$询问过。${\rm{C}}$任意选择$b \in \left\{ {0,1} \right\}$，运行加密算法生成密文，发送给${{\rm{A}}_{\rm{I}}}$；

(4) 猜测阶段：${{\rm{A}}_{\rm{I}}}$以$b \in \left\{ {0,1} \right\}$作为猜测值输出。如果$b' = b$，则${{\rm{A}}_{\rm{I}}}$获胜。

${{\rm{A}}_{\rm{I}}}$获胜的优势为${\rm{Ad}}{{\rm{v}}_{{{\rm{A}}_{\rm{I}}}}}\left( {{k}} \right) = \left| {{\rm{Pr}}\left[ {{{b' = b}}} \right]{\rm{ - }}\dfrac{{\rm{1}}}{{\rm{2}}}} \right|$。

游戏2：挑战者${\rm{C}}$和${{\rm{A}}_{{\rm{II}}}}$的游戏过程如下：

(1) 系统建立阶段：${\rm{C}}$输入安全参数${{K}}$，输出主密钥$s$和参数${\rm{PP}}$并返回给${{\rm{A}}_{{\rm{II}}}}$；

(2) 询问阶段：与游戏1中过程相同，除了不进行部分私钥询问和公钥替换询问；

(3) 挑战阶段：与游戏1中过程相同；

(4) 猜测阶段：${{\rm{A}}_{{\rm{II}}}}$输出$b' \in \left\{ {0,1} \right\}$作为猜测值，如果$b' = b$，则${{\rm{A}}_{{\rm{II}}}}$获胜。

${{\rm{A}}_{{\rm{II}}}}$获胜的优势为：${\rm{Ad}}{{\rm{v}}_{{{\rm{A}}_{{\rm{II}}}}}}\left( {{k}} \right) = \left| {{\rm{Pr}}\left[ {{b' = b}} \right]{\rm{ - }}\dfrac{{\rm{1}}}{{\rm{2}}}} \right|$。

3.   CLEETS方案

3.1   具体方案

(1) 系统设置。输入安全参数${{K}}$，生成系统参数${\rm{PP}}$。${\rm{KGC}}$执行以下过程：

(a)选取两个循环群${G_1}{\text{和}}{G_2}$，其阶为$q$, $g$为${G_1}$的生成元，再选择双线性映射$e:{G_1} \times {G_1} \to {G_2}$; (b)随机选择$s \in Z_q^ *$作为主密钥并秘密保存，并计算$\hat g = {g^s}$; (c)选择4个抗碰撞的哈希函数${H_1},{H_2}: {\left\{ {0,1} \right\}^ * } \to {G_1}$, ${H_3}:{\left\{ {0,1} \right\}^ * } \to Z_q^ *$, ${H_4}:{G_2} \to Z_q^ *$; (d)公开系统参数${\rm{PP = }}\left\{ {G_1},{G_2},e,q,g,\hat g,{H_1}, {H_2}, {H_3},{H_4} \right\}$。

(2) 生成部分私钥。${\rm{KGC}}$执行以下步骤生成接收者和云服务器的部分私钥：

(a)输入接收者的身份信息${{\rm{ID}}_{\rm{R}}} \in {\left\{ {0,1} \right\}^ * }$，计算${Q_{\rm{R}}} = {H_1}\left( {{{\rm{ID}}_{\rm{R}}}} \right)$，计算接收者的部分私钥${D_{\rm{S}}} = {Q^s_{\rm{R}}}$; (b)输入云服务器的身份信息${{\rm{ID}}_{\rm{S}}} \in {\left\{ {0,1} \right\}^ * }$，计算${Q_{\rm{S}}} = {H_1}\left( {{{\rm{ID}}_{\rm{S}}}} \right)$，计算云服务器的部分私钥${D_{\rm{S}}} = {Q^s_{\rm{S}}}$。

(3) 生成秘密值。选择一个随机数作为秘密值。

(a)接收者任意选取${{{X}}_{\rm{R}}} \in Z_q^*$作为其秘密值；(b)云服务器任意选取${{{X}}_{{S}}} \in Z_q^ *$作为其秘密值。

(4) 生成私钥。用户输入秘密值和部分私钥，产生自己的完整私钥。

(a)接收者输入${{{X}}_{\rm{R}}} \in Z_q^ *$和${D_{\rm{R}}}$，生成私钥${\rm{S}}{{\rm{K}}_{\rm{R}}} = {{{D}}^{{{{X}}_{\rm{R}}}}_{\rm{R}}}$；(b)云服务器输入${{{X}}_{{\rm{S}}}} \in Z_q^ *$和${D_{\rm{S}}}$，生成私钥${\rm{S}}{{\rm{K}}_{{{\rm{S}}}}} = {{{D}}_{{{\rm{S}}}}}^{{{{X}}_{{{\rm{S}}}}}}$。

(5) 生成公钥。输入秘密值生成用户的公钥。

(a)接收者输入秘密值${{\rm{X}}_{\rm{R}}}$和系统公钥$\hat g$，生成接收者的公钥${\rm{P}}{{\rm{K}}_{\rm{R}}} = {{{\hat g}}^{{{\rm{X}}_{\rm{R}}}}}$; (b)云服务器输入${{{X}}_{\rm{S}}}$和系统公钥$\hat g$，生成接收者的公钥${\rm{P}}{{\rm{K}}_{\rm{S}}} = {{{\hat g}}^{{{\rm{X}}_{\rm{S}}}}}$。

(6) 加密。设一组关键字集$W = \left\{ {{w_i}\left| {1 \le i \le n} \right.} \right\}$。输入${\rm{PP}}$, ${\rm{I}}{{\rm{D}}_{\rm{S}}}$, ${\rm{I}}{{\rm{D}}_{\rm{R}}}$, ${\rm{P}}{{\rm{K}}_{\rm{R}}}$, ${\rm{P}}{{\rm{K}}_{\rm{S}}}$, ${w_i}$和消息$M$，数据拥有者执行以下计算过程：

(a)随机选择$\alpha ,\beta \in Z_q^ *$，计算${C_{1i}} = {g^\alpha }$和${C_{2i}} = {g^\beta }$；(b)计算${C_{3i}} = e\left( {{H_2}{{\left( {{w_i}} \right)}^\alpha },{\rm{P}}{{\rm{K}}_{\rm{R}}}{\rm{P}}{{\rm{K}}_{{{\rm{S}}}}}} \right)e\left( {{Q_R}^\alpha ,\hat {{g}}} \right)$；(c)计算${C_{4i}} = {H_3}{\left( M \right)^\alpha } \cdot {H_4}\left( {e\left( {{\rm{P}}{{\rm{K}}_{\rm{R}}},} \right.} \right.\left. {{Q_{\rm{R}}}} \right)\left. {^{\alpha }} \right)$。则目标密文$C = \left\{ {{C_1},{C_2},···,{C_n}} \right\}$，其中${C_i} = \left( {C_{1i}},{C_{2i}}, {C_{3i}},{C_{4i}} \right)$。

(7) 生成搜索陷门。接收者输入${\rm{PP}}$, ${w_i}^\prime$和${\rm{S}}{{\rm{K}}_{\rm{R}}}$，计算出搜索陷门${T_{\rm{W}}} = {H_2}{\left( {{w_i}^\prime } \right)^{{{{X}}_{\rm{R}}}}}{D_{\rm{R}}}$。

(8) 生成测试陷门。接收者输入${\rm{PP}}$和${\rm{S}}{{\rm{K}}_{\rm{R}}}$，接收者计算出测试陷门${T_{\rm{d}}} = {D_{\rm{R}}}^{{{{X}}_{\rm{R}}}}$。

(9) ${\rm{Tes}}{{\rm{t}}_{\rm{1}}}$算法。云服务器输入${\rm{PP}}$, ${\rm{S}}{{\rm{K}}_{\rm{S}}}$和${T_{{{\rm{W}}_i}}}$，验证$e\left( {{T_{\rm{W}}},{C_1}} \right)e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{S}}}}},{C_1}} \right) = {C_3}$是否成立。若等式成立则继续执行以下算法，否则返回“0”。

(10) ${\rm{Tes}}{{\rm{t}}_{\rm{2}}}$算法。云服务器输入${\rm{PP}}$, ${T_{{d_{\rm{A}}}}}$, ${T_{{d_{\rm{B}}}}}$, ${C_{\rm{A}}} = \left( {{C_{\rm{A}}}_1,{C_{\rm{A}}}_2,{C_{\rm{A}}}_3,{C_{\rm{A}}}_4} \right)$, ${C_{\rm{B}}} = \left( {{C_{\rm{B}}}_1,{C_{\rm{B}}}_2,} \right.{C_{\rm{B}}}_3 \left. {{C_{\rm{B}}}_4} \right)$，计算${K_{\rm{A}}} = \dfrac{{{C_{{\rm{A}}4}}}}{{{H_4}\left( {e\left( {{C_{{\rm{A}}2}},{T_{d{\rm{A}}}}} \right)} \right)}}$, ${K_{\rm{B}}} = \dfrac{{{C_{{\rm{B}}4}}}}{{{H_4}\left( {e\left( {{C_{{\rm{B}}2}},{T_{d{\rm{B}}}}} \right)} \right)}}$，验证等式$e\left( {{C_{{\rm{A}}1}},{K_{\rm{B}}}} \right) = e\left( {{C_{{\rm{B}}1}},{K_{\rm{A}}}} \right.)$。若等式成立则给用户返回“1”，否则返回“0”。

3.2   正确性

CLEETS方案正确当且仅当Test₁算法和Test₂算法中的验证等式成立。

(1) Test₁中的验证等式成立，如果$w = {w_i}$：

即等式$e\left( {{T_{\rm{W}}},{C_1}} \right)e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{S}}}}},{C_1}} \right) = {C_3}$成立。

(2) Test₂中的验证等式成立：

如果${M_{\rm{A}}} = {M_{\rm{B}}}$，则$e\left( {{C_{{\rm{A}}1}},{K_{\rm{B}}}} \right) = e\left( {{C_{{\rm{B}}1}},{K_{\rm{A}}}} \right)$成立。

4.   安全性证明

假设挑战者${\rm{C}}$无法以一定的优势解决BDH (Bilinear Diffie-Hellman)困难问题，则在随机预言模型下，方案在适应性选择关键字攻击下具有关键字不可区分性安全。

引理1　假设敌手${{\rm{A}}_{{{\rm{I}}}}}$以一定的优势${\rm{\varepsilon }}$攻破CLEETS方案，则存在一个算法${\rm{B}}$以一定的优势解决BDH困难问题。设${q_{{H_1}}}$, ${q_{{\rm{PP}}}}$, ${q_{\rm{P}}}$, ${q_{\rm{T}}}$和${q_{\rm{A}}}$分别表示${H_1}$哈希询问、部分私钥询问、私钥询问、搜索陷门询问和测试陷门询问，则算法${\rm{B}}$解决BDH困难问题的优势为

证明　给出${\rm{BDH}}$问题实例$\left( {g,{g^a},{g^b},{g^c}} \right)$, ${\rm{C}}$的主要任务是通过${{\rm{A}}_{{{\rm{I}}}}}$的回答，计算出$e{\left( {g,g} \right)^{abc}}$。

(1) 系统设置。${\rm{C}}$选择一个${\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}\left( 1 \le {\rm{I}}{{\rm{D}}_{{{\rm{I}}}}} \le {q_{{H_1}}} \right)$作为挑战身份，计算$\hat g = {g^a}$,将系统参数${\rm{PP}} =\{ {{ K}},{G_1},{G_2},e,q,g,\hat g,{H_1},{H_2},{H_3},{H_4}{\rm{\} }}$发送给敌手${{\rm{A}}_{{{\rm{I}}}}}$。

(2) ${H_1}$哈希询问：${\rm{C }}$维持${L_{{H_1}}}$数据表，该表包含元组$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{\alpha _i},{Q_i}} \right\rangle$。${{\rm{A}}_{{{\rm{I}}}}}$询问${\rm{I}}{{\rm{D}}_{{i}}}$时，${\rm{C}}$执行以下操作：

(a)如果${\rm{I}}{{\rm{D}}_{{i}}}$已经在$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{\alpha _i},{Q_i}} \right\rangle$中，${\rm{C}}$输出${Q_i}$; (b)否则，判断${\rm{I}}{{\rm{D}}_{{i}}}$是否等于${\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}$。如果${\rm{I}}{{\rm{D}}_{{i}}} = {\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}$, ${\rm{C}}$随机选取${\alpha _i} \in Z_q^ *$并计算${Q_i} = {{{g}}^{{\alpha _i}b}}$; (c)否则，${\rm{C}}$随机选取${\alpha _i} \in Z_q^ *$并计算${Q_i} = {{{g}}^{{\alpha _i}}}$，添加$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{\alpha _i},{Q_i}} \right\rangle$到表${L_{{H_1}}}$中并输出${Q_i}$。

(3)${H_2}$哈希询问：${\rm{C}}$维持${L_{{H_2}}}$数据表，该表包含元组$\left\langle {{w_i},{\beta _i},{H_2}\left( {{w_i}} \right)} \right\rangle$。${{\rm{A}}_{{I}}}$询问${w_i}$时，${\rm{C}}$执行以下操作：

(a)如果${H_2}\left( {{w_i}} \right)$已经在$\left\langle {{w_i},{\beta _i},{H_2}\left( {{w_i}} \right)} \right\rangle$中，${\rm{C}}$输出${H_2}\left( {{w_i}} \right)$; (b)否则，${\rm{C}}$随机选取${\beta _i} \in Z_q^ *$并计算${H_2}\left( {{w_i}} \right) = {{{g}}^{{\beta _i}}}$，添加$\left\langle {{w_i},{\beta _i},{H_2}\left( {{w_i}} \right)} \right\rangle$到表${L_{{H_2}}}$中并输出${H_2}\left( {{w_i}} \right)$。

(4)${H_3}$哈希询问：${\rm{C}}$维持${L_{{H_3}}}$数据表，该表包含元组$\left\langle {{M_j},{\beta _j},{H_3}\left( {{M_j}} \right)} \right\rangle$。当${{\rm{A}}_{{{\rm{I}}}}}$对${M_j}$进行询问时，${\rm{C}}$执行以下操作：

(a)如果${H_3}\left( {{M_j}} \right)$已经在$\left\langle {{M_j},{\beta _j},{H_3}\left( {{M_j}} \right)} \right\rangle$中，${\rm{C}}$输出${H_3}\left( {{M_j}} \right)$; (b)否则，${\rm{C}}$随机选取${\gamma _i} \in Z_q^ *$并计算${H_3}\left( {{M_j}} \right) = {g^{{\gamma _i}}}$，添加$\left\langle {{w_i},{\beta _i},{H_2}\left( {{w_i}} \right)} \right\rangle$到表${L_{{H_3}}}$中并输出${H_3}\left( {{M_j}} \right)$。

(5)${H_4}$哈希询问：${\rm{C}}$维持${L_{{H_4}}}$数据表，该表包含元组$\left\langle {{\rm{P}}{{\rm{K}}_{{i}}},{Q_i},{H_4}} \right\rangle$。当${{\rm{A}}_{{{\rm{I}}}}}$对${\rm{P}}{{\rm{K}}_{{i}}}$, ${Q_i}$进行询问时，${\rm{C}}$执行以下操作：

(a)如果${\rm{P}}{{\rm{K}}_{{i}}},\;{Q_i}$已经在${L_{{H_1}}},{L_{{\rm{PK}}}}$在中，${\rm{C}}$输出${H_4}$; (b)否则，${\rm{C}}$随机选取${x_i},{\alpha _i} \in Z_q^ *$并计算${\rm{P}}{{\rm{K}}_{{i}}} = {g^{{x_i}}}$, ${Q_i} = {g^{{\alpha _i}}}$，添加$\left\langle {{\rm{P}}{{\rm{K}}_{\rm{i}}},{Q_i},{H_4}} \right\rangle$到表${L_{{H_4}}}$中并输出${H_4}$。

(6)部分私钥提取询问。${\rm{C}}$维持为${L_{{\rm{PSK}}}}$数据表，该表包含元组$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i},{D_i}} \right.\rangle$。${{\rm{A}}_{{{\rm{I}}}}}$询问${\rm{I}}{{\rm{D}}_{{i}}}$的部分私钥时，${\rm{ C}}$执行${H_1}$询问获得$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},} \right.\left. {{\alpha _i},{Q_i}} \right\rangle$，然后执行：

(a)如果${\rm{I}}{{\rm{D}}_{{i}}} \ne {\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}$，先计算${D_i} = {\hat g^{{\alpha _i}}}$，然后添加$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i},{D_i}} \right\rangle$到表${L_{{\rm{PSK}}}}$中并输出${D_i}$; (b)否则，${\rm{C}}$终止操作，记录该事件为${{{E}}_{\rm{1}}}$。

(7)公钥提取询问。${\rm{C}}$维持${L_{{\rm{PK}}}}$数据表，该表包括元组$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{\rm{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$。${{\rm{A}}_{{{\rm{I}}}}}$询问${\rm{I}}{{\rm{D}}_{{i}}}$的公钥时，${\rm{C}}$执行如下操作：

(a)如果${\rm{P}}{{\rm{K}}_{{i}}}$存在于${L_{{\rm{PK}}}}$中则输出${\rm{P}}{{\rm{K}}_{{i}}}$; (b)否则${\rm{C}}$随机选取${{{X}}_{{i}}} \in Z_q^*$计算${\rm{P}}{{\rm{K}}_{{i}}} = {g^{\tfrac{1}{{X{{i}}}}}}$, ${\rm{C}}$添加$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{\rm{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$到表 ${L_{{\rm{PK}}}}$中并输出 ${\rm{P}}{{\rm{K}}_{{i}}}$。

(8)公钥替换询问。${{\rm{A}}_{{{\rm{I}}}}}$以一个随机值代替任意用户的公钥。

(9)私钥询问。输入用户身份${\rm{I}}{{\rm{D}}_{{i}}}$，如果${\rm{I}}{{\rm{D}}_{{i}}} = {\rm{I}}{{\rm{D}}_{{I}}}$, ${\rm{C}}$终止查询，此事件记为${{{E}}_{\rm{2}}}$；否则${\rm{C}}$执行以下操作：

(a)如果$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i},{D_i}} \right\rangle$和$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$分别位于表${L_{{\rm{PSK}}}}$和${L_{{\rm{PK}}}}$中，则${\rm{C}}$设置私钥${\rm{S}}{{\rm{K}}_{{i}}} = \left( {{{\rm{X}}_{{i}}},} \right.\left. {{D_i}} \right)$并输出此值；(b)否则，${\rm{C}}$以身份${{\rm{ID}} _{{i}}}$进行查询，通过上述过程获得${\rm{S}}{{\rm{K}}_{{i}}} = \left( {{X_i},{D_i}} \right)$并输出。

(10)搜索陷门询问。当${{\rm{A}}_{{{\rm{I}}}}}$对关键字${w_i}$对应的${T_{{{\rm{W}}_i}}}$进行陷门查询时，挑战者${\rm{C}}$执行以下操作:

(a)如果${\rm{I}}{{\rm{D}}_{{i}}} = {\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}$，则${\rm{C}}$终止查询，此事件记为${{{E}}_{\rm{3}}}$；(b)否则，${\rm{C}}$从表${L_{{\rm{PK}}}}$中取出$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$，从表${L_{{\rm{PSK}}}}$中取出$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i},{D_i}} \right\rangle$，从表${L_{{H_2}}}$中取出$\left\langle {{w_i},{\beta _i},{H_2}\left( {{w_i}} \right)} \right\rangle$，计算 ${T_{{W_i}}} = {H_2}{({w_i}^\prime )^{{{{X}}_{\rm{R}}}}}{D_{\rm{R}}}$并输出。

(11)测试陷门询问。当${{\rm{A}}_{{{\rm{I}}}}}$对消息${M_j}$进行测试陷门查询时，挑战者${\rm{C}}$执行以下操作:

(a)如果${\rm{I}}{{\rm{D}}_{{i}}} = {\rm{I}}{{\rm{D}}_{{I}}}$，则${\rm{C}}$终止查询，此事件记为${{{E}}_{\rm{4}}}$；(b)否则，${\rm{C}}$从表${L_{{\rm{PK}}}}$中取出$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$，从表${L_{{\rm{PSK}}}}$中取出$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i},{D_i}} \right\rangle$，计算${t_{{M_j}}}$$= {D_{\rm{R}}}^{{{{X}}_{\rm{R}}}}$。

(12)挑战。利用身份${\rm{I}}{{\rm{D}}^{\rm{*}}}$, ${{\rm{A}}_{{{\rm{I}}}}}$对两个关键字${w_0}$和${w_1}$发起挑战，C执行以下操作：

(a)如果${\rm{I}}{{\rm{D}}^{\rm{*}}} \ne {\rm{I}}{{\rm{D}}_{{i}}}$，${\rm{C}}$终止查询，此事件记为${{{E}}_{\rm{5}}}$；(b)否则，随机选择$b \in \left\{ {0,1} \right\}$, $r \in Z_q^ *$，输出${C^ * } = \left( {{g^{{\rm{rc}}}},{C_{{\rm{3b}}}}} \right)$。如果${C^ * }$是有效密文，则${C^ * } =$$e\left( {{g^{{\beta _i}}},} {g^{{{{X}}_{\rm{R}}}}}{\rm{P}}{{\rm{K}}_{\rm{S}}} \right)^{{\rm{rc}}} e{\left( {{g^{{\alpha _i}b}},{g^a}} \right)^{{\rm{rc}}}} = e{\left( {g,g} \right)^{{\beta _i}{{{X}}_{\rm{R}}}{\rm{rc}}}}e{\left( {g,{\rm{P}}{{\rm{K}}_{\rm{S}}}} \right)^{{\beta _i}{\rm{rc}}}}e\left( g, g \right)^{{\alpha _i}ab{\rm{rc}}}$。

(13)更多陷门询问。${{\rm{A}}_{\rm{I}}}$通过发送${w_i}$给挑战者${\rm{C}}$，进行更多的陷门询问，其中${w_i} \ne {w_0}$且${w_i} \ne {w_1}$, ${\rm{C}}$像上面一样输出，以事件${{{E}}_{\rm{6}}}$表示${{\rm{A}}_{\rm{I}}}$既没有对${w_0}$询问也没有对${w_1}$询问。

(14)猜测。${{\rm{A}}_{\rm{I}}}$输出$b' \in \left\{ {0,1} \right\}$作为猜测值，此时，

以下分析${\rm{C}}$获胜的优势$\varepsilon '$：

(a)当${{\rm{A}}_{\rm{I}}}$执行${H_i}\left( {1 \le i \le 4} \right)$询问时，${\rm{C}}$以随机值回应；(b)如果${E_i}\left( {1 \le i \le 6} \right)$都不发生，${\rm{C}}$不终止查询。显然，$\Pr \left[ {\neg {{{E}}_{\rm{1}}} \wedge \neg {{{E}}_{\rm{2}}} \wedge \neg {{{E}}_{\rm{3}}} \wedge \neg {{{E}}_{\rm{4}}} \wedge \neg {{{E}}_{\rm{5}}}} \right]= {\left( {1 - {1}/{{{q_{{H_1}}}}}} \right)^{{q_{{\rm{PP}}}} + {q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}}\left( {{1}/{{{q_{{H_1}}}}}} \right)$。

根据文献[8]可知解决困难问题的优势为

引理2　假设敌手${{\rm{A}}_{{\rm{II}}}}$以一定的优势${\rm{\varepsilon }}$攻破CLEETS方案，则存在一个算法${\rm{B}}$以一定的优势解决BDH困难问题。设${q_{{H_1}}}$, ${q_{\rm{P}}}$, ${q_{\rm{T}}}$和${q_{\rm{A}}}$分别表示${H_1}$哈希询问、私钥询问、搜索陷门询问和测试陷门询问。则算法${\rm{B}}$解决BDH困难问题的优势为

证明　给出${\rm{BDH}}$问题实例$\left( {g,{g^a},{g^b},{g^c}} \right)$, ${\rm{C}}$的主要任务是通过${{\rm{A}}_{{\rm{II}}}}$的回答，计算$e{\left( {g,g} \right)^{abc}}$。

(1)系统设置。${\rm{C}}$选择${\rm{I}}{{\rm{D}}_{\rm{I}}}\left( {1 \le {\rm{I}}{{\rm{D}}_{\rm{I}}} \le {q_{{H_1}}}} \right)$作为挑战身份，并计算$\hat g = {g^s}$，最后将系统参数${\rm{PP}} = \{{\rm{ K}}, {G_1},{G_2},e,q,g,\hat g,{H_1},{H_2},{H_3},{H_4}\}$和$s$发送给敌手${{\rm{A}}_{{\rm{II}}}}$。

(2)${H_1}$哈希询问：${\rm{C}}$维持${L_{{H_1}}}$数据表，该表包含元组$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i}} \right\rangle$。当${{\rm{A}}_{{\rm{II}}}}$询问${\rm{I}}{{\rm{D}}_{{i}}}$时，${\rm{C}}$执行以下操作：

(a)如果${\rm{I}}{{\rm{D}}_{\rm{i}}}$已经在$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{\alpha _i},{Q_i}} \right\rangle$中，${\rm{C}}$输出${Q_i}$；(b)否则，${\rm{C}}$随机选取${Q_i} \in {G_1}$，添加$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i}} \right\rangle$到表${L_{{H_1}}}$中并输出${Q_i}$。

(3)${H_2}$哈希询问：与定理1中证明过程相同。

(4)${H_3}$哈希询问：与定理1中证明过程相同。

(5)${H_4}$哈希询问：与定理1中证明过程相同。

(6)公钥提取询问。${\rm{C}}$维持${L_{{\rm{PK}}}}$数据表，该表包含元组$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$。当${{\rm{A}}_{{\rm{II}}}}$询问${\rm{I}}{{\rm{D}}_{{i}}}$的公钥时，${\rm{C}}$执行如下操作：

(a)如果${\rm{P}}{{\rm{K}}_{{i}}}$已经存在于${L_{{\rm{PK}}}}$中，输出${\rm{P}}{{\rm{K}}_{{i}}}$；(b)否则，${\rm{C}}$随机选取${{{X}}_{{i}}} \in Z_q^*$，如果${\rm{I}}{{\rm{D}}_{{i}}} = {\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}$，计算${\rm{P}}{{\rm{K}}_{{i}}} = {g^{b\frac{1}{{{X_i}}}}}$。否则，${\rm{P}}{{\rm{K}}_{{i}}} = {g^{\frac{1}{{{X_i}}}}}$，添加$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$到表${L_{{\rm{PK}}}}$中并输出${\rm{P}}{{\rm{K}}_{{i}}}$。

(7)私钥询问。输入用户身份${\rm{I}}{{\rm{D}}_{{i}}}$，如果${\rm{I}}{{\rm{D}}_{{i}}} = {\rm{I}}{{\rm{D}}_{{{\rm{I}}}}}$, ${\rm{C}}$终止查询，此事件记为${{{E}}_{\rm{1}}}$。否则，${\rm{C}}$查询${L_{{H_1}}}{\text{和}}{L_{{\rm{PK}}}}$获得$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}},{Q_i}} \right\rangle$和$\left\langle {{\rm{I}}{{\rm{D}}_{{i}}}{\rm{,}}{{{X}}_{{i}}}{\rm{,P}}{{\rm{K}}_{{i}}}} \right\rangle$。最后，输出${\rm{S}}{{\rm{K}}_{{i}}} = \left( {{{{X}}_{{i}}},s{Q_i}} \right)$。

(8)搜索陷门询问。与定理1中相同，除了计算${T_{{{\rm{W}}_i}}} = {H_2}{\left( {{w_i}^\prime } \right)^{{{\rm{D }}_{\rm{R}}}}}s{Q_{\rm{R}}}$。

(9)测试陷门询问。与定理1中相同，除了计算${t_{{M_j}}} = s{Q_{\rm{R}}}^{{X_{\rm{R}}}}$。

(10)挑战。与定理1中挑战过程相同。

(11)更多陷门询问。与定理1中证明过程相同。

(12)猜测。${{\rm{A}}_{{\rm{II}}}}$输出$b' \in \left\{ {0,1} \right\}$作为猜测值，此时：

以下分析${\rm{C}}$获胜的优势$\varepsilon '$：

(a)当${{\rm{A}}_{{\rm{II}}}}$执行${H_i}\left( {1 \le i \le 4} \right)$询问时，${\rm{C}}$以随机值回应；(b)如果${E_i}\left( {1 \le i \le 5} \right)$都不发生，则C不终止查询。显然：$\Pr \left[ {\neg {{{E}}_{\rm{1}}} \wedge \neg {{{E}}_{\rm{2}}} \wedge \neg {{{E}}_{\rm{3}}} \wedge \neg {{{E}}_{\rm{4}}}} \right] = {\left( {1 - \dfrac{1}{{{q_{{H_1}}}}}} \right)^{{q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}}\left( {\dfrac{1}{{{q_{{H_1}}}}}} \right)$根据文献[8]可知解决困难问题的优势为：

证毕

5.   性能分析

5.1   功能对比

从表1可以看出，文献[6]方案支持关键字搜索功能但不支持密文等值测试；文献[16]方案支持密文等值测试但不支持关键字搜索功能，其搜索准确度不高。本文方案同时支持密文等值测试和关键字搜索功能。先通过关键字搜索判断是否有用户所需的密文信息，再执行密文等值测试，有效地提高了检索效率。

表 1  功能对比

方案	等值测试	关键字搜索	搜索陷门生成	测试内容
文献[6]方案	不支持	支持	与关键字绑定	判断密文对应明文是否相等
文献[16]方案	支持	不支持	与密文或加密者绑定	判断密文是否包含关键字
本文方案	支持	支持	以上两者都具备	以上两者都具备

下载: 导出CSV 

| 显示表格

5.2   效率分析

文献[6]方案和本文方案均能实现关键字搜索加密，因此仅对本文方案和文献[6]方案的通信开销进行比较。$\left| {{G_1}} \right|$和$\left| {{G_2}} \right|$代表群${G_1}$和${G_2}$上元素的长度，${\lg _q}$代表二进制比特数，$\left| {{Z_q}} \right|$代表${Z_q}$上数的长度。从表2可以看出，与文献[6]方案相比，本文方案秘密值长度和公钥长度相同，部分私钥长度和密文长度稍高。

表 2  通信开销

方案	部分私钥长度	秘密值长度	公钥长度	密文长度
文献[6]方案	|2Zq|	|2Zq|	|2G1|	n(|G1|+lgq)
本文方案	|2G1|	|2Zq|	|2G1|	n(|G1|+|G2|+lgq)

下载: 导出CSV 

| 显示表格

5.3   计算代价

以下模拟方案的计算代价。假设${T_{{\rm{sm}}}}$为生成随机数时间；${T_{\rm{b}}}$为双线性对运算时间；${T_{\rm{H}}}$为哈希函数运算时间；${T_{{\rm{ex}}}}$为指数运算时间；${T_{{\rm{mul}}}}$为乘法运算时间。仿真环境为戴尔笔记本电脑(I7-4700CPU@ 3.2 GHz，16 GB和Ubuntu Linux)和PBC^[20]函数库。方案的执行时间如表3所示，其中，T_sm=2.142 ms, T_b=0.671 ms, T_H=5.762 ms, T_ex=5.611ms, T_mul=0.1 ms。

表 3  计算代价(ms)

密钥生成		加密		陷门		授权		测试算法1		测试算法2
4Tex +2TH +2Tsm=38.252		4Tex +3Tb +Tmul +2TH +2Tsm= 40.365		TH +Tex +Tmul =11.473		Tex =5.611		2Tb +Tex=6.953		4Tb +2TH=14.208

下载: 导出CSV 

| 显示表格

6.   结束语

本文提出了一种支持关键字搜索的无证书密文等值测试加密方案。该方案可以实现未对密文解密的情况下，先执行关键字检索，再判断是否执行密文等值测试，进而判断两个密文是否是同一明文产生。该方案不仅克服了传统可搜索加密的密文等值测试问题，也解决了等值测试中检索效率低的问题。通过安全性分析，证明本文方案满足关键字不可区分性。由于方案在密文等值测试的基础上增加了密文关键字搜索功能，使服务器免于执行遍历密文的等值测试，但是，增加了两个双线性对运算和一个映射到循环群的哈希运算，因此，具有相对较大的计算开销。未来，我们会进一步解决计算和通信开销问题。