云计算的快速发展带动了云存储的普及，越来越多的用户和企业选择将数据存储在云服务器中^[1]. 云服务器通常由不可信第三方维护和管理，存在诸多安全隐患. 如果将数据直接存储在云端，可能会使数据被未授权实体访问，从而导致隐私泄露. 一种保护数据隐私和实现安全数据共享的方式是采用公钥加密算法将数据加密后再存储到云服务器^[2]，但这种方式极大地阻碍了数据的可用性. 当用户对存储在云服务器的加密数据进行搜索时，最直接的方法是将所有加密数据下载到本地后执行解密再对明文信息进行搜索，显然这种方法极其繁琐且低效.

为了解决数据机密性和可搜索性之间的矛盾，Boneh等人^[3]提出了支持关键词检索的公钥加密的概念. 在PKEKS系统中，发送者利用接收者的公钥和关键词生成关键词密文，并附在对应的文件密文后上传到云服务器. 接收者可以利用自己的私钥和关键词生成陷门上传至云服务器，随后云服务器利用陷门对关键词密文执行检索以判断关键词密文是否包含陷门中嵌入的关键词. 由于在检测过程中云服务器无法获取密文对应的关键词信息以及接收者私钥. 大量的PKEKS方案被提出以进一步提升公钥可搜索加密的安全性^[4-5]、效率^[6-7]和功能^[8]. 尽管PKEKS支持对于密文的搜索功能，但其存在功能上的限制：无法对不同公钥加密的2条信息进行检索. 同时还存在着严重的安全隐患：关键词空间远小于密钥空间，攻击者可以借此实施关键词猜测攻击.

为了解决上述问题，Yang等人^[9]在2010年提出了支持等式测试的公钥加密（public-key encryption with equality test, PKEET）方案. PKEET允许任何用户对不同公钥加密生成的密文进行对比以判断其中是否包含相同的明文. 由于对比的密文空间远大于密钥空间，关键词猜测攻击无法对PKEET系统生效. 受Yang等人^[9]的启发，国内外学者围绕PKEET的授权测试^[10-11]、通用构造^[12]和应用场景（无证书^[13]、签密^[14]、异构^[15]）等展开大量研究，一系列具有等式测试功能的加密方案被陆续提出. 在传统支持等式测试的公钥加密方案中，公钥是一个不可读的字符串，需要公钥基础设施^[16]（public key infrastructure, PKI）系统来签发公钥证书以绑定用户的身份与公钥. 公钥证书包括用户的身份信息、权威机构的签名和各种参数，以结构化数据的形式存储. 这种复杂且昂贵的证书管理方式在实际应用场景中带来了棘手的证书管理问题. 基于此，Ma^[17]受标识密码体制思想启发^[18]，构造了支持等式测试的标识加密（identity-based encryption with equality test，IBEET）体制. 在IBEET中，用户的公钥根据其身份信息生成，而用户的私钥由私钥生成中心（private key generator，PKG）构建.

目前已有的IBEET方案虽然避免了证书管理的问题，却存在着严重的安全隐患：大部分IBEET方案都难以抵抗渗透攻击. 斯诺登事件表明^[19]，攻击者可以在正常使用条件下秘密设置后门以泄露用户隐私. 受此启发，Bellare 等人^[20]提出的算法篡改攻击 （algorithm-substitution attacks，ASA）表明攻击者可以非法占据用户的个人设备来篡改加密算法，从被篡改的密文中获取明文信息. 具体来说，Bellare 等人^[20]构建了颠覆加密（subverting encryption）框架，对ASA的受害者实施IV篡改攻击（IV-replacement attacks）和偏密文攻击（the biased-ciphertext attack）. 攻击者利用颠覆密钥篡改随机化输入IV，继而跟踪篡改密文以获取明文. 目前大量的无状态随机化密码算法被证明几乎无法抵抗这类ASA. 因此，一旦用户遭遇ASA，云服务器上的所有加密数据都有被泄露的风险. 考虑到ASA的危害性，密码逆向防火墙（cryptographic reverse firewalls，CRF）的概念由Mironov等人^[21]在斯诺登事件之后提出. CRF可以被认为是部署在用户与外部世界的一个实体，通过重随机化用户发送和接收的信息将其映射到与原始输出相同的空间中，达到抵抗隐私泄露的作用. CRF具有3个性质：维持功能性、保留安全性和抵抗渗透性. 到目前为止，CRF已被成功应用于密钥协商协议^[22]、基于属性的加密体制^[23]和基于签名的不经意电子信封^[24]. 将CRF部署在云服务器与用户之间，分别负责用户密文与陷门的重随机化. 由于用户输出的是重随机化结果，即便算法遭到篡改，用户隐私也不会泄露. 基于此，有必要为IBEET构建CRF.

另外，目前IBEET都是基于国外密码算法设计且存在计算与通信开销大的问题，还没有出现支持国产商用密码算法的高效等式测试方案. SM9作为一种具有效率优势的双线性对标识密码算法（identity-based cryptographic algorithm），可以良好地拓展至IBEET领域中. 2016年我国国家密码管理局正式发布SM9密码算法，其相关标准为“GM/T 0044—2016 SM9标识密码算法”. SM9标识密码算法主要包括4个部分：数字签名算法、密钥交换协议、密钥封装机制和标识加密算法. 其中SM9标识加密算法于2021年正式成为国标（ISO/IEC 18033-5:2015/AMD 1:2021）. 虽然SM9在密码技术和网络安全领域占据越来越重要的地位，但关于SM9在云环境安全下的研究却寥寥无几. 因此，为了实现我国密码算法国产自主，提高其在信息安全领域的核心竞争力，亟需推进国密算法在云计算场景中的研究应用. 基于此，本文提出了一种支持等式测试并具有密码逆向防火墙的SM9标识加密方案（SM9 identity-based encryption scheme with equality test and cryptographic reverse firewalls，SM9-IBEET-CRF）. 本文的贡献有3点：

1） 本文将SM9标识加密算法应用于等式测试这一密码学原语，提出了支持等式测试的SM9标识密码方案（SM9 identity-based encryption scheme with equality test，SM9-IBEET）. 利用SM9是标识密码算法这一性质，避免了传统等式测试算法中证书管理的问题. 与传统IBEET方案相比，具有更强的安全性和计算开销的优势. 同时，丰富国产商用密码算法在云计算领域的研究.

2） 解决传统IBEET体制难以抵抗渗透攻击的问题. 本文将CRF部署在用户与云服务器之间的上行信道，分别实现用户密文、陷门的重随机化. 攻击者即使非法占据用户设备，由于其输出结果要经过CRF的处理，无法造成明文信息泄露.

3） 本文实现了形式化的安全性证明. 严谨的安全性分析证明其满足选择密文攻击下的不可区分性（IND-CCA）和选择密文攻击下的单向性（OW-CCA）. CRF的设置使其具备抵抗算法篡改攻击的能力. 经过大量的实验仿真证明，SM9-IBEET-CRF在计算与通信开销上具有一定的优势，适用于云计算场景. 相关工作有：

1） 支持等式测试的公钥加密体制. 支持等式测试的公钥加密方案首先由Yang等人^[9]在2010年提出. 该方案允许任何用户对不同公钥加密的密文进行比较，解决了关键词检索公钥加密方案的局限性. 接下来，Tang^[25]为PKEET提出了具有细粒度的授权机制，以确保只有被授权的用户才有能力执行等式测试. 此外，Tang^[10]提出了混合粒度授权的支持等式测试的公钥加密方案（all-or-nothing PKE-ET，AoN-PKE-ET）来实现粗细粒度授权. 然而，在实际中云服务器与用户需要交互来授权，导致了方案的不可拓展性. 为应对这一挑战，Tang^[26]和Ma^[11]分别提出了带有灵活授权机制的等式测试方案，其基本思想是用户单独对云服务器进行授权. 为了解决PKEET中的密钥管理问题，Ma^[17]将标识加密体制集成到PKEET中，提出一种IBEET方案. Qu等人^[13]提出的无证书等式测试加密方案（certificateless-based encryption with equality test，CLEET），旨在同时避免密钥托管和证书管理的问题.Wang等人^[14]将签密的概念引入等式测试中，有效降低了计算和通信开销. Xiong等人^[15]提出的异构签密等式测试方案（heterogeneous signcryption scheme with equality test，HSC-ET），则实现了IBE与PKE的异构等式测试系统. 目前已有的PKEET体制难以抵抗渗透攻击.

2） 密码逆向防火墙. 斯诺登事件爆发后，为了保护用户隐私和维持密码方案安全性，Mironov等人^[21]提出CRF的概念. CRF位于用户计算机与外部世界之间，通过修改用户设备输入和输出，为受到篡改算法攻击的用户提供安全保护. 2016年，Dodis等人^[22]设计了一种具有逆向防火墙的消息传输协议，缩短公钥交换轮数至4轮. 同年，Chen等人^[24]基于可延展的平滑映射哈希函数（smooth projective Hash function，SPHF）为多个密码协议设计了CRF框架. 2018年，Ma等人^[23]将逆向防火墙的概念引入属性基加密体制，提出了一种基于密文在线/离线属性的加密算法. 2019年，Zhou等人^[27]提出具有逆向防火墙的标识加密体制（identity-based encryption with cryptographic reverse firewalls，IBE-CRF），为IBE设计了2种CRF方案. 目前还不存在具有逆向防火墙的PKEET方案.

