开放科学（资源服务）标志码（OSID）：

0 概述

云存储技术的快速发展使得人们存储、管理大量数据更加便捷，但是数据面临泄露风险。为保护云服务器中的数据隐私，云存储技术通常对原始数据进行加密，把加密后的密文数据上传至云服务器，但是会给使用数据的用户带来不便。例如，当用户需要检索数据时，需要将全部密文数据下载到本地，在本地解密之后再执行检索操作。为更好地解决云数据的安全问题，可搜索加密（Searchable Encryption，SE）技术应运而生，并得到研究人员的广泛关注。SE技术允许云服务器在密文场景下进行安全检索，并将满足检索条件的密文数据返回给用户，最后由用户在本地将检索结果解密，从而获得自己需要的明文数据。

本文结合SM9算法构造基于身份的可搜索加密方案。根据非对称双线性对的特性，同时结合SM9加密算法的密钥形式，设计相应的索引生成算法、陷门生成算法和服务器检索匹配算法。基于可证明安全理论，验证该方案在随机谕言模型下满足密文不可区分性和陷门不可区分性。

1 相关工作

文献[1]首次提出对称可搜索加密（Symmetric Searchable Encryption，SSE）的概念，解决在密文环境下的搜索难题，实现了在对称密码体制下密文的搜索。文献[2]基于布隆过滤器（Bloom Filter，BF）^[3]设计满足安全索引的SSE方案，将检索的时间复杂度改进为与文档的数目呈线性关系。SSE的计算效率较高，适用于大部分第三方存储。文献[4]提出公钥可搜索加密（Public-key Encryption with Keyword Search，PEKS）方案，并基于文献[5]利用双线性对设计一个具体构造，适用于复杂的加密环境。PEKS不用在发送者与接收者之间建立安全信道，因其实用性较强，而得到快速发展，其中基于身份加密的可搜索加密减少了建立和维护公钥基础设施（Public Key Infrastructure，PKI）的开销，因此成为该领域的研究热点。

文献[6]提出带关键字搜索的基于身份加密（Identity-Based Encryption with Keyword Search，IBEKS）方案，并给出一般化的转换方法，将任意的选择明文攻击模式下不可区分安全且匿名的IBE方案转换为选择明文攻击模式下不可区分安全的PEKS方案。文献[7]提出一种基于身份的关键字搜索加密方案，不需要安全通道，但要求服务器是可信的。文献[8]提出带关键字搜索的阈值公钥加密（Threshold Public-key Encryption with Keyword Search，TPEKS）和带分布式私钥生成器的基于身份匿名加密。文献[9]提出模糊关键词检索，可以防范内部敌手和外部敌手的关键词猜测攻击。文献[10]提出指定服务器的带关键字搜索的基于身份加密方案，该方案不需要额外的安全信道。文献[11]对可搜索加密进行探讨和总结。文献[12]提出一种具有隐藏结构的可搜索公钥密文（Searchable Public-key Ciphertexts with Hidden Structure，SPCHS），提高了关键字搜索效率。文献[13]对加密数据的关键字搜索技术进行研究，并对他们的效率和安全性进行分析。文献[14]提出基于公钥并且带身份验证功能的PEAKS方案。文献[15]结合格理论提出一种基于身份的可搜索加密方案，可以抵抗量子计算机的攻击。文献[16]设计基于身份的关键词可搜索加密的广播加密方案，以防范内部敌手的攻击。文献[17]提出基于身份的指定服务器用于加密邮件的可搜索认证加密方案。文献[18]提出支持代理重加密的基于身份可搜索加密方案，支持搜索权限的高效共享。文献[19]提出基于身份的动态可搜索加密方案，可以删除指定身份的文件。文献[20]提出在电子邮件系统中指定服务器的关键字搜索加密方案。文献[21]提出一种基于生物识别身份的多关键字搜索（Biometric Identity-Based Multi-Keyword Search，BIBMKS）机制。文献[22]提出身份认证权威辅助的基于身份可搜索加密，在保持效率和安全性的同时，减少存储空间的开销。

上述方案为达到一定的安全级别，多是基于安全参数较大的对称双线性对，且在方案中多次使用双线性对运算，导致方案的计算效率降低。因此，通过优化方案设计，提高可搜索加密方案的检索效率和安全性成为研究热点。

从国家信息安全方面考虑，发展我国自己的加密算法势在必行。2016年，基于身份的SM9密码算法为国家商用密码行业标准（GM/T 0044—2016），并于2018年11月被纳入国际标准。SM9密码算法的密钥长度为256 bit，采用运算速度快、安全性能高的R-ate双线性对^[23]，可以有效减少Miller算法循环次数，提高计算效率。近年来，SM9密码算法作为基于身份的密码算法，受到越来越多的关注。

SM9密码算法使用安全参数较小的非对称双线性对，用户的公私钥分别在两个循环群中产生，而现有的可搜索加密方案大多通过安全参数较大的对称双线性对来实现，计算效率相对较低^[24]。由于用户密钥的形式不同，因此现有的可搜索加密方案并不能很好地与SM9密码算法相结合。

