离线/在线的可验证外包属性代理重加密方案

Offline/Online Attribute-Based Proxy Re-Encryption with Verifiable Outsourced Decryption

摘要: 基于密文策略的属性代理重加密方案可以同时实现灵活的访问控制和云端密文共享功能。但现有的属性代理重加密方案多以双线性映射构造而成，面临着加解密运算效率低的问题。为解决上述问题，本文提出一种新的加密方案：离线/在线的可验证外包属性代理重加密方案(offline/online attribute-based proxy re-encryption with verifiable outsourced decryption, VF-OO-ABPRE)。基于已有的外包解密属性加密方案，利用离线/在线加密技术，对加密算法进行改进，提高加密效率，结合代理重加密的思想，实现密文共享。同时将解密工作外包给云服务商，并且能够快速地验证外包解密计算结果的正确性。理论分析表明本方案在随机预言机模型中满足选择明文攻击的不可区分安全性，并且提供了外包的可验证性证明，同时能抵抗共谋攻击。

Abstract: Ciphertext policy attribute-based proxy re-encryption (CP-ABPRE) can achieve both flexible access control and ciphertext sharing in the cloud. The existing CP-ABPRE schemes are mostly constructed by bilinear mapping, and the operations of encryption and decryption have low efficiency. To solve these problems, an offline/online attribute-based proxy re-encryption with verifiable outsourced decryption (VF-OO-ABPRE) is proposed in this paper. Based on the existing outsourcing of the decryption of ABE ciphertexts scheme, and by using offline/online encryption technology to improve the encryption algorithm, the proposed scheme can improve the encryption efficiency. Combined with the proxy re-encryption, the ciphertext sharing in the cloud is realized. At the same time, the scheme outsources the decryption work to the cloud service provider, and can verify the correctness of the computing results in an efficient way. The results of theoretical analysis show that the proposed scheme satisfies the chosen plaintext attack secure under the random oracle model and is provided with verifiable outsourced decryption’s proof, it also can resist collusive attack.

1. 引言

基于属性的加密(attribute-based encryption, ABE) [1] 可以实现加密数据的细粒度访问控制，在数据的隐私保护场景中应用广泛。主要有两种形式：基于密文策略的属性加密 [2] (ciphertext-policy attribute-based encryption, CP-ABE)和基于密钥策略的属性加密 [3] (key-policy attribute-based encryption, KP-ABE)。前者私钥关联授权属性集合，密文关联属性集合满足的访问策略，后者则相反。2007年，Bethencourt等 [2] 第一次提出基于密文策略的属性加密方案(CP-ABE)，采用访问树的结构进行秘密共享。2011年，Waters等 [4] 第一次提出线性秘密共享方案(linear secret sharing scheme, LSSS)的CP-ABE，较Bethencourt等 [2] 的方案在共享效率上有所提升，但是面临着私钥生成，数据加密和解密阶段的大量运算，且计算量与属性集合或者访问策略的复杂度成线性增长，这将会给移动用户端带来严重的计算负担和电量消耗，为解决上述问题，2011年，Green等 [5] 提出一种解密外包的ABE方案，在解密阶段首先将数据密文发送给解密外包服务器，由解密外包服务器对数据密文进行一次密文转换，生成部分密文再发送给用户，用户利用自身私钥解密出数据明文，可以缓解数据用户端的解密计算压力。运用相同的思想，更多的外包ABE方案 [6] [7] [8] [9] 被相继提出。除了解密外包，一些学者也实现了加密外包。2012年，Li等 [10] 构造加密外包的CP-ABE方案中，用户只需要做一些简单的操作就可以获得部分密文，云服务器将通过使用外包加密密钥继续完成大部分的加密操作，以获取密文的其他部分。然而，该方案仍然需要用户做大量与属性相关的求幂运算。2016年，Wang等 [11] 提出了一种可验证外包的ABE方案，实现加密、解密和密钥生成外包。但在方案中，密文的大小过大造成了密文存储空间的浪费。

2014年，Hohenberger等 [12] 提出离线/在线的ABE技术，将加密分成两个阶段进行，离线阶段在不知道相关的属性集合或者访问结构时，自动完成大量的加密计算预处理工作，在线阶段可以进行较少的计算快速完成属性加密工作。通过这种技术，可以将计算量大的工作尽可能多地在离线阶段完成，减少在线阶段的加密工作量。相较于加密外包，离线/在线同样减轻了用户加密阶段的计算负担，同时保证了数据的机密性。但是该方案不支持外包解密。2017年，Liu等 [13] 提出可验证外包解密的离线/在线ABE加密方案，采用离线/在线技术结合可验证外包计算技术，在标准模型下被证明是选择性明文攻击安全的，但是方案中离线/在线技术只用于私钥的生成，用户端的加密负担仍然存在。

单纯的离线/在线加密技术不足以解决解密授权转让和密文共享的问题，代理重加密 [14] (proxy re-encryption, PRE)是一种很好的解决方式。2009年，Liang等 [15] 首次在ABE方案中引入代理重加密技术，提出第一个基于密文策略的属性代理重加密方案(ciphertext-policy attribute-based proxy encryption, CP-ABPRE)，解决了ABE方案中共享访问策略更新和数据密文共享的问题，访问策略采取“AND”门，策略的表达性不高。2013年，Liang等 [16] 结合LSSS提出一个CP-ABPRE方案，能抵抗选择明文攻击(chosen plaintext attack, CPA)和选择密文攻击(chosen ciphertext attack, CCA)，在合数阶双线性群中的CP-ABPRE方案被相继提出 [17] [18]，都能实现标准模型中的自适应CCA安全。同样地，重加密的密钥生成和重加密都需要大量的计算。为弥补一般服务器在计算和存储能力上的不足问题，2014年，Gritti等 [19] 提出在线/离线的CP-ABPRE方案，虽然引入了代理重加密，实则利用代理者进行外包加密，不具备解密授权转让的功能。2015年，Kawai等 [20] 提出将重加密密钥外包的CP-ABPRE方案，重加密密钥不再由用户端生成，而是由授权中心来生成，这无疑增加了授权中心的计算负担。2017年，Sepehri等 [21] 提出将用户属性集合与共享访问策略用向量表示的CP-ABPRE方案，只有二者内积为0时，才能重加密密文，达到实现策略隐藏的目的。Yin等 [22] 在2017年提出一种改进的具有访问策略隐藏功能的CP-ABPRE方案，采用“AND”门共享访问策略，表达性较低。Hong等 [23] 在2018年提出一种具有密钥隔离功能的CP-ABPRE方案，实现了重加密密钥和用户密钥的前向安全。但是，以上的方案都存在加解密效率较低的问题。

基于上述研究，考虑资源受限用户利用移动设备进行加解密和数据共享的现实需求。本文在Green等 [5] 提出的外包CP-ABE方案基础上，结合离线/在线加密(offline/online encryption)技术，提出一种离线/在线的可验证外包属性代理重加密方案(offline/online attribute-based proxy re-encryption with verifiable outsourced decryption, VF-OO-ABPRE)。主要贡献如下：

1) 通过结合离线/在线ABE加密技术和外包解密技术来实现属性代理重加密方案，是率先以最小的在线计算代价同时实现数据的访问控制功能和密文共享功能。

2) 本文的方案中，大量的计算操作将在离线阶段执行或者外包给云服务商来执行，用户端在线加密和解密的计算控制在常数级别的指数运算，不会随属性集合或访问策略的复杂度而增加计算开销。

3) 给出了本文方案的安全性分析，分析表明方案基于判定性q-parallel BDHE假设在随机预言机模型下具有选择明文攻击的不可区分安全性，同时提供本方案的可验证性和抗共谋攻击证明，理论分析表明本方案在功能性和效率方面有优势。

2. 相关概念及方案

2.1. 双线性映射

令 $\Gamma$ 和 ${\Gamma }_T$ 是两个 $p$ 阶乘法循环群，定义一个双线性映射 $e:\Gamma \times \Gamma \to {\Gamma }_T$，满足以下性质：

1) 双线性：对于 $\forall u,v\in \Gamma$， $a,b\in {\mathbb{Z}}_p$， $e\left(u^a,v^b\right)=e\left(u^b,v^a\right)=e{\left(u,v\right)}^{ab}$ ；

2) 非退化性：存在 $g$ 是 $\Gamma$ 的生成元，使得 $e\left(g,g\right)\ne 1$ ；

3) 可计算性： $\forall u,v\in \Gamma$，存在一个有效算法可计算出 $e\left(u,v\right)$。

2.2. 困难性假设

判定性q-parallel BDHE假设：给定一个安全参数 $\kappa \in {\rm N}$，整数q，设 $\Gamma$， ${\Gamma }_T$ 是两个素数阶p的乘法循环群。群生成器 $\mathcal{G}\left(\kappa \right)$ 生成一个双线性群组 $\left(p,\Gamma ,{\Gamma }_T,e\right)$， $g$ 是 $\Gamma$ 的生成元，取随机值 $a,s,b_1,\cdots ,b_q\in {\mathbb{Z}}_p$。公开： $Y=g,g^s,g^a,···,g^{a^q},g^{a^{q+2}},\cdot \cdot \cdot ,g^{a^{2q}}$， $\forall 1\le j\le q,g^{s\cdot b_j},g^{a/b_j},···,g^{a^q/b_j},g^{a^{q+2}/b_j},\cdot \cdot \cdot ,g^{a^{2q/b_j}}$， $\forall 1\le j,k\le q,k\ne j,g^{a\cdot s\cdot b_k/b_j},\cdot \cdot \cdot ,g^{a^q\cdot s\cdot b_k/b_j}$， $R\in {\Gamma }_T$。在概率多项式时间(probabilistic polynomial time, PPT)内不存在算法 $\mathcal{B}$ 以不可忽视的优势区分出随机元素 $R\in {\Gamma }_T$ 和 $T=e{\left(g,g\right)}^{a^{q+1}s}\in {\Gamma }_T$。则称判定性q-parallel BDHE假设是成立的。