1.   基础知识

1.1   非对称双线性对

给定3个循环群${G_1},{G_2}$,${G_{\mathrm{T}}}$，它们的阶均为素数$N$，${P_1}$为${G_1}$的生成元，${P_2}$为${G_2}$的生成元，存在非对称双线性对$e:{G_1} \times {G_2} \to {G_T}$，满足3个条件：

1） 双线性. 对任意$P \in {G_1},Q \in {G_2},a,b \in {\mathbb{Z}_N}$，有$e([a]P,[b]Q) = e{(P,Q)^{ab}}$.

2） 非退化性. $e({P_1},{P_2}) \ne 1$.

3） 可计算性. 对任意$P \in {G_1},Q \in {G_2},$存在有效的算法计算$e(P,Q)$.

1.2   BDH假设

BDH假设首先由Boneh等人^[28]在对称双线性配对中提出，然后被拓展到非对称双线性对中. 本文使用Boyen等人^[29]在非对称双线性对中推广的BDH假设.

1）BDH问题. 给定$({P_1},{P_2},[a]{P_1},[a]{P_2},[b]{P_i},[c]{P_j})$，其中$a,b,c \in \mathbb{Z}_N^*$，$i,j \in \{ 1,2\}$，计算$e{({P_1},{P_2})^{abc}}$是困难的.

2）BDH假设. 给定一个BDH问题实例，不存在一个PPT攻击者$\mathcal{A}$具有不可忽略的优势计算出$e{({P_1},{P_2})^{abc}}$. 其中$\mathcal{A}$的优势被定义为

1.3   密码逆向防火墙（CRF）

CRF位于用户计算机与外部实体之间，只能修改用户的输入输出消息. 对于用户而言，他们并不知道CRF的存在.

CRF是一种具有状态的算法$\mathcal{W}$，它以当前状态和消息作为输入，输出更新后的状态和消息. 对于初始状态为$\sigma$的参与方$P = (receive,next,output)$和逆向防火墙$\mathcal{W}$，它们的组成被定义为

当组成方$\mathcal{W}^\circ P$参与协议时，$\mathcal{W}$的状态被初始化为系统公开参数params，如果$\mathcal{W}$是与参与方P共同组成的，则我们称$\mathcal{W}$为参与方P的逆向防火墙.

显然，参与方P希望获得管理并部署多台防火墙的权力. 这种多个防火墙的组合$(\mathcal{W}^\circ \mathcal{W}^\circ … ^\circ \mathcal{W}^\circ P)$只会增强系统的安全性，而不会破坏其初始协议的功能.

定义1. CRF具有维持功能性. 对任意逆向防火墙$\mathcal{W}$与参与方P，令${\mathcal{W}^1}^\circ P{\text{ = }}\mathcal{W}^\circ P$，当任意多项式边界$k \geqslant 2$时，令${\mathcal{W}^k}^\circ P{\text{ = }}\mathcal{W}^\circ ({\mathcal{W}^{k - 1}}^\circ P{\text{)}}$. 在$k \geqslant 1$的协议$\mathcal{P}$中，如果${\mathcal{W}^k}^\circ P$维持了参与方${P_i}$的功能$\mathcal{F}$，也就是说当$\left( {{\mathcal{W}^k}^\circ {P_i}{\text{ = }}\mathcal{W}^\circ {P_i}} \right) \cap \left( {{\mathcal{F}_{\mathcal{W}^\circ {P_i}}} = {\mathcal{F}_{{P_i}}}} \right) = 1$时，CRF具有维持功能性.

定义2. CRF具有保留安全性. 对满足安全性$\mathcal{S}$，功能$\mathcal{F}$的协议$\mathcal{P}$与逆向防火墙$\mathcal{W}$：

1） 对于任意改变协议功能$\mathcal{F}$的PPT攻击者$P_\mathcal{A}^*$，如果协议${\mathcal{P}_{P \Rightarrow \mathcal{W}^\circ P_{\mathcal{A}}^*}}$仍满足安全性$\mathcal{S}$，则称CRF对于协议参与方P具有强保留安全性.

2） 对于任意不改变协议功能$\mathcal{F}$的PPT攻击者$\hat P$，如果协议${\mathcal{P}_{P \Rightarrow \mathcal{W}^\circ \hat P}}$仍满足安全性$\mathcal{S}$，则称CRF对于协议参与方P具有弱保留安全性.

当PPT攻击者$P_\mathcal{A}^*$破坏协议功能$\mathcal{F}$时，由于协议参与方$P$可以很快感知到这种破坏，在云计算场景中攻击效果较差，是一种罕见的攻击方式. 因此，本文主要证明CRF对于不破坏协议功能的ASA安全性.

定义3. CRF具有抵抗渗透性.CRF具有阻止参与方P对消息篡改泄露的能力. 使用Mironov等人^[21]定义的泄露游戏$LEAK(\mathcal{P},P,J,\mathcal{W},\lambda )$，如图1所示：$\mathcal{P}$代表密码协议，P为协议正常参与方，J代表被敌手控制的协议参与方，$\mathcal{W}$为逆向防火墙，$\lambda$表示系统参数.$P_\mathcal{A}^*,P_\mathcal{B}^*$代表被敌手控制的协议参与方，${\sigma _{P_\mathcal{B}^*}}$为协议运行后$P_\mathcal{B}^*$的状态，敌手在游戏LEAK中的优势被定义为

图  1  LEAK示意图

Figure  1.  Illustration of LEAK

下载: 全尺寸图片 幻灯片

1） 对于任意改变协议功能$\mathcal{F}$的PPT攻击者$P_\mathcal{A}^*$，其优势$Adv_{\mathcal{A}. \mathcal{W}}^{LEAK}(\lambda )$是可以忽略不计的，则称CRF对于协议参与方P具有强抵抗渗透性.

2） 对于任意不改变协议功能$\mathcal{F}$的PPT攻击者${\hat P_\mathcal{A}}$，其优势$Adv_{\mathcal{A}. \mathcal{W}}^{LEAK}(\lambda )$是可以忽略不计的，则称CRF对于协议参与方P具有弱抵抗渗透性.

与定义2相同，本文主要讨论CRF对于不破坏协议功能的ASA安全性.

2.   方案定义

本节我们给出了本文方案的系统模型SMP-IBEET-CRF、形式化定义，并且通过考虑3种不同的敌手来定义安全模型.

2.1   系统模型

系统模型如图2所示，在SM9-IBEET-CRF中，存在5种实体.

图  2  SM9-IBEET-CRF示意图

Figure  2.  Illustration of SM9-IBEET-CRF

下载: 全尺寸图片 幻灯片

1） 数据上传者. 生成密文并将其上传到云服务器的实体.

2） 数据接收者. 可以从云服务器下载密文并解密，或者可以委托云服务器执行等式测试的实体.

3） 云服务器. 存储密文，在收到用户请求后可以执行等式测试但无法解密的实体.

4） 密钥生成中心（KGC）. 为用户秘密地生成并且分配密钥的实体.

5） 密码逆向防火墙（CRF）. 部署在用户（数据上传者和数据接收者）与云服务器的上行信道中，重随机化用户密文与陷门，再发送给云服务器的实体.

KGC初始化系统，根据用户的身份来生成其私钥，并秘密传输给用户. 数据上传者计算接收者的公钥来生成密文，然后上传到云服务器. 密文在上传过程中会受到CRF的重随机化处理，而数据上传者并不知道有这个过程. 在任何时候，数据接收者都可以从云服务器下载密文，并使用KGC生成的私钥来解密数据. 当接收者想要测试其存储在云服务器的密文时，可以利用自己的私钥计算出陷门并将其发送给云服务器进行测试，但是并没有给云服务器提供解密的能力. 陷门在上传过程中会受到CRF的重随机化处理，而数据接收者不会知道有这个过程.

2.2   形式化定义

SM9-IBEET-CRF方案由8个算法组成.

1） 系统建立 Setup. 输入安全参数k，KGC 运行该算法并生成系统公开参数params和系统主密钥，包括消息空间.

2） 私钥提取 KeyExtract. 输入系统公开参数params、用户ID以及主私钥s，KGC 运行该算法生成用户身份所对应的私钥d.

3） 陷门生成 Trapdoor. 输入用户ID以及用户私钥d，输出对应的陷门$td$.

4） 加密 Encrypt. 输入明文M和用户ID，输出密文C.

5） 重随机化密文 ReEncrypt. 输入密文C，CRF运行该算法输出对应的重随机化密文$C'$.

6） 密文解密 Decrypt. 输入密文C、用户ID和用户私钥$d$，解密输出明文M.

7） 重随机化陷门 ReTrapdoor. 输入陷门td，CRF运行该算法输出对应的重随机化陷门$td'$.