SM9密码算法在邮件系统、数据安全传输协议、物联网安全平台等场景中都有重要的应用，但由于缺少适应性强的可搜索加密方案，用户难以对这些加密数据进行检索，导致这些系统中的加密数据可用性较低。此外，通过为每个用户提供一对额外的密钥，以实现可搜索加密，但繁琐的操作流程会给用户的使用带来不便。为解决该问题，结合以上对SM9密码算法的分析，本文设计基于SM9密码算法的可搜索加密（SM9-based Searchable Encryption，SM9SE）方案。方案中用户的公私钥对分别在不同的子群中生成，其形式与SM9密码算法的密钥对一致，因此用户可以用同一对密钥完成数据的加解密和密文检索操作，并且使用系统参数相对较小的非对称双线性对运算，从而提高计算效率。

2 基础知识 2.1 双线性对

假设$ n $为正整数，$ ({G}_{1}, +) $和$ ({G}_{2}, +) $是两个$ n $阶加法循环群，其零元分别记作$ {O}_{1} $和$ {O}_{2} $。又设$ ({G}_{T}, g) $为$ n $阶乘法循环群，其单位元记为$ {1}_{T} $。假设在群$ {G}_{1} $，$ {G}_{2} $，$ {G}_{T} $上计算离散对数是困难的。

定义1  如果一个二元函数$ \widehat{e}:（{G}_{1}\cdot {G}_{2}）\to {G}_{T} $，满足双线性和非退化性。

双线性是对$ \forall {P}_{1}\mathrm{、}{P}_{2}\in {G}_{1} $，$ Q\in {G}_{2} $，都有$ \widehat{e}({P}_{1}+{P}_{2}, Q)=\widehat{e}({P}_{1}, Q)\cdot \widehat{e}({P}_{2}, Q) $成立，对$ \forall P\in {G}_{1} $，$ {Q}_{1}\mathrm{、}{Q}_{2}\in $ $ {G}_{2} $，都有$ \widehat{e}(P, {Q}_{1}+{Q}_{2})=\widehat{e}(P, {Q}_{1})\cdot \widehat{e}(P, {Q}_{2}) $成立。

非退化性是对$ \forall P\in {G}_{1} $，$ P\ne {O}_{1} $，$ \exists Q\in {G}_{2} $，使得$ \widehat{e}(P, Q)\ne {1}_{T} $，$ \forall Q\in {G}_{2} $，$ Q\ne {O}_{2} $，$ \exists P\in {G}_{1} $，使得$ \widehat{e}(P, Q)\ne {1}_{T} $，则称二元函数$ \widehat{e} $为双线性对。

2.2 基于双线性对的困难性问题及假设

双线性DH（DBDH）问题判定：在一个双线性映射$ \widehat{e}:({G}_{1}\cdot {G}_{2})\to {G}_{T} $中，若$ {P}_{1}\in {G}_{1} $，$ {P}_{2}\in {G}_{2} $，$ Z\in {G}_{T} $，对于给定的元组$ Y=({P}_{1}, [a]{P}_{1}, [b]{P}_{1}, {P}_{2}, [b]{P}_{2}, [c]{P}_{2}, Z) $，以及$ \beta \in \left\{\mathrm{0, 1}\right\} $，若$ Z=\widehat{e}({P}_{1}, {P}_{2}{)}^{abc} $，则令$ \beta =0 $，否则令$ \beta =1 $，判定$ \beta $的值，其中a、b、c为未知的整数。

DBDH假设：对于任何一个概率多项式时间敌手A，解决DBDH问题的概率都是可忽略的，即$ \mathrm{P}\mathrm{r}[0\leftarrow A(Y\left)\left|\beta =0\right.\right]-\mathrm{P}\mathrm{r}[0\leftarrow A(Y\left)\left|\beta =1\right.\right] $是可忽略的。

3 方案构造与安全模型 3.1 方案构造

本文方案使用的椭圆曲线及曲线参数与SM9加密算法中所使用的参数一致。

本文SM9SE方案由系统参数初始化算法、密钥生成算法、索引生成算法、陷门生成算法和检索匹配算法构成。

1）系统参数初始化算法$ \mathrm{S}\mathrm{y}\mathrm{s}\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}\left(\lambda \right) $，输入安全参数$ \lambda $以生成一个基于循环群上的双线性对映射$ \widehat{e}:({G}_{1}\cdot {G}_{2})\to {G}_{T} $，其中群$ {G}_{1} $、$ {G}_{2} $和$ {G}_{T} $的阶为大素数$ q $。PKG随机选择整数$ s\in [1, q-1] $作为系统主密钥保密存储，然后计算系统公钥$ {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}=s{P}_{1} $，$ {P}_{1} $为循环群$ {G}_{1} $的生成元，$ {P}_{2} $为循环群$ {G}_{2} $的生成元。此外，PKG选择$ {H}_{1}:{\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\to {Z}_{q}^{\mathrm{*}} $，$ {H}_{2}:{\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}}\to {Z}_{q}^{\mathrm{*}} $，$ {H}_{3}:{G}_{T}\to {\left\{\mathrm{0, 1}\right\}}^{\mathrm{*}} $三个哈希函数。系统主密钥对为$ (s, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}) $，系统公共参数为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}=({G}_{1}, {G}_{2}, {G}_{T}, {P}_{1}, {P}_{2}, \widehat{e}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, q, {H}_{1}, {H}_{2}, {H}_{3}) $。