CDH假设(computational Diffie-Hellman, CDH)：给定一个安全参数 $\kappa \in {\rm N}$，设 $\Gamma$， ${\Gamma }_T$ 是两个素数阶 $p$ 的乘法循环群。群生成器 $\mathcal{G}\left(\kappa \right)$ 生成一个双线性群组 $\left(p,\Gamma ,{\Gamma }_T,e\right)$， $g$ 是 $\Gamma$ 的生成元，取随机值 $\alpha ,\beta \in {\mathbb{Z}}_p$，计算 $g^{\alpha },g^{\beta },g^{\alpha \beta }$。在多项式时间(PPT)内不存在算法 $\mathcal{B}$ 以不可忽视的优势在已知 $g^{\alpha }$ 和 $g^{\beta }$ 情况下计算出 $g^{\alpha \beta }$，则称CDH假设是成立的。

2.3. 基础解密外包的ABE方案

Green等 [5] CPA安全的解密外包的ABE方案一共包含五个算法：系统初始化算法 $Setup$ 、密钥生成算法 $KeyGen$ 、外包密钥生成算法 $KeyGe{n}_{out}$ 、加密算法 $Encrypt$ 、转换密文生成算法 $Transfor{m}_{out}$ 、转换密文解密算法 $Decryp{t}_{out}$。算法运行过程如下：

$Setup\left(\lambda ,U\right)$ ：输入系统参数 $\lambda \in {\rm N}$ 和属性全集 $U={\left\{0,1\right\}}^{*}$，选择两个 $p$ 阶的循环群 $\Gamma$ 和 ${\Gamma }_T$， $\Gamma$ 的生成元为 $g$， $e\left(g,g\right)\subset {\Gamma }_T$，定义杂凑函数 $F:{\left\{0,1\right\}}^{*}\to \Gamma$。选择两个随机数 $\alpha ,a\in {\mathbb{Z}}_p^{*}$，输出系统主密钥 $MSK=\left(g^{\alpha },PK\right)$ 和系统公钥 $PK=\left(g,e{\left(g,g\right)}^{\alpha },g^a,F\right)$，公开 $PK$。

$KeyGen\left(PK,MSK,S\right)$ ：输入系统主密钥 $MSK$ 、系统公钥 $PK$ 属性集合 $S$，随机选择 $t\in {\mathbb{Z}}_p$，对于所有的 $x\in S$，计算 $K=g^{\alpha }{g}^{at}$， $L=g^t$， ${\left\{K_x=F\left(\rho {\left(x\right)}^t\right)\right\}}_{x\in S}$。输出私钥 $S{K}_S=\left(S,K,L,{\left\{K_x\right\}}_{x\in S}\right)$。

$KeyGe{n}_{out}\left(MSK,S,S{K}_S\right)$ ：输入系统主密钥 $MSK$ 、属性集合 $S$，私钥 $S{K}_S$，随机选择 $z\in {\mathbb{Z}}_p$，计算 $K_{tk}=K^{(1/z)}$， $L_{tk}=L^{(1/z)}$， ${\left\{K_{x,tk}=K_x{}^{(1/z)}\right\}}_{x\in S}$，输出外包密钥 $DT{K}_S=\left(S,K_{tk},L_{tk},{\left\{K_{x,tk}\right\}}_{x\in S}\right)$，用户解密密钥 $Key=\left(z,DT{K}_S\right)$。

$Encrypt\left(PK,m,\left(M,\rho \right)\right)$ ：输入系统公钥 $PK$ 和明文 $m$，属性 $S$ 满足的LSSS访问结构 $\left(M,\rho \right)$ (其中 $M$ 是一个 $l\times n$ 的矩阵， $\rho (\cdot )$ 是一个单射函数可以把矩阵 $M$ 的每一行映射成一个属性)， $s\in {\mathbb{Z}}_p$ 是共享的秘密值，取随机数 $y_2,\cdot \cdot \cdot ,y_n\in {\mathbb{Z}}_p$，向量 $v=\left(s,y_2,\cdot \cdot \cdot ,y_n\right)\in {\mathbb{Z}}_p^n$， $M_i$ 表示矩阵M的第i行，计算 ${\lambda }_i={\left\{M_i{v}^{\text{T}}\right\}}_{i\in \{1,\cdots ,l)}$。取随机数 $r_1,\cdot \cdot \cdot ,r_n\in {\mathbb{Z}}_p$，对于任意 $i\in \left\{1,\cdots ,l\right\}$，计算得到密文组件： $C=m\cdot e{\left(g,g\right)}^{\alpha s}$， $C_1=g^s$，

${\left\{C_{2,i}={\text{g}}^{a{\lambda }_i}F{\left(\rho \left(i\right)\right)}^{-r_i},C_{3,i}=g^{r_i}\right\}}_{i\in \{1,\cdots ,l\}}$。输出密文 $CT=\left(C,C_1,{\left\{C_{2,i},C_{3,i}\right\}}_{i\in \{1,\cdots l\}}\right)$。

$Transfor{m}_{out}\left(DT{K}_S,CT\right)$ ：输入密文 $CT$ 和外包密钥 $DT{K}_S$，若用户属性集 $S$ 不满足访问结构 $\left(M,\rho \right)$，则输出 $\perp$。若用户属性集 $S$ 满足访问结构 $\left(M,\rho \right)$，则定义 $I\subset \left\{1,\cdots ,l\right\}$ 为 $I=\left\{i:\rho \left(i\right)\in S\right\}$， $\left\{{\lambda }_i\right\}$ 是根据矩阵 $M$ 对秘密 $s$ 的有效共享，存在一个常数集 ${\left\{{\omega }_i\in {\mathbb{Z}}_p\right\}}_{i\in I}$，使得 ${\displaystyle {\sum }_{i\in I}{\omega }_i\cdot }{\lambda }_i=s$。计算： $C{T}_{part}=e\left(C_1,K_{tk}\right)/{\prod }_{i\in I}{\left(e\left(C_{2,i},L_{tk}\right)\cdot e\left(C_{3,i},K_{\rho (i),tk}\right)\right)}^{{\omega }_i}=e{\left(g,g\right)}^{\alpha s/z}$。输出外包解密转换密文 $TC=\left(C,C{T}_{part}\right)$。

$Decryp{t}_{out}\left(Key,CT\right)$ ：输入密文 $CT$ 和解密密钥 $Key$，若密文 $CT$ 未进行外包解密，则首先运行转换密文生成算法 $Transfor{m}_{out}\left(DT{K}_S,CT\right)$，若算法输出 $\perp$，最终也输出 $\perp$。否则，计算 $C/C{T}_{part}^z=m$。

3. VF-OO-ABPRE方案定义及安全模型

本方案的系统中，主要包含5个实体：属性授权中心(attribute authority, AA)、数据拥有者(data owner, DO)、数据用户(data user, DU)、存储云服务商(storage-cloud service provider, S-CSP)、解密云服务商(decryption cloud service provider, D-CSP)、云服务代理商Proxy。

属性授权中心AA提供密钥生成服务，是一个完全可信的机构；数据拥有者DO可以使用移动设备加密明文信息并存储在云端；数据用户DU可以使用移动设备从云端下载密文并解密，包含两类：授权用户DU和被授权用户DU，授权用户DU可以直接解密由数据拥有者DO加密的原始密文，当数据需要重加密时，生成重加密密钥发送给云服务代理商Proxy，被授权用户DU用户只能解密被重加密的密文；云服务代理商Proxy提供数据密文重加密服务；存储云服务商S-DCP提供数据存储服务；解密云服务商D-CSP提供数据解密服务，所有的云服务商都是诚实且好奇的。

3.1. 方案形式化定义

离线/在线的可验证外包属性代理重加密方案(VF-OO-ABPRE)包含八个算法：系统初始化算法 $Setup$ 、密钥生成算法 $KeyGen$ 、外包密钥生成算法 $KeyGe{n}_{out}$ 、加密算法Encrypt (包含离线加密算法 $Offline.Enc$ 和在线加密算法 $Online.Enc$ 两种)、重加密密钥生成算法 $ReKeyGen$ 、重加密算法 $ReEncrypt$ 、重加密验证算法 $ReEncryptVerify$ 、解密算法Decrypt (包含转换密文生成算法 $Transfor{m}_{out}$ 、转换密文解密算法 $Decryp{t}_{out}$ 两种)。其中，解密算法包含了初始密文解密算法Dec₁和重加密密文解密算法Dec₂。算法运行过程如下：

1) 系统初始化算法 $Setup\left(1^{\lambda },U\right)$ ：由可信方AA执行，输入系统参数 $\lambda \in \mathbb{N}$ 和属性全集U，系统主密钥MSK和系统公钥PK，公开PK。

2) 密钥生成算法 $KeyGen\left(PK,MSK,S\right)$ ：可信方AA根据系统公钥PK，系统主密钥MSK和与用户相关的属性集S，为用户生成私钥SK_S并通过安全通道分发给用户。

3) 外包密钥生成算法 $KeyGe{n}_{out}\left(S,S{K}_S\right)$ ：用户DU输入自己的私钥SK_S，属性集合S，生成解密密钥Key用户秘密保存，外包密钥 $DT{K}_S$ 通过安全通道发给解密云服务商D-CSP。

4) 加密算法Encrypt

a) 离线加密算法 $Offline.Enc\left(PK,P\right)$ ：数据拥有DO在闲时执行，输入系统公钥PK和假设用户最大可能的属性集合 $P\subseteq U$。生成临时密钥TK保存在本地，输出中间密文ICH并将其上传至存储云服务商S-CSP。

b) 在线加密算法 $Online.Enc\left(PK,m,ICH,TK,\left(M,\rho \right)\right)$ ：数据拥有者DO在真正加密时执行，输入系统公钥PK，明文信息m，中间密文ICH，临时密钥TK，以及属性S满足的访问结构 $\mathbb{A}=\left(M,\rho \right)$，生成初始密文 $C_{(M,\rho )}$ 和验证标识 $V{K}_m$ 发送给存储云服务商S-CSP进行存储。

5) 重加密密钥生成算法 $ReKeyGen\left(PK,S{K}_S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ ：授权用户DU根据系统公钥PK，用户自己私钥 $S{K}_S$ 和另一个访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$，生成重加密密钥 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 并发送给云服务器代理商Proxy。注意：其中访问结构 $\left(M,\rho \right)$ 和访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$ 是不相交的。

6) 重加密算法 $ReEnc\left(PK,R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)},C{T}_{(M,\rho )}\right)$ ：云服务代理商Proxy根据系统公钥PK，重加密密文组件 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$，加密初始密文 $C{T}_{(M,\rho )}$ 得到重加密密文 $C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 和验证标识 $V{K}_m$ 并发送给解密云服务商D-CSP。