8） 等式测试 Test. 分别输入$I{D_A}$对应的密文${C_A}$和陷门$t{d_A}$，$I{D_B}$对应的密文${C_B}$和陷门$t{d_B}$，云服务器执行等式测试，若${C_A}$和${C_B}$的内容为相同的明文，则输出1，否则输出0.

根据IBEET的安全模型，SM9-IBEET需要考虑3种类型的敌手.

1） Ⅰ型敌手. 这类敌手没有目标用户的陷门，不能执行等式测试，其目的是在2个挑战密文中做区分. 我们针对这种类型的敌手定义了IBE-IND-CCA安全游戏Game 1.

安全游戏Game 1中让${\mathcal{A}_1}$表示Ⅰ型敌手，挑战者$\mathcal{C}$与${\mathcal{A}_1}$按如下顺序进行游戏：

①系统建立 Setup.挑战者$\mathcal{C}$执行系统建立Setup算法生成系统参数params和主私钥对.$\mathcal{C}$保存主私钥对并将params发送给${\mathcal{A}_1}$.

② 阶段1. ${\mathcal{A}_1}$可以自适应地执行查询：

i）公钥查询. 当接收到身份为ID_i的公钥询问时，$\mathcal{C}$通过运用主私钥对计算，生成公钥${Q_i}$并发送给${\mathcal{A}_1}$.

ii）私钥查询. 当接收到身份为ID_i的公钥询问时，$\mathcal{C}$通过执行私钥提取算法KeyExtract生成私钥${d_i}$并发送给${\mathcal{A}_1}$.

iii）解密查询. 当接收到身份为ID_i以及密文$C$的密钥解密询问时，$\mathcal{C}$执行密文解密算法Decrypt生成明文M并返回给${\mathcal{A}_1}$.

③挑战. 敌手${\mathcal{A}_1}$将身份ID^*以及消息$M_0^*,M_1^*$（二者长度相同）发送给$\mathcal{C}$，且在阶段1，ID^*对应的私钥没有被询问到，则$\mathcal{C}$随机选取$\rho \in \{ 0,1\}$，并且计算${C^*} = Encrypt({M_\rho },{d^*},I{D^*})$并发送给${\mathcal{A}_1}$.

④阶段2. ${\mathcal{A}_1}$像在阶段1一样发出询问，但是ID^*对应的私钥以及密文${C^*}$不可以被询问到.

⑤ 猜测. ${\mathcal{A}_1}$输出$\rho ' \in \{ 0,1\}$.

定义4. 如果对于任意多项式时间攻击者${\mathcal{A}_1}$，在IND-CCA游戏中的优势$Ad{v}_{\text{SM9-IBEET,Type-І}}^{\text{IBE-IND-CCA}}({\mathcal{A}}_{1})=\left|2Pr\left[\rho = {\rho }^{\prime }\right] -1\right|$都是可忽略的，则SM9-IBEET方案是满足IBE-IND-CCA安全的.

2）Ⅱ型敌手. 这类敌手拥有目标用户密文的陷门，因此可以执行挑战密文的等式测试，其目的是为了揭示挑战密文对应的消息. 我们针对这种类型的敌手定义了IBE-OW-CCA安全游戏Game 2.

安全游戏Game 2中让${\mathcal{A}_2}$表示Ⅱ型敌手，挑战者$\mathcal{C}$与${\mathcal{A}_2}$按如下顺序进行游戏：

①系统建立 Setup. 挑战者$\mathcal{C}$执行系统建立Setup算法生成系统参数params和主私钥对. $\mathcal{C}$保存主私钥对并将params发送给${\mathcal{A}_2}$.

②阶段1.${\mathcal{A}_2}$可以自适应地执行查询：

i）公钥查询. 当接收到身份为ID_i的公钥询问时，$\mathcal{C}$通过运用主私钥对计算，生成公钥${Q_i}$并发送给${\mathcal{A}_2}$.

ii）私钥查询. 当接收到身份为ID_i的公钥询问时，$\mathcal{C}$通过执行私钥提取算法KeyExtract生成私钥${d_i}$并发送给${\mathcal{A}_2}$.

iii）陷门查询. 当接收到身份为ID_i的陷门询问时，$\mathcal{C}$通过执行陷门生成算法Trapdoor生成陷门$t{d_i}$并发送给${\mathcal{A}_2}$.

iv）解密查询. 当接收受到身份为ID_i以及密文$C$的密钥解密询问时，$\mathcal{C}$执行密文解密算法Decrypt生成明文M并返回给${\mathcal{A}_2}$.

③挑战. 敌手${\mathcal{A}_2}$将身份ID^*发送给$\mathcal{C}$，且在阶段1，ID^*对应的私钥没有被询问到. 则$\mathcal{C}$随机选取消息$M_{}^*$，计算${C^*} = Encrypt({M^*},{d^*},I{D^*})$并发送给${\mathcal{A}_2}$.

④阶段2. ${\mathcal{A}_2}$像在阶段1一样发出询问，但是ID^*对应的私钥、陷门以及密文${C^*}$不可以被询问到.

⑤猜测. ${\mathcal{A}_2}$输出$M'$.

定义5. 如果对于任意多项式时间攻击者${\mathcal{A}_2}$，在IBE-OW-CCA游戏中的优势$Ad{v}_{\text{SM9-IBEET,Type-П}}^{\text{IBE-OW-CCA}}({\mathcal{A}}_{2})=$ $\Big|Pr\Big[{M}^{*}= {M}^{\prime }\Big]\Big|$都是可忽略的，则SM9-IBEET方案是满足IBE-OW-CCA安全的.

为证明CRF的部署带来的ASA安全性，SM9-IBEET-CRF还需考虑Ⅲ型敌手.

3） Ⅲ型敌手. 其具备ASA能力，在保持算法功能不变的前提下，可以替换除了CRF重随机化以外的算法，然后对系统发起攻击. 针对这种类型的敌手，我们可以证明CRF的部署没有改变原SM9-IBEET的功能与安全性，同时增强了ASA安全性. 基于此，我们定义了ASA安全游戏Game 3.

安全游戏Game 3中让${\mathcal{A}_3}$表示Ⅲ型敌手，挑战者$\mathcal{C}$与${\mathcal{A}_3}$按如下顺序进行游戏.

① 篡改阶段.${\mathcal{A}_3}$选择一些篡改的算法Setup*，KeyExtract*，Encrypt*，Decrypt*，Trapdoor*，Test*发送给$\mathcal{C}$，$\mathcal{C}$收到后用篡改算法来替换自己的原始算法.

②系统建立 Setup.挑战者$\mathcal{C}$执行系统建立Setup*算法生成系统参数params和主私钥对.$\mathcal{C}$保存主私钥对并将params发送给${\mathcal{A}_3}$.

③阶段1.${\mathcal{A}_3}$可以自适应地执行查询：

i） 公钥查询. 当接受到身份为ID_i的公钥询问时，$\mathcal{C}$通过运用主私钥对计算，生成公钥${Q_i}$并发送给${\mathcal{A}_3}$.

ii）私钥查询. 当接受到身份为ID_i的公钥询问时，$\mathcal{C}$执行私钥提取算法KeyExtract*生成私钥d_i并发送给${\mathcal{A}_3}$.