2）密钥生成算法$ \mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{I}\mathrm{D}, s) $，对于用户A的唯一身份标识$ \mathrm{I}{\mathrm{D}}_{\mathrm{A}} $，以及系统主私钥$ s $，PKG在有限域$ {F}_{N} $上计算$ {t}_{1}={H}_{1}\left(\mathrm{I}{\mathrm{D}}_{\mathrm{A}}\right)+s $。若$ {t}_{1}=0 $则重新计算系统主密钥并更新已有用户的私钥，否则计算$ {t}_{2}=s\times {t}_{1}^{-1} $。用户私钥$ {d}_{\mathrm{A}}=\left[{t}_{2}\right]{P}_{2} $，用户公钥的计算方法为$ {Q}_{\mathrm{A}}=\left[{H}_{1}\right(\mathrm{I}{\mathrm{D}}_{\mathrm{A}}\left)\right]{P}_{1}+{P}_{\mathrm{p}\mathrm{u}\mathrm{b}}=\left[{t}_{1}\right]{P}_{1} $。

3）索引生成算法$ \mathrm{B}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}(\mathrm{I}{\mathrm{D}}_{\mathrm{R}}, w) $，对于接收者R的唯一身份标识$ \mathrm{I}{\mathrm{D}}_{\mathrm{R}} $以及关键字$ w $。该算法随机选择$ r\in [1, q-1] $，计算并生成关键字对应的密文索引$ I=({I}_{1}, {I}_{2}, {I}_{3}) $，并将其发送给服务器。其中$ {I}_{1}=\left[r\right]{Q}_{\mathrm{R}} $，$ {I}_{2}=\left[r\right]{P}_{2} $，$ {I}_{3}={H}_{3}\left(\widehat{e}\right({H}_{2}\left(w\right)\cdot {I}_{2}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}\left)\right) $。

4）陷门生成算法$ \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{d}\mathrm{o}\mathrm{o}\mathrm{r}({w}', {d}_{\mathrm{R}}) $，文件接收者R运行该算法以生成检索陷门，输入要搜索的关键字$ {w}' $和其私钥$ {d}_{\mathrm{R}} $。该算法选择随机数$ t\in [1, q-1] $，然后计算陷门信息$ T=({T}_{1}, {T}_{2}) $，并将其发送给服务器，其中$ {T}_{1}=\left[t\right]{P}_{\mathrm{p}\mathrm{u}\mathrm{b}} $，$ {T}_{2}=\left[{H}_{2}\right({w}')-t]\cdot {d}_{\mathrm{R}} $，并且$ {H}_{2}\left({w}'\right)-t\ne 0 $，否则重新选取$ t $。

5）检索匹配算法$ \mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}(I, T) $，由服务器执行，给定安全密文索引$ I=({I}_{1}, {I}_{2}, {I}_{3}) $和陷门$ T=({T}_{1}, {T}_{2}) $，服务器执行该算法来判断接收到的陷门信息与其存储的关键词密文索引信息是否能正确匹配。如果匹配，则返回密文文件，若$ {I}_{3}={H}_{3}\left(\widehat{e}\right({T}_{2}, {I}_{1})\cdot \widehat{e}({T}_{1}, {I}_{2}\left)\right) $，则匹配成功。

3.2 安全模型

本节通过以下两个游戏来刻画本文方案在面对内部敌手的离线关键词猜测攻击（Keyword Guessing Attack，KGA）时的语义安全。由于内部敌手所获取的信息大于等于任意外部敌手所能获取的信息，因此不再考虑外部敌手。这两个游戏均由敌手A和挑战者B交互完成。游戏1是密文不可区分性游戏，游戏2是陷门不可区分性游戏。

3.2.1 密文不可区分性游戏

在密文不可区分性游戏中，假设半诚实服务器就是敌手A，它会诚实执行用户预设的操作，但是会尝试获取用户数据的信息。密文不可区分性旨在防止敌手分辨出某个给定的密文是从两个选定的关键词（由敌手自己选定）中的哪一个加密而来，即密文不可区分性可以保证服务器在没有获得用户授权的情况下无法私自对密文进行检索操作。

1）初始化。挑战者B生成系统的公共参数$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s} $和主私钥$ s $，以及各个用户的私钥，然后将系统的公共参数$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s} $发送给敌手A。

2）询问阶段1。敌手A可以适应性地向如下的随机谕言机进行多项式时间次的询问，以获得用户的私钥、密文索引和陷门密文信息。其中，“适应性”是指敌手A每次的询问都会根据当前已知的信息来决定应该询问的信息。挑战者B运行随机谕言机，并按如下规则返回询问结果：（1）Hash谕言机$ {O}_{H} $，对于给定的输入值，给敌手A返回其哈希值；（2）密钥谕言机$ {O}_{E} $，对于指定的用户，给敌手A返回该用户的密钥；（3）索引谕言机$ {O}_{C} $，给定关键词及接收方$ \mathrm{I}\mathrm{D} $，给敌手A返回其对应的密文索引；（4）陷门谕言机$ {O}_{T} $，给定一个关键词，计算并给敌手A返回其对应的陷门。

