支持关键字搜索的无证书密文等值测试加密方案

张玉磊; 陈文娟; 张永洁; 张雪微; 王彩芬

doi:10.11999/JEIT190752

支持关键字搜索的无证书密文等值测试加密方案

doi: 10.11999/JEIT190752

1.
西北师范大学兰州 730070
2.
甘肃卫生职业学院兰州 730000
3.
深圳技术大学深圳 518118

基金项目: 国家自然科学基金(61662069)，甘肃省高等学校科研项目(2017A-003, 2018A-207)

详细信息

作者简介:
张玉磊：男，1979年生，博士，副教授，研究方向为密码学与信息安全

陈文娟：女，1993年生，硕士生，研究方向为密码学与信息安全

张永洁：女，1978年生，硕士，副教授，研究方向为密码学与信息安全

张雪微：女，1995年生，硕士生，研究方向为密码学与信息安全

王彩芬：女，1963年生，博士，教授，研究方向为密码学与信息安全

通讯作者:
陈文娟　497604722@qq.com

中图分类号: TP309
计量
- 文章访问数: 1808
- HTML全文浏览量: 868
- PDF下载量: 96
- 被引次数: 12
出版历程
- 收稿日期: 2019-09-29
- 修回日期: 2020-04-23
- 网络出版日期: 2020-05-28
- 刊出日期: 2020-11-16

Certificateless Puklic Key Encryption With Equality Test of Supporting Keyword Search

1.
Northwest Normal University, Lanzhou 730070, China
2.
Gansu Health Vocational, Lanzhou 730000, China
3.
Shenzhen Technology University, Shenzhen 518118, China

Funds: The National Natural Science Foundation of China(61662069), The Higher Educational Scientific Research Foundation of Gansu Province (2017A-003, 2018A-207)

摘要

摘要: 公钥加密等值测试(PKEET)可以实现云环境下不同公钥加密数据之间的密文等值比较，即不对密文解密的情况下测试两个密文对应的明文是否一致。但是，密文等值测试加密不提供关键字密文搜索功能。已有密文等值测试加密方案直接以消息生成陷门作为等值测试的凭证，测试的准确度不高，搜索效率较低。针对此问题，该文首先提出了支持关键字搜索的无证书密文等值测试加密(CLEETS)方案。方案通过关键字检索判断是否包含自己需要的信息，根据判断结果选择执行等值测试，从而避免无效测试。然后，在随机预言机模型下证明该方案满足适应性选择关键词不可区分性。最后，对方案进行功能和效率对比。对比结果表明，该文方案的计算代价略高，但是方案在密文等值测试加密中实现了关键字的检索功能，弥补了效率低的不足。
- 无证书公钥密码 /
- 可搜索加密 /
- 密文等值测试
Abstract: Public Key Encryption with Equality Test (PKEET) is an important method to achieve the equality test of ciphertexts which are generated by the different public key aiming to the same plaintext in cloud environment. In other words, it can tests the plaintext corresponding to the two ciphertext’s equivalence without decrypting the ciphertext, but does not supply the searchable function. Nowadays, the existing PKEET scheme takes directly the message to generate a trapdoor as the proof of equality test, which has low test accuracy and search efficiency. To solve the above problems, a certificateless public key encryption with equality test scheme supporting keyword search (CertificateLess Equality test EncrypTion with keyword Search, CLEETS) is proposed. The scheme determines whether it contains information needed by the user through the keyword search, then performs the equality test according to the search result, which can avoid invalid test. Then, it is proved that the scheme satisfies the indistinguishability of adaptive selection of keywords under the random oracle model. Finally, the comparison analyses of function and efficiency are performed. The results indicate the computation cost of CLEETS scheme is less efficient. Fortunately, it can realizes the function of keyword search in encryption with equality test, which can remedies the inefficiency.
- Certificateless public key cryptography /
- Encryption with keyword search /
- Equality test

HTML全文

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}$ ：