iii） 陷门查询. 当接受到身份为ID_i的陷门询问时，$\mathcal{C}$执行陷门生成算法Trapdoor*生成陷门td_i，然后运行陷门重随机化算法ReTrapdoor生成陷门$t{d_i}$的重随机化陷门$t{d'_i}$并发送给${\mathcal{A}_3}$.

iv） 解密查询. 当接受到身份为ID_i以及密文$C$的密钥解密询问时，$\mathcal{C}$执行密文解密算法Decrypt*生成明文并返回给${\mathcal{A}_3}$.

④挑战. 敌手${\mathcal{A}_3}$将身份ID^*以及消息$M_0^*,M_1^*$（二者长度相同）发送给$\mathcal{C}$，且在阶段1，ID^*对应的私钥没有被询问到，则$\mathcal{C}$随机选取$\rho \in \{ 0,1\}$，并且计算${C^*} = Encrypt^*({M_\rho },{d^*},I{D^*})$，然后再计算$C^{*'} = ReEncrypt({C^*})$并发送给${\mathcal{A}_3}$.

⑤阶段2. ${\mathcal{A}_3}$像在阶段1一样发出询问，但是ID^*对应的私钥以及密文${C^*},C^{*'}$不可以被询问到.

⑥猜测. ${\mathcal{A}_3}$输出$\rho ' \in \{ 0,1\}$.

定义6. 如果对于任意多项式时间攻击者${\mathcal{A}_3}$，在ASA游戏中的优势$Ad{v}_{\text{SM9ET-CRF}}^{\text{ASA,Type-Ш}}({\mathcal{A}}_{3})=\left|2Pr\left[\rho ={\rho }^{\prime }\right]-1\right|$都是可忽略的，则SM9-IBEET-CRF方案是满足ASA安全的.

3.   具体方案

本文方案由8个算法组成，具体构造过程介绍如下.

1） 系统建立 Setup.

① 初始化系统，输出系统参数$params =\Big\langle {{G_1}}, \Big. \Big. {{G_2},{G_T},e,{P_1},{P_2},{P_{{\text{pub}}1}},{P_{{\text{pub}}2}},KDF,MAC,EUC} \Big\rangle$. 其中$e$为双线性对映射$e:{G_1} \times {G_2} \to {G_T}$，$G_{1}$，$G_ { 2}$的阶均为$N$，$P_1$为$G_{1}$的生成元，$P_2$为$G_{ 2 }$的生成元. 消息空间$\mathcal{M} \in {\{ 0,1\} ^*}$，用户的身份$id \in {\{ 0,1\} ^*}$均为比特串.

② KGC随机选取$s,s' \in [1,N - 1]$作为主私钥对$(s,s')$，并计算主公钥${P_{{\text{pub1}}}} = [s]{P_1}$，${P_{{\text{pub2}}}} = [s']{P_1}$.

③ 获取KGC公布的5个哈希函数：${H_1}:{\{ 0,1\} ^*} \to \mathbb{Z}_N^*$，${H_2}:{G_T} \to {G_{\text{2}}}$，${H_3}:{G_{\text{1}}} \to {\{ 0,1\} ^*}$，${H_4}:{\{ 0,1\} ^*} \to {G_2}$，${H_5}:{G_T} \to {\{ 0,1\} ^*}$.

④ 使用SM9规定的密钥派生函数$KDF(Z,klen)$，输入比特串$Z$、非负整数$klen$，输出长度为$klen$的密钥数据比特串$K$.

⑤消息认证码函数$MAC({K_2},Z)$. 输入为比特长度${K_2}\_len$的密钥${K_2}$，比特串消息$Z$. 其作用是防止消息数据$Z$被非法篡改.

⑥ 拓展欧几里得函数$EUC(r)$. 输入$r \in [1,N - 1]$，运行拓展欧几里得算法计算输出r的逆元.

2） 私钥提取 KeyExtract. 输入系统公开参数params、用户身份$I{D_A}$和主私钥对s，KGC 按①~③方式生成$I{D_A}$的私钥${d_A}$：

① 在有限域${F_N}$上计算${t_1} = {H_1}(I{D_A}) + s$，若${t_1} = 0$则需要重新产生主私钥；

② 否则，计算${t_2} = st_1^{ - 1}$，${t'_2} = s't_1^{ - 1}$；

③ 然后计算${d_A} = ({d_{A1}},{d_{A2}})$，此处的$(s,s')$是主私钥对，即

3） 陷门生成 Trapdoor. 输入用户身份$I{D_A}$，私钥${d_A}$. 输出陷门$t{d_A} = [{t'_2}]{P_2}$.

4） 加密 Encrypt. 输入系统公开参数params、用户身份$I{D_A}$，运算生成用户公钥${Q_A}$. 对于消息长度为mlen比特的比特串$M \in {\{ 0,1\} ^*}$，mlen为密钥${K_1}$的比特长度，${K_2}\_len$为$MAC({K_2},Z)$中密钥${K_2}$的比特长度，过程运算有：

① ${Q_A} = [{H_1}(I{D_A})]{P_1} + {P_{{\text{pub1}}}}$；

② 随机选取${r_1},{r_2} \in [1,N - 1]$；

③ ${C_1} = [{r_1}]{Q_A}$；

④$g = e({P_{{\text{pub1}}}},{P_2})$；

⑤ $w = {g^{{r_1}}}$；

⑥ 计算${K_1}$,${K_2}$：

i）$klen = mlen + {K_2}\_len$；

ii） ${K_1}||{K_2} = KDF({H_3}({C_1})||{H_5}(w)||I{D_A},klen)$；

⑦ ${C_2} = M \oplus {K_1}$；

⑧ ${C_3} = MAC({K_2},{C_2})$；

⑨ ${C_4} = [{r_2}]{H_4}(M){H_2}(e{({P_{{\text{pub2}}}},[{r_1}]{P_2})^{{r_2}}})$；

⑩ ${C_5} = [{r_2}]{P_1}$；

⑪ ${C_6} = [{r_1}{r_2}]{Q_A}$；

⑫ 输出$C = ({C_1},{C_2},{C_3},{C_4},{C_5},{C_6})$作为密文.

5） 重随机化密文 ReEncrypt. CRF收到密文$C = ({C_1},{C_2},{C_3},{C_4},{C_5},{C_6})$后，随机选取${r_3} \in [1,N - 1]$，然后计算$C$的重随机化密文$C' = ({C_1},{C_2},{C_3},{C_4},$${C_5},[{r_3}]{C_6})$，并发送给云服务器.

6） 解密 Decrypt. 输入$C' = ({C_1},{C_2},{C_3},{C_4},{C_5},{C'_6})$，私钥${d_A} = ({d_{A1}},{d_{A2}})$和用户身份$I{D_A}$.

① 验证${C_1} \in {G_1}$，若不成立则无法解密；

② $w' = e({C_1},{d_{A1}})$；

③ $klen = mlen + {K_2}\_len$；

④ ${K'_1}||{K'_2} = KDF({H_3}({C_1})||{H_5}(w')||I{D_A},klen$ $)$；

⑤ $M' = {C_2} \oplus {K'_1}$；

⑥ 若${C_3} \ne MAC({K'_2},{C_2})$，则解密失败，密文完整性有误；

⑦ 输出$M'$作为消息的明文.

7） 重随机化陷门 ReTrapdoor. 输入陷门$td$，CRF运行$EUC({r_3})$生成${r_3}$的逆元${r_4} \in [1,N - 1]$，计算$td$的重随机化陷门$td' = [{r_4}]td = [{r_4}{t'_2}]{P_2}$.

8）等式测试 Test. 输入2个用户的密文${C'_\alpha } = ({C_{1,\alpha }},$ ${C_{2,\alpha }},{C_{3,\alpha }},{C_{4,\alpha }},{C_{5,\alpha }},{C'_{6,\alpha }})$，${C'_\beta } = ({C_{1,\;\beta }},{C_{2,\;\beta }},{C_{3,\;\beta }},{C_{4,\;\beta }},{C_{5,\;\beta }}, {C'_{6,\;\beta }})$和2个陷门 $t{d'_\alpha }$, $t{d'_\beta }$，然后按3个步骤进行测试.

①${X_\alpha } = \dfrac{{{C_{4,\alpha }}}}{{{H_2}\left( {e\left( {{{C'}_{6,\alpha }},t{{d'}_\alpha }} \right)} \right)}}$；

② ${X_\beta } = \dfrac{{{C_{4,\;\beta }}}}{{{H_2}\left( {e\left( {{{C'}_{6,\;\beta }},t{{d'}_\beta }} \right)} \right)}}$；

③ 若$e({C_{\alpha ,5}},{X_\beta }) = e({C_{\beta ,5}},{X_\alpha })$，则${M_\alpha } = {M_\beta }$.

4.   安全性分析

4.1   SM9-IBEET正确性分析

本节首先对SM9-IBEET进行正确性分析.

1） 验证密文解密过程的正确性

采用用户私钥d以及密文消息$C = ({C_1},{C_2}, {C_3}, {C_4},{C_5},{C_6})$来验证：

其中${K'_{1,\;\beta }}$为KDF函数结果左边的mlen比特.

2） 计算消息认证码函数

$u = MAC({K'_{2,\;\beta }},{C_{2,\alpha }})$（${K'_{2,\;\beta }}$为$KDF$函数结果右边的${K_2}\_len$比特）.

若$u = {C_{3,\alpha }}$，则消息认证完整性的结果通过，解密结果正确，输出明文${M'_\alpha }$.

3） 验证等式测试计算结果的正确性

第1层计算的安全性如下所示，采用用户的陷门以及部分密文验证：

第2层计算的正确性分析如下所示，带入第1层中计算的中间结果：

若${M_\alpha } = {M_\beta }$，则等式测试的结果成立.

4.2   SM9-IBEET安全性证明

定理1. 假定嵌入的BDH困难问题是不可破解的猜想成立，则表示本文提出的支持等式测试的SM9算法是IBE-IND-CCA安全的.

证明. 假设存在无法获取目标用户陷门且不能任意执行等式测试的Ⅰ型敌手${\mathcal{A}_1}$，其攻击目的是破坏所提方案的语义安全，也即在安全游戏中对挑战密文进行区分. 如果敌手${\mathcal{A}_1}$可以成功破坏本文方案，则存在挑战者$\mathcal{C}$能够以不可忽略的优势解决BDH困难问题. 给定$({P_1},{P_2},[a]{P_1},[a]{P_2},[b]{P_1},[c]{P_1})$，其中$a,b,c \in \mathbb{Z}_N^*$， $\mathcal{C}$的目标是计算出$e{({P_1},{P_2})^{abc}}$. $\mathcal{C}$与${\mathcal{A}_1}$的挑战过程有7个.

1） 初始化.

$\mathcal{C}$随机选取$\kappa \in \left\{ {1,2, … ,{q_{{H_1}}}} \right\}$，${N_\kappa } \in \mathbb{Z}_N^*$以及${\tau _1}, {\tau _2}, … , {\tau _{\kappa - 1}},{\tau _{\kappa + 1}}, … ,{\tau _N} \in \mathbb{Z}_N^*$，${q_{{H_1}}}$代表的是查询随机预言机${\mathcal{H}_1}$的次数，对$i = 1,2, … ,\kappa - 1,\kappa + 1, … ,N$，计算${N_i} = {N_\kappa } - {\tau _i}$并保存. ${P_1},{P_2}$分别为群${G_1},{G_2}$的生成元，通过使用文献[30]的方法，$\mathcal{C}$随机选取$\gamma \in [1,N - 1]$，对$i \in \{ 1,2, … ,N\} \backslash \{ \kappa \}$，$\mathcal{C}$可以获得$N - 1$个数值对$\left( {{\tau _i},\left( {1/\gamma - {\tau _i}} \right)} \right)$，计算${P_{{\text{pub1}}}} = \left( {\gamma - {N_\kappa }} \right){P_1}$，令 ${P_{{\text{pub2}}}} = a{P_1}$. 得到公共参数$params = \left\langle {{G_1},{G_2},{G_T},e,} \right.$$\left. {{P_1},{P_2},{P_{{\text{pub1}}}},{P_{{\text{pub2}}}}, MAC} \right\rangle$，并将其发送给${\mathcal{A}_1}$.

$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_1}}},{\mathcal{L}_{{\mathcal{H}_2}}}{\mathcal{L}_{{\mathcal{H}_3}}},{\mathcal{L}_{{\mathcal{H}_4}}},{\mathcal{L}_{{\mathcal{H}_5}}},{\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$，初始化内容为空，用来模拟随机预言机$\left\langle {{\mathcal{H}_1},{\mathcal{H}_2},{\mathcal{H}_3},{\mathcal{H}_4},{\mathcal{H}_5}, }\right. \left.{ \mathcal{K}\mathcal{D}\mathcal{F}} \right\rangle$. 设置空列表${\mathcal{L}_K}$来保存公钥查询的结果.

2） 敌手${\mathcal{A}_1}$向$\mathcal{C}$提出6个询问.

① ${\mathcal{H}_1} {\text{-}} query$. 在任何时刻${\mathcal{A}_1}$可以询问随机预言机${\mathcal{H}_1}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_1}}}$用来存取元组$\left\langle {I{D_i},{N_i}} \right\rangle$，当接收到身份为$I{D_i}$的${\mathcal{H}_1}$查询时，$\mathcal{C}$查找$I{D_i}$对应的数值${N_i}$，用${H_1}\left( {I{D_i}} \right) = {N_i}$返回给${\mathcal{A}_1}$，并将$\left\langle {I{D_i},{N_i}} \right\rangle$添加到${\mathcal{L}_{{\mathcal{H}_1}}}$中.

② ${\mathcal{H}_2} {\text{-}} query$. 在任何时刻${\mathcal{A}_1}$可以询问随机预言机${\mathcal{H}_2}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_2}}}$用来存取元组$\left\langle {\sigma ,\phi } \right\rangle$，$\mathcal{C}$按2个步骤回应：