7) 重加密验证算法 $ReEncVerify\left(PK,\delta ,C_6,C_7\right)$ ：授权用户DU输入系统公钥PK，群元素 $\delta$，重加密密钥组件 $\left(C_6,C_7\right)$，验证重加密密文是否被云服务代理商Proxy正确加密。

8) 解密算法 $Decrypt$

a) 初始密文解密算法Dec₁

· 转换密文生成算法 $Transfor{m}_{out}\left(PK,DT{K}_S,C_{(M,\rho )}\right)$ ：解密云服务商D-CSP输入系统公钥 $PK$，外包密钥 $DT{K}_S$ 和初始密文 $C_{(M,\rho )}$，系统首先检验外包密钥 $DT{K}_S$ 中的属性集合 $S$ 是否满足 $C_{(M,\rho )}$ 中的访问结构 $\left(M,\rho \right)$，若满足，则预解密初始密文 $C_{(M,\rho )}$ 得到外包解密转换密文 $TC$ 并发送给授权用户DU。否则，输出 $\perp$，终止操作。

· 转换密文解密 $Decryp{t}_{out}\left(PK,Key,TC,V{K}_m\right)$ ：授权用户DU执行，输入解密密钥 $Key$ 、来自解密云服务商的外包解密转换密文 $TC$ 、验证标识 $V{K}_m$，解密并对结果进行验证，验证正确得到明文 $m$。否则，输出 $\perp$。

b) 重加密密文解密算法Dec₂

· 转换密文生成算法 $Transfor{m}_{out}\left(PK,DT{K}_{S^{\prime }},C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}\right)$ ：解密云服务商D-CSP输入系统公钥 $PK$，外包密钥 $DT{K}_{S^{\prime }}$ 和重加密密文 $C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$，系统首先检验外包密钥 $DT{K}_{S^{\prime }}$ 中的属性集合 $S^{\prime }$ 是否满足 $C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 中的访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$，若满足，则预解密重加密密文 $C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 得到外包解密转换密文 $T{C}^{\prime }$ 并发送给被授权用户DU。否则，输出 $\perp$，终止操作。

· 转换密文解密 $Decryp{t}_{out}\left(PK,Ke{y}^{\prime },T{C}^{\prime },V{K}_m\right)$ ：被授权用户DU执行，输入解密密钥 $Ke{y}^{\prime }$ 、来自解密云服务商的外包解密转换密文 $T{C}^{\prime }$ 、验证标识 $V{K}_m$，解密并对结果进行验证，验证正确得到明文m。否则，输出 $\perp$。

3.2. 方案安全模型

选择性选择明文攻击(selective chosen plaintext attack, s-CPA)安全博弈游戏：一个VF-OO-ABPRE方案是s-CPA安全的，则没有一个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势赢得下面的博弈。定义 $\mathcal{C}$ 为挑战者， $\lambda$ 为系统安全参数， $U$ 为属性全集。博弈游戏如下：

初始化阶段 $Init$ $\mathcal{A}$ 选择一个挑战的访问结构 $\left(M^{*},{\rho }^{*}\right)$。

系统建立阶段 $Setup$ $\mathcal{C}$ 运行系统初始化算法 $Setup\left(1^{\lambda },U\right)$ 得到系统主密钥 $MSK$ 和系统公钥 $PK$，输出系统公钥 $PK$ 给 $\mathcal{A}$，自己保留主密钥 $MSK$。

查询阶段1 $Phase\text{1}$ $\mathcal{A}$ 可以重复向预言机进行如下查询：

1) 私钥查询 ${\mathcal{O}}_{sk}\left(S\right)$ ： $\mathcal{A}$ 提交一个属性集合S，该属性集合S不满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$， $\mathcal{C}$ 运行私钥生成算法 $KeyGen\left(PK,MSK,S\right)$ 和外包密钥生成算法 $KeyGe{n}_{out}\left(S,S{K}_S\right)$，并返回私钥 $S{K}_S$ 和外包密钥 $DT{K}_S$ 给 $\mathcal{A}$。

2) 重加密密钥查询 ${\mathcal{O}}_{rk}\left(S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ ： $\mathcal{A}$ 提交一个属性集合S，该属性集合S不满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$，满足访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$， $\mathcal{C}$ 运行重加密密钥生成算法 $ReKeyGen\left(PK,S{K}_S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ 返回 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 给 $\mathcal{A}$。其中 $S{K}_S$ 由算法 $KeyGen\left(PK,MSK,S\right)$ 生成。

挑战阶段 $Challenge$ $\mathcal{A}$ 输出两个相同长度的消息 $m_0$ 和 $m_1$ 给 $\mathcal{C}$。 $\mathcal{C}$ 随机选择 $b\in \left\{0,1\right\}$ 并运行加密算法 $Online.Enc\left(PK,m_b,IC{H}^{*},T{K}^{*},\left(M^{*},{\rho }^{*}\right)\right)$ 得到挑战密文 $C_b$ 给 $\mathcal{A}$。其中 $Offline.Enc\left(PK,P\right)\to \left(T{K}^{*},IC{H}^{*}\right)$。

查询阶段2 $Phase\text{2}$ $\mathcal{A}$ 继续查询阶段1中的查询。

猜测阶段 $Guess$ $\mathcal{A}$ 输出一个猜测 $b^{\prime }\in \left\{0,1\right\}$。如果 $b^{\prime }=b$，则 $\mathcal{A}$ 获胜。 $\mathcal{A}$ 获胜的优势被定义为： ${\epsilon }_1=Ad{v}_{\mathcal{A}}^{s-CPA}\left(\lambda \right)=\left|Pr\left[b^{\prime }=b\right]-\frac{1}{2}\right|$。

定义3.1 一个VF-OO-ABPRE方案是s-CPA安全的，则没有一个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势赢得上面的博弈，即 ${\epsilon }_1\le negl\left(\lambda \right)$。

可验证博弈游戏：可验证主要是确保外包解密阶段的转换密文是否被正确执行。一个VF-OO-ABPRE方案具有可验证性，则没有一个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势赢得下面的博弈。定义 $\mathcal{C}$ 为挑战者， $\lambda$ 为系统安全参数， $U$ 为属性全集。博弈游戏如下：

系统建立阶段 $Setup$ $\mathcal{C}$ 运行系统初始化算法 $Setup\left(1^{\lambda },U\right)$ 得到系统主密钥 $MSK$ 和系统公钥 $PK$，输出系统公钥 $PK$ 给 $\mathcal{A}$，自己保留主密钥 $MSK$。

查询阶段1 $Phase1$ $\mathcal{A}$ 可以重复向预言机进行如下查询：

1) 私钥查询 ${\mathcal{O}}_{sk}\left(S\right)$ ： $\mathcal{A}$ 提交一个属性集合S，该属性集合S不满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$， $\mathcal{C}$ 运行私钥生成算法 $KeyGen\left(PK,MSK,S\right)$ 和外包密钥生成算法 $KeyGe{n}_{out}\left(S,S{K}_S\right)$，并返回私钥SK_S和外包密钥 $DT{K}_S$ 给 $\mathcal{A}$。

2) 重加密密钥查询 ${\mathcal{O}}_{rk}\left(S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ ： $\mathcal{A}$ 提交一个属性集合S，该属性集合S不满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$，满足访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$， $\mathcal{C}$ 运行重加密密钥生成算法 $ReKeyGen\left(PK,S,S{K}_S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ 返回 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 给 $\mathcal{A}$。其中SK_S由算法 $KeyGen\left(PK,MSK,S\right)$ 生成。

挑战阶段 $Challenge$ $\mathcal{A}$ 输出两个相同长度的消息 $m_0$ 和 $m_1$ 以及一个挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$ 给 $\mathcal{C}$。 $\mathcal{C}$ 随机选择 $b\in \left\{0,1\right\}$ 并运行加密算法 $Online.Enc\left(PK,m_b,IC{H}^{*},T{K}^{*},\left(M^{*},{\rho }^{*}\right)\right)$ 得到挑战密文 $C_b$ 给 $\mathcal{A}$。其中 $Offline.Enc\left(PK,P\right)\to \left(T{K}^{\ast },IC{H}^{\ast }\right)$。

查询阶段2 $Phase2$ $\mathcal{C}$ 按照查询阶段1的方式响应 $\mathcal{A}$ 的询问。但是 $\mathcal{A}$ 不能询问满足访问结构 $\left(M^{*},{\rho }^{*}\right)$ 的属性集合S。

猜测阶段 $Guess$ $\mathcal{A}$ 输出满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$ 的属性集合 $S^{*}$ 和满足属性集合 $S^{*}$ 的外包解密转换密文 $T{C}^{*}$。若能成功恢复出明文 $m_b$，则 $\mathcal{A}$ 获胜。 $\mathcal{A}$ 获胜的优势为 ${\epsilon }_2=Ad{v}_{\mathcal{A}}^{Ver.}\left(\lambda \right)=\left|Pr\left[\mathcal{A}\text{Wins}\right]\right|$。

定义3.2 一个VF-OO-ABPRE方案具有可验证性，则没有一个敌手 $\mathcal{A}$ 能在概率多项式时间 $\left(PPT\right)$ 内以不可忽略的优势赢得上面的博弈，即 ${\epsilon }_2\le negl\left(\lambda \right)$。

抗共谋攻击博弈游戏：一个VF-OO-ABPRE方案是抗共谋攻击的。则没有一个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势赢得下面的博弈。定义 $\mathcal{C}$ 为挑战者， $\lambda$ 为系统安全参数， $U$ 为属性全集。博弈游戏如下：

系统建立阶段 $Setup$ $\mathcal{C}$ 运行系统初始化算法 $Setup\left(1^{\lambda },U\right)$ 得到系统主密钥 $MSK$ 和系统公钥 $PK$，输出系统公钥 $PK$ 给 $\mathcal{A}$，自己保留主密钥 $MSK$。

查询阶段Phase重加密密钥查询 ${\mathcal{O}}_{rk}\left(S^{*},\left(M^{\prime },{\rho }^{\prime }\right)\right)$ ： $\mathcal{A}$ 提交一个属性集合 $S^{*}\subseteq U$，该属性集合 $S^{*}$ 不满足访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$，如果 $S^{*}$ 从未被询问过， $\mathcal{C}$ 首先运行 $KeyGen\left(PK,MK,S^{*}\right)$ 生成 $S{K}_{S^{*}}$，运行重加密密钥生成算法 $ReKeyGen\left(PK,S^{*},S{K}_{S^{*}},\left(M^{\prime },{\rho }^{\prime }\right)\right)$ 并返回 $R{K}_{S^{*}\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 给 $\mathcal{A}$。同时运行 $KeyGen\left(PK,MK,S^{\prime }\right)$ 得到 $S{K}_{S^{\text{'}}}$ 发送给 $\mathcal{A}$，其中 $S{K}_{S^{\text{'}}}$ 满足访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$。

挑战阶段 $Challenge$ 最后， $\mathcal{A}$ 提交一个密钥 $S{K}_{S^{\text{'}\text{'}}}$，如果 $S{K}_{S^{″}}=S{K}_{S^{*}}$ 则 $\mathcal{A}$ 赢得游戏。 $\mathcal{A}$ 赢得游戏的优势为 ${\epsilon }_3=Ad{v}_{\mathcal{A}}^{CR}\left(\lambda \right)=\left|Pr\left[S{K}_{S^{″}}=S{K}_{S^{*}}\right]-\frac{1}{2}\right|$。

定义3.3 一个VF-OO-ABPRE方案是抗共谋攻击的。则没有一个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势赢得上面的博弈，即 ${\epsilon }_3\le negl\left(\lambda \right)$。

4. VF-OO-ABPRE方案构造

4.1. 具体方案

1) 系统初始化算法 $Setup\left(1^{\lambda },U\right)$

该算法由AA执行。AA输入安全参数 $\lambda \in \mathbb{N}$ 和属性全集 $U=\left\{1,2,\cdots ,n\right\}\subset {\mathbb{Z}}_p^{*}$，选择一个 $p$ 阶的乘法循环群 $\Gamma$，生成元为 $g$， $g_1,h_1,\cdots ,h_n\in \mathbb{G}$ 为随机群元素。另一个 $p$ 阶的乘法循环群为 ${\Gamma }_T$， $e\left(g,g\right)\subset {\Gamma }_T$，选择两个随机数 $\alpha ,a\in {\mathbb{Z}}_p^{*}$，定义抗碰撞杂凑函数 $H_0:{\left\{0,1\right\}}^{*}\to {\mathbb{Z}}_p$， $H_1:{\left\{0,1\right\}}^{*}\to {\left\{0,1\right\}}^{\lambda }$， $H_2:{\left\{0,1\right\}}^{2\lambda }\to {\left\{0,1\right\}}^{*}$。最后生成系统公钥 $PK=\left(p,g,e{\left(g,g\right)}^{\alpha },g^a,g_1,h_1,\cdots ,h_n,H_0,H_1,H_2\right)$，主密钥 $MSK=\left(g^{\alpha }\right)$，可信机构将 $MSK=\left(g^{\alpha }\right)$ 作为主密钥保存起来。

2) 密钥生成算法 $KeyGen\left(PK,MSK,S\right)$

该算法由AA执行。输入系统公钥 $PK$，主密钥 $MSK$ 和属性集 $S\subseteq U$，AA随机选择 $t\in {\mathbb{Z}}_p$，对于所有的 $i\in S$，计算 $K=g^{\alpha }{g}^{at}$， $L=g^t$， ${\left\{K_i=h_i^t\right\}}_{i\in S}$，最后输出用户私钥 $S{K}_S=\left(S,K,L,{\left\{K_i\right\}}_{i\in S}\right)$ 通过安全通道发给用户。

3) 外包密钥生成算法 $KeyGe{n}_{out}\left(S,S{K}_S\right)$