$\begin{split} & e\left( {{T_{\rm{W}}},{C_1}} \right)e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{S}}}}},{C_1}} \right)\\ & \quad= e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{R}}}}}{D_{\rm{R}}},{g^\alpha }} \right)e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{S}}}}},{g^\alpha }} \right)\\ & \quad= e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{R}}}}},{g^\alpha }} \right)e\left( {{D_{\rm{R}}},{g^\alpha }} \right)e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{S}}}}},{g^\alpha }} \right)\\ & \quad= e\left( {{H_2}{{\left( {{w_i}} \right)}^{{{{X}}_{\rm{R}}}{{ + }{{{{X}}_{\rm{S}}}}}}},{g^\alpha }} \right)e\left( {{Q_{\rm{R}}}^{\rm{s}},{g^\alpha }} \right)\\ & \quad= 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_{\rm{R}}}^\alpha ,\hat g} \right) = {C_3} \end{split}$

即等式 $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₂中的验证等式成立：

$\begin{split} {K_{\rm{A}}} =\,& \frac{{{C_{{\rm{A}}4}}}}{{{H_4}\left( {e\left( {{C_{{\rm{A}}2}},{T_{d{\rm{A}}}}} \right)} \right)}} \\ =& \frac{{{H_3}{{\left( {{M_{\rm{A}}}} \right)}^{{\alpha _{\rm{A}}}}} \cdot {H_5}\left( {e{{\left( {{\rm{P}}{{\rm{K}}_{{\rm{RA}}}},Q{}_{{\rm{R}}{\rm{A}}}} \right)}^{{\beta _{\rm{A}}}}}} \right)}}{{{H_4}\left( {e\left( {{g^{{\beta _{\rm{A}}}}},{D_{{\rm{RA}}}}^{{{{X}}_{{\rm{RA}}}}}} \right)} \right)}}\\ =& \frac{{{H_3}{{\left( {{M_{\rm{A}}}} \right)}^{{\alpha _{\rm{A}}}}} \cdot {H_4}\left( {e{{\left( {{g^{s{{{X}}_{{\rm{RA}}}}}},Q{}_{{\rm{RA}}}} \right)}^{{\beta _{\rm{A}}}}}} \right)}}{{{H_4}\left( {e\left( {{g^{{\beta _{\rm{A}}}}},{Q_{{\rm{RA}}}}^{s{{{X}}_{{\rm{RA}}}}}} \right)} \right)}} \\ =& {H_3}{\left( {{M_{\rm{A}}}} \right)^{{\alpha _{\rm{A}}}}},\\ {K_{\rm{B}}} =\,& \frac{{{C_{{\rm{B}}4}}}}{{{H_4}\left( {e\left( {{C_{{\rm{B}}2}},{T_{d{\rm{B}}}}} \right)} \right)}} \\ =& \frac{{{H_3}{{\left( {{M_{\rm{B}}}} \right)}^{{\alpha _{\rm{B}}}}} \cdot {H_4}\left( {e{{\left( {{\rm{P}}{{\rm{K}}_{{\rm{RB}}}},Q{}_{{\rm{RB}}}} \right)}^{{\beta _{\rm{B}}}}}} \right)}}{{{H_4}\left( {e\left( {{g^{{\beta _{\rm{B}}}}},{D_{{\rm{RB}}}}^{{{{X}}_{{\rm{RB}}}}}} \right)} \right)}} \\ =& \frac{{{H_3}{{\left( {{M_{\rm{B}}}} \right)}^{{\alpha _{\rm{B}}}}} \cdot {H_4}\left( {e{{\left( {{g^{s{{{X}}_{{\rm{RB}}}}}},Q{}_{{\rm{RB}}}} \right)}^{{\beta _{\rm{B}}}}}} \right)}}{{{H_4}\left( {e\left( {{g^{{\beta _{\rm{B}}}}},{Q_{{\rm{RB}}}}^{s{{{X}}_{{\rm{RB}}}}}} \right)} \right)}} \\ =& {H_3}{\left( {{M_{\rm{B}}}} \right)^{{\alpha _{\rm{B}}}}}{\text{。}} \end{split}$