i） 如果询问的$I{D_i}$已经出现在${\mathcal{L}_{{\mathcal{H}_2}}}$的元组$\left\langle {\sigma ,\phi } \right\rangle$中，$\mathcal{C}$用$\phi$来回复.

ii） 否则，$\mathcal{C}$随机选取$\sigma \in {G_T},\phi \in {G_1}$，并将元组$\left\langle {\sigma ,\phi } \right\rangle$插入${\mathcal{L}_{{\mathcal{H}_2}}}$中，然后用$\phi$来回复${\mathcal{A}_1}$.

③ ${\mathcal{H}_3} {\text{-}} query$. 在任何时刻${\mathcal{A}_1}$可以询问随机预言机${\mathcal{H}_3}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_3}}}$用来存取元组$\left\langle {{C_1},{h_3}} \right\rangle$，如果询问的${C_1}$存在${\mathcal{L}_{{\mathcal{H}_3}}}$中，返回${h_3}$给${\mathcal{A}_1}$；否则，$\mathcal{C}$随机选取${h_3} \in {\{ 0,1\} ^*}$并添加表项$\left\langle {{C_1},{h_3}} \right\rangle$到${\mathcal{L}_{{\mathcal{H}_3}}}$中，并返回${h_3}$给${\mathcal{A}_1}$.

④ ${\mathcal{H}_4} {\text{-}} query$. 在任何时刻${\mathcal{A}_1}$可以询问随机预言机${\mathcal{H}_4}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_4}}}$用来存取元组$\left\langle {M,{h_4}} \right\rangle$，如果询问的$M$存在${\mathcal{L}_{{\mathcal{H}_4}}}$中，返回${h_4}$给${\mathcal{A}_1}$；否则，$\mathcal{C}$随机选取${h_4} \in {G_1}$并添加表项$\left\langle {M,{h_4}} \right\rangle$到${\mathcal{L}_{{\mathcal{H}_4}}}$中，返回${h_4}$给${\mathcal{A}_1}$.

⑤ ${\mathcal{H}_5} {\text{-}} query$. 在任何时刻${\mathcal{A}_1}$可以询问随机预言机${\mathcal{H}_5}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_5}}}$用来存取元组$\left\langle {w,{h_5}} \right\rangle$，如果询问的$w$存在${\mathcal{L}_{{\mathcal{H}_5}}}$中，返回${h_5}$给${\mathcal{A}_1}$；否则，$\mathcal{C}$随机选取${h_5} \in {\{ 0,1\} ^*}$并添加表项$\left\langle {w,{h_5}} \right\rangle$到${\mathcal{L}_{{\mathcal{H}_5}}}$中，返回${h_5}$给${\mathcal{A}_1}$.