该算法由解密用户DU执行，输入用户私钥 $S{K}_S$，随机选择 $z\in {\mathbb{Z}}_p$，满足 $gcd\left(z,p\right)=\text{1}$，计算 $K_{tk}=K^{(1/z)}$， $L_{tk}=L^{(1/z)}$， ${\left\{K_{i,tk}=K_i{}^{(1/z)}\right\}}_{i\in S}$。输出解密密钥 $Key=z$ 用户秘密保存，外包密钥 $DT{K}_S=\left(S,K_{tk},L_{tk},{\left\{K_{i,tk}\right\}}_{i\in S}\right)$ 通过安全通道发给解密云服务商D-CSP。

4) 加密算法 $Encrypt$

加密算法分为两个阶段，由数据拥有者DO在闲时执行的离线加密算法 $Offline.Enc$ 和真正加密阶段执行的在线加密算法 $Online.Enc$。

a) 离线加密算法 $Offline.Enc\left(PK,P\right)$。该阶段算法由数据拥有者DO执行，利用文献 [12] 的“pooling”思想，输入系统公钥 $PK$，用户根据自己需求假设最大可能的属性集合 $P\subseteq U$。对于每一个 $i\in P$，随机选取 ${\lambda }_{i,1},s_i\in {\mathbb{Z}}_p$，计算 ${\left\{C_{2,i}=g^{a{\lambda }_{i,1}}{h}_i^{-s_i},C_{3,i}=g^{s_i}\right\}}_{i\in P}$ 作为密文组件，输出中间密文 $ICH=\left({\left\{C_{2,i},C_{3,i}\right\}}_{i\in P}\right)$，可将其上传至存储云服务商S-CSP以节省本地存储资源。将临时密钥 $TK={\left\{{\lambda }_{i,1}\right\}}_{i\in P}$ 保存在本地。

b) 在线加密算法 $Online.Enc\left(PK,m,ICH,TK,\left(M,\rho \right)\right)$ ：该阶段算法由数据拥有者DO执行。输入系统公钥 $PK$，明文信息 $m\in {\left\{0,1\right\}}^{\lambda }$，中间密文 $ICH$，临时密钥 $TK$，以及属性 $S$ 满足的访问结构 $\mathbb{A}=\left(M,\rho \right)$ (其中 $M$ 是一个 $l\times n$ 的矩阵， $\rho (\cdot )$ 是一个单射函数可以把矩阵 $M$ 的每一行映射成一个属性值)。从“pooling”中随机选取 $l$ 个 $ICH$，随机选择 $W\in \mathbb{G}$，并计算 $s=H_0\left(W,m\right)$，取随机数 $y_2,\cdot \cdot \cdot ,y_n\in {\mathbb{Z}}_p$，向量 $v=\left(s,y_2,\cdot \cdot \cdot ,y_n\right)\in {\mathbb{Z}}_p^n$， $M_j$ 表示矩阵 $M$ 的第 $j$ 行，计算 ${\lambda }_j={\left\{M_j{v}^{\text{T}}\right\}}_{j\in \{1,\cdots ,l)}$。对于任意 $j\in \left\{1,\cdots ,l\right\}$，计算密文组件得：

$\begin{array}{l}C=W\cdot e{\left(g,g\right)}^{\alpha s},C_1=g^s,C_{2,j}=C_{2,\rho (j)},C_{3,j}=C_{3,\rho (j)},C_{4,j}\text{=}{\lambda }_j-{\lambda }_{j,1},k=H_1\left(W\right),\\ C_5=k\oplus m,C_6=g^{H_1(e{(g,g)}^{\alpha s})},V{K}_m=H_2\left(k\Vert C_5\right)\end{array}$

最后输出密文初始密文 $C_{(M,\rho )}=\left(C,C_1,{\left\{C_{2,j},C_{3,j},C_{4,j}\right\}}_{j\in \{1,\cdots ,l)},C_5,C_6\right)$ 和验证标识 $V{K}_m=H_2\left(k\Vert C_5\right)$ 发送给存储云服务商S-CSP进行存储。

5) 重加密密钥生成算法 $ReKeyGen\left(PK,S{K}_S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$

该算法由授权用户DU执行。假设授权用户A满足访问结构 $\mathbb{A}=\left(M,\rho \right)$，用户A运行重加密密钥生成算法 $ReKeyGen$，输入系统公钥 $PK$ 、和用户A的私钥 $S{K}_S$，新的访问结构 ${\mathbb{A}}^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ (其中 $M^{\prime }$ 是一个 $l^{\prime }\times n^{\prime }$ 的矩阵， ${\rho }^{\prime }(\cdot )$ 是一个单射函数可以把矩阵 $M^{\prime }$ 的每一行映射成一个属性值，且属性集合 $S^{\prime }$ 满足 ${\mathbb{A}}^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ )。随机选择 $\delta \in \mathbb{G}$， $s^{\prime }\in {\mathbb{Z}}_p^{*}$，其中 $s^{\prime }$ 是共享的秘密值。取随机数 ${y^{\prime }}_2,\cdot \cdot \cdot ,{y^{\prime }}_n\in {\mathbb{Z}}_p$，向量 $v^{\prime }=\left(s^{\prime },{y^{\prime }}_2,\cdot \cdot \cdot ,{y^{\prime }}_n\right)$， ${M^{\prime }}_j$ 表示矩阵 $M^{\prime }$ 的第 $j$ 行， ${{\lambda }^{\prime }}_j={\left\{{M^{\prime }}_j{v^{\prime }}^{\text{T}}\right\}}_{j\in \left\{1,\cdots ,l^{\prime }\right\}}$。首先，随机选取 ${{\lambda }^{\prime }}_{j,1},{s^{\prime }}_j\in {\mathbb{Z}}_p$，对于 $j\in \left\{1,\cdots ,l^{\prime }\right\}$，计算密文组件：

$C^{\prime }=\delta \cdot e{\left(g,g\right)}^{\alpha s^{\prime }},{C^{\prime }}_1=g^{s^{\prime }},{C^{\prime }}_{2,j}=g^{a{{\lambda }^{\prime }}_{j,1}}{h}_{{\rho }^{\prime }(j)}^{-{s^{\prime }}_j},{C^{\prime }}_{3,j}=g^{{s^{\prime }}_j},{C^{\prime }}_{4,j}={{\lambda }^{\prime }}_j-{{\lambda }^{\prime }}_{j,1}$

记 $C_{\left(M^{\prime },{\rho }^{\prime }\right)}=\left(C^{\prime },{C^{\prime }}_1,{\left\{{C^{\prime }}_{2,j},{C^{\prime }}_{3,j},{C^{\prime }}_{4,j}\right\}}_{j\in \{1,\cdots ,l^{\prime }\}}\right)$。随机选择 $\theta \in {\mathbb{Z}}_p$，并计算 $r{k}_1=K^{H_1(\delta )}\cdot g_1^{\theta }$， $r{k}_2=g_1^{\theta }$， $r{k}_3=L^{H_1(\delta )}$，对于所有的 $j\in \left\{1,\cdots ,l^{\prime }\right\}$， $r{k}_4=C_{\left(M^{\prime },{\rho }^{\prime }\right)}$， $r{k}_j=K_j^{H_1(\delta )}$，最后输出重加密密钥 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}=\left(S,r{k}_1,r{k}_2,r{k}_3,r{k}_4,r{k}_j\right)$ 发送给Proxy。