3）挑战。敌手A向挑战者B声明一个发送者的身份标识$ \mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，并将其作为挑战，然后选择两个长度相等的挑战关键字$ ({w}_{0}, {w}_{1}) $。挑战者B随机选择$ \beta \in \left\{\mathrm{0, 1}\right\} $，根据选择结果，运行索引生成算法$ \mathrm{B}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}(\mathrm{I}{\mathrm{D}}_{\mathrm{R}}, {w}_{\beta }) $，生成密文索引$ {I}_{\beta } $，并将其发送给敌手A。

4）询问阶段2。敌手A继续向各个随机谕言机进行询问，该阶段的询问与询问阶段1相同。

5）猜测。敌手A输出一个字节$ {\beta }'\in \left\{\mathrm{0, 1}\right\} $作为对关键字$ {w}_{\beta } $的猜测，假如$ \beta ={\beta }' $，则敌手A赢得游戏。前提是敌手没有询问过$ \mathrm{I}{\mathrm{D}}^{\mathrm{*}} $对应的私钥，也没有询问过与身份$ \mathrm{I}{\mathrm{D}}^{\mathrm{*}} $对应的关键字$ {w}_{0} $和$ {w}_{1} $的陷门密文信息及索引密文信息。

敌手A在该游戏中的优势定义为：

$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right)=\left|\mathrm{P}\mathrm{r}[\beta ={\beta }']-\frac{1}{2}\right| $

若敌手A赢得游戏的优势可以忽略，即$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right)\le \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}\left(\lambda \right) $，其中$ \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}\left(\lambda \right) $为可忽略函数，则该方案满足密文不可区分性。

3.2.2 陷门不可区分性游戏

与游戏1相似，游戏2仍然假设半诚实服务器是敌手A。陷门不可区分性旨在防止敌手A从一个给定的陷门信息中获取其对应关键词的信息。陷门不可区分性保证即使是服务器本身，也无法生成针对某接收者的有效密文。

1）初始化。与游戏1的初始化相同。

2）询问阶段1。与游戏1的询间阶段1相同。

3）挑战。敌手A向挑战者B声明一个发送者的身份标识$ \mathrm{I}{\mathrm{D}}^{\mathrm{*}} $作为挑战，并选择两个长度相等的挑战关键字$ ({w}_{0}, {w}_{1}) $，挑战者B随机选择$ \beta \in （\mathrm{0, 1}） $，并根据选择结果，运行陷门生成算法$ \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{d}\mathrm{o}\mathrm{o}\mathrm{r}({w}_{\beta }, {d}_{\mathrm{R}}) $，生成陷门$ {T}_{\beta } $，并将其发送给敌手A。

4）询问阶段2。与游戏1中的询问阶段2相同。

5）猜测。敌手A输出一个字节$ {\beta }'\in （\mathrm{0, 1}） $，作为对关键字$ {w}_{\beta } $的猜测，假如$ \beta ={\beta }' $，则敌手A赢得游戏。限制条件与游戏1相同。

敌手A在该游戏中的优势定义为：

$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{T}\left(\lambda \right)=\left|\mathrm{P}\mathrm{r}[\beta ={\beta }']-\frac{1}{2}\right| $

若敌手A赢得游戏的优势可以忽略，即$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{T}\left(\lambda \right)\le \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}\left(\lambda \right) $，则该方案满足陷门不可区分性。

4 方案分析与证明 4.1 正确性分析

本文根据双线性对的性质来验证本文方案的正确性。

定义2  假设在本文方案中所有密文索引和陷门都是按照正确的步骤生成，且在传输过程中未遭到恶意攻击，数据没有被篡改。方案正确性是指当用户向服务器发送包含关键词$ {w}' $的检索陷门时，服务器运行检索匹配算法，以正确匹配到包含该关键词的密文索引，从而返回包含该关键词的密文文件。