如果 ${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{\varepsilon '}} \ge \frac{{\rm{\varepsilon }}}{{{q_{{H_1}}}}}{\left( {1 - \frac{1}{{{q_{{H_1}}}}}} \right)^{{q_{{\rm{PP}}}} + {q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}}$

证明　给出 ${\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\}$ 作为猜测值，此时，

$\begin{split} & {\left( {\frac{{{C^ * }}}{{e{{\left( {{g^c},g} \right)}^{r{\beta _i}{{{X}}_{\rm{i}}}}}e{{\left( {{g^c},{\rm{P}}{{\rm{K}}_{\rm{S}}}} \right)}^{r{\beta _i}}}}}} \right)^{\frac{1}{{r{\alpha _i}}}}} \\ &\quad = {\left( {\frac{{e{{\left( {g,g} \right)}^{cr{\beta _i}{{{X}}_{\rm{i}}}}}e{{\left( {g,{\rm{P}}{{\rm{K}}_{\rm{S}}}} \right)}^{cr{\beta _i}}}e{{\left( {g,g} \right)}^{rabc{\alpha _i}}}}}{{e{{\left( {{g^c},g} \right)}^{r{\beta _i}{{{X}}_i}}}e{{\left( {{g^c},{\rm{P}}{{\rm{K}}_{\rm{S}}}} \right)}^{r{\beta _i}}}}}} \right)^{\frac{1}{{r{\alpha _i}}}}}\\ &\quad = {\left( {\frac{{e{{\left( {g,g} \right)}^{cr{\beta _i}{{{X}}_{\rm{i}}}}}e{{\left( {g,{\rm{P}}{{\rm{K}}_{\rm{S}}}} \right)}^{cr{\beta _i}}}e{{\left( {g,g} \right)}^{rabc{\alpha _i}}}}}{{e{{\left( {{g^c},g} \right)}^{r{\beta _i}{{{X}}_i}}}e{{\left( {{g^c},{\rm{P}}{{\rm{K}}_{\rm{S}}}} \right)}^{r{\beta _i}}}}}} \right)^{\frac{1}{{r{\alpha _i}}}}} \\ &\quad = {\left( {e{{\left( {g,g} \right)}^{rabc{\alpha _i}}}} \right)^{\frac{1}{{r{\alpha _i}}}}} = e{\left( {g,g} \right)^{abc}} \end{split}$

以下分析 ${\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]可知解决困难问题的优势为

$\varepsilon ' \!\ge\! \frac{1}{2}\Pr \left[ {\neg {{{E}}_{\rm{6}}}} \right]\Pr \left[ {\neg {{{E}}_1} \!\wedge\! \neg {{{E}}_{\rm{2}}} \!\wedge\! \neg {{{E}}_{\rm{3}}}\! \wedge\! \neg {{{E}}_{\rm{4}}} \!\wedge\! \neg {{{E}}_{\rm{5}}}} \right]$

$\begin{split} & \ge \frac{1}{2} \cdot 2\varepsilon \cdot {\left( {1{\rm{ - }}\frac{1}{{{q_{{H_1}}}}}} \right)^{{q_{{\rm{PP}}}} + {q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}} \cdot \left( {\frac{1}{{{q_{{H_1}}}}}} \right) \\ & = \left( {\frac{\varepsilon }{{{q_{{H_1}}}}}} \right){\left( {1{\rm{ - }}\frac{1}{{{q_{{H_1}}}}}} \right)^{{q_{{\rm{PP}}}} + {q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{证毕} \end{split}$

引理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{\varepsilon '}} \ge \frac{{\rm{\varepsilon }}}{{{q_{{H_1}}}}}{\left( {1 - \frac{1}{{{q_{{H_1}}}}}} \right)^{{q_P} + {q_T} + {q_A}}}$

证明　给出 ${\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\}$ 作为猜测值，此时：

$\begin{split} & {\left( {\frac{{{C^ * }}}{{e{{\left( {{g^a},{g^{c{X_S}}}} \right)}^{r{\beta _i}}}e{{\left( {{Q_i},{g^{cs}}} \right)}^r}}}} \right)^{\frac{1}{{r{\beta _i}{{{X}}_i}}}}}\\ & \quad = {\left( {\frac{{e{{\left( {g,g} \right)}^{a{\beta _i}b{{{X}}_{{i}}}rc}}e{{\left( {{g^a},{g^{c{{{X}}_{\rm{S}}}}}} \right)}^{{\beta _i}r}}e{{\left( {{Q_i},{g^{cs}}} \right)}^r}}}{{e{{\left( {{g^a},{g^{c{{{X}}_{\rm{S}}}}}} \right)}^{r{\beta _i}}}e{{\left( {{Q_i},{g^{cs}}} \right)}^r}}}} \right)^{\frac{1}{{r{\beta _i}{{{X}}_{\rm{i}}}}}}}\\ & \quad = {\left( {e{{\left( {g,g} \right)}^{a{\beta _i}b{{{X}}_{\rm{i}}}rc}}} \right)^{\frac{1}{{r{\beta _i}{{{X}}_i}}}}} = e{\left( {g,g} \right)^{abc}} \end{split}$

以下分析 ${\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]可知解决困难问题的优势为：

$\begin{split} \varepsilon '\,& \ge \frac{1}{2}\Pr \left[ {\neg {{{E}}_{\rm{5}}}} \right]\Pr \left[ {\neg {{{E}}_{\rm{1}}} \wedge \neg {{{E}}_{\rm{2}}} \wedge \neg {{{E}}_{\rm{3}}} \wedge \neg {{{E}}_{\rm{4}}}} \right]\\ & \ge \frac{1}{2} \cdot 2\varepsilon \cdot {\left( {1{\rm{ - }}\frac{1}{{{q_{{H_1}}}}}} \right)^{{q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}} \cdot \left( {\frac{1}{{{q_{{H_1}}}}}} \right) \\ & = \left( {\frac{\varepsilon }{{{q_{{H_1}}}}}} \right){\left( {1{\rm{ - }}\frac{1}{{{q_{{H_1}}}}}} \right)^{{q_{\rm{P}}} + {q_{\rm{T}}} + {q_{\rm{A}}}}} \end{split}$

证毕

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]方案	\|2Z_q\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+lg_q)
本文方案	\|2G₁\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+\|G₂\|+lg_q)

下载: 导出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
4T_ex +2T_H +2T_sm=38.252		4T_ex +3T_b +T_mul +2T_H +2T_sm= 40.365		T_H +T_ex +T_mul =11.473		T_ex =5.611		2T_b +T_ex=6.953		4T_b +2T_H=14.208

下载: 导出CSV

| 显示表格

6. 结束语

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

图 1 系统模型图

下载: 全尺寸图片幻灯片

表 1 功能对比

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

下载: 导出CSV

表 2 通信开销

方案	部分私钥长度	秘密值长度	公钥长度	密文长度
文献[6]方案	\|2Z_q\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+lg_q)
本文方案	\|2G₁\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+\|G₂\|+lg_q)

下载: 导出CSV

表 3 计算代价(ms)

密钥生成		加密		陷门		授权		测试算法1		测试算法2
4T_ex +2T_H +2T_sm=38.252		4T_ex +3T_b +T_mul +2T_H +2T_sm= 40.365		T_H +T_ex +T_mul =11.473		T_ex =5.611		2T_b +T_ex=6.953		4T_b +2T_H=14.208

下载: 导出CSV

参考文献(20)

张键红, 李鹏燕. 一种有效的云存储数据完整性验证方案[J]. 信息网络安全, 2017(3): 1–5. doi: 10.3969/j.issn.1671-1122.2017.03.001

ZHANG Jianhong and LI Pengyan. An efficient data integrity verification scheme for cloud storage[J]. Netinfo Security, 2017(3): 1–5. doi: 10.3969/j.issn.1671-1122.2017.03.001

MAYER-SCHONBERGER V and CUKIER K. Big data: A Revolution that Will Transform How We Live, Work and Think[M]. London: John Murray, 2013: 94–98.

SONG D X, WAGNER D, and PERRIG A. Practical techniques for searches on encrypted data[C]. 2000 IEEE Symposium on Security and Privacy, Berkeley, USA, 2000: 44–55. doi: 10.1109/SECPRI.2000.848445.

BONEH D, DI CRESCENZO G, OSTROVSKY R, et al. Public key encryption with keyword search[C]. International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2004: 506–522. doi: 10.1007/978-3-540-24676-3_30.

江明明, 郭宇燕, 余磊, 等. 有效的标准模型下格上基于身份的代理重加密[J]. 电子与信息学报, 2019, 41(1): 61–66. doi: 10.11999/JEIT180146

JIANG Mingming, GUO Yuyan, YU Lei, et al. Efficient identity-based proxy re-encryption on lattice in the standard model[J]. Journal of Electronics &Information Technology, 2019, 41(1): 61–66. doi: 10.11999/JEIT180146

PENG Yanguo, CUI Jiangtao, PENG Changgen, et al. Certificateless public key encryption with keyword search[J]. China Communications, 2014, 11(11): 100–113. doi: 10.1109/CC.2014.7004528

MA Mimi, HE Debiao, KUMAR N, et al. Certificateless searchable public key encryption scheme for industrial internet of things[J]. IEEE Transactions on Industrial Informatics, 2018, 14(2): 759–767. doi: 10.1109/TII.2017.2703922

MA Mimi, HE Debiao, KHAN M K, et al. Certificateless searchable public key encryption scheme for mobile healthcare system[J]. Computers & Electrical Engineering, 2018, 65: 413–424. doi: 10.1016/j.compeleceng.2017.05.014

张玉磊, 刘祥震, 郎晓丽, 等. 云存储环境下多服务器的密钥聚合可搜索加密方案[J]. 电子与信息学报, 2019, 41(3): 674–679. doi: 10.11999/JEIT180418

ZHANG Yulei, LIU Xiangzhen, LANG Xiaoli, et al. Multi-server key aggregation searchable encryption scheme in cloud environment[J]. Journal of Electronics &Information Technology, 2019, 41(3): 674–679. doi: 10.11999/JEIT180418

张玉磊, 刘文静, 刘祥震, 等. 基于授权的多服务器可搜索密文策略属性基加密方案[J]. 电子与信息学报, 2019, 41(8): 1808–1814. doi: 10.11999/JEIT180944

ZHANG Yulei, LIU Wenjing, LIU Xiangzhen, et al. Searchable multi-server CP-ABE scheme based on authorization[J]. Journal of Electronics &Information Technology, 2019, 41(8): 1808–1814. doi: 10.11999/JEIT180944

YANG Guomin, TAN C H, HUANG Qiong, et al. Probabilistic public key encryption with equality test[C]. Cryptographers’ Track at the RSA Conference 2010, San Francisco, USA, 2010: 119–131. doi: 10.1007/978-3-642-11925-5_9.

TANG Qiang. Towards public key encryption scheme supporting equality test with fine-grained authorization[C]. The 16th Australasian Conference on Information Security and Privacy, Melbourne, Australia, 2011: 389–406.

TANG Qiang. Public key encryption supporting plaintext equality test and user-specified authorization[J]. Security and Communication Networks, 2012, 5(12): 1351–1362. doi: 10.1002/sec.418

TANG Qiang. Public key encryption schemes supporting equality test with authorisation of different granularity[J]. International Journal of Applied Cryptography, 2012, 2(4): 304–321. doi: 10.1504/IJACT.2012.048079

MA Sha, HUANG Qiong, ZHANG Mingwu, et al. Efficient public key encryption with equality test supporting flexible authorization[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(3): 458–470. doi: 10.1109/TIFS.2014.2378592

MA Sha. Identity-based encryption with outsourced equality test in cloud computing[J]. Information Sciences, 2016, 328: 389–402. doi: 10.1016/j.ins.2015.08.053

QU Haipeng, YAN Zhen, LIN Xijun, et al. Certificateless public key encryption with equality test[J]. Information Sciences, 2018, 462: 76–92. doi: 10.1016/j.ins.2018.06.025

HUANG Kaibin, TSO R, CHEN Yuchi, et al. PKE-AET: Public key encryption with authorized equality test[J]. The Computer Journal, 2015, 58(10): 2686–2697. doi: 10.1093/comjnl/bxv025

LEE H T, LING San, SEO J H, et al. Semi-generic construction of public key encryption and identity-based encryption with equality test[J]. Information Sciences, 2016, 373: 419–440. doi: 10.1016/j.ins.2016.09.013

The pairing-based cryptography library[EB/OL]. http://crypto.stanford.edu/pbc/, 2015.

施引文献

期刊类型引用(2)

1.	宋文帅，邓淼磊，马米米，李昊宸. 可搜索公钥加密研究进展. 计算机应用. 2023(03): 794-803 . 百度学术
2.	张玉磊，白巧玲，马彦丽，闫晨阳，王彩芬. 无证书密文等值测试签密方案. 电子与信息学报. 2021(09): 2534-2541 . 本站查看

其他类型引用(10)

资源附件(0)

访问统计

图(1) / 表(3)

计量

文章访问数: 1808
HTML全文浏览量: 868
PDF下载量: 96
被引次数: 12

1. 引言
2. CLEETS方案安全模型
2.1 CLEETS方案系统模型
2.2 CLEETS方案形式化定义
2.3 CLEETS方案安全模型
3. CLEETS方案
3.1 具体方案
3.2 正确性
4. 安全性证明
5. 性能分析
5.1 功能对比
5.2 效率分析
5.3 计算代价
6. 结束语

姓名
邮箱
手机号码
标题
留言内容
验证码

方案	部分私钥长度	秘密值长度	公钥长度	密文长度
文献[6]方案	\|2Z_q\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+lg_q)
本文方案	\|2G₁\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+\|G₂\|+lg_q)

方案	部分私钥长度	秘密值长度	公钥长度	密文长度
文献[6]方案	\|2Z_q\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+lg_q)
本文方案	\|2G₁\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+\|G₂\|+lg_q)