6) 重加密算法 $ReEnc\left(PK,R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)},C{T}_{(M,\rho )}\right)$

该算法由Proxy执行。Proxy收到重加密密钥 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 后，运行重加密算法 $ReEncrypt$，输入系统公钥 $PK$，重加密密钥 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 和初始密文 $C_{(M,\rho )}$。若 $C_{(M,\rho )}$ 与访问结构 $\mathbb{A}=\left(M,\rho \right)$ 有关，且属性集 $S$ 满足访问结构 $\mathbb{A}$，则定义 $I\subset \left\{1,\cdots ,l\right\}$ 为 $I=\left\{j:\rho \left(j\right)\in S\right\}$， $\left\{{\lambda }_j\right\}$ 是根据矩阵 $M$ 对秘密 $s$ 的有效共享，存在一个常数集 ${\left\{{\omega }_j\in {\mathbb{Z}}_p\right\}}_{j\in I}$，使得 ${\displaystyle {\sum }_{j\in I}{\omega }_j\cdot }{\lambda }_j=s$。计算：

$C_7=\frac{e\left(C_1,r{k}_1\right)/e\left(C_1,r{k}_2\right)}{{\prod }_{j\in I}{\left(e\left(C_{2,j}\cdot g^{a\cdot C_{4,j}},r{k}_3\right)\cdot e\left(C_{3,j},r{k}_{\rho \left(j\right)}\right)\right)}^{{\omega }_j}}=e{\left(g,g\right)}^{\alpha s{H}_1\left(\delta \right)}$，

最后输出重加密密文 $C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}=\left(\left(M^{\prime },{\rho }^{\prime }\right),C,C_5,C_6,C_7,r{k}_4\right)$ 和验证标识 $V{K}_m$ 发送给解密云服务商D-CSP。

7) 重加密验证算法 $ReEncVerify\left(PK,\delta ,C_6,C_7\right)$

该阶段由授权用户 $DU$ 执行。验证重加密密文是否被云服务代理商Proxy正确加密时， $\delta$ 对授权用户DU是已知的，输入来自云服务器Proxy的 $C_7$，计算 $V={\left(C_7\right)}^{H_1{(\delta )}^{-1}}$，若 $C_6=g^{H_1(V)}$，则说明代理商Proxy重加密计算结果正确，输出 $True$，否则输出终止符 $\perp$。

8) 解密算法 $Decrypt$

解密算法包含了对初始密文的解密算法 $De{c}_1$ 和对重加密密文的解密算法 $De{c}_2$。二者均包含了由外包云服务器D-CSP提供的外包解密转换密文生成算法 $Transfor{m}_{out}$ 和用户端提供的转换密文解密 $Decryp{t}_{out}$。

a) 初始密文解密算法Dec₁

· 转换密文生成算法 $Transfor{m}_{out}\left(PK,DT{K}_S,C_{(M,\rho )}\right)$ ：该阶段由解密云服务商D-CSP执行。若用户属性集 $S$ 不满足访问结构 $\mathbb{A}=\left(M,\rho \right)$，则输出 $\perp$。若 $C_{(M,\rho )}$ 与访问结构 $\mathbb{A}$ 有关，授权人外包密钥 $DT{K}_S=\left(S,K_{tk},L_{tk},{\left\{K_{i,tk}\right\}}_{i\in S}\right)$ 与用户属性集 $S$ 相关，且用户属性集 $S$ 满足访问结构 $\mathbb{A}$，则定义 $I\subset \left\{1,\cdots ,l\right\}$ 为 $I=\left\{j:\rho \left(j\right)\in S\right\}$， $\left\{{\lambda }_j\right\}$ 是根据矩阵 $M$ 对秘密 $s$ 的有效共享，存在一个常数集 ${\left\{{\omega }_j\in {\mathbb{Z}}_p\right\}}_{j\in I}$，使得 ${\displaystyle {\sum }_{j\in I}{\omega }_j\cdot }{\lambda }_j=s$。计算：

$C{T}_{part}=\frac{e\left(C_1,K_{tk}\right)}{{\prod }_{j\in I}{\left(e\left(C_{2,j}\cdot g^{a\cdot C_{4,j}},L_{tk}\right)\cdot e\left(C_{3,j},K_{\rho (j),tk}\right)\right)}^{{\omega }_j}}=e{\left(g,g\right)}^{\alpha s/z}$

将外包解密转换密文 $TC=\left(C,C{T}_{part},C_5\right)$ 发送给用户。

· 转换密文解密 $Decryp{t}_{out}\left(PK,Key,TC,V{K}_m\right)$ ：该阶段由授权用户DU执行，输入解密密钥 $Key=z$ 、来自解密云服务商的外包解密转换密文 $TC$ 、验证标识 $V{K}_m$，计算 $W=C/C{T}_{part}{}^{Key}$， $k=H_1\left(W\right)$。若 $V{K}_m\ne H_2\left(k\Vert C_5\right)$，则输出终止符 $\perp$ ；否则计算 $m=C_5\oplus k$， $s=H_0\left(W,m\right)$。若 $C=W\cdot e{\left(g,g\right)}^{\alpha s}$， $C{T}_{part}=e{\left(g,g\right)}^{\alpha s/z}$，输出 $m$ ；否则输出终止符 $\perp$。

b) 重加密密文解密算法Dec₂

· 转换密文生成算法 $Transfor{m}_{out}\left(PK,DT{K}_{S^{\prime }},C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}\right)$ ：该阶段由解密云服务商S-CSP执行。若用户属性集 $S^{\prime }$ 不满足访问结构 ${\mathbb{A}}^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$，则输出 $\perp$。若 $C_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 与访问结构 ${\mathbb{A}}^{\prime }$ 有关，被授权人外包密钥 $DT{K}_{S^{\prime }}=\left(S,{K^{\prime }}_{tk},{L^{\prime }}_{tk},{\left\{{K^{\prime }}_{i,tk}\right\}}_{i\in S}\right)$ 与用户属性集 $S^{\prime }$ 相关，且用户属性集 $S^{\prime }$ 满足访问结构 ${\mathbb{A}}^{\prime }$，则定义 $I^{\prime }\subset \left\{1,\cdots ,l^{\prime }\right\}$ 为 $I^{\prime }=\left\{j:{\rho }^{\prime }\left(j\right)\in S^{\prime }\right\}$， $\left\{{{\lambda }^{\prime }}_j\right\}$ 是根据矩阵 $M^{\prime }$ 对秘密 $s^{\prime }$ 的有效共享，存在一个常数集 ${\left\{{{\omega }^{\prime }}_j\in {\mathbb{Z}}_p\right\}}_{j\in I^{\prime }}$，使得 ${\displaystyle {\sum }_{j\in I^{\prime }}{\omega }_j\cdot }{\lambda }_j=s^{\prime }$。计算：

$C{T^{\prime }}_{part}=\frac{e\left({C^{\prime }}_1,{K^{\prime }}_{tk}\right)}{{\prod }_{j\in I^{\prime }}{\left(e\left({C^{\prime }}_{2,j}\cdot g^{a\cdot {C^{\prime }}_{4,j}},{L^{\prime }}_{tk}\right)\cdot e\left({C^{\prime }}_{3,j},{K^{\prime }}_{{\rho }^{\prime }(j),tk}\right)\right)}^{{{\omega }^{\prime }}_j}}=e{\left(g,g\right)}^{\alpha s^{\prime }/z^{\prime }}$

将 $T{C}^{\prime }=\left(C,C^{\prime },C{T^{\prime }}_{part},C_5,C_7\right)$ 发送给用户。

· 转换密文解密 $Decryp{t}_{out}\left(PK,Ke{y}^{\prime },T{C}^{\prime },V{K}_m\right)$ ：该阶段由被授权用户DU执行，输入解密密钥 $Ke{y}^{\prime }=z^{\prime }$ 、来自解密云服务商的外包解密转换密文 $T{C}^{\prime }$ 、验证标识 $V{K}_m$，计算 $\delta =C^{\prime }/C{T^{\prime }}_{part}{}^{Ke{y}^{\prime }}$， $W=C/{\left(C_7\right)}^{H_1(\delta )}$， $k=H_1\left(W\right)$。若 $V{K}_m\ne H_2\left(k\Vert C_5\right)$，则输出终止符 $\perp$ ；否则计算 $m=C_5\oplus k$， $s=H_0\left(W,m\right)$。若 $C=W\cdot e{\left(g,g\right)}^{\alpha s}$， $C{T^{\prime }}_{part}=e{\left(g,g\right)}^{\alpha s^{\prime }/z^{\prime }}$，输出 $m$ ；否则输出终止符 $\perp$。

4.2. 正确性

1) 原始密文的解密正确性。如果用户属性集 $S$ 满足访问结构 $\mathbb{A}$，存在 ${\displaystyle {\sum }_{j\in I}{\omega }_j\cdot }{\lambda }_j=s$。则计算：

$\begin{array}{c}C{T}_{part}=\frac{e\left(C_1,K_{tk}\right)}{{\prod }_{j\in I}{\left(e\left(C_{2,j}\cdot g^{a\cdot C_{4,j}},L_{tk}\right)\cdot e\left(C_{3,j},K_{\rho (j),tk}\right)\right)}^{{\omega }_j}}=\frac{e\left(g^s,{\left(g^{\alpha }{g}^{at}\right)}^{1/z}\right)}{{\prod }_{j\in I}{\left(e\left(g^{a{\lambda }_{j,1}}{h}_{\rho (j)}^{-s_j}\cdot g^{a\cdot ({\lambda }_j-{\lambda }_{j,1})},g^{t/z}\right)\cdot e\left(g^{s_j},h_{\rho (j)}^{t/z}\right)\right)}^{{\omega }_j}}\\ =\frac{e\left(g^s,{\left(g^{\alpha }{g}^{at}\right)}^{1/z}\right)}{{\prod }_{j\in I}{\left(e\left(g^{a{\lambda }_j}{h}_{\rho (j)}^{-s_j},g^{t/z}\right)\cdot e\left(g^{s_j},h_{\rho (j)}^{t/z}\right)\right)}^{{\omega }_j}}=\frac{e{\left(g,g\right)}^{\alpha s/z}\cdot e{\left(g,g\right)}^{ats/z}}{e{\left(g,g\right)}^{at/z{\displaystyle {\sum }_{j\in I}{\lambda }_j{\omega }_j}}}=e{\left(g,g\right)}^{\alpha s/z}\end{array}$