假设用户$ \mathrm{I}{\mathrm{D}}' $的公私钥对为$ {Q}'=\left[{t}_{1}'\right]{P}_{1}, {d}'=\left[{t}_{2}'\right]{P}_{2} $，用户$ \mathrm{I}{\mathrm{D}}' $为关键词$ {w}' $生成的陷门$ {T}'({T}_{1}'=[{t}']{P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, {{T}_{2}}^{\mathrm{\text{'}}}=[{H}_{2}\left({w}'\right)-{t}']\cdot {d}') $。当服务器运行检索匹配算法并逐个对比密文索引，由双线性对的性质可知：

$ \begin{array}{l}{H}_{3}\left(\widehat{e}\right({T}_{2}', {I}_{1})\cdot \widehat{e}({T}_{1}', {I}_{2}\left)\right)=\\ {H}_{3}\left(\widehat{e}\right(\left[{H}_{2}\right({w}')-{t}']\cdot {d}', \left[r\right]{Q}')\cdot \widehat{e}(\left[{t}'\right]{P}_{\mathrm{p}\mathrm{u}\mathrm{b}}, \left[r\right]{P}_{2}\left)\right)=\\ {H}_{3}\left(\widehat{e}\right({H}_{2}\left({w}'\right)\cdot \left[{t}_{2}'\right]{P}_{2}, \left[r\right]\left[{t}_{1}'\right]{P}_{1})\cdot \widehat{e}({P}_{1}, {P}_{2}{)}^{-{t}'sr}\cdot \\ \widehat{e}({P}_{1}, {P}_{2}{)}^{{t}'sr})={H}_{3}\left(\widehat{e}\right({H}_{2}\left({w}'\right)\cdot {P}_{2}, {P}_{1}{)}^{r{t}_{1}'{t}_{2}'})=\\ {H}_{3}\left(\widehat{e}\right({H}_{2}\left({w}'\right)\cdot {P}_{2}, {P}_{1}{)}^{rs})=\\ {H}_{3}\left(\widehat{e}\right({H}_{2}\left({w}'\right)\cdot \left[r\right]{P}_{2}, \left[s\right]{P}_{1}\left)\right)={H}_{3}\left(\widehat{e}\right({H}_{2}\left({w}'\right)\cdot {I}_{2}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}\left)\right)\end{array} $

如果$ w={w}' $，则有：

$ {H}_{3}\left(\widehat{e}\right({T}_{2}', {I}_{1})\cdot \widehat{e}({T}_{1}', {I}_{2}\left)\right)={H}_{3}\left(\widehat{e}\right({H}_{2}\left(w\right)\cdot {I}_{2}, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}\left)\right)={I}_{3} $

则服务器可以正确匹配到密文索引，正确性成立。

4.2 安全性证明

本文SM9SE方案在随机谕言模型下满足适应性密文不可区分性以及适应性陷门不可区分性。具体证明过程如下：

定理1  若敌手A能以优势$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right) $赢得密文不可区分性游戏（最多进行$ {q}_{{H}_{1}} $次$ {H}_{1} $询问），则存在一个挑战者B能利用敌手A以$ [1/(2\cdot {q}_{{H}_{1}}\left)\right]\cdot \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right) $的优势解决DBDH问题。

证明  若挑战者B解决一个DBDH实例元组$ Y= $ $ ({G}_{1}, {G}_{2}, {G}_{T}, \widehat{e}, q, {P}_{1}, [x]{P}_{1}, [y]{P}_{1}, {P}_{2}, [y]{P}_{2}, [z]{P}_{2}, Z) $，则挑战者B按如下过程与敌手A进行密文不可区分性游戏。

1）初始化。挑战者B选择随机数$ x\in {Z}_{q}^{\mathrm{*}} $，将系统参数设为$ \mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}=({G}_{1}, {G}_{2}, {G}_{T}, {P}_{1}, {P}_{2}, \widehat{e}, q, {P}_{\mathrm{p}\mathrm{u}\mathrm{b}}=[x\left]{P}_{1}\right) $。

2）询问阶段1。敌手A适应性地询问由挑战者B模拟的随机谕言机，假设敌手A不会对同一个随机谕言机进行相同询问，并且在向$ {H}_{1} $询问$ \mathrm{I}\mathrm{D} $值之前不会对$ \mathrm{I}\mathrm{D} $做任何计算。随机谕言机主要有以下6个：

（1）Hash谕言机$ {O}_{{H}_{1}} $：挑战者B建立并维护一张初始为空的表$ {L}_{{H}_{1}}= < \cdot , \cdot > $，设敌手A最多进行$ {q}_{{H}_{1}} $次询问，挑战者B随机选择$ i\in \{\mathrm{1, 2}, \cdots , {q}_{{H}_{1}}\} $，并猜测敌手A的第$ i $次询问正是挑战的$ \mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，如果敌手A询问$ \mathrm{I}\mathrm{D} $的哈希值，挑战者B按以下情况将值返回，若这是第$ i $次询问，即$ \mathrm{I}\mathrm{D}=\mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，随机返回值$ h\in {Z}_{q}^{\mathrm{*}} $，并将$ < \mathrm{I}\mathrm{D}, h, \left[y\right]{P}_{1}, \left[z\right]{P}_{2}, \perp > $添加到表$ {L}_{{H}_{1}} $中，否则随机返回$ {h}_{1}\in {Z}_{q}^{\mathrm{*}} $，并且在表中添加$ < \mathrm{I}\mathrm{D}, {h}_{1}, [{h}_{1}+x]{P}_{1}=\left[{t}_{1}\right]{P}_{1}, \left[x/({h}_{1}+x)\right]{P}_{2}=\left[{t}_{2}\right]{P}_{2}, {h}_{1} > $。

（2）Hash谕言机$ {O}_{{H}_{2}} $：对于关键词$ w $，若$ \mathrm{I}\mathrm{D}=\mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，则返回x，否则随机选择$ {h}_{2}\in {Z}_{q}^{\mathrm{*}} $作为$ {H}_{2}\left(w\right) $的值输出。

（3）Hash谕言机$ {O}_{{H}_{3}} $：对于群$ {G}_{T} $中的元素，随机选择任意长度的随机位串作为$ {H}_{3}(\cdot ) $的值输出。