⑥ $\mathcal{K}\mathcal{D}\mathcal{F} {\text{-}} query$. 在任何时刻${\mathcal{A}_1}$可以询问随机预言机$\mathcal{K}\mathcal{D}\mathcal{F}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$用来存取元组$\left\langle {Z,K} \right\rangle$，如果询问的$Z$存在于${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$中，返回$K$给${\mathcal{A}_1}$；否则，$\mathcal{C}$随机选取$K \in {\{ 0,1\} ^*}$并添加表项$\left\langle {Z,K} \right\rangle$到${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$中，返回$K$给${\mathcal{A}_1}$.

3） 公钥查询. 当接受到身份为$I{D_i}$的公钥询问时，$\mathcal{C}$按照如下方式回应：检查列表${\mathcal{L}_{{\mathcal{H}_1}}}$，如果$i = \kappa$， $\mathcal{C}$放弃，否则得到${H_1}\left( {I{D_i}} \right) = {N_i}$；计算用户公钥${Q_i} = [{H_1}(I{D_i})]{P_1} +{P_{{\text{pub1}}}} = {N_i}{P_1} + (\gamma - {N_\kappa }){P_1} = (\gamma - {\tau _i}){P_1}$，并将$Q_i$发送给${\mathcal{A}_1}$.

4） 私钥查询. 当接受到身份为$I{D_i}$的私钥询问时，$\mathcal{C}$按照如下方式回应：检查列表${\mathcal{L}_{{\mathcal{H}_1}}}$，如果$i = \kappa$，$\mathcal{C}$放弃；否则得到${H_1}\left( {I{D_i}} \right) = {N_i}$，计算用户私钥为

并将$d_{i,1}$和$d_{i,2}$发送给${\mathcal{A}_1}$.

5） 解密查询. 当接受到身份为$I{D_i}$以及密文$C = ({C_1},{C_2},{C_3},{C_4},{C_5},{C_6})$的解密询问时，如果$i \ne \kappa$，$\mathcal{C}$计算${d_{i,1}} = [(\gamma - {N_\kappa })/(\gamma - {\tau _i})]{P_2}$；如果$i = \kappa$，计算${d_{\kappa ,1}} = [1 - {N_\kappa }/\gamma ]{P_2}$. 计算$w' = e({C_1},{d_{i,1}})$，查找${C_1}$在${\mathcal{L}_{{\mathcal{H}_3}}}$对应的表项$\left\langle {{C_1},{h_3}} \right\rangle$，$w'$在${\mathcal{L}_{{\mathcal{H}_5}}}$对应的表项$\left\langle {w',{h_5}} \right\rangle$，得到$Z =$ ${h_3}||{h_5}||I{D_i}$，查找Z在${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$中对应的表项$\left\langle {Z,K} \right\rangle$，拆分$K = {K'_1}||{K'_2}$. 计算$M' = {C_2} \oplus {K'_1}$，验证${C_3} =MAC({K'_2}, {C_2})$是否成立，如果成立，则返回明文；如果不成立，则$\mathcal{C}$输出$\bot$.

6） 挑战. 敌手${\mathcal{A}_1}$将身份$I{D^*}$以及消息$M_0^*,M_1^*$（二者长度相同）发送给$\mathcal{C}$，如果$I{D^*} \ne I{D_\kappa }$，$\mathcal{C}$放弃游戏；如果$I{D^*} = I{D_\kappa }$，$\mathcal{C}$随机选取$\rho \in \{ 0,1\}$，$C_2^* \in {\{ 0,1\} ^*}$，$C_3^* \in {\{ 0,1\} ^*}$，$C_4^* \in {G_1}$，$C_6^* \in {G_1}$，并计算$C_1^* = (\gamma - {\tau _i})b{P_1}$，$C_5^* = c{P_1}$后将${C^*} = (C_1^*,C_2^*,C_3^*,C_4^*,C_5^*,C_6^*)$发送给${\mathcal{A}_1}$作为挑战密文.

7） 猜测. ${\mathcal{A}_1}$输出$\rho ' \in \{ 0,1\}$. $\mathcal{C}$从${\mathcal{L}_{{\mathcal{H}_2}}}$随机选取一个元组$\left\langle {{\sigma ^*},{\phi ^*}} \right\rangle$，并输出${\sigma ^*} = e{({P_1},{P_2})^{abc}}$作为BDH实例的解. 证毕.

定理2. 假定嵌入的BDH困难问题是不可破解的猜想成立，则表示我们提出的支持等式测试的国密SM9算法方案是IBE-OW-CCA安全的.

证明. 假定存在可以获取目标用户陷门且可以执行等式测试的Ⅱ型敌手${\mathcal{A}_2}$，其攻击目的是为了破坏所提方案的机密性，也即揭示挑战密文对应的消息. 如果敌手${\mathcal{A}_2}$可以成功破坏所提方案，则存在挑战者$\mathcal{C}$能够以不可忽略的优势解决BDH困难问题. 给定$({P_1},{P_2},[a]{P_1},[a]{P_2},[b]{P_1},[c]{P_1})$，其中$a,b,c \in \mathbb{Z}_N^*$， $\mathcal{C}$的目标是计算出$e{({P_1},{P_2})^{abc}}$.$\mathcal{C}$与${\mathcal{A}_2}$的挑战过程有8个.

1） 初始化. $\mathcal{C}$随机选取$\kappa \in \left\{ {1,2, … ,{q_{{H_1}}}} \right\}$，${N_\kappa } \in \mathbb{Z}_N^*$以及${\tau _1},{\tau _2}, … ,{\tau _{\kappa - 1}},{\tau _{\kappa + 1}}, … ,{\tau _N} \in \mathbb{Z}_N^*$，${q_{{H_1}}}$代表的是查询随机预言机${\mathcal{H}_1}$的次数，对$i = 1,2, … ,\kappa - 1,\kappa + 1, … ,N$，计算${N_i} = {N_\kappa } - {\tau _i}$并保存. ${P_1},{P_2}$分别为群${G_1},{G_2}$的生成元，通过使用文献[30]的方法，$\mathcal{C}$随机选取$\gamma \in [1,N - 1]$，对$i \in \{ 1,2, … ,N\} \backslash \{ \kappa \}$，$\mathcal{C}$可以获得$N - 1$个数值对$\left( {{\tau _i},\left( {1/\gamma - {\tau _i}} \right)} \right)$，计算${P_{{\text{pub1}}}} = \left( {\gamma - {N_\kappa }} \right){P_1}$，令 ${P_{{\text{pub2}}}} = a{P_1}$. 得到公共参数$params = \left\langle {{G_1},{G_2},{G_T},e,} \right.$$\left. {{P_1},{P_2},{P_{{\text{pub1}}}}, {P_{{\text{pub2}}}},}\right. \left.{ MAC} \right\rangle$，并将其发送给${\mathcal{A}_2}$.

$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_1}}},{\mathcal{L}_{{\mathcal{H}_2}}}{\mathcal{L}_{{\mathcal{H}_3}}},{\mathcal{L}_{{\mathcal{H}_4}}},{\mathcal{L}_{{\mathcal{H}_5}}},{\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$，初始化内容为空，用来模拟随机预言机$\left\langle {{\mathcal{H}_1},{\mathcal{H}_2},{\mathcal{H}_3},{\mathcal{H}_4},{\mathcal{H}_5},}\right. \left.{\mathcal{K}\mathcal{D}\mathcal{F}} \right\rangle$. 设置空列表${\mathcal{L}_K}$来保存公钥查询的结果.

2） 敌手${\mathcal{A}_2}$向$\mathcal{C}$提出6点询问.

① ${\mathcal{H}_1} {\text{-}} query$. 在任何时刻${\mathcal{A}_2}$可以询问随机预言机${\mathcal{H}_1}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_1}}}$用来存取元组$\left\langle {I{D_i},{N_i}} \right\rangle$，当接收到身份为$I{D_i}$的${\mathcal{H}_1}$查询时，$\mathcal{C}$查找$I{D_i}$对应的数值${N_i}$，用${H_1}\left( {I{D_i}} \right) = {N_i}$返回给${\mathcal{A}_2}$，并将$\left\langle {I{D_i},{N_i}} \right\rangle$添加到${\mathcal{L}_{{\mathcal{H}_1}}}$中.

② ${\mathcal{H}_2} {\text{-}} query$. 在任何时刻${\mathcal{A}_2}$可以询问随机预言机${\mathcal{H}_2}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_2}}}$用来存取元组$\left\langle {\sigma ,\phi } \right\rangle$，$\mathcal{C}$按2个步骤回应：

i） 如果询问的$I{D_i}$已经出现在${\mathcal{L}_{{\mathcal{H}_2}}}$的元组$\left\langle {\sigma ,\phi } \right\rangle$中，$\mathcal{C}$用$\phi$来回复.

ii） 否则，$\mathcal{C}$随机选取$\sigma \in {G_T},\phi \in {G_1}$，并将元组$\left\langle {\sigma ,\phi } \right\rangle$插入${\mathcal{L}_{{\mathcal{H}_2}}}$中，然后用$\phi$来回复${\mathcal{A}_2}$.

③ ${\mathcal{H}_3} {\text{-}} query$. 在任何时刻${\mathcal{A}_2}$可以询问随机预言机${\mathcal{H}_3}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_3}}}$用来存取元组$\left\langle {{C_1},{h_3}} \right\rangle$，如果询问的${C_1}$存在${\mathcal{L}_{{\mathcal{H}_3}}}$中，返回${h_3}$给${\mathcal{A}_2}$；否则，$\mathcal{C}$随机选取${h_3} \in {\{ 0,1\} ^*}$并添加表项$\left\langle {{C_1},{h_3}} \right\rangle$到${\mathcal{L}_{{\mathcal{H}_3}}}$中，并返回${h_3}$给${\mathcal{A}_2}$.

④ ${\mathcal{H}_4} {\text{-}} query$. 在任何时刻${\mathcal{A}_2}$可以询问随机预言机${\mathcal{H}_4}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_4}}}$用来存取元组$\left\langle {M,{h_4}} \right\rangle$，如果询问的$M$存在${\mathcal{L}_{{\mathcal{H}_4}}}$中，返回${h_4}$给${\mathcal{A}_2}$；否则，$\mathcal{C}$随机选取${h_4} \in {G_1}$并添加表项$\left\langle {M,{h_4}} \right\rangle$到${\mathcal{L}_{{\mathcal{H}_4}}}$中，返回${h_4}$给${\mathcal{A}_2}$.

⑤ ${\mathcal{H}_5} {\text{-}} query$. 在任何时刻${\mathcal{A}_2}$可以询问随机预言机${\mathcal{H}_5}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{{\mathcal{H}_5}}}$用来存取元组$\left\langle {w,{h_5}} \right\rangle$，如果询问的$w$存在${\mathcal{L}_{{\mathcal{H}_5}}}$中，返回${h_5}$给${\mathcal{A}_2}$；否则，$\mathcal{C}$随机选取${h_5} \in {\{ 0,1\} ^*}$并添加表项$\left\langle {w,{h_5}} \right\rangle$到${\mathcal{L}_{{\mathcal{H}_5}}}$中，返回${h_5}$给${\mathcal{A}_2}$.