接着计算 $\frac{C}{C{T}_{part}{}^{K\text{ey}}}=\frac{W\cdot e{\left(g,g\right)}^{\alpha s}}{{\left(e{\left(g,g\right)}^{\alpha s/z}\right)}^z}=W$， $k=H_1\left(W\right)$， $k\oplus C_5=k\oplus k\oplus m=m$ 得到明文。

2) 重加密密文的解密正确性。如果用户属性集 $S^{\prime }$ 满足访问结构 ${\mathbb{A}}^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$，存在 ${\displaystyle {\sum }_{j\in I^{\prime }}{{\omega }^{\prime }}_j\cdot }{{\lambda }^{\prime }}_j=s^{\prime }$。先计算重加密密文组件 $C_7$，计算得：

$\begin{array}{c}{C}_7=\frac{e\left(C_1,r{k}_1\right)/e\left(C_1,r{k}_2\right)}{{\prod }_{j\in I}{\left(e\left(C_{2,j}\cdot g^{a\cdot C_{4,j}},r{k}_3\right)\cdot e\left(C_{3,j},r{k}_j\right)\right)}^{{\omega }_j}}=\frac{e\left(g^s,{\left(g^{\alpha }{g}^{at}\right)}^{H_1(\delta )}\cdot g_1^{\theta }\right)/e\left(g^s,g_1^{\theta }\right)}{{\prod }_{j\in I}{\left(e\left(g^{a{\lambda }_{j,1}}{h}_{\rho (j)}^{-s_j}\cdot g^{a\cdot ({\lambda }_j-{\lambda }_{j,1})},{\left(g^t\right)}^{H_1(\delta )}\right)\cdot e\left(g^{s_j},{\left(h_{{\rho }^{\text{'}}(j)}^t\right)}^{H_1(\delta )}\right)\right)}^{{\omega }_j}}\\ =\frac{e{\left(g,g\right)}^{s\alpha H_1(\delta )}e{\left(g,g\right)}^{sat}{}^{H_1(\delta )}}{{\prod }_{j\in I}{\left(e\left(g^{a{\lambda }_j}{h}_{\rho (j)}^{-s_j},{\left(g^t\right)}^{H_1(\delta )}\right)\cdot e\left(g^{s_j},{\left(h_{\rho (j)}^t\right)}^{H_1(\delta )}\right)\right)}^{{\omega }_j}}=\frac{e{\left(g,g\right)}^{s\alpha H_1(\delta )}e{\left(g,g\right)}^{sat}{}^{H_1(\delta )}}{e{\left(g,g\right)}^{at/H_1(\delta ){\displaystyle {\sum }_{j\in I}{\lambda }_j{\omega }_j}}}=e{\left(g,g\right)}^{s\alpha H_1(\; \delta \; )}\end{array}$

同样的，按照 $C{T}_{part}$ 的计算方法，可以计算出 $C{T^{\prime }}_{part}=e{\left(g,g\right)}^{\alpha s^{\prime }/z^{\prime }}$，综合以上结果，接着计算 $C^{\prime }/C{T^{\prime }}_{part}{}^{Ke{y}^{\prime }}=\delta \cdot e{\left(g,g\right)}^{\alpha s^{\prime }}/{\left(e{\left(g,g\right)}^{\alpha s^{\prime }/z^{\prime }}\right)}^{z^{\prime }}=\delta$， $C/{\left(C_7\right)}^{H_1{(\delta )}^{-1}}=W\cdot e{\left(g,g\right)}^{\alpha s}/{\left(e{\left(g,g\right)}^{s\alpha \cdot }{}^{H_1(\delta )}\right)}^{H_1{(\delta )}^{-1}}=W$， $k=H_1\left(W\right)$， $k\oplus C_5=k\oplus k\oplus m=m$ 得到明文。

5. VF-OO-ABPRE方案分析

5.1. 安全性分析

定理1. 如果判定性q-parallel BDHE假设成立，那么VF-OO-ABPRE方案是随机预言机模型下s-CPA安全的。

证明 假设存在某个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势攻破本文提出的方案，那么可以构造仿真者 $\mathcal{B}$ 在概率多项式时间(PPT)内以不可忽略的优势解决判定性q-parallel BDHE假设困难问题。

$Init$ $\mathcal{A}$ 选择一个挑战的访问结构 $\left(M^{*},{\rho }^{*}\right)$ 发送给 $\mathcal{B}$。 $\mathcal{B}$ 输入判定性q-parallel BDHE假设挑战元组 $\left(p,\mathbb{G},{\mathbb{G}}_T,Z,Y\right)$，其中， $Z$ 为群 ${\Gamma }_T$ 中的随机元素 $R\in {\mathbb{G}}_T$ 或者 $e{\left(g,g\right)}^{a^{q+1}s}\in {\mathbb{G}}_T$， $Y=g,g^s,g^a,···,g^{a^q},g^{a^{q+2}},\cdot \cdot \cdot ,g^{a^{2q}}$， $\forall 1\le j\le q,g^{s\cdot b_j},g^{a/b_j},···,g^{a^q/b_j},g^{a^{q+2}/b_j},\cdot \cdot \cdot ,g^{a^{2q/b_j}}$， $\forall 1\le j,k\le q,k\ne j,g^{a\cdot s\cdot b_k/b_j},\cdot \cdot \cdot ,g^{a^q\cdot s\cdot b_k/b_j}$。

$Setup$ $\mathcal{B}$ 运行系统初始化算法 $Setup\left(1^{\lambda },U\right)\to \left(PK,MSK\right)$，随机选择 ${\alpha }^{\prime }\in {\mathbb{Z}}_p$，使得 $\alpha ={\alpha }^{\prime }+a^{q+1}$。在此阶段 $\mathcal{B}$ 不知道 $\alpha$ 的值，但是可计算 $e{\left(g,g\right)}^{\alpha }=e\left(g^a,g^{a^q}\right)e{(g,g)}^{{\alpha }^{\prime }}$。对于任意 $x\in U$，随机选取 $z_x\in {\mathbb{Z}}_p$，当 ${\rho }^{*}\left(i\right)=x$， $\mathcal{B}$ 计算 $h_x=g^{z_x}\cdot g^{a{M}_{i,1}^{\ast }/b_i}\cdot g^{a^2{M}_{i,2}^{\ast }/b_i}\cdots g^{a^{n^{\ast }}{M}_{i,n^{\ast }}^{\ast }/b_i}$，否则计算 $h_x=g^{z_x}$。输出 $PK=\left(p,g,e{\left(g,g\right)}^{\alpha },g^a,g_1,h_1,\cdots ,h_n,H_0,H_1,H_2\right)$ 给 $\mathcal{A}$。

$Phase1$ $\mathcal{B}$ 初始化空表 ${\mathcal{T}}_0$， ${\mathcal{T}}_1$， ${\mathcal{T}}_2$， $\mathcal{A}$ 可重复进行以下查询：

1) $H_0\left(W,m\right)$ ：若表 ${\mathcal{T}}_0$ 中已经存在 $\left(W,m,s\right)$，则返回 $s$ ；否则选取一个随机值 $s\in {\mathbb{Z}}_p$，并将 $\left(W,m,s\right)$ 记录在表 ${\mathcal{T}}_0$ 中，返回 $s$。

2) $H_1\left(W\right)$ ：若表 ${\mathcal{T}}_1$ 中已经存在 $\left(W,k\right)$，则返回 $k$ ；否则选取一个随机值 $k\in {\left\{0,1\right\}}^{\lambda }$，并将 $\left(W,k\right)$ 记录在表 ${\mathcal{T}}_1$ 中，返回 $k$。

3) 私钥查询 ${\mathcal{O}}_{sk}\left(S\right)$ ： $\mathcal{A}$ 可重复发出查询请求。输入属性集 $S$， $\mathcal{B}$ 做出如下回应：

a) 属性集合 $S|\ne \left(M^{*},{\rho }^{*}\right)$ 时， $\mathcal{B}$ 选择向量 $w=\left(w_{\text{1}},w_{\text{2}},\cdots ,w_{n^{*}}\right)\in {\mathbb{Z}}_p^{n^{*}}$，其中 $w_1=-\text{1}$，对于所有的 $i$ 满足 ${\rho }^{*}\left(i\right)\in S$ 时， $M_i^{*}\cdot w=0$。随机选取 $r\in {\mathbb{Z}}_p$，定义 $t=r+w_{\text{1}}{a}^q+w_{\text{2}}{a}^{q-\text{1}}+\cdots +w_{n^{*}}{a}^{q-n^{*}+\text{1}}$。计算

$L=g^r{{\displaystyle \underset{i=1,\cdots ,n^{*}}{\prod }\left(g^{a^{q+1-i}}\right)}}^{w_i}=g^t$， $K=g^{{\alpha }^{\prime }}{g}^{ar}{{\displaystyle \underset{i=2,\cdots ,n^{*}}{\prod }\left(g^{a^{q+2-i}}\right)}}^{w_i}=g^{\alpha }{g}^{at}$。对于 ${\rho }^{*}\left(i\right)=x$，计算 $K_x=L^{z_x}{{\displaystyle \underset{j=1,\cdots ,n^{\ast }}{\prod }\left(g^{\left(a^j/b_i\right)\cdot r}{\displaystyle \underset{\begin{array}{l}k=1,\cdots ,n^{\ast }\\ k\ne j\end{array}}{\prod }{\left(g^{a^{q+1+j-k/b_i}}\right)}^{w_k}}\right)}}^{M_{i,j}^{\ast }}$，其余情况则计算 $K_x=L^{z_x}=h_x^t$。用户私钥 $S{K}_S=\left(S,K,L,{\left\{K_x\right\}}_{x\in S}\right)$。随机选取 $z\in {\mathbb{Z}}_p$ 作为解密密钥。计算外包密钥得 $DT{K}_S=\left(K^{(1/z)},L^{(1/z)},K_x^{(1/z)}\right)$。将元组 $\left(S,S{K}_S,DT{K}_S\right)$ 记录在表 ${\mathcal{T}}_2$ 中，发送 $DT{K}_S$ 给 $\mathcal{A}$。

b) 属性集合 $S|=\left(M^{*},{\rho }^{*}\right)$ 时，无法查询 $S$ 对应的私钥。按如下方法选择一个“伪”外包密钥： $\mathcal{B}$ 随机选取 $d\in {\mathbb{Z}}_p^{*}$，运行 $KeyGen\left(PK,d,S\right)$ 生成密钥 $S{K^{\prime }}_S$，令 $DT{K}_S=S{K^{\prime }}_S$， $S{K}_S=\left(d,DT{K}_S\right)$，将元组 $\left(S,S{K}_S,DT{K}_S\right)$ 记录在表 ${\mathcal{T}}_2$ 中，发送 $DT{K}_S$ 给 $\mathcal{A}$。

4) 重加密密钥查询 ${\mathcal{O}}_{rk}\left(S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ ： $\mathcal{A}$ 输入属性集 $S$ 和访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$，若 $S|\ne \left(M^{*},{\rho }^{*}\right)$ 时， $\mathcal{B}$ 运行重加密密钥生成算法 $ReKeyGen\left(PK,S,S{K}_S,\left(M^{\prime },{\rho }^{\prime }\right)\right)\to R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 返回 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 给 $\mathcal{A}$。其中 $S{K}_S$ 由算法 $KeyGen\left(PK,MSK,S\right)\to S{K}_S$ 生成。

$Challenge$ $\mathcal{A}$ 向 $\mathcal{B}$ 输出两个相同长度的消息 $m_0$ 和 $m_1$， $\mathcal{B}$ 执行如下计算：

1) 随机选择 $W\in {\mathbb{G}}_T$， $b\in \left\{0,1\right\}$， $k^{*}\in {\mathbb{Z}}_p$， $C_6^{*}\in \mathbb{G}$ 计算得到部分密文 $C_b^{part}=\left(C^{\text{*}},C_1^{\text{*}},C_5^{*},C_6^{*}\right)$ 得：

$C^{*}=W\cdot Z\cdot e\left(g^{{\alpha }^{\prime }},g^s\right)$， $C_1^{\text{*}}=g^s$， $C_5^{*}=k^{*}\oplus m_b$， $C_6^{*}=C_6^{*}$ ；

2) 随机选择，计算 $v=\left(s,sa+c_2,s{a}^2+c_3,\cdots ,s{a}^{n^{*}-1}+c_{n^{*}}\right)$，对于 $i\in \left\{1,\cdots ,l^{*}\right\}$， $M_i^{*}$ 表示矩阵 $M^{*}$ 的第 $i$ 行， ${\lambda }_i^{*}={\left\{M_i^{*}{v}^{\text{T}}\right\}}_{i\in I}$，随机选择 $s_i^{\ast }\in {\mathbb{Z}}_p$，对于 $i=\left\{1,\cdots ,l^{*}\right\}$，定义 $R_i$ 表示 $k\ne i$ 且 ${\rho }^{*}\left(i\right)={\rho }^{*}\left(k\right)$ 时的集合。计算：

$C_{2,i}^{\ast }=h_{{\rho }^{\ast }\left(i\right)}^{s_i^{\ast }}\left(\underset{j=2,\cdots ,n^{\ast }}{\prod }{\left(g^a\right)}^{M_{i,j}^{\ast }{c}_j}\right){\left(g^{b_i\cdot s}\right)}^{-z_{{\rho }^{\ast }(i)}}\cdot \left(\underset{k\in R_i}{\prod }\underset{j=1,\cdots ,n^{\ast }}{\prod }{\left(g^{a^i\cdot s\cdot \left(b_i/b_k\right)}\right)}^{M_{k,j}^{\ast }}\right)$ , $C_{3,i}^{\ast }=g^{-s_i^{\ast }}{g}^{-s{b}_i}$

3) $\mathcal{B}$ 将挑战密文 $C_b=\left(C^{\text{*}},C_1^{\text{*}},{\left\{C_{2,i}^{*},C_{3,i}^{*},C_{4,i}^{*}\right\}}_{i\in \{1,\cdots ,l^{*}\}},C_5^{*},C_6^{*}\right)$ 发送给 $\mathcal{A}$。

$Phase2$ $\mathcal{A}$ 继续查询阶段1中的查询，但是不能查询任何属性集 $S$ 满足 $\left(M^{*},{\rho }^{*}\right)$。

$Guess$ $\mathcal{A}$ 输出一个猜测 $b^{\prime }\in \left\{0,1\right\}$。若仿真者 $\mathcal{B}$ 认为 $b^{\prime }=b$，则猜测 $Z=e{\left(g,g\right)}^{a^{q+1}s}$，否则，猜测 $Z$ 是群 ${\mathbb{G}}_T$ 的随机元素。如果 $Z=e{\left(g,g\right)}^{a^{q+1}s}$，仿真者 $\mathcal{B}$ 赢得该游戏的概率是：

$Pr\left[\mathcal{B}\left(Y,Z=e{\left(g,g\right)}^{a^{q+1}s}\right)=1\right)=\frac{1}{2}+\epsilon$。如果 $Z$ 是群 ${\mathbb{G}}_T$ 的随机元素，消息 $m_b$ 对敌手来说是隐藏的，仿真者 $\mathcal{B}$ 赢得该游戏的概率是： $Pr\left[\mathcal{B}\left(Y,Z=R\right)=1\right)=\frac{1}{2}$。因此，挑战者在解决判定性q-parallel BDHE假设问题上具有不容忽视的优势： $Ad{v}_{\mathcal{B}}^{q-BDHE}=Pr\left[\mathcal{B}\left(Y,Z=e{\left(g,g\right)}^{a^{q+1}s}\right)=1\right]-Pr\left[\mathcal{B}\left(Y,Z=R\right)=1\right]=\epsilon$。

这与判定性q-parallel BDHE假设成立矛盾，所以定理1得证。证毕

定理2. 假设 $H_1,H_2$ 是抗碰撞的杂凑函数，那么VF-OO-ABPRE方案具有可验证性。

证明 假设存在敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势攻破可验证性，那么可以构建一个仿真者 $\mathcal{B}$ 打破底层杂凑函数 $H_1,H_2$ 的抗碰撞能力。 $\mathcal{A}$ 提交2个挑战杂凑函数 $H_1^{*},H_2^{*}$， $\mathcal{B}$ 进行如下的仿真实验过程：

$Setup$ $\mathcal{B}$ 执行 $Setup$ 算法获取系统公钥 $PK$ 和主密钥 $MSK$，并用 $H_1^{*},H_2^{*}$ 替换 $PK$ 中的 $H_1,H_2$。注： $\mathcal{B}$ 知道主密钥 $MSK$。

$Phase1$ $\mathcal{A}$ 可以重复向预言机进行如下查询：

1) 私钥查询 ${\mathcal{O}}_{sk}(S)$ ： $\mathcal{A}$ 提交一个属性集合 $S$，该属性集合 $S$ 不满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$， $\mathcal{C}$ 运行私钥生成算法 $KeyGen\left(PK,MSK,S\right)$ 和外包密钥生成算法 $KeyGe{n}_{out}\left(S,S{K}_S\right)$，并返回私钥 $S{K}_S$ 和外包密钥 $DT{K}_S$ 给 $\mathcal{A}$。