（4）密钥谕言机$ {O}_{E} $：对于$ \mathrm{I}\mathrm{D} $，若$ \mathrm{I}\mathrm{D}=\mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，中断模拟，并随机输出字节$ {\beta }' $，否则查找表$ {L}_{{H}_{1}} $，并返回$ {d}_{\mathrm{I}\mathrm{D}}=\left[{t}_{2}\right]{P}_{2} $，$ {Q}_{\mathrm{I}\mathrm{D}}=\left[{t}_{1}\right]{P}_{1} $。

（5）索引谕言机$ {O}_{C} $：对于$ (\mathrm{I}{\mathrm{D}}_{\mathrm{R}}, w) $，随机选择$ r\in {Z}_{q}^{\mathrm{*}} $，并按以下情况计算索引$ I=({I}_{1}, {I}_{2}, {I}_{3}) $，若$ \mathrm{I}\mathrm{D}=\mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，则$ {I}_{1}=\left[r\right]{P}_{1} $，$ {I}_{2}=\left[r\right]{P}_{2} $，$ {I}_{3}={H}_{3}\left({Z}^{r}\right) $；否则查找表$ {L}_{{H}_{1}} $并计算$ {I}_{1}=\left[r\right]\left[{t}_{1}\right]{P}_{1} $，$ {I}_{2}=\left[r\right]{P}_{2} $，以及$ {I}_{3}={H}_{3}\left(\widehat{e}\right({H}_{2}\left(w\right)\cdot {I}_{2}, \left[x\right]{P}_{1}\left)\right) $。

（6）陷门谕言机$ {O}_{T} $：随机选择$ t\in {Z}_{q}^{\mathrm{*}} $，并按以下情况计算陷门$ T=({T}_{1}, {T}_{2}) $，若$ \mathrm{I}\mathrm{D}=\mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，则$ {T}_{1}=\left[t\right]\left[y\right]{P}_{1} $，$ {T}_{2}=\left[{H}_{2}\right(w)-t]\left[y\right]{P}_{2} $；否则查找表$ {L}_{{H}_{1}} $并计算$ {T}_{1}=\left[t\right]{P}_{\mathrm{p}\mathrm{u}\mathrm{b}} $，$ {T}_{2}=\left[{H}_{2}\right(w)-t]\left[{t}_{2}\right]{P}_{2} $。

3）挑战。敌手A提交两个挑战关键词$ {w}_{0}\mathrm{、}{w}_{1} $以及要挑战的$ \mathrm{I}{\mathrm{D}}^{\mathrm{*}} $，挑战者B随机选择字节$ \widehat{\beta }\in \left\{\mathrm{0, 1}\right\} $和元素$ r\in {Z}_{q}^{\mathrm{*}} $，返回密文索引$ {I}^{\mathrm{*}}=({I}_{1}^{\mathrm{*}}, {I}_{2}^{\mathrm{*}}, {I}_{3}^{\mathrm{*}}) $，其中，$ {I}_{1}^{\mathrm{*}}=\left[r\right]{P}_{1} $，$ {I}_{2}^{\mathrm{*}}=\left[r\right]{P}_{2} $，$ {I}_{3}^{\mathrm{*}}={H}_{3}\left(\widehat{e}\right({H}_{2}\left(w\right)\cdot {I}_{2}, \left[x\right]{P}_{1}\left)\right) $。

4）询问阶段2。与询问阶段1相同。

5）猜测。敌手A输出猜测的字节$ {\widehat{\beta }}' $，如果$ {\widehat{\beta }}'=\widehat{\beta } $，挑战者B输出$ {\beta }'=0 $，否则挑战者B输出$ {\beta }'=1 $。

若挑战者B对挑战身份的猜测不正确，则模拟中断，将此事件表示为$ \mathrm{F} $。若挑战者B模拟中断，则挑战者B随机输出字节$ {\beta }'=\beta $的概率为$ 1/2 $。由于挑战者B的猜测是随机的，因此F不发生的概率为$ 1/{q}_{{H}_{1}} $，即$ \mathrm{P}\mathrm{r}\left[\stackrel{-}{\mathrm{F}}\right]=1/{q}_{{H}_{1}} $。

假设挑战者B模拟不中断，若$ Z=\widehat{e}({P}_{1}, {P}_{2}{)}^{xyz} $，则挑战者B的模拟和敌手A在真实攻击中的视图相同，此时敌手A赢得游戏的概率为$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right)+1/2 $。若$ Z $是$ {G}_{T} $中的随机元素，由于挑战者B的模拟是完备的，因此挑战密文会将字节$ \widehat{\beta } $完全隐藏，则敌手A赢得游戏的概率最多为$ 1/2 $。因此，挑战者B在解决DBDH问题中的优势可表示为：