⑥ $\mathcal{K}\mathcal{D}\mathcal{F} {\text{-}} query$. 在任何时刻${\mathcal{A}_2}$可以询问随机预言机$\mathcal{K}\mathcal{D}\mathcal{F}$，为了回答这些询问，$\mathcal{C}$保存表格${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$用来存取元组$\left\langle {Z,K} \right\rangle$，如果询问的$Z$存在于${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$中，返回$K$给${\mathcal{A}_2}$；否则，$\mathcal{C}$随机选取$K \in {\{ 0,1\} ^*}$并添加表项$\left\langle {Z,K} \right\rangle$到${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$中，返回$K$给${\mathcal{A}_2}$.

3） 公钥查询. 当接受到身份为$I{D_i}$的公钥询问时，C按照如下方式回应：检查列表${\mathcal{L}_{{\mathcal{H}_1}}}$，如果$i = \kappa$， $\mathcal{C}$放弃；否则得到${H_1}\left( {I{D_i}} \right) = {N_i}$，计算用户公钥

并将$Q_i$发送给${\mathcal{A}_2}$.

4） 私钥查询. 当接受到身份为$I{D_i}$的私钥询问时，$\mathcal{C}$按照如下方式回应：检查列表${\mathcal{L}_{{\mathcal{H}_1}}}$，如果$i = \kappa$，$\mathcal{C}$放弃；否则得到${H_1}\left( {I{D_i}} \right) = {N_i}$，计算用户私钥

并将$d_{i,1}$和$d_{i,2}$发送给${\mathcal{A}_2}$.

5） 陷门查询. 当接受到身份为$I{D_i}$的陷门询问时，如果$i = \kappa$， $\mathcal{C}$放弃；否则计算

并将$d_{i,1}$和$d_{i,2}$发送给${\mathcal{A}_2}$.

6） 解密查询. 当接受到身份为$I{D_i}$以及密文$C = ({C_1},{C_2},{C_3},{C_4},{C_5},{C_6})$的解密询问时，C按照如下方式回应：如果$i \ne \kappa$，$\mathcal{C}$计算${d_{i,1}} = [(\gamma - {N_\kappa })/(\gamma - {\tau _i})]{P_2}$；如果$i = \kappa$，计算${d_{\kappa ,1}} = [1 - {N_\kappa }/\gamma ]{P_2}$、计算$w' = e({C_1},{d_{i,1}})$，查找${C_1}$在${\mathcal{L}_{{\mathcal{H}_3}}}$对应的表项$\left\langle {{C_1},{h_3}} \right\rangle$，$w'$在${\mathcal{L}_{{\mathcal{H}_5}}}$对应的表项$\left\langle {w',{h_5}} \right\rangle$，得到$Z = {h_3}||{h_5}||I{D_i}$，查找Z在${\mathcal{L}_{\mathcal{K}\mathcal{D}\mathcal{F}}}$中对应的表项$\left\langle {Z,K} \right\rangle$，拆分$K = {K'_1}||{K'_2}$. 计算$M' = {C_2} \oplus {K'_1}$，验证${C_3} = MAC({K'_2},{C_2})$是否成立，如果成立，则返回明文；如果不成立，则$\mathcal{C}$输出$\bot$.

7） 挑战. 敌手${\mathcal{A}_2}$将身份$I{D^*}$以及消息${M^*} \in {\{ 0,1\} ^*}$发送给$\mathcal{C}$，如果$I{D^*} \ne I{D_\kappa }$，$\mathcal{C}$放弃游戏；如果$I{D^*} = I{D_\kappa }$，$\mathcal{C}$随机选取$C_2^* \in {\{ 0,1\} ^*}$，$C_3^* \in {\{ 0,1\} ^*}$，$C_4^* \in {G_1}$，$C_6^* \in {G_1}$，并计算$C_1^* = (\gamma - {\tau _i})b{P_1}$，$C_5^* = c{P_1}$后将${C^*} = (C_1^*,C_2^*,C_3^*,C_4^*, C_5^*,C_6^*)$发送给${\mathcal{A}_2}$作为挑战密文.

8） 猜测. ${\mathcal{A}_2}$输出$M' \in {M^*}$. $\mathcal{C}$从${\mathcal{L}_{{\mathcal{H}_2}}}$随机选取一个元组$\left\langle {{\sigma ^*},{\phi ^*}} \right\rangle$，并输出${\sigma ^*} = e{({P_1},{P_2})^{abc}}$作为BDH实例的解. 证毕.

4.3   ASA安全性

ASA安全性要求SM9-IBEET-CRF可以抵抗Ⅲ型敌手${\mathcal{A}_3}$的攻击. 其中敌手${\mathcal{A}_3}$具备ASA能力，在保持算法功能不变的前提下，可以替换除了CRF重随机化以外的算法，然后对系统发起攻击.

定理3. SM9-IBEET-CRF中的CRF具有维持功能性.

证明. 维持功能性要求CRF不影响原协议的功能与安全性，当数据上传者将密文与陷门经由CRF上传至云服务器后，可以得到与原协议相同的功能与安全强度.

数据上传者运行加密算法Encrypt生成密文$C = ({C_1},{C_2},{C_3},{C_4},{C_5},{C_6})$并发送给CRF.CRF重随机化密文后得到$C' = ({C_1},{C_2},{C_3},{C_4},{C_5},[{r_3}]{C_6})$，并将其上传至云服务器.

当数据接收者需要解密时，从云服务器上下载密文，此时不需要经过CRF. 解密过程的正确性通过用户私钥$d$以及密文消息${C'_\alpha } = ({C_1},$${C_2},{C_3},{C_4},{C_5}, [{r_3}]{C_6})$来验证：

其中${K'_{1,\;\beta }}$为KDF函数结果左边的mlen比特. 接下来计算消息认证码函数：

$u = MAC({K'_{2,\;\beta }},{C_{2,\alpha }})$（${K'_{2,\;\beta }}$为$KDF$函数结果右边的${K_2}\_len$比特）.

若$u = {C_{3,\alpha }}$，则消息认证完整性的结果通过，解密结果正确，输出明文${M'_\alpha }$，解密过程不受影响.

当数据接收者需要执行等式测试时，运行Trapdoor算法生成陷门td并发送给CRF. CRF重随机化陷门后得到$td' = [{r_4}]td = [{r_4}{t'_2}]{P_2}$，并将$td'$上传至云服务器. 接下来验证等式测试计算结果的正确性.

1） 第1层计算的安全性采用用户的陷门以及部分密文验证：

2） 第2层计算的正确性分析带入第1层中计算的中间结果：

若${M_\alpha } = {M_\beta }$，则等式测试的结果成立. 证毕.

定理4. SM9-IBEET-CRF中的CRF具有弱保留安全性和预防泄露性.

证明. 假定存在可以替换除CRF重随机化以外算法的Ⅲ型敌手${\mathcal{A}_3}$，其攻击目的是破坏所提方案的机密性，也即通过篡改原始算法来泄露隐私信息. 如果${\mathcal{A}_3}$可以成功破坏所提方案，使用篡改算法Setup*，KeyExtract*，Encrypt*，Decrypt*，Trapdoor*，Test*来替换原始算法. 我们则将通过SM9-IBEET-CRF的安全性游戏和原SM9-IBEET安全性游戏的不可区分性，来证明CRF满足弱保留安全性和预防泄露性. 本文考虑3种安全游戏：

1） 安全游戏Game 1. 与第2节中定义的Game 3相同.

2） 安全游戏Game 2. 与Game 1的其他部分都相同，除了在陷门查询阶段，$\mathcal{C}$用于生成陷门的算法为Trapdoor，而不是先执行Trapdoor*算法再执行ReTrapdoor算法.

3） 安全游戏Game 3. 与Game 2的其他部分都相同，除了挑战阶段，$\mathcal{C}$用于生成密文的算法为Encrypt，而不是先执行Encrypt*算法再执行ReEncrypt算法. 事实上，Game 3就是原基础方案SM9-IBEET的安全性游戏.

现在我们证明，Game 1和Game 2，Game 2和Game 3分别具有不可区分性.

Game 1和Game 2之间，对于任何篡改算法Trapdoor*，其生成的陷门$td'$在经由CRF的重随机化算法ReTrapdoor后，由于数据的可延展性，$td'$会重新分布，被映射到与原始Trapdoor相同的输出空间中. 也就是说，即使敌手篡改了Trapdoor算法的实现，它也难以区分$td'$是由Trapdoor算法产生，还是由先执行Trapdoor*算法再执行ReTrapdoor产生. 因此，Game 1和Game 2之间具有不可区分性.

Game 2和Game 3之间，对于任何篡改算法Encrypt*，其生成的密文$C'$在经由CRF的重随机化算法ReEncrypt后，由于数据的可延展性，$C'$会重新分布，被映射到与原始密文相同的输出空间中. 也就是说，即使敌手篡改了Encrypt算法的实现，它也难以区分$C'$由Encrypt算法产生，还是是由先执行Encrypt*算法再执行ReEncrypt产生. 因此，Game 2和Game 3之间具有不可区分性.

综上所述，Game 1与Game 3具有不可区分性，SM9-IBEET-CRF满足与原方案相同的IBE-IND-CCA安全性与IBE-OW-CCA安全性. 这种选择密文攻击下的不可区分性表明云服务器与用户之间的CRF具有弱保留安全性，Game 1，Game 2，Game 3之间的不可区分性证明CRF有弱抵抗渗透性. 证毕.

5.   方案对比

在本节中主要从计算开销、通信开销、安全性等方面对本文方案（SM9-IBEET-CRF）与其他等式测试的公钥加密方案和支持关键词检索的公钥加密文献[4, 6, 11, 13, 15, 17]进行比较. 其中，文献[4]为具有前向安全性的公钥可搜索加密方案（FS-PKSE）；文献[6]为带有关键字搜索的公钥认证加密方案（PAEKS）；文献[11]为具有灵活授权机制的公钥加密等式测试方案（PKEET-FA）；文献[13]为支持等式测试的无证书公钥加密方案（CLE-PKEET）；文献[15]为支持等式测试的异构签密方案（HSC-ET）；文献[17]为支持等式测试标识加密方案（IBEET）.

为评估方案性能，将本文方案与其他方案在相同的环境下逐一对比，该环境配置的处理器为Intel^® Core™ i7-8750H，内存为16 GB（RAM），在VMware软件的虚拟机上运行，在PBC（pairing-based cryptography library）库中实现双线性对的接口，实现了双线性对公钥密码体制的有效仿真，达到了1024 b RSA安全.

使用SM9定义256 b的BN曲线，椭圆曲线方程为${y^2} = {x^3} + b$来生成映射$e:{G_1} \times {G_2} \to {G_T}$，嵌入次数为12，根据SM9的参数配置PBC库中对应的算法，进行多次模拟后取平均值，与之前的文献进行了对比，其中涉及的符号定义和密码算法的执行时间定义分别如表1和表2所示.

表  1  符号定义

Table  1.  Symbols Definition

符号	含义
$|{G_1}|$	${G_1}$中元素的大小
$|{G_2}|$	${G_2}$中元素的大小
$|{G_T}|$	${G_T}$中元素的大小
$|G|$	对称配对$G$中元素的大小
$|{G_T}'|$	对称配对${G_T}'$中元素的大小
$|{\mathbb{Z}_p}|$	${\mathbb{Z}_p}$中元素的大小
$|PK|$	公钥长度
$|CL|$	密文长度
$|TD|$	陷门长度
${T_p}$	1次双线性配对运算
${T_{x1}}$	1次${G_1}$或${G_2}$上的幂运算
${T_{x2}}$	1次${G_T}$上的幂运算

下载: 导出CSV 

| 显示表格

表  2  密码操作的执行时间

Table  2.  Execution Time of Cryptographic Operation

具体操作	计算时间/ms
${T_P}$	7.5954
${T_{x1}}$	3.8915
${T_{x2}}$	1.2357

下载: 导出CSV 

| 显示表格

为评估方案的通信开销，考虑部署2类无线传感器节点平台MICAz^[31]和Tmote Sky^[32]. 其中MICAz配置的微控制器为ATmega128L，内存为4 KB（RAM）. Tmote Sky配置的微控制器为MSP430，内存为10 KB（RAM）. 采用CC2420, 2.4 GHz IEEE 802.15.4作为射频收发器标准，在 TinyOS系统运行. 使用文献[33]的方法，在2类传感器节点架构体系上实现对公钥密码通信系统的有效仿真.

5.1   计算开销对比

我们首先比较了不同方案，包括Enc加密操作、Dec解密操作和Test等式测试操作的计算开销. 具体结果如表3所示.

表  3  不同方案的计算开销对比

Table  3.  Computation Cost Comparison of Different Schemes

方案	加密	解密	等式测试/搜索
FS-PKSE[4]	$6{T_{x1}}$		$5{T_p} + 3{T_{x2}}$
PAEKS[6]	${T_p} + 4{T_{x1}}$		$4{T_p} + {T_{x2}}$
PKEET-FA[11]	$6{T_{x1}}$	$5{T_{x1}}$	$2{T_p} + 6{T_{x1}}$
CLE-PKEET[13]	$4{T_p} + 5{T_{x1}}$	$2{T_P} + 2{T_{x1}}$	$4{T_p}$
HSC-ET[15]	$5{T_{x1}} + 2{T_{x2}}$	$3{T_p} + {T_{x2}}$	$4{T_p} + 4{T_{x2}}$
IBEET[17]	$2{T_p} + 6{T_{x1}}$	$2{T_p} + 2{T_{x1}}$	$4{T_p}$
本文方案	$2{T_p} + 5{T_{x1}} + 2{T_{x2}}$	${T_p}$	$4{T_p}$

下载: 导出CSV 

| 显示表格

图3（a）表示在模拟环境下，不同方案的加密时间随消息数量的变化，虽然当消息数量增加到100时，本文方案的时间开销比文献[4, 6, 11, 15]大1.58倍左右，但很明显，与其他标识加密的等式测试的文献[13, 17]相比，本文方案的时间开销要小得多. 作为一种IBE-ET体制，本方案在加密时间上的开销是可以接受的. 与本文方案相比，文献[11]并没有实现IBE体制，在实际场景中，存在着密钥管理的问题；文献[15]异构等式测试，只能实现PKI端到IBE端的测试环境，具有一定的限制；文献[4, 6]实现的可搜索加密，不能对密文解密，只支持关键词搜索，无法搜索整段密文，搜索性有所降低. 本文方案的等式测试功能，可以实现双向密文的任意测试；用户与测试者均采用标识加密的方法，避免了密钥管理的问题；与其他标识加密的方案相比，降低了加密开销.

图  3  不同方案的计算开销对比

Figure  3.  Computation overhead comparison for different schemes

下载: 全尺寸图片 幻灯片

从图3（b）可以得出，本文方案在解密过程的计算时间远小于其他对比方案，具有解密开销上的优势.

从图3（c）中得出，本文方案与文献[13, 17]在测试计算过程耗费的计算时间是相近的，文献[4, 11, 15]在测试场景下耗费的时间要大于其他方案. 文献[4, 6]实现的传统可搜索加密并不能支持整段密文的测试，可以看出，本文方案在等式测试过程中耗费的时间是合理且具有一定优势的.

5.2   通信开销与功能对比

表4表示的是不同方案在通信开销与实际功能上的对比，可以看出本文方案与其他方案相比，具有更强的安全性与功能性. 在实际应用场景中，本文方案实现的标识加密体制避免了证书管理的问题，大大降低在通信过程中的开销. 同时，支持等式测试的功能相比于其他可搜索加密文献[4, 6]具有更强的搜索性. CRF的设置使得本文方案具备抵抗渗透攻击的能力，这意味着在面对算法篡改攻击这类威胁时本文方案提供了更高的安全性. 值得注意的是，本文方案还是唯一一个支持国密SM9算法的方案.

表  4  不同方案的通信开销与功能对比

Table  4.  Comparison of Communication Overhead and Function of Different Schemes

方案	$|PK|$	$|CL|$	$|TD|$	等式测试	标识加密	抗渗透攻击	支持国密算法
FS-PKSE[4]	$4|G|$	$5|G| + |{\mathbb{Z}_p}|$	$5|G| + |{\mathbb{Z}_p}|$	×	×	×	×
PAEKS[6]	$|G|$	$2|G|$	$|G|$	×	×	×	×
PKEET-FA[11]	$3|G|$	$5|G| + |{\mathbb{Z}_p}|$	$|{\mathbb{Z}_p}|$	√	×	×	×
CLE-PKEET[13]	$2|G|$	$3|G| + |{\mathbb{Z}_p}|$	$|G|$	√	×	×	×
HSC-ET[15]	$|G|$	$3|G| + 2|{\mathbb{Z}_p}|$	$|G|$	√	√	×	×
IBEET[17]	$2|G|$	$4|G| + |{\mathbb{Z}_p}|$	$|G|$	√	√	×	×
本文方案	$|{G_1}|$	$3|{G_1}| + |{G_2}| + 2|{\mathbb{Z}_p}|$	$|{G_2}|$	√	√	√	√
注：“√”表示存在，“×”表示不存在.

下载: 导出CSV 

| 显示表格

图4表示在模拟环境下，不同方案随着用户数量增加下各种通信开销的对比. 从图4（a）（b）可以看出，本文方案享有最低的公钥通信开销与密文通信开销. 并且在图4（c）中，本文方案的陷门开销小于除了文献[11]以外的所有方案的开销. 这是由于本文方案不仅实现了标识加密体制，在实际场景中避免了公钥证书的通信开销. 同时还是所有文献中唯一建立在非对称双线性配对基础上的方案，这大大降低了在实际通信场景中的存储开销. 由此可见本文方案具有通信开销上的优势，更适用于实际应用场景.

图  4  不同方案通信开销对比

Figure  4.  Comparison of communication overhead of different schemes

下载: 全尺寸图片 幻灯片

总的来说，通过严格的实验仿真与性能对比证明，本文方案在计算开销与通信开销上都具有一定的优势. 等式测试功能的引入，使本文方案具有比可搜索加密方案更强的搜索性；标识加密体制的拓展，解决了密钥协商和证书管理的问题；逆向防火墙的部署，进一步提升了本文方案抵抗渗透攻击与篡改攻击的能力. 本文方案不仅解决了SM9密文难以搜索的问题，还解决了目前支持等式测试的标识加密体制下计算与通信开销大、安全性弱的问题. 同时，本文方案是国密SM9密码算法在云计算场景下的一次良好应用，对于推动我国密码领域的安全研究也具有一定意义.

6.   结　　论

针对已有IBEET算法难抵抗渗透攻击的问题，本文提出了一种支持等式测试并具有逆向防火墙的SM9标识密码方案SM9-IBEET-CRF，该方案可以运用于云服务器中加密数据的外包计算方案. 本文方案在用户与云服务器之间的上行信道分别部署了密码逆向防火墙；形式化了本文方案的系统模型和定义，并考虑3种不同的对手来定义安全模型；然后在BDH假设下的随机预言机模型中证明了它的安全性；最后通过严格的实验仿真和分析结果表明，本文方案比已有方法在解密与通信开销方面具有一定的效率优势.

作者贡献声明：熊虎提出了算法思路和实验方案；林烨负责完成实验并撰写论文；姚婷协助完成实验并修改论文.