2) 重加密密钥查询 ${\mathcal{O}}_{rk}\left(S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ ： $\mathcal{A}$ 提交一个属性集合 $S$，该属性集合 $S$ 不满足挑战访问结构 $\left(M^{*},{\rho }^{*}\right)$，满足访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$， $\mathcal{C}$ 运行重加密密钥生成算法 $ReKeyGen\left(PK,S,S{K}_S,\left(M^{\prime },{\rho }^{\prime }\right)\right)$ 返回 $R{K}_{S\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 给 $\mathcal{A}$。其中 $S{K}_S$ 由算法 $KeyGen\left(PK,MSK,S\right)$ 生成。

$Challenge$ $\mathcal{A}$ 提交两个相同长度的消息 $m_0$ 和 $m_1$ 以及一个挑战的访问结构 $\left(M^{*},{\rho }^{*}\right)$ 给 $\mathcal{B}$。 $\mathcal{B}$ 随机选择 $b\in \left\{0,1\right\}$， $W^{*}\in {\mathbb{G}}_T$，并计算 $C{T}^{W^{*}}=\left(C,C_1,{\left\{C_{2,i},C_{3,i},C_{4,i}\right\}}_{1\le i\le l}\right)$， $k^{*}=H_1^{*}\left(W^{*}\right)$， $C_5^{*}=k^{*}\oplus m_b$，

$V{K}_{m_b}^{*}=H_2^{*}\left(k^{*}\Vert C_5^{*}\right)$。 $\mathcal{B}$ 将 $C_{\left(M^{*},{\rho }^{*}\right)}^{*}=\left(C{T}^{W^{*}},C_5^{*}\right)$ 和 $V{K}_{m_b}^{*}$ 发送给 $\mathcal{A}$。同时自己保留 $V{K}_{m_b}^{*}$ 和 $\left(W^{*},C_5^{*}\right)$。

$Phase2$ $\mathcal{B}$ 按照查询阶段1的方式响应 $\mathcal{A}$ 的询问。但是 $\mathcal{A}$ 不能询问满足访问结构 $\left(M^{*},{\rho }^{*}\right)$ 的属性集合 $S$。

$Guess$ $\mathcal{A}$ 输出属性集合 $S^{*}$ 和外包解密转换密文 $T{C}^{*}=\left(C,C{T}_{part},C_5\right)$。

若敌手 $\mathcal{A}$ 可攻破可验证性，那么仿真者 $\mathcal{B}$ 将通过转换密文解密 $Decryp{t}_{out}\left(PK,Ke{y}^{*},T{C}^{*},V{K}_{m_b}^{*}\right)$ 恢复出明文 $m_b$。若 $V{K}_{m_b}^{*}\ne H_2^{*}\left(k\Vert C_5^{*}\right)$，则解密算法输出终止符 $\perp$，其中 $k=H_1^{*}\left(W\right)$， $W=C/C{T}_{part}{}^{Ke{y}^{\prime }}$。考虑如下情况：

情况1： $\left(k,C_5\right)\ne \left(k^{*},C_5^{*}\right)$。因仿真者 $\mathcal{B}$ 知道 $\left(k^{*},C_5^{*}\right)$，若出现此种情况，则 $\mathcal{B}$ 可得到杂凑函数 $H_2^{*}$ 的碰撞。

情况2： $\left(k,C_5\right)=\left(k^{*},C_5^{*}\right)$。但是 $W\ne W^{*}$，因为 $H_1^{*}\left(W\right)=k=k^{*}=H_1^{*}\left(W^{*}\right)$，若出现此种情况，则将打破杂凑函数 $H_1^{*}$ 的抗碰撞能力。

通过上述分析完成定理2的安全证明。证毕

定理3. 假定CDH假设成立，那么VF-OO-ABPRE方案是抗共谋攻击的。

证明 假设存在某个敌手 $\mathcal{A}$ 能在概率多项式时间(PPT)内以不可忽略的优势攻破本文提出的方案，那么可以构造仿真者 $\mathcal{B}$ 在概率多项式时间(PPT)内以不可忽略的优势解决CDH困难问题。

$Setup$ $\mathcal{B}$ 运行 $Setup\left(1^{\lambda },U\right)$ 算法，随机选择 $h_1,\cdots ,h_{\left|U\right|}\in \mathbb{G}$， $\alpha ,a,b\in {\mathbb{Z}}_p$，计算 $e{\left(g,g\right)}^{\alpha }$ 和 $g_1=g^b$，得到系统公钥 $PK=\left(p,g,e{\left(g,g\right)}^{\alpha },g^a,g_1,h_1,\cdots ,h_{\left|U\right|},H_0,H_1,H_2\right)$ 和主密钥 $MSK=g^{\alpha }$。

$Phase1$ 对于不满足访问结构 $\left(M^{*},{\rho }^{*}\right)$ 但是满足访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$ 的属性集合 $S^{\prime }\subseteq U$， $\mathcal{B}$ 运行 $KeyGen\left(PK,MSK,S^{\prime }\right)\to S{K}_{S^{\prime }}$ 生成 $S{K}_{S^{\prime }}=\left(S^{\prime },K^{\prime },L^{\prime },{\left\{{K^{\prime }}_i\right\}}_{i\in S^{\prime }}\right)$ 将其发送给 $\mathcal{A}$。对于满足访问结构 $\left(M^{*},{\rho }^{*}\right)$ 的属性集合 $S^{*}\subseteq U$， $\mathcal{B}$ 运行 $KeyGen\left(PK,MSK,S^{*}\right)\to S{K}_{S^{*}}$ 生成 $S{K}_{S^{*}}=\left(S^{*},K^{*},L^{*},{\left\{K_i^{*}\right\}}_{i\in S^{*}}\right)$ 由 $\mathcal{B}$ 自己秘密保存。对于关于 $\left(S^{*},\left(M^{\prime },{\rho }^{\prime }\right)\right)$ 的重加密密钥询问，如果 $S^{*}$ 从未被询问过，通过访问结构 $\left(M^{\prime },{\rho }^{\prime }\right)$， $\mathcal{B}$ 随机选择 ${\theta }^{*}\in {\mathbb{Z}}_p$，计算 $g^{{\theta }^{*}}={\delta }^{*}\in \mathbb{G}$，对于 $j\in \left\{1,\cdots ,l^{\prime }\right\}$，计算 $C^{\prime }={\delta }^{*}\cdot e{\left(g,g\right)}^{\alpha s^{*}}$， ${C^{\prime }}_1=g^{s^{\prime }}$， ${C^{\prime }}_{2,j}=g^{a{{\lambda }^{\prime }}_{j,1}}{h}_{\rho (j)}^{-{s^{\prime }}_j}$， ${C^{\prime }}_{3,j}=g^{{s^{\prime }}_j}$， ${C^{\prime }}_{4,j}={{\lambda }^{\prime }}_j-{{\lambda }^{\prime }}_{j,1}$，得到 $C_{\left(M^{\prime },{\rho }^{\prime }\right)}=\left(C^{\prime },{C^{\prime }}_1,{\left\{{C^{\prime }}_{2,j},{C^{\prime }}_{3,j},{C^{\prime }}_{4,j}\right\}}_{j\in \left\{1,\cdots ,l^{\prime }\right\}}\right)$， $r{k}_1={\left(K^{*}\right)}^{H_1\left({\delta }^{*}\right)}\cdot g_1^{{\theta }^{*}}$， $r{k}_2=g_1^{{\theta }^{*}}$， $r{k}_3={\left(L^{*}\right)}^{H_1\left({\delta }^{*}\right)}$，对于所有的 $j\in \left\{1,\cdots ,l^{\prime }\right\}$， $r{k}_4=C_{\left(M^{\prime },{\rho }^{\prime }\right)}$， $r{k}_j={\left(K_j^{*}\right)}^{H_1\left({\delta }^{*}\right)}$，最后输出重加密密钥 $R{K}_{S^{*}\to C_{\left(M^{\prime },{\rho }^{\prime }\right)}}=\left(S,r{k}_1,r{k}_2,r{k}_3,r{k}_4,r{k}_j\right)$ 和私钥 $S{K}_{S^{\prime }}$ 发送给 $\mathcal{A}$。

$Challenge$ 最后， $\mathcal{A}$ 提交一个密钥 $S{K}_{S^{\prime }}$，如果 $S{K}_{S^{″}}=S{K}_{S^{*}}$ 则 $\mathcal{A}$ 赢得游戏。

注： $\left(M^{*},{\rho }^{*}\right)$ 与 $\left(M^{\prime },{\rho }^{\prime }\right)$ 是不相交的， $C_{\left(M^{\prime },{\rho }^{\prime }\right)}$ 实际上是 ${\delta }^{*}$ 在访问结构下Waters等 [4] 方案的ABE加密， $\mathcal{A}$ 可以通过对应的私钥 $S{K}_{S^{\prime }}$ 恢复得到 ${\delta }^{*}=g^{{\theta }^{*}}$，为了从重加密密钥 $R{K}_{S^{*}\to \left(M^{\prime },{\rho }^{\prime }\right)}$ 中恢复 $S{K}_{S^{*}}$， $\mathcal{A}$ 还需计算出 $g_1^{{\theta }^{*}}$，已知 $g^{{\theta }^{*}}$， $g_1=g^b$，计算 $g_1^{{\theta }^{*}}=g^{b{\theta }^{*}}$ 相当于解决CDH困难问题。证毕

5.2. 效率分析

本方案将与文献 [5] 中外包解密CP-ABE方案和文献 [13] 可验证外包CP-ABE方案，文献 [15] 和文献 [21] [22] [23] CP-ABPRE方案进行具体的性能分析。B表示双线性运算，E表示 $\mathbb{G}$ 群的指数运算， $E_T$ 表示 ${\mathbb{G}}_T$ 群的指数运算，l表示访问结构 $\left(M,\rho \right)$ 中矩阵M的行数，s表示用户私钥属性数量，N表示系统属性空间属性数量。 $\left|\mathbb{G}\right|$ 表示 $\mathbb{G}$ 中的元素长度， $\left|{\mathbb{G}}_T\right|$ 表示 ${\mathbb{G}}_T$ 中的元素长度。忽略实际运算中涉及的杂凑函数及异或运算的计算开销和存储开销。

表1展示了几种方案用户端的计算开销对比，表2展示了几种方案的私钥与密文存储空间占用对比。本文基于文献 [5] 提出VF-OO-ABPRE方案，实现了离线/在线加密且外包解密可验证的功能，减少了用户端实际加密过程中的计算开销和带宽。在原始文献 [5] 的基础上结合代理重加密，实现了密文共享功能，原始密文加密计算只消耗了4E_T，虽然原始密文解密计算多了2E_T，但是实现了可验证的功能；文献 [13] 可验证的外包解密的离线/在线ABE加密方案，虽然用户端在线加密计算只消耗了2E，但是密文解密阶段的计算量较大的双线性对的运算B消耗较多，且计算开销随属性集合的数量呈线性增长的关系。而本方案将解密计算外包，所以用户端的解密计算消耗4E_T；文献 [15] 仅支持“AND”门访问结构，表达能力有限。本方案采取离线/在线加密操作以及解密外包，将复杂的双线性运算外包给D-CSP，使得解密只需进行4个 ${\mathbb{G}}_T$ 群的指数运算，重加密密钥的生成也相对应地节省了在 $\mathbb{G}$ 群上的指数计算开销。大大提高了计算效率，节省了带宽。对比文献 [21] [22] [23] 不同功能的属性代理重加密方案，计算开销与所占带宽的优势明显。

综合以上分析，本方案实现了离线/在线加密操作的同时，将解密外包且支持外包可验证性。离线/在线的加密操作适用于使用资源受限设备加密的用户，可以在设备插入电源时离线完成大部分加密过程，实际加密时，只需以较小的能耗就能迅速完成在线加密。理论分析表明，本方案非常适用于资源受限的移动设备。

Table 1. Comparison of user client computing overhead

表1. 用户客户端计算开销对比

Table 2. Comparison of private key and ciphertext storage overhead

表2. 私钥与密文存储空间占用对比

6. 总结

本文针对CP-ABPRE加密的性能问题，提出新的离线/在线加密且可验证外包解密的VF-OO-ABPRE方案，主要将加密算法分为两个阶段，离线加密和在线加密。用户可以在插入电源时首先离线完成大部分的加密预处理计算，在线加密则可以利用离线加密的计算结果，快速高效地完成最终加密，有效地提高了CP-ABPRE案的加密性能。将解密外包，并且能验证外包计算的正确性，同时抗合谋攻击，提高了方案的安全性。有效缓解了资源受限用户的加解密负担，同时，本方案在随机预言机模型下被证明是选择明文攻击的不可区分安全的。通过对比已有方案的计算开销和存储开销，本方案在功能性和效率方面均具有明显优势，具有现实的应用价值。

基金项目

国家自然科学基金(No. U1836205, 61662009, 61772008)，贵州省科技计划项目(No. 黔科合重大专项字[2018] 3001，黔科合重大专项字[2018] 3007，黔科合重大专项字[2017] 3002，黔科合支撑[2019] 2004，黔科合支撑[2018] 2162，黔科合支撑[2018] 2159，黔科合基础[2019] 1049，黔科合基础[2017] 1045)，“十三五”国家密码发展基金(No. MMJJ20170129)。

NOTES

^*通讯作者。