$ \begin{array}{l}\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{B}}^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}\left(\lambda \right)=\\ \left|\mathrm{P}\mathrm{r}[{\beta }'=\beta \left|\mathrm{F}]\cdot \mathrm{P}\mathrm{r}[\mathrm{F}]\right.+\mathrm{P}\mathrm{r}[{\beta }'=\beta \left|\stackrel{-}{\mathrm{F}}]\cdot \mathrm{P}\mathrm{r}[\stackrel{-}{\mathrm{F}}]-1/2\right.\right|=\\ \left|\frac{1}{2}\cdot (1-\mathrm{P}\mathrm{r}[\stackrel{-}{\mathrm{F}}\left]\right)\right.+\left(\mathrm{P}\mathrm{r}\right[{\beta }'=0\left|\stackrel{-}{\mathrm{F}}\wedge \beta =0\right.]\cdot \mathrm{P}\mathrm{r}[\beta =0]+\\ \mathrm{P}\mathrm{r}[{\beta }'=1\left|\stackrel{-}{\mathrm{F}}\right.\wedge \beta =1]\cdot \mathrm{P}\mathrm{r}[\beta =1])\cdot \mathrm{P}\mathrm{r}[\stackrel{-}{\mathrm{F}}]\left.-\frac{1}{2}\right|\ge \\ \left|\frac{1}{2}\right.\cdot (1-\mathrm{P}\mathrm{r}[\stackrel{-}{\mathrm{F}}\left]\right)+\mathrm{P}\mathrm{r}\left[\stackrel{-}{\mathrm{F}}\right]\cdot \left(\right(\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right)+\frac{1}{2})\cdot \frac{1}{2}+\frac{1}{4})\left.-\frac{1}{2}\right|=\\ \frac{1}{2}\cdot \mathrm{P}\mathrm{r}\left[\stackrel{-}{\mathrm{F}}\right]\cdot \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right)=\frac{1}{2{q}_{{H}_{1}}}\cdot \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right)\end{array} $

若$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{C}\left(\lambda \right) $不可忽略，则$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{B}}^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}\left(\lambda \right) $也不可忽略，即挑战者B能以不可忽略的优势解决DBDH问题，与DBDH假设矛盾。因此，敌手A无法以不可忽略的优势赢得密文不可区分性游戏。

定理2  若敌手A能以优势$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{T}\left(\lambda \right) $赢得陷门不可区分性游戏（最多进行$ {q}_{{H}_{1}} $次$ {H}_{1} $询问），则存在一个挑战者B能利用敌手A以$ [1/(2\times {q}_{{H}_{1}}\left)\right]\times \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}^{T}\left(\lambda \right) $的优势解决DBDH问题。

陷门不可区分性的证明与密文不可区分性的证明相似。陷门不可区分性只是在挑战阶段挑战者B返回陷门$ {T}^{\mathrm{*}}=({T}_{1}^{\mathrm{*}}, {T}_{2}^{\mathrm{*}}) $。首先随机选择$ t\in {Z}_{q}^{\mathrm{*}} $，然后计算$ {T}_{1}^{\mathrm{*}}=\left[t\right]\left[y\right]{P}_{1} $，$ {T}_{2}^{\mathrm{*}}=\left[{H}_{2}\right(w)-t]\left[y\right]{P}_{2} $。

定理3  若一个敌手$ {\mathrm{A}}_{1} $能以不可忽略的优势$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{{\mathrm{A}}_{1}}^{\mathrm{K}\mathrm{G}\mathrm{A}}\left(\lambda \right) $对SM9SE方案进行离线关键词猜测攻击，则存在另一个敌手$ {\mathrm{A}}_{2} $能以$ \frac{1}{2}+\frac{1}{2}\times \mathrm{A}\mathrm{d}{\mathrm{v}}_{{\mathrm{A}}_{1}}^{\mathrm{K}\mathrm{G}\mathrm{A}}\left(\lambda \right) $的优势赢得密文不可区分性游戏。

证明  当敌手$ {\mathrm{A}}_{2} $和挑战者B进行密文不可区分性游戏时，在挑战阶段，敌手$ {\mathrm{A}}_{2} $可将挑战者B返回的挑战密文发送给敌手$ {\mathrm{A}}_{1} $，若敌手$ {\mathrm{A}}_{1} $猜测的结果为敌手$ {\mathrm{A}}_{2} $挑选的关键词之一，则敌手$ {\mathrm{A}}_{2} $向挑战者B输出对应的结果作为猜测，否则随机输出猜测结果。可知敌手$ {\mathrm{A}}_{2} $的优势为：

$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{{\mathrm{A}}_{2}}^{C}=\frac{1}{2}+\frac{1}{2}\cdot \mathrm{A}\mathrm{d}{\mathrm{v}}_{{\mathrm{A}}_{1}}^{\mathrm{K}\mathrm{G}\mathrm{A}}\left(\lambda \right) $

该证明与定理1矛盾。因此，如果DBDH假设成立，则不存在敌手能以不可忽略的优势对SM9SE方案发起离线关键词猜测攻击。

5 仿真实验与分析 5.1 效率分析

本文将SM9SE方案与其他现有的基于身份可搜索加密方案进行对比分析。本文在同一标准下将EdIBEKS方案^[10]、PEAKS方案^[14]以及dIBAEKS方案^[17]进行效率分析。基于文献[25]中的定义，表 1定义了若干不同符号及其换算方法。