方案	部分私钥长度	秘密值长度	公钥长度	密文长度
文献[6]方案	\|2Z_q\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+lg_q)
本文方案	\|2G₁\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+\|G₂\|+lg_q)

方案	部分私钥长度	秘密值长度	公钥长度	密文长度
文献[6]方案	\|2Z_q\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+lg_q)
本文方案	\|2G₁\|	\|2Z_q\|	\|2G₁\|	n(\|G₁\|+\|G₂\|+lg_q)

留言板

支持关键字搜索的无证书密文等值测试加密方案

doi: 10.11999/JEIT190752

通讯作者:
陈文娟　497604722@qq.com

计量

Certificateless Puklic Key Encryption With Equality Test of Supporting Keyword Search

1. 引言

2. CLEETS方案安全模型

2.1 CLEETS方案系统模型

2.2 CLEETS方案形式化定义

2.3 CLEETS方案安全模型

3. CLEETS方案

3.1 具体方案

3.2 正确性

4. 安全性证明

5. 性能分析

5.1 功能对比

5.2 效率分析

5.3 计算代价

6. 结束语

期刊类型引用(2)

其他类型引用(10)

计量

目录

1. 引言

2. CLEETS方案安全模型

2.1 CLEETS方案系统模型

2.2 CLEETS方案形式化定义

2.3 CLEETS方案安全模型

3. CLEETS方案

3.1 具体方案

3.2 正确性

4. 安全性证明

5. 性能分析

5.1 功能对比

5.2 效率分析

5.3 计算代价

6. 结束语

留言板

支持关键字搜索的无证书密文等值测试加密方案

doi: 10.11999/JEIT190752

通讯作者: 陈文娟 497604722@qq.com

计量

出版历程

Certificateless Puklic Key Encryption With Equality Test of Supporting Keyword Search

1. 引言

2. CLEETS方案安全模型

2.1 CLEETS方案系统模型

2.2 CLEETS方案形式化定义

2.3 CLEETS方案安全模型

3. CLEETS方案

3.1 具体方案

3.2 正确性

4. 安全性证明

5. 性能分析

5.1 功能对比

5.2 效率分析

5.3 计算代价

6. 结束语

期刊类型引用(2)

其他类型引用(10)

计量

出版历程

目录

1. 引言

2. CLEETS方案安全模型

2.1 CLEETS方案系统模型

2.2 CLEETS方案形式化定义

2.3 CLEETS方案安全模型

3. CLEETS方案

3.1 具体方案

3.2 正确性

4. 安全性证明

5. 性能分析

5.1 功能对比

5.2 效率分析

5.3 计算代价

6. 结束语

通讯作者:
陈文娟　497604722@qq.com