EdIBEKS方案、PEAKS方案以及dIBAEKS方案所有的运算都建立在对称双线性对上，使用的曲线为嵌入度2，以1 024 bit的大素数$ p $为阶的超奇异椭圆曲线$ E\left({F}_{p}\right):{y}^{2}={x}^{3}+x $。本文方案的运算建立在非对称双线性对上，使用的曲线为嵌入度12，阶为256 bit的大素数$ p $的BN曲线$ E:{y}^{2}={x}^{3}+5 $。以上选择参数能够确保所有方案都可以实现与2 048 bit的RSA密钥相当的安全级别。表 2表示不同方案的安全性假设、安全级别及其参数大小，以及本文方案与其他基于身份可搜索加密方案中用户执行一次索引生成算法、陷门生成算法和服务器执行一次检索匹配算法所需要执行的操作，其中忽略了方案中都存在的哈希函数运算。当计算椭圆曲线上的双线性对时，曲线的嵌入次数越多，计算越复杂，因此安全性也更高。相比其他方案采用嵌入度为2的超奇异椭圆曲线，本文方案采用嵌入度为12的BN曲线，因此本文方案的安全性优于其他方案。由于BN曲线的双线性对具有友好性^[26]，在BN曲线上计算双线性对更加高效。从表 2可以看出，本文SM9SE方案在保证计算效率的前提下，采用更小的安全参数实现与其他方案同等的安全级别，并且在索引生成算法上的效率优于其他三个方案，在陷门生成算法上的效率优于PEAKS方案和dIBAEKS方案，与EdIBEKS方案持平，都需要一次双线性对运算。由于本文方案采用参数更小的BN曲线，因此计算效率会更高，检索匹配算法的效率优于EdIBEKS方案和dIBAEKS方案，与PEAKS方案持平，都需要两次双线性对运算和一次椭圆曲线标量点乘法运算。由于本文方案采用参数更小的BN曲线，因此计算效率会更高。因此，本文方案的总体性能优于其他方案。

5.2 仿真结果分析

本文对EdIBEKS、PEAKS、dIBAEKS和SM9SE方案进行仿真实验，在2.40 GHz的4核64位Intel^® Core^TMi5-10200H处理器、8 GB内存（RAM）、Windows 10操作系统的实验环境进行实验，以myeclipse 10作为实验平台、Java作为实验编程语言，对各方案的索引生成算法、陷门生成算法和匹配检索算法进行模拟运行。本文首先使用不同长度的关键词对各个方案进行模拟运行，以分析关键词长度对各方案效率的影响，然后分别抽取Enron邮件数据集中的部分数据和Kaggle邮件数据集中的部分数据作为测试输入，使用不同数量的关键词进行对比实验。关键词长度对各方案的算法运行时间的影响如图 1所示。

从图 1可以看出，关键词长度对各算法运行效率的影响较小（关键词长度影响哈希函数运行时间，但哈希运算速度极快），略受各算法所选择的随机数影响，但总体运行时间较为平稳。

图 2表示各个方案中索引生成算法的运行时间，其中横坐标是关键词的个数，纵坐标为建立索引所需要的时间。从图 2可以看出，SM9SE方案在索引生成算法上的运行效率优于其他三种方案。SM9SE方案生成一个密文索引的平均时间在8 ms左右，而其他方案的密文索引时间则在35~68 ms之间。因此，本文方案在索引生成算法上的效率相比其他三种方案提高了77%以上。

图 3表示在各个方案中陷门生成算法的运行时间对比，其中横坐标是关键词的个数，纵坐标为生成检索陷门所需要的时间。从图 3可以看出，SM9SE方案在陷门生成算法上的运行效率也优于其他三种方案。其他三种方案生成一个陷门的运行时间平均为30~53 ms之间，而SM9SE方案生成一个陷门的平均时间在25 ms左右，效率提高了16.67%以上。

图 4表示在各个方案中检索匹配算法所运行的时间，其中横坐标是密文索引的个数，纵坐标为所有密文索引的运行时间。从图 4可以看出：SM9SE方案单次检索匹配算法的平均运行时间为18 ms左右；dIBAEKS方案的单次检索匹配算法的平均运行时间为53 ms左右；PEAKS方案和EdIBEKS方案的单次检索匹配算法的平均运行时间在25~45 ms之间。因此，SM9SE方案的检索匹配算法运行效率相对其他三种方案提高了28%以上。

图 5表示在不同方案中各个算法的平均运行时间。从图 5可以看出，本文方案执行一次索引生成算法、陷门生成算法和检索匹配算法的全过程所需要的平均时间总和为52 ms，其他三种方案则在105~168 ms之间。相比其他三种方案，本文方案的总体效率提高了50.4%以上。

6 结束语

针对现有基于身份的可搜索加密方案计算效率低、与SM9密码算法难以结合等问题，本文提出一种基于SM9密码算法的可搜索加密方案。根据非对称双线性对的性质，结合SM9加密算法的密钥形式，设计索引生成算法、陷门生成算法和服务器检索匹配算法，并验证方案的正确性和安全性。该方案在随机谕言模型下满足适应性密文不可区分性和适应性陷门不可区分性。仿真结果表明，相比EdIBEKS、PEAKS、dIBAEKS方案，本文方案具有较高的计算效率，能够实现可搜索加密与国家商用密码算法SM9的结合，并扩展了SM9密码算法的应用。下一步将在本文方案中增加指定身份检索、身份验证等更灵活的功能，使其适用于较复杂的应用场景。此外，还将在安全索引中嵌入数据发送者的私钥，并在陷门中嵌入发送者的公钥，通过设计相应的匹配算法实现精确检索目标文件的